Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems

Abstract

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 $\tilde{\mathcal{O}}(\sqrt{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.

Cited by in corpus (6)

• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
• Learning Augmented Index Policy for Optimal Service Placement at the Network Edge
• Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Setting
• Opportunistic Spectrum Access: Does Maximizing Throughput Minimize File Transfer Time?
• Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Bandits
• Screening for an Infectious Disease as a Problem in Stochastic Control