# Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2019.

## Built on by (most cited first, 30 of 34)

- [Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health](https://mlsanity.com/paper/2109.08075/) (2021)
- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting](https://mlsanity.com/paper/2106.07677/) (2021)
- [An Information-Theoretic Analysis of Nonstationary Bandit Learning](https://mlsanity.com/paper/2302.04452/) (2023)
- [On learning Whittle index policy for restless bandits with scalable regret](https://mlsanity.com/paper/2202.03463/) (2022)
- [Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints](https://mlsanity.com/paper/2312.10303/) (2023)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Policy Optimization for Personalized Interventions in Behavioral Health](https://mlsanity.com/paper/2303.12206/) (2023)
- [Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation](https://mlsanity.com/paper/2202.13187/) (2022)
- [Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2107.01689/) (2021)
- [Context in Public Health for Underserved Communities: A Bayesian Approach to Online Restless Bandits](https://mlsanity.com/paper/2402.04933/) (2024)
- [Networked Restless Bandits with Positive Externalities](https://mlsanity.com/paper/2212.05144/) (2022)
- [Learning Augmented Index Policy for Optimal Service Placement at the Network Edge](https://mlsanity.com/paper/2101.03641/) (2021)
- [Faster Q-Learning Algorithms for Restless Bandits](https://mlsanity.com/paper/2409.05908/) (2024)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?](https://mlsanity.com/paper/2106.08771/) (2021)
- [Decision-Focused Evaluation: Analyzing Performance of Deployed Restless Multi-Arm Bandits](https://mlsanity.com/paper/2301.07835/) (2023)
- [Fairness of Exposure in Online Restless Multi-armed Bandits](https://mlsanity.com/paper/2402.06348/) (2024)
- [A Federated Online Restless Bandit Framework for Cooperative Resource Allocation](https://mlsanity.com/paper/2406.07992/) (2024)
- [Whittle Index Learning Algorithms for Restless Bandits with Constant Stepsizes](https://mlsanity.com/paper/2409.04605/) (2024)
- [Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocation](https://mlsanity.com/paper/2501.06103/) (2025)
- [Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels](https://mlsanity.com/paper/2506.18186/) (2025)
- [Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits](https://mlsanity.com/paper/2109.09855/) (2021)
- [Efficient Public Health Intervention Planning Using Decomposition-Based Decision-Focused Learning](https://mlsanity.com/paper/2403.05683/) (2024)
- [A resource-constrained stochastic scheduling algorithm for homeless street outreach and gleaning edible food](https://mlsanity.com/paper/2403.10638/) (2024)
- [Structured Reinforcement Learning for Delay-Optimal Data Transmission in Dense mmWave Networks](https://mlsanity.com/paper/2404.16920/) (2024)
- [Restless Bandit Problem with Rewards Generated by a Linear Gaussian Dynamical System](https://mlsanity.com/paper/2405.09584/) (2024)
- [From Restless to Contextual: A Thresholding Bandit Reformulation For Finite-horizon Improvement](https://mlsanity.com/paper/2502.05145/) (2025)
- [Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee](https://mlsanity.com/paper/2508.10804/) (2025)

## Abstract (arXiv)

Restless bandit problems are instances of non-stationary multi-armed bandits. These problems have been studied well from the optimization perspective, where the goal is to efficiently find a near-optimal policy when system parameters are known. However, very few papers adopt a learning perspective, where the parameters are unknown. In this paper, we analyze the performance of Thompson sampling in episodic restless bandits with unknown parameters. We consider a general policy map to define our competitor and prove an tildeO(√T) Bayesian regret bound. Our competitor is flexible enough to represent various benchmarks including the best fixed action policy, the optimal policy, the Whittle index policy, or the myopic policy. We also present empirical results that support our theoretical findings.