Fixed-Budget Change Point Identification in Piecewise Constant Bandits
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fixed-Confidence Multiple Change Point Identification under Bandit Feedback
Piecewise constant functions describe a variety of real-world phenomena in domains ranging from chemistry to manufacturing. In practice, it is often required to confidently identify the locations of the abrupt changes in…
The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
We study multiple change point localization under bandit feedback. An unknown piecewise-constant function on a compact interval can be queried sequentially at adaptively chosen inputs, and each query returns a noisy eval…
Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits
We propose a {\em novel} piecewise stationary linear bandit (PSLB) model, where the environment randomly samples a context from an unknown probability distribution at each changepoint, and the quality of an arm is measur…
Change DetectionOn the Existence of a Complexity in Fixed Budget Bandit Identification
In fixed budget bandit identification, an algorithm sequentially observes samples from several distributions up to a given final time. It then answers a query about the set of distributions. A good algorithm will have a …
BAPR: Bayesian amnesic piecewise-robust reinforcement learning for non-stationary continuous control
Real-world control systems frequently operate under \emph{piecewise stationary} conditions, where dynamics remain stable for extended periods before undergoing abrupt regime changes. Standard robust RL methods face a fun…
Reinforcement LearningContinuous ControlChange Detection