# Thompson Sampling in Non-Episodic Restless Bandits

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

## Key facts

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

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

- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting](https://mlsanity.com/paper/2106.07677/) (2021)
- [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)
- [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)
- [Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learning](https://mlsanity.com/paper/2306.08803/) (2023)
- [Fairness of Exposure in Online Restless Multi-armed Bandits](https://mlsanity.com/paper/2402.06348/) (2024)
- [Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits](https://mlsanity.com/paper/2109.09855/) (2021)
- [A resource-constrained stochastic scheduling algorithm for homeless street outreach and gleaning edible food](https://mlsanity.com/paper/2403.10638/) (2024)
- [Risk-Aware Decision Making in Restless Bandits: Theory and Algorithms for Planning and Learning](https://mlsanity.com/paper/2410.23029/) (2024)
- [Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee](https://mlsanity.com/paper/2508.10804/) (2025)
- [Meta-Learning Multi-armed Bandits for Beam Tracking in 5G and 6G Networks](https://mlsanity.com/paper/2512.05680/) (2025)
- [Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs](https://mlsanity.com/paper/2606.14095/) (2026)
- [Learning in Markovian bandits with non-observable states and constrained decision epochs](https://mlsanity.com/paper/2606.27448/) (2026)

## Abstract (arXiv)

Restless bandit problems assume time-varying reward distributions of the arms, which adds flexibility to the model but makes the analysis more challenging. We study learning algorithms over the unknown reward distributions and prove a sub-linear, O(√Tlog T), regret bound for a variant of Thompson sampling. Our analysis applies in the infinite time horizon setting, resolving the open question raised by Jung and Tewari (2019) whose analysis is limited to the episodic case. We adopt their policy mapping framework, which allows our algorithm to be efficient and simultaneously keeps the regret meaningful. Our algorithm adapts the TSDE algorithm of Ouyang et al. (2017) in a non-trivial manner to account for the special structure of restless bandits. We test our algorithm on a simulated dynamic channel access problem with several policy mappings, and the empirical regrets agree with the theoretical bound regardless of the choice of the policy mapping.