Fixed-budget change point identification in piecewise constant bandits
File(s)
Accepted version
Author(s)
Lazzaro, Joseph
Pike-Burke, Ciara
Type
Conference Paper
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 opti-
mal for both small and large budgets simultaneously. We complement our theoretical analysis with experimental results in simulated environments to support our findings.
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 opti-
mal for both small and large budgets simultaneously. We complement our theoretical analysis with experimental results in simulated environments to support our findings.
Date Issued
2025-05-03
Date Acceptance
2025-01-22
Citation
Proceedings of Machine Learning Research, 2025, 258, pp.3268-3276
ISSN
2640-3498
Publisher
MLResearchPress
Start Page
3268
End Page
3276
Journal / Book Title
Proceedings of Machine Learning Research
Volume
258
Copyright Statement
Copyright © The authors and PMLR 2025. MLResearchPress.
Source
International Conference on Artificial Intelligence and Statistics (AISTATS)
Publication Status
Published
Start Date
2025-05-03
Finish Date
2025-05-05
Coverage Spatial
Mai Khao, Thailand