Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits
In this paper, we consider the setting of piecewise i.i.d. bandits under a safety constraint. In this piecewise i.i.d. setting, there exists a finite number of changepoints where the mean of some or all arms change simultaneously. We introduce the safety constraint studied in \citet{wu2016conservative} to this setting such that at any round the cumulative reward is above a constant factor of the default action reward. We propose two actively adaptive algorithms for this setting that satisfy the safety constraint, detect changepoints, and restart without the knowledge of the number of changepoints or their locations. We provide regret bounds for our algorithms and show that the bounds are comparable to their counterparts from the safe bandit and piecewise i.i.d. bandit literature. We also provide the first matching lower bounds for this setting. Empirically, we show that our safety-aware algorithms perform similarly to the state-of-the-art actively adaptive algorithms that do not satisfy the safety constraint.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Distribution-dependent and Time-uniform Bounds for Piecewise i.i.d Bandits
We consider the setup of stochastic multi-armed bandits in the case when reward distributions are piecewise i.i.d. and bounded with unknown changepoints. We focus on the case when changes happen simultaneously on all arm…
Multi-Armed BanditsAlmost 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 DetectionEfficient Change-Point Detection for Tackling Piecewise-Stationary Bandits
We introduce GLR-klUCB, a novel algorithm for the piecewise iid non-stationary bandit problem with bounded rewards. This algorithm combines an efficient bandit algorithm, kl-UCB, with an efficient, parameter-free, change…
Change Point DetectionFrom Observations to Parameters: Detecting Changepoint in Nonlinear Dynamics with Simulation-based Inference
Detecting regime shifts in chaotic time series is hard because observation-space signals are entangled with intrinsic variability. We propose Parameter--Space Changepoint Detection (Param--CPD), a two--stage framework th…
Bayesian InferenceEfficient line search for optimizing Area Under the ROC Curve in gradient descent
Receiver Operating Characteristic (ROC) curves are useful for evaluation in binary classification and changepoint detection, but difficult to use for learning since the Area Under the Curve (AUC) is piecewise constant (g…
Binary Classification