# Achieving tildeO(1/N) Optimality Gap in Restless Bandits through Gaussian Approximation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2024.

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

- [Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs](https://mlsanity.com/paper/2606.14095/) (2026)

## Abstract (arXiv)

We study the finite-horizon Restless Multi-Armed Bandit (RMAB) problem with N homogeneous arms. Prior work has shown that when an RMAB satisfies a non-degeneracy condition, Linear-Programming-based (LP-based) policies derived from the fluid approximation, which captures the mean dynamics of the system, achieve an exponentially small optimality gap. However, it is common for RMABs to be degenerate, in which case LP-based policies can result in a Theta(1/√N) optimality gap per arm. In this paper, we propose a novel Stochastic-Programming-based (SP-based) policy that, under a uniqueness assumption, achieves an tildeO(1/N) optimality gap for degenerate RMABs. Our approach is based on the construction of a Gaussian stochastic system that captures not only the mean but also the variance of the RMAB dynamics, resulting in a more accurate approximation than the fluid approximation. We then solve a stochastic program for this system to obtain our policy. This is the first result to establish an tildeO(1/N) optimality gap for degenerate RMABs.