Restarted Bayesian Online Change-point Detector achieves Optimal Detection Delay
In this paper, we consider the problem of sequential change-point detection where both the change-points and the distributions before and after the change are assumed to be unknown. For this key problem in statistical and sequential learning theory, we derive a variant of the Bayesian Online Change Point Detector proposed by \cite{adams2007bayesian} which is easier to analyze than the original version while keeping its powerful message-passing algorithm. We provide a non-asymptotic analysis of the false-alarm rate and the detection delay that matches the existing lower-bound. We further provide the first explicit high-probability control of the detection delay for such approach. Experiments on synthetic and real-world data show that this proposal compares favorably with the state-of-art change-point detection strategy, namely the Improved Generalized Likelihood Ratio (Improved GLR) while outperforming the original Bayesian Online Change Point Detection strategy.
Code (1)
Tasks
Change Point DetectionLearning TheorySimilar Papers 제목 키워드 기반
Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit
We study a structured multi-agent multi-armed bandit (MAMAB) problem in a dynamic environment. A graph reflects the information-sharing structure among agents, and the arms' reward distributions are piecewise-stationary …
Change Point DetectionDecision MakingRestarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processes
We consider the problem of learning in a non-stationary reinforcement learning (RL) environment, where the setting can be fully described by a piecewise stationary discrete-time Markov decision process (MDP). We introduc…
Change Point DetectionReinforcement Learning (RL)Online Distributional Prediction via Latent Cluster Geometry Under Drift and Corruption
Online learning in non-stationary streams is often formulated as tracking a point estimate, but many applications require predicting the full data-generating distribution. We study online distributional prediction under …
Event-Triggered Safe Bayesian Optimization on Quadcopters
Bayesian optimization (BO) has proven to be a powerful tool for automatically tuning control parameters without requiring knowledge of the underlying system dynamics. Safe BO methods, in addition, guarantee safety during…
Bayesian OptimizationA Risk-Averse Framework for Non-Stationary Stochastic Multi-Armed Bandits
In a typical stochastic multi-armed bandit problem, the objective is often to maximize the expected sum of rewards over some time horizon $T$. While the choice of a strategy that accomplishes that is optimal with no addi…
Change Point DetectionMulti-Armed Bandits