Online Learning of Rested and Restless Bandits

Cem Tekin, Mingyan Liu

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:

  1. Rested Bandits: The state of an arm freezes when it is not being played.
  2. 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.

The Upper Confidence Bound - Multiple Plays (UCB-M) algorithm for rested bandits.

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

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.
BibTeX
@article{tekin2012online,
  author = {Cem Tekin and Mingyan Liu},
  title = {{Online Learning of Rested and Restless Bandits}},
  journal = {IEEE Trans. Information Theory},
  year = {2012},
  url = {https://openreview.net/forum?id=tk9boXLFe-},
}
Figure