mlsanityData to 7 Oct 2026

Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems

arXiv 1905.12673 ↗First posted 29 May 2019cs.LG stat.MLcited by 34

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 4; 2023: 6; 2024: 10; 2025: 6; 2026: 2.

34 papers.

Sort:

By area:

  1. 2021Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Healthcited by 43
  2. 2022Optimistic Whittle Index Policy: Online Learning for Restless Banditscited by 18
  3. 2023Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximationcited by 14
  4. 2021Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Settingcited by 12
  5. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  6. 2023Online Restless Multi-Armed Bandits with Long-Term Fairness Constraintscited by 10
  7. 2022On learning Whittle index policy for restless bandits with scalable regretcited by 9
  8. 2023A Definition of Non-Stationary Banditscited by 9
  9. 2023Policy Optimization for Personalized Interventions in Behavioral Healthcited by 9
  10. 2021Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learningcited by 7
  11. 2022Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximationcited by 7
  12. 2022Networked Restless Bandits with Positive Externalitiescited by 5
22 more
  1. 2024Context in Public Health for Underserved Communities: A Bayesian Approach to Online Restless Banditscited by 5
  2. 2021Learning Augmented Index Policy for Optimal Service Placement at the Network Edgecited by 4
  3. 2024Faster Q-Learning Algorithms for Restless Banditscited by 2
  4. 2024DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedbackcited by 2
  5. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  6. 2023Decision-Focused Evaluation: Analyzing Performance of Deployed Restless Multi-Arm Banditscited by 1
  7. 2024Fairness of Exposure in Online Restless Multi-armed Banditscited by 1
  8. 2024A Federated Online Restless Bandit Framework for Cooperative Resource Allocationcited by 1
  9. 2024Whittle Index Learning Algorithms for Restless Bandits with Constant Stepsizescited by 1
  10. 2025Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocationcited by 1
  11. 2025Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernelscited by 1
  12. 2021Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Banditscited by 0
  13. 2024Efficient Public Health Intervention Planning Using Decomposition-Based Decision-Focused Learningcited by 0
  14. 2024A resource-constrained stochastic scheduling algorithm for homeless street outreach and gleaning edible foodcited by 0
  15. 2024Structured Reinforcement Learning for Delay-Optimal Data Transmission in Dense mmWave Networkscited by 0
  16. 2024Restless Bandit Problem with Rewards Generated by a Linear Gaussian Dynamical Systemcited by 0
  17. 2025From Restless to Contextual: A Thresholding Bandit Reformulation For Finite-horizon Improvementcited by 0
  18. 2025Non-Stationary Restless Multi-Armed Bandits with Provable Guaranteecited by 0
  19. 2025Meta-Learning Multi-armed Bandits for Beam Tracking in 5G and 6G Networkscited by 0
  20. 2025Restless Multi-Process Multi-Armed Bandits with Applications to Self-Driving Microscopiescited by 0
  21. 2026Learning in Markovian bandits with non-observable states and constrained decision epochscited by 0
  22. 2026From Relaxed Indexability to Exact Indexability: A t-Step Approach for Partially Observable Restless Banditscited by 0