From Restless to Contextual: A Thresholding Bandit Reformulation for Finite-horizon Improvement

Jiamin Xu, Ivan Nazarov, Aditya Rastogi, Africa Perianez Santiago, Kyra Gan
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:4231-4239, 2026.

Abstract

This paper addresses the poor finite-horizon performance of existing online \emph{restless bandit} (RB) algorithms, which stems from the prohibitive sample complexity of learning a full \emph{Markov decision process} (MDP) for each agent. We argue that superior finite-horizon performance requires \emph{rapid convergence} to a \emph{high-quality} policy. Thus motivated, we introduce a reformulation of online RBs as a \emph{budgeted thresholding contextual bandit}, which simplifies the learning problem by encoding long-term state transitions into a scalar reward. We prove the first non-asymptotic optimality of an oracle policy for a simplified finite-horizon setting. We propose a practical learning policy under a heterogeneous-agent, multi-state setting, and show that it achieves a sublinear regret, achieving \emph{faster convergence} than existing methods. This directly translates to higher cumulative reward, as empirically validated by significant gains over state-of-the-art algorithms in large-scale heterogeneous environments. The code is provided in \url{https://github.com/jamie01713/EGT}. Our work provides a new pathway for achieving practical, sample-efficient learning in finite-horizon RBs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-xu26e, title = { From Restless to Contextual: A Thresholding Bandit Reformulation for Finite-horizon Improvement }, author = {Xu, Jiamin and Nazarov, Ivan and Rastogi, Aditya and Santiago, Africa Perianez and Gan, Kyra}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {4231--4239}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/xu26e/xu26e.pdf}, url = {https://proceedings.mlr.press/v300/xu26e.html}, abstract = { This paper addresses the poor finite-horizon performance of existing online \emph{restless bandit} (RB) algorithms, which stems from the prohibitive sample complexity of learning a full \emph{Markov decision process} (MDP) for each agent. We argue that superior finite-horizon performance requires \emph{rapid convergence} to a \emph{high-quality} policy. Thus motivated, we introduce a reformulation of online RBs as a \emph{budgeted thresholding contextual bandit}, which simplifies the learning problem by encoding long-term state transitions into a scalar reward. We prove the first non-asymptotic optimality of an oracle policy for a simplified finite-horizon setting. We propose a practical learning policy under a heterogeneous-agent, multi-state setting, and show that it achieves a sublinear regret, achieving \emph{faster convergence} than existing methods. This directly translates to higher cumulative reward, as empirically validated by significant gains over state-of-the-art algorithms in large-scale heterogeneous environments. The code is provided in \url{https://github.com/jamie01713/EGT}. Our work provides a new pathway for achieving practical, sample-efficient learning in finite-horizon RBs. } }
Endnote
%0 Conference Paper %T From Restless to Contextual: A Thresholding Bandit Reformulation for Finite-horizon Improvement %A Jiamin Xu %A Ivan Nazarov %A Aditya Rastogi %A Africa Perianez Santiago %A Kyra Gan %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-xu26e %I PMLR %P 4231--4239 %U https://proceedings.mlr.press/v300/xu26e.html %V 300 %X This paper addresses the poor finite-horizon performance of existing online \emph{restless bandit} (RB) algorithms, which stems from the prohibitive sample complexity of learning a full \emph{Markov decision process} (MDP) for each agent. We argue that superior finite-horizon performance requires \emph{rapid convergence} to a \emph{high-quality} policy. Thus motivated, we introduce a reformulation of online RBs as a \emph{budgeted thresholding contextual bandit}, which simplifies the learning problem by encoding long-term state transitions into a scalar reward. We prove the first non-asymptotic optimality of an oracle policy for a simplified finite-horizon setting. We propose a practical learning policy under a heterogeneous-agent, multi-state setting, and show that it achieves a sublinear regret, achieving \emph{faster convergence} than existing methods. This directly translates to higher cumulative reward, as empirically validated by significant gains over state-of-the-art algorithms in large-scale heterogeneous environments. The code is provided in \url{https://github.com/jamie01713/EGT}. Our work provides a new pathway for achieving practical, sample-efficient learning in finite-horizon RBs.
APA
Xu, J., Nazarov, I., Rastogi, A., Santiago, A.P. & Gan, K.. (2026). From Restless to Contextual: A Thresholding Bandit Reformulation for Finite-horizon Improvement . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:4231-4239 Available from https://proceedings.mlr.press/v300/xu26e.html.

Related Material