mlsanityData to 14 Oct 2026

Tabular and Deep Reinforcement Learning for Gittins Index

arXiv 2405.01157 ↗First posted 2 May 2024cs.LG cs.PF stat.MLcited by 1

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

Abstract (arXiv)

In the realm of multi-arm bandit problems, the Gittins index policy is known to be optimal in maximizing the expected total discounted reward obtained from pulling the Markovian arms. In most realistic scenarios however, the Markovian state transition probabilities are unknown and therefore the Gittins indices cannot be computed. One can then resort to reinforcement learning (RL) algorithms that explore the state space to learn these indices while exploiting to maximize the reward collected. In this work, we propose tabular (QGI) and Deep RL (DGN) algorithms for learning the Gittins index that are based on the retirement formulation for the multi-arm bandit problem. When compared with existing RL algorithms that learn the Gittins index, our algorithms have a lower run time, require less storage space (small Q-table size in QGI and smaller replay buffer in DGN), and illustrate better empirical convergence to the Gittins index. This makes our algorithm well suited for problems with large state spaces and is a viable alternative to existing methods. As a key application, we demonstrate the use of our algorithms in minimizing the mean flowtime in a job scheduling problem when jobs are available in batches and have an unknown service time distribution.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 9 of its 38 references that are in the map. First posted on arXiv 2 May 2024.

Builds on

9 of 38 references.

References · 9

  1. 2015Continuous control with deep reinforcement learningcited by 3,407
  2. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,745
  3. 2020Whittle index based Q-learning for restless bandits with average rewardcited by 45
  4. 2019A Whittle Index Approach to Minimizing Functions of Age of Informationcited by 21
  5. 2022On learning Whittle index policy for restless bandits with scalable regretcited by 10
  6. 2022DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABscited by 6
  7. 2016Reinforcement Learning algorithms for regret minimization in structured Markov Decision Processescited by 3
  8. 2023Practical First-Order Bayesian Optimization Algorithmscited by 3
  9. 2018A Structure-aware Online Learning Algorithm for Markov Decision Processescited by 1

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Model-Based Learning of Whittle indicescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Tabular and Deep Learning for the Whittle Index
  2. 2024GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Bandits
  3. 2024Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning
  4. 2022Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch
  5. 2024State-Separated SARSA: A Practical Sequential Decision-Making Algorithm with Recovering Rewards
  6. 2024Faster Q-Learning Algorithms for Restless Bandits
  7. 2024A Comprehensive Survey of Reinforcement Learning: From Algorithms to Practical Challenges
  8. 2024Efficient Exploration in Deep Reinforcement Learning: A Novel Bayesian Actor-Critic Algorithm