# Regime Switching Bandits

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2020.

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

- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2301.12366/) (2023)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [Tractable Optimality in Episodic Latent MABs](https://mlsanity.com/paper/2210.03528/) (2022)
- [Bridging Adversarial and Nonstationary Multi-armed Bandit](https://mlsanity.com/paper/2201.01628/) (2022)
- [Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting](https://mlsanity.com/paper/2410.01331/) (2024)
- [Achieving widetildeO(√T) Regret in Average-Reward POMDPs with Known Observation Models](https://mlsanity.com/paper/2501.18790/) (2025)
- [A Direct Approach for Handling Contextual Bandits with Latent State Dynamics](https://mlsanity.com/paper/2604.08149/) (2026)

## Abstract (arXiv)

We study a multi-armed bandit problem where the rewards exhibit regime switching. Specifically, the distributions of the random rewards generated from all arms are modulated by a common underlying state modeled as a finite-state Markov chain. The agent does not observe the underlying state and has to learn the transition matrix and the reward distributions. We propose a learning algorithm for this problem, building on spectral method-of-moments estimations for hidden Markov models, belief error control in partially observable Markov decision processes and upper-confidence-bound methods for online learning. We also establish an upper bound O(T2/3√log T) for the proposed learning algorithm where T is the learning horizon. Finally, we conduct proof-of-concept experiments to illustrate the performance of the learning algorithm.