Abstract
In this paper we study the online learning problem involving rested and restless multiarmed bandits with multiple plays. The system consists of a single player/user and a set of K finite-state discrete-time Markov chains (arms) with unknown state spaces and statistics. At each time step the player can play M arms. The objective of the user is to decide for each step which M of the K arms to play over a sequence of trials so as to maximize its long term reward. The restless multiarmed bandit is particularly relevant to the application of opportunistic spectrum access (OSA), where a (secondary) user has access to a set of K channels, each of time-varying condition as a result of random fading and/or certain primary users' activities.
Introduction
The classic Multi-Armed Bandit (MAB) problem models the fundamental tradeoff between exploration (learning the value of new options) and exploitation (selecting the known best option). While standard MAB models assume rewards are drawn from fixed, independent distributions, real-world systems like wireless communications involve "arms" (e.g., channels) with states that evolve over time as Markov chains.
This paper addresses two critical variants:
- Rested Bandits: The state of an arm freezes when it is not being played.
- Restless Bandits: The state of an arm continues to evolve regardless of whether it is played or not.
Restless bandits are notoriously difficult because the state observed next depends heavily on the time elapsed since the last observation, breaking the mathematical assumptions of standard i.i.d. bandit algorithms. The authors aim to design algorithms that select $M$ out of $K$ arms to maximize long-term reward, effectively minimizing "regret" relative to an ideal policy.
Methods
The authors propose two primary algorithms to handle these scenarios.
UCB-M for Rested Bandits
For the rested case, the authors provide the Upper Confidence Bound - Multiple Plays (UCB-M) algorithm. This is a straightforward extension of the classic UCB1 algorithm, adapted to allow the player to select $M$ arms simultaneously. It maintains an index for each arm that balances the observed sample mean with an uncertainty bound to guide exploration.
RCA-M for Restless Bandits
The core novelty for the restless case is the Regenerative Cycle Algorithm - Multiple Plays (RCA-M). RCA-M utilizes a sampling trick based on Markov chain "regenerative cycles." When the algorithm plays an arm, it waits until it observes a specific "regenerative state" twice, completing a cycle. By calculating UCB indices using only rewards gathered during these complete cycles, the algorithm effectively "stitches together" a stationary sample path. This allows the use of standard sample-mean index policies on a non-stationary problem without needing to model the passive evolution of unplayed arms.
Results
The performance of these algorithms was evaluated theoretically and through simulations using the Gilbert-Elliot channel model, a standard two-state Markov model used to simulate wireless channel conditions.
Theoretical Optimality
The authors mathematically prove that both UCB-M and RCA-M achieve logarithmic regret ($O(\log n)$) uniformly over time. This is the theoretical gold standard for bandit algorithms, indicating that the algorithm identifies the optimal arms exponentially fast.
Empirical Performance
Simulations demonstrate that RCA-M successfully achieves sub-linear normalized regret across various environments, including bursty and non-bursty channels. Interestingly, while the theoretical proof suggests a large exploration constant ($L$) based on eigenvalue gaps, empirical results show that setting $L=1$ provides superior practical performance, suggesting the theoretical bounds are conservative.
Conclusion and Future Work
This work provides a robust framework for managing restless bandits in environments like cognitive radio networks. However, some limitations remain. The current proof assumes a strict gap between the $M$-th and $(M+1)$-th best arms to prevent index oscillation. Furthermore, the regret metric used is "weak regret," comparing against the best fixed-action policy rather than a dynamic one. Future research aims to extend these findings to decentralized, multi-player settings where coordination is limited and collisions may occur.
Summary updated