mlsanityData to 7 Oct 2026

An Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits

arXiv 1707.00205 ↗First posted 1 Jul 2017math.OCcited by 20

Not on the map. Why?

Abstract (arXiv)

We consider restless multi-armed bandit (RMAB) with a finite horizon and multiple pulls per period. Leveraging the Lagrangian relaxation, we approximate the problem with a collection of single arm problems. We then propose an index-based policy that uses optimal solutions of the single arm problems to index individual arms, and offer a proof that it is asymptotically optimal as the number of arms tends to infinity. We also use simulation to show that this index-based policy performs better than the state-of-art heuristics in various problem settings.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Jul 2017.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 5; 2023: 3; 2024: 4; 2025: 3.

20 papers.

Sort:

  1. 2021Restless Bandits with Many Arms: Beating the Central Limit Theoremcited by 18
  2. 2022Optimistic Whittle Index Policy: Online Learning for Restless Banditscited by 18
  3. 2022Efficient Resource Allocation with Fairness Constraints in Restless Multi-Armed Banditscited by 11
  4. 2022Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Banditscited by 10
  5. 2023Online Restless Multi-Armed Bandits with Long-Term Fairness Constraintscited by 10
  6. 2022Near-optimality for infinite-horizon restless bandits with many armscited by 9
  7. 2023Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumptioncited by 9
  8. 2021Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problemscited by 6
  9. 2023Weakly Coupled Deep Q-Networkscited by 6
  10. 2022Towards Soft Fairness in Restless Multi-Armed Banditscited by 5
  11. 2024Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Banditscited by 5
  12. 2024Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumptioncited by 4
8 more
  1. 2021Low-Complexity Algorithm for Restless Bandits with Imperfect Observationscited by 3
  2. 2025Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPscited by 2
  3. 2021Bandits with Dynamic Arm-acquisition Costscited by 1
  4. 2024Model Predictive Control is Almost Optimal for Restless Banditcited by 1
  5. 2025Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocationcited by 1
  6. 2025Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Banditscited by 1
  7. 2021Reinforcement Learning for Finite-Horizon Restless Multi-Armed Multi-Action Banditscited by 0
  8. 2024Structured Reinforcement Learning for Delay-Optimal Data Transmission in Dense mmWave Networkscited by 0