# Fixed-Budget Change Point Identification in Piecewise Constant Bandits

arXiv: https://arxiv.org/abs/2501.12957 · HTML: https://mlsanity.com/paper/2501.12957/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jan 2025.

## Built on by (most cited first, 3 of 3)

- [Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond](https://mlsanity.com/paper/2503.01701/) (2025)
- [Fixed-Confidence Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2507.08994/) (2025)
- [The Sample Complexity of Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2605.13252/) (2026)

## Abstract (arXiv)

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.