Fixed-Budget Change Point Identification in Piecewise Constant Bandits

Joseph Lazzaro, Ciara Pike-Burke
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:3268-3276, 2025.

Abstract

We study the piecewise constant bandit problem where the expected reward is a piecewise constant function with one change point (discontinuity) across the action space $[0,1]$ and the learner’s aim is to locate the change point. Under the assumption of a fixed exploration budget, we provide the first non-asymptotic analysis of policies designed to locate abrupt changes in the mean reward function under bandit feedback. We study the problem under a large and small budget regime, and for both settings establish lower bounds on the error probability and provide algorithms with near matching upper bounds. Interestingly, our results show a separation in the complexity of the two regimes. We then propose a regime adaptive algorithm which is near optimal for both small and large budgets simultaneously. We complement our theoretical analysis with experimental results in simulated environments to support our findings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-lazzaro25a, title = {Fixed-Budget Change Point Identification in Piecewise Constant Bandits}, author = {Lazzaro, Joseph and Pike-Burke, Ciara}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {3268--3276}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/lazzaro25a/lazzaro25a.pdf}, url = {https://proceedings.mlr.press/v258/lazzaro25a.html}, abstract = {We study the piecewise constant bandit problem where the expected reward is a piecewise constant function with one change point (discontinuity) across the action space $[0,1]$ and the learner’s aim is to locate the change point. Under the assumption of a fixed exploration budget, we provide the first non-asymptotic analysis of policies designed to locate abrupt changes in the mean reward function under bandit feedback. We study the problem under a large and small budget regime, and for both settings establish lower bounds on the error probability and provide algorithms with near matching upper bounds. Interestingly, our results show a separation in the complexity of the two regimes. We then propose a regime adaptive algorithm which is near optimal for both small and large budgets simultaneously. We complement our theoretical analysis with experimental results in simulated environments to support our findings.} }
Endnote
%0 Conference Paper %T Fixed-Budget Change Point Identification in Piecewise Constant Bandits %A Joseph Lazzaro %A Ciara Pike-Burke %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-lazzaro25a %I PMLR %P 3268--3276 %U https://proceedings.mlr.press/v258/lazzaro25a.html %V 258 %X We study the piecewise constant bandit problem where the expected reward is a piecewise constant function with one change point (discontinuity) across the action space $[0,1]$ and the learner’s aim is to locate the change point. Under the assumption of a fixed exploration budget, we provide the first non-asymptotic analysis of policies designed to locate abrupt changes in the mean reward function under bandit feedback. We study the problem under a large and small budget regime, and for both settings establish lower bounds on the error probability and provide algorithms with near matching upper bounds. Interestingly, our results show a separation in the complexity of the two regimes. We then propose a regime adaptive algorithm which is near optimal for both small and large budgets simultaneously. We complement our theoretical analysis with experimental results in simulated environments to support our findings.
APA
Lazzaro, J. & Pike-Burke, C.. (2025). Fixed-Budget Change Point Identification in Piecewise Constant Bandits. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:3268-3276 Available from https://proceedings.mlr.press/v258/lazzaro25a.html.

Related Material