# On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2018.

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

- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits](https://mlsanity.com/paper/2107.11419/) (2021)
- [On Slowly-varying Non-stationary Bandits](https://mlsanity.com/paper/2110.12916/) (2021)
- [Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret](https://mlsanity.com/paper/2101.08980/) (2021)
- [Decentralized Competing Bandits in Non-Stationary Matching Markets](https://mlsanity.com/paper/2206.00120/) (2022)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2306.05998/) (2023)
- [Curriculum optimization for low-resource speech recognition](https://mlsanity.com/paper/2202.08883/) (2022)
- [Deterministic Sequencing of Exploration and Exploitation for Reinforcement Learning](https://mlsanity.com/paper/2209.05408/) (2022)
- [Solve Smart, Not Often: Policy Learning for Costly MILP Re-solving](https://mlsanity.com/paper/2509.23470/) (2025)
- [Fixed-Confidence Best Arm Identification with Decreasing Variance](https://mlsanity.com/paper/2502.07199/) (2025)
- [Nonparametric Learning and Earning with One-Point Feedback under Nonstationarity](https://mlsanity.com/paper/2605.21263/) (2026)

## Abstract (arXiv)

We study the non-stationary stochastic multiarmed bandit (MAB) problem and propose two generic algorithms, namely, the limited memory deterministic sequencing of exploration and exploitation (LM-DSEE) and the Sliding-Window Upper Confidence Bound# (SW-UCB#). We rigorously analyze these algorithms in abruptly-changing and slowly-varying environments and characterize their performance. We show that the expected cumulative regret for these algorithms under either of the environments is upper bounded by sublinear functions of time, i.e., the time average of the regret asymptotically converges to zero. We complement our analytic results with numerical illustrations.