Quickest change detection with unknown parameters: Constant complexity and near optimality

Abstract

We consider the quickest change detection problem where both the parameters of pre- and post- change distributions are unknown, which prevents the use of classical simple hypothesis testing. Without additional assumptions, optimal solutions are not tractable as they rely on some minimax and robust variant of the objective. As a consequence, change points might be detected too late for practical applications (in economics, health care or maintenance for instance). Available constant complexity techniques typically solve a relaxed version of the problem, deeply relying on very specific probability distributions and/or some very precise additional knowledge. We consider a totally different approach that leverages the theoretical asymptotic properties of optimal solutions to derive a new scalable approximate algorithm with near optimal performance that runs~in~$\mathcal{O}(1)$, adapted to even more complex Markovian settings.

References in corpus (6)

• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Bayesian Online Changepoint Detection
• Generative Adversarial Imitation Learning
• Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research
• Minimax Robust Quickest Change Detection
• Multi-task Maximum Entropy Inverse Reinforcement Learning