# Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 29 Sep 2026.

## Builds on (most cited first, 9 of 9)

- [Restless Bandits with Many Arms: Beating the Central Limit Theorem](https://mlsanity.com/paper/2107.11911/) (2021)
- [Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption](https://mlsanity.com/paper/2306.00196/) (2023)
- [Reoptimization Nearly Solves Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2211.01961/) (2022)
- [Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits](https://mlsanity.com/paper/2402.05689/) (2024)
- [An Optimal-Control Approach to Infinite-Horizon Restless Bandits: Achieving Asymptotic Optimality with Minimal Assumptions](https://mlsanity.com/paper/2403.11913/) (2024)
- [Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption](https://mlsanity.com/paper/2405.17882/) (2024)
- [Asymptotically Optimal Policies for Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2406.04751/) (2024)
- [Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs](https://mlsanity.com/paper/2502.06072/) (2025)
- [Model Predictive Control is almost Optimal for Heterogeneous Restless Multi-armed Bandits](https://mlsanity.com/paper/2511.08097/) (2025)

## Abstract (arXiv)

We study average-reward weakly-coupled Markov decision processes (WCMDPs), where a WCMDP consists of N smaller MDPs, called arms, that share multiple per-step budget constraints. We consider the setting where the arms have identical model parameters, multiple actions, and state- and action-dependent costs. For restless bandits (RBs), a well-studied special case of WCMDPs, prior work has developed policies that achieve an O(1/√N) optimality gap under general conditions, and has further identified conditions under which policies can achieve a better-than-1/√N optimality gap. However, for general WCMDPs, no prior result achieves an optimality gap better than 1/√N. In this paper, we identify conditions analogous to those for RBs under which a better-than-1/√N optimality gap is achievable, and design a policy that attains an O(1/N) optimality gap. Notably, unlike prior approaches based on generalizing priority orderings, our policy is not priority-based but rather is designed to induce locally linear mean-field dynamics.