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

arXiv: https://arxiv.org/abs/2408.09882 · HTML: https://mlsanity.com/paper/2408.09882/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 34 references that are in the map.
- First posted on arXiv 19 Aug 2024.

## Builds on (most cited first, 14 of 14)

- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health](https://mlsanity.com/paper/2109.08075/) (2021)
- [Deep Reinforcement Learning for Dynamic Multichannel Access in Wireless Networks](https://mlsanity.com/paper/1802.06958/) (2018)
- [Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare](https://mlsanity.com/paper/2105.07965/) (2021)
- [NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL](https://mlsanity.com/paper/2110.02128/) (2021)
- [Deep Reinforcement Learning for Wireless Sensor Scheduling in Cyber-Physical Systems](https://mlsanity.com/paper/1809.05149/) (2018)
- [A Whittle Index Approach to Minimizing Functions of Age of Information](https://mlsanity.com/paper/1908.10438/) (2019)
- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Dual-Mandate Patrols: Multi-Armed Bandits for Green Security](https://mlsanity.com/paper/2009.06560/) (2020)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [DeepCAS: A Deep Reinforcement Learning Algorithm for Control-Aware Scheduling](https://mlsanity.com/paper/1803.02998/) (2018)
- [Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximation](https://mlsanity.com/paper/2202.13187/) (2022)
- [Dynamic priority allocation via restless bandit marginal productivity indices](https://mlsanity.com/paper/2304.06115/) (2023)
- [An Index Policy for Minimizing the Uncertainty-of-Information of Markov Sources](https://mlsanity.com/paper/2212.02752/) (2022)

## Built on by (most cited first, 1 of 1)

- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)

## Abstract (arXiv)

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.