# Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 1 Apr 2023.

## Builds on (most cited first, 19 of 19)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Variational Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1905.05857/) (2019)
- [A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions](https://mlsanity.com/paper/1805.10066/) (2018)
- [Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Model](https://mlsanity.com/paper/1806.01492/) (2018)
- [Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management](https://mlsanity.com/paper/1905.04337/) (2019)
- [Minimum-Delay Adaptation in Non-Stationary Reinforcement Learning via Online High-Confidence Change-Point Detection](https://mlsanity.com/paper/2105.09452/) (2021)
- [Analysis and Control of Epidemics: A survey of spreading processes on complex networks](https://mlsanity.com/paper/1505.00768/) (2015)
- [Spatio-temporal Bayesian On-line Changepoint Detection with Model Selection](https://mlsanity.com/paper/1805.05383/) (2018)
- [Quickest Change Detection Approach to Optimal Control in Markov Decision Processes with Model Changes](https://mlsanity.com/paper/1609.06757/) (2016)
- [Large Scale Markov Decision Processes with Changing Rewards](https://mlsanity.com/paper/1905.10649/) (2019)
- [Blind Dynamic Resource Allocation in Closed Networks via Mirror Backpressure](https://mlsanity.com/paper/1903.02764/) (2019)
- [Reinforcement with Fading Memories](https://mlsanity.com/paper/1907.12227/) (2019)

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

- [Tracking Drift: Variation-Aware Entropy Scheduling for Non-Stationary Reinforcement Learning](https://mlsanity.com/paper/2601.19624/) (2026)
- [Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Information](https://mlsanity.com/paper/2409.08434/) (2024)

## Abstract (arXiv)

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 introduce a variant of the Restarted Bayesian Online Change-Point Detection algorithm (R-BOCPD) that operates on input streams originating from the more general multinomial distribution and provides near-optimal theoretical guarantees in terms of false-alarm rate and detection delay. Based on this, we propose an improved version of the UCRL2 algorithm for MDPs with state transition kernel sampled from a multinomial distribution, which we call R-BOCPD-UCRL2. We perform a finite-time performance analysis and show that R-BOCPD-UCRL2 enjoys a favorable regret bound of Oleft(D O √A T KT logleft (fracTδ right) + fracKT log fracKTδminlimitsℓ : KLleft( θ(ℓ+1)midmidθ(ℓ)right)right), where D is the largest MDP diameter from the set of MDPs defining the piecewise stationary MDP setting, O is the finite number of states (constant over all changes), A is the finite number of actions (constant over all changes), KT is the number of change points up to horizon T, and θ(ℓ) is the transition kernel during the interval [cℓ, cℓ+1), which we assume to be multinomially distributed over the set of states mathbbO. Interestingly, the performance bound does not directly scale with the variation in MDP state transition distributions and rewards, ie. can also model abrupt changes. In practice, R-BOCPD-UCRL2 outperforms the state-of-the-art in a variety of scenarios in synthetic environments. We provide a detailed experimental setup along with a code repository (upon publication) that can be used to easily reproduce our experiments.