Abstract
Restless multi-armed bandits (RMABs) extend the classical bandit framework by allowing arm states to evolve independently of the learner's actions. While RMABs are powerful for modeling non-stationary environments, they are notoriously difficult to solve and learn. This paper provides the first rigorous Bayesian regret analysis for Thompson Sampling (TS) in RMABs. By focusing on an episodic setting, the authors prove a near-optimal $\tilde{\mathcal{O}}(\sqrt{T})$ regret bound against any deterministic competitor policy, including the complex Whittle index policy. Empirical results using the Gilbert-Elliott channel model validate the theoretical findings.
Introduction: The Challenge of Restless Bandits
In a standard Multi-Armed Bandit (MAB) problem, the state of an arm is static unless it is played. However, many real-world applications—such as dynamic channel access in telecommunications or online recommendation systems—require a more sophisticated model. Restless bandits address this by assuming every arm’s state evolves according to a Markov chain, regardless of whether it is pulled.
This "restless" nature introduces significant complexity. RMABs are technically Partially Observable Markov Decision Processes (POMDPs) because the learner only observes the states of the arms they choose to pull. Even with known transition probabilities, finding an optimal strategy is PSPACE-hard. This paper shifts the focus from pure optimization to the learning problem: how can a learner maximize rewards when the underlying transition probabilities are unknown?
Methodology: Episodic Thompson Sampling
The authors analyze Thompson Sampling (TS) within an episodic framework. To manage the complexity of partial observability, they assume the total time $T$ is divided into $m$ episodes of length $L$. At the start of each episode, the system resets to an initial state. This reset prevents the "compounding error" of state uncertainty from growing indefinitely, making the analysis tractable.
The algorithm operates as follows:
- Sampling: At the start of each episode, the learner draws a sample parameter $\theta$ from their current posterior distribution (belief).
- Execution: The learner follows a deterministic policy (e.g., the Whittle index policy or a myopic policy) based on that sample for the entire episode.
- Update: At the end of the episode, the learner updates their posterior belief based on the observed state transitions and rewards.
The core technical innovation lies in a new regret decomposition using Bellman operators. The authors demonstrate that the difference in expected rewards between the true parameters and the sampled parameters can be bounded by the accuracy of the learner's transition probability estimates.
Theoretical Contributions
The primary result is a Bayesian regret bound of $\tilde{\mathcal{O}}(\sqrt{KL^3N^3T \log T})$. This confirms that regret grows at a rate of $\sqrt{T}$, the "gold standard" for online learning efficiency.
Crucially, this bound is competitor-agnostic. Unlike many bandit results that compare the learner only to the best fixed arm, this analysis compares TS to any deterministic policy mapping. This includes high-performance benchmarks like the Whittle index policy. Furthermore, the analysis bridges the gap to classical theory; when the episode length $L=1$ and the number of arms pulled $N=1$, the bound reduces to the standard $\tilde{\mathcal{O}}(\sqrt{T})$ bound for classical MABs.
Empirical Performance
The algorithm was evaluated using the Gilbert-Elliott channel model, a standard benchmark in communication systems where arms represent channels in "good" or "bad" states. The goal is to decide which $N$ channels to probe to maximize the discovery of "good" states.
As shown in the simulations, Thompson Sampling successfully converges to the performance of the Whittle index policy. The log-log plot confirms the theoretical $\sqrt{T}$ growth rate, as the regret curves remain below the theoretical upper bound.
Conclusion and Future Directions
This work provides a foundational theoretical guarantee for learning in restless bandits. However, several challenges remain:
- The Reset Assumption: The episodic reset is a strong assumption. Extending this analysis to non-episodic, infinite-horizon settings is a critical next step for applications like autonomous exploration.
- State Space: The current analysis is tailored to binary states and rewards. Generalizing the framework to continuous or high-dimensional state spaces would broaden its applicability.
- Computational Scalability: For a large number of arms $K$, the computational cost of updating the posterior and calculating indices (like Whittle) can be significant.
Despite these limitations, the paper establishes that Thompson Sampling is a robust and theoretically sound approach for navigating the complexities of restless bandit problems.
Summary updated