GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits

Gongpu Chen, Soung Chang Liew, Deniz Gunduz

TL;DR

GINO-Q is a novel reinforcement learning algorithm for large-scale Restless Multi-armed Bandits (RMABs) that achieves asymptotic optimality without requiring the restrictive "indexability" property. By employing a three-timescale stochastic approximation approach, it efficiently learns a "gain index" policy that scales linearly with the number of arms, consistently outperforming state-of-the-art Whittle-index-based methods.

What Problem Does This Paper Address?

Restless Multi-armed Bandits (RMABs) are a powerful framework for resource allocation, where a controller must choose $N$ out of $M$ active processes (arms) to maximize long-term rewards. However, RMABs suffer from a brutal "curse of dimensionality": the state space grows exponentially with the number of arms. For a moderate system with 100 arms and 10 states each, the state space reaches a staggering $10^{100}$, making traditional Reinforcement Learning (RL) like DQN computationally impossible.

To solve this, researchers typically turn to index policies, like the famous Whittle index, which decompose the problem into $M$ independent subproblems. The catch? Whittle indices only work if the RMAB is "indexable"—a property that is notoriously difficult to prove and often doesn't hold in practice. When indexability fails, existing RL algorithms for RMABs can produce erratic or even detrimental policies.

Methods

The authors introduce GINO-Q (Gain-Index-Oriented Q-learning). Instead of the Whittle index, it learns a Gain Index, which quantifies the advantage of activating an arm in its current state compared to leaving it idle, based on the optimal Lagrange multiplier ($\lambda^*$) of a relaxed version of the problem.

The core of GINO-Q is a three-timescale stochastic approximation algorithm that operates without any prior knowledge of the system dynamics:

  1. Fast Timescale (SARSA): Estimates the average cost ($h_i$) of an auxiliary Markov Decision Process (MDP) for each arm.
  2. Medium Timescale (Relative Value Iteration Q-learning): Learns the state-action value functions ($Q_i$) for each arm given the current cost of activation ($\lambda$).
  3. Slow Timescale (Stochastic Gradient Descent): Updates the Lagrange multiplier $\lambda$ to find the optimal balance between arm activation and the resource constraint.

By carefully scheduling the learning rates for these three processes, GINO-Q ensures that the Q-functions and average costs stabilize enough to provide a reliable gradient for updating $\lambda$.

Datasets

The algorithm was evaluated on three distinct RMAB environments:

  • Non-indexable RMAB: A synthetic counter-example specifically designed to break Whittle-index-based algorithms.
  • Channel Allocation: A communication network problem focused on minimizing the "Age of Information" (AoI) for users across different classes.
  • Patrol Scheduling: A security-inspired task where agents must visit sites to detect Markovian events (e.g., intruders).

Key Insights and Ideas

  • Bypassing Indexability: The Gain Index policy is shown to be asymptotically optimal as the number of arms $M \to \infty$, regardless of whether the RMAB is indexable. This makes GINO-Q far more robust for real-world applications where system parameters are unknown.
  • Robustness to $\lambda$ Inaccuracy: The authors prove (Lemma 2) that the policy remains asymptotically optimal even if the algorithm only converges to a neighborhood of the optimal $\lambda^*$, rather than the exact value. This is crucial for stability in noisy, model-free settings.
  • Linear Scalability: Because GINO-Q decomposes the RMAB, its computational complexity increases linearly with the number of arms (or number of arm classes), circumventing the exponential growth that plagues standard MDP solvers.

Key Results

  • Handling Non-indexability: In tests on non-indexable arms, GINO-Q successfully learned the correct gain indices (see Gain index over training), while the baseline WIBQ algorithm converged to poor policies, sometimes performing worse than a random selection.
  • Superior Convergence: In the channel allocation task, GINO-Q converged significantly faster and with much lower variance than state-of-the-art baselines like Neurwin and WIBQ.
  • Large-Scale Performance: For $M=100$ arms, GINO-Q closely approached the theoretical upper bound of the reward, demonstrating its effectiveness in high-dimensional spaces where DQN fails entirely.
Gain index over training
Performance comparison in channel allocation

Limitations and Future Work

  • Tabular Limitations: As presented, GINO-Q is a tabular method. While the authors mention that complexity scales with the number of states, applying this to continuous or extremely high-dimensional state spaces would likely require integration with deep neural network function approximators.
  • Hyperparameter Sensitivity: Three-timescale algorithms require careful tuning of three different learning rate schedules ($C_1, C_2, C_3$). Finding the "sweet spot" for these constants in a new environment may require significant empirical effort.
  • Future Directions: The authors suggest that extending GINO-Q to handle arms with continuous state spaces or incorporating deep RL architectures (similar to how Neurwin extends Whittle learning) is a promising next step.

Summary updated

Abstract

The restless multi-armed bandit (RMAB) framework is a popular model with applications across a wide variety of fields. However, its solution is hindered by the exponentially growing state space (with respect to the number of arms) and the combinatorial action space, making traditional reinforcement learning methods infeasible for large-scale instances. In this paper, we propose GINO-Q, a three-timescale stochastic approximation algorithm designed to learn an asymptotically optimal index policy for RMABs. GINO-Q mitigates the curse of dimensionality by decomposing the RMAB into a series of subproblems, each with the same dimension as a single arm, ensuring that complexity increases linearly with the number of arms. Unlike recently developed Whittle-index-based algorithms, GINO-Q does not require RMABs to be indexable, enhancing its flexibility and applicability. Our experimental results demonstrate that GINO-Q consistently learns near-optimal policies, even for non-indexable RMABs where Whittle-index-based algorithms perform poorly, and it converges significantly faster than existing baselines.
BibTeX
@misc{chen2024gino,
  author = {Gongpu Chen and Soung Chang Liew and Deniz Gunduz},
  title = {{GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits}},
  year = {2024},
  eprint = {2408.09882},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.09882},
}
Figure