A Modularized Framework for Piecewise-Stationary Restless Bandits

Kuan-Ta Li, Chia-Chun Lin, Ping-Chun Hsieh, Yu-Chih Huang
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3610-3618, 2026.

Abstract

We study the piecewise-stationary restless multi-armed bandit (PS-RMAB) problem, where each arm evolves as a Markov chain but \emph{mean rewards may change across unknown segments}. To address the resulting exploration–detection delay trade-off, we propose a modular framework that integrates arbitrary RMAB base algorithms with change detection and a novel diminishing exploration mechanism. This design enables flexible plug-and-play use of existing solvers and detectors, while efficiently adapting to mean changes without prior knowledge of their number. To evaluate performance, we introduce a refined regret notion that measures the \emph{excess regret due to exploration and detection}, benchmarked against an oracle that restarts the base algorithm at the true change points. Under this metric, we prove a regret bound of $\tilde{O}(\sqrt{LMKT})$, where $L$ denotes the maximum mixing time of the Markov chains across all arms and segments, $M$ the number of segments, $K$ the number of arms, and $T$ the horizon. Simulations confirm that our framework achieves regret close to that of the segment oracle and consistently outperforms base solvers that do not incorporate any mechanism to handle environmental hanges.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-li26g, title = { A Modularized Framework for Piecewise-Stationary Restless Bandits }, author = {Li, Kuan-Ta and Lin, Chia-Chun and Hsieh, Ping-Chun and Huang, Yu-Chih}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3610--3618}, 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/li26g/li26g.pdf}, url = {https://proceedings.mlr.press/v300/li26g.html}, abstract = { We study the piecewise-stationary restless multi-armed bandit (PS-RMAB) problem, where each arm evolves as a Markov chain but \emph{mean rewards may change across unknown segments}. To address the resulting exploration–detection delay trade-off, we propose a modular framework that integrates arbitrary RMAB base algorithms with change detection and a novel diminishing exploration mechanism. This design enables flexible plug-and-play use of existing solvers and detectors, while efficiently adapting to mean changes without prior knowledge of their number. To evaluate performance, we introduce a refined regret notion that measures the \emph{excess regret due to exploration and detection}, benchmarked against an oracle that restarts the base algorithm at the true change points. Under this metric, we prove a regret bound of $\tilde{O}(\sqrt{LMKT})$, where $L$ denotes the maximum mixing time of the Markov chains across all arms and segments, $M$ the number of segments, $K$ the number of arms, and $T$ the horizon. Simulations confirm that our framework achieves regret close to that of the segment oracle and consistently outperforms base solvers that do not incorporate any mechanism to handle environmental hanges. } }
Endnote
%0 Conference Paper %T A Modularized Framework for Piecewise-Stationary Restless Bandits %A Kuan-Ta Li %A Chia-Chun Lin %A Ping-Chun Hsieh %A Yu-Chih Huang %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-li26g %I PMLR %P 3610--3618 %U https://proceedings.mlr.press/v300/li26g.html %V 300 %X We study the piecewise-stationary restless multi-armed bandit (PS-RMAB) problem, where each arm evolves as a Markov chain but \emph{mean rewards may change across unknown segments}. To address the resulting exploration–detection delay trade-off, we propose a modular framework that integrates arbitrary RMAB base algorithms with change detection and a novel diminishing exploration mechanism. This design enables flexible plug-and-play use of existing solvers and detectors, while efficiently adapting to mean changes without prior knowledge of their number. To evaluate performance, we introduce a refined regret notion that measures the \emph{excess regret due to exploration and detection}, benchmarked against an oracle that restarts the base algorithm at the true change points. Under this metric, we prove a regret bound of $\tilde{O}(\sqrt{LMKT})$, where $L$ denotes the maximum mixing time of the Markov chains across all arms and segments, $M$ the number of segments, $K$ the number of arms, and $T$ the horizon. Simulations confirm that our framework achieves regret close to that of the segment oracle and consistently outperforms base solvers that do not incorporate any mechanism to handle environmental hanges.
APA
Li, K., Lin, C., Hsieh, P. & Huang, Y.. (2026). A Modularized Framework for Piecewise-Stationary Restless Bandits . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3610-3618 Available from https://proceedings.mlr.press/v300/li26g.html.

Related Material