mlsanityData to 14 Oct 2026

Model-Based Learning of Whittle indices

arXiv 2511.20397 ↗First posted 25 Nov 2025cs.LG cs.DS cs.NAcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We present BLINQ, a new model-based algorithm that learns the Whittle indices of an indexable, communicating and unichain Markov Decision Process (MDP). Our approach relies on building an empirical estimate of the MDP and then computing its Whittle indices using an extended version of a state-of-the-art existing algorithm. We provide a proof of convergence to the Whittle indices we want to learn as well as a bound on the time needed to learn them with arbitrary precision. Moreover, we investigate its computational complexity. Our numerical experiments suggest that BLINQ significantly outperforms existing Q-learning approaches in terms of the number of samples needed to get an accurate approximation. In addition, it has a total computational cost even lower than Q-learning for any reasonably high number of samples. These observations persist even when the Q-learning algorithms are speeded up using neural networks to predict Q-values.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 13 of its 40 references that are in the map. First posted on arXiv 25 Nov 2025.

Builds on

13 of 40 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Faster Q-Learning Algorithms for Restless Bandits6 Sep
  2. 2024Whittle Index Learning Algorithms for Restless Bandits with Constant Stepsizes6 Sep
  3. 2024Tabular and Deep Reinforcement Learning for Gittins Index2 May

Other references · 10

  1. 2020Whittle index based Q-learning for restless bandits with average rewardcited by 45
  2. 2021Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcarecited by 35
  3. 2020Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Banditscited by 27
  4. 2021NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RLcited by 27
  5. 2022Optimistic Whittle Index Policy: Online Learning for Restless Banditscited by 20
  6. 2017Opportunistic Scheduling as Restless Banditscited by 14
  7. 2023Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximationcited by 14
  8. 2022On learning Whittle index policy for restless bandits with scalable regretcited by 10
  9. 2022Whittle Index based Q-Learning for Wireless Edge Caching with Linear Function Approximationcited by 8
  10. 2025Asymptotically optimal regret in communicating Markov decision processescited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Tabular and Deep Learning for the Whittle Index
  2. 2024Q-learning for Quantile MDPs: A Decomposition, Performance, and Convergence Analysis
  3. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes
  4. 2026Fast Rates for Offline Q-Learning with KL Regularization
  5. 2025Quantizer Design for Finite Model Approximations, Model Learning, and Quantized Q-Learning for MDPs with Unbounded Spaces
  6. 2024Q-Learning under Finite Model Uncertainty
  7. 2021Q-Learning for MDPs with General Spaces: Convergence and Near Optimality via Quantization under Weak Continuity
  8. 2024Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity