Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation

Guojun Xiong, Jian Li

Introduction

Resource allocation in dynamic environments is a fundamental challenge across various domains, from healthcare intervention scheduling to communication network management. These scenarios are often modeled as Restless Multi-Armed Bandits (RMABs), where multiple independent processes (arms) evolve over time regardless of whether they are acted upon. While RMABs provide a powerful framework, they suffer from the "curse of dimensionality," as the state space grows exponentially with the number of arms, making optimal policies computationally intractable.

To address this, researchers frequently turn to the Whittle index—a heuristic that assigns a value to each state of an arm, representing the marginal benefit of taking an action. By selecting the arms with the highest indices, practitioners can achieve near-optimal performance with significantly reduced complexity. However, calculating these indices traditionally requires full knowledge of the underlying Markov Decision Process (MDP). In real-world settings where dynamics are unknown, agents must learn these indices through reinforcement learning (RL).

The Neural-Q-Whittle Framework

This paper introduces Neural-Q-Whittle, a deep reinforcement learning algorithm designed to learn Whittle indices in unknown environments using neural network function approximation. Unlike traditional tabular Q-learning, which fails to scale to large state spaces, or linear function approximation, which often relies on restrictive data assumptions, Neural-Q-Whittle leverages the representational power of neural networks to generalize across states.

The algorithm is structured as a nonlinear two-timescale stochastic approximation (2TSA):

  1. Fast Timescale (Q-Value Update): A two-layer neural network with ReLU activations approximates the Q-function, updated via temporal difference (TD) errors.
  2. Slow Timescale (Whittle Index Update): The Whittle indices are iteratively refined based on the difference between the approximated Q-values of active and passive actions.

Theoretical Breakthroughs: Taming Nonlinearity

The primary contribution of this work is the first rigorous, finite-time convergence analysis for a two-timescale neural Q-learning algorithm under realistic Markovian noise. Historically, theoretical guarantees for neural RL have relied on an "artificial projection step"—a mathematical constraint that forces neural network weights to stay within a predefined boundary to prevent divergence. While useful for proofs, this step is rarely implemented in practice.

The authors successfully remove the need for this projection step by employing a Lyapunov drift approach. They approximate the highly nonlinear neural network with a local linear surrogate and define a joint Lyapunov function that captures the coupled dynamics of the fast Q-updates and the slow Whittle updates. Their analysis proves that the algorithm achieves a convergence rate of $\mathcal{O}(1/k^{2/3})$, where $k$ is the number of iterations.

Key theoretical insights include:

  • Stability without Constraints: Stability and convergence can be guaranteed under Markovian noise without artificial weight clipping or projections.
  • The Benefit of Width: The mathematical error introduced by the linear surrogate approximation decreases as the width of the neural network's hidden layer increases, suggesting that overparameterization actually aids theoretical stability.

Empirical Validation

The authors validated Neural-Q-Whittle using a synthetic 4-state RMAB problem characterized by "circulant dynamics," a standard benchmark where exact Whittle indices are known.

The results demonstrated that Neural-Q-Whittle successfully converged to the true Whittle indices (-0.5, 0.5, 1.0, and -1.0). Furthermore, the algorithm exhibited a significant speedup over baseline tabular Q-Whittle methods. This efficiency stems from the neural network's ability to generalize; the agent can update the index for a specific state even while visiting a different, related state, leading to faster global convergence.

Conclusion and Future Directions

By bridging the gap between deep reinforcement learning and RMAB theory, this paper provides a solid mathematical foundation for using neural networks in index-based resource allocation. While the current analysis is focused on two-layer ReLU networks, it paves the way for future research into deeper architectures and more complex activation functions. The removal of the projection step makes these findings particularly relevant for practitioners looking to deploy theoretically-grounded RL in large-scale, real-world resource management systems.

Summary updated

BibTeX
@inproceedings{xiong2023finite,
  author = {Guojun Xiong and Jian Li},
  title = {{Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=yhNHpLWJDl},
}
Figure