Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs
Abstract
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.
Related
- Non-asymptotic Convergence of Average-reward Q-learning with Options
- Optimality of delayed reward attainment under uncertainty
- List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
- Entropy-Regularized Mean-Field Games with Average-Reward Criterion: Span-Seminorm Contractions and Model-Free Learning
BibTeX
@misc{hong2026achieving,
title = {{Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs}},
author = {Yige Hong and Xiangcheng Zhang and Qiaomin Xie and Yudong Chen and Weina Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38132},
eprint = {2609.38132},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38132},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs
AU - Yige Hong
AU - Xiangcheng Zhang
AU - Qiaomin Xie
AU - Yudong Chen
AU - Weina Wang
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.38132
UR - https://arxiv.org/abs/2609.38132
AB - 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.
ER -