Research map / Bandits and online learning / Multi-armed bandits
Achieving $\tilde{\mathcal{O}}(1/N)$ Optimality Gap in Restless Bandits through Gaussian Approximation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a Gaussian-approximation-based stochastic-programming policy for finite-horizon degenerate restless bandits that achieves Õ(1/N) optimality gap under a uniqueness assumption, versus Θ(1/√N) for LP-based policies.
Problem
Finite-horizon restless multi-armed bandits with N homogeneous arms that are degenerate (violate the non-degeneracy condition), where LP-based fluid policies incur a Θ(1/√N) per-arm optimality gap.
Approach
Build a Gaussian stochastic system around the fluid LP optimum that matches both mean and covariance of the N-system, restrict the search to a neighborhood of the fluid solution, solve the resulting stochastic program, and round it to a feasible N-system action.
Key results
- On degenerate RMABs under the uniqueness assumption, the SP-based policy achieves a Õ(1/N) optimality gap, whereas LP-based policies have Θ(1/√N) gap per arm.
- On machine maintenance experiments, the SP-based policy's total reward advantage over the LP-based policy grows with N in both unique and non-unique fluid LP settings.
- Computation time of EDDP increases linearly in H and S in the reported experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Gaussian stochastic program instead of an LP-based policy | Finite-horizon RMABs satisfying the uniqueness assumption · Degenerate finite-horizon RMAB | optimality gap per arm: \Theta(1 / \sqrt{N}) -> \tilde{\mathcal{O}}(1/N) | Helped |
| Use the SP-based policy rather than any policy in the LP-based class, when the stated Gaussian-system advantage condition holds | Finite-horizon RMABs without the uniqueness assumption · Finite-horizon RMAB | improvement in value per arm: \Omega(1/\sqrt{N}) | Helped |
| Use an LP-based policy for degenerate RMABs | Degenerate finite-horizon RMAB · Degenerate finite-horizon RMAB | optimality gap per arm: \Theta(1 / \sqrt{N}) | Hurt |
| Approximate the stochastic N-system with the fluid LP rather than a Gaussian stochastic system | Degenerate finite-horizon RMAB · Degenerate finite-horizon RMAB | approximation error: \Theta(1/\sqrt{N}) -> \tilde{\mathcal{O}}(1/N) | Hurt |
| Use the SP-based policy instead of the LP-based policy | Machine maintenance RMABs · Machine maintenance RMABs with unique and non-unique fluid LP solutions | reward difference (SP minus LP) | Helped |
Surprising findings
- The LP upper bound itself has a Θ(1/√N) gap from the optimal value for degenerate RMABs, so it is not tight.
Limitations
- Main optimality guarantee requires the uniqueness assumption of the fluid LP solution.
- Without uniqueness, only an Ω(1/√N) improvement over LP-based policies is shown, under an extra strict-improvement condition.
Experimental setup
Benchmarks: two-state two-step RMAB example machine maintenance RMAB
Metrics: optimality gap total reward difference (SP minus LP) computation time of EDDP
Baselines: LP-based index policy fluid LP-based policies LP upper bound
Builds on: fluid approximation LP for RMAB non-degeneracy condition diffusion approximation
Closest papers by meaning
- Global Rewards in Restless Multi-Armed Bandits (NeurIPS 2024 · similarity 0.88)
- Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback (ICML 2024 · similarity 0.88)
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.87)
- Contextual Linear Bandits with Delay as Payoff (ICML 2025 · similarity 0.87)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.87)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.