{"id":"arxiv/2609.38132","url":"https://arxiv.org/abs/2609.38132","tags":["cs.LG","math.OC","math.PR"],"score":0,"title":"Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs","domain":"cs.LG","source":"arxiv","authors":["Yige Hong","Xiangcheng Zhang","Qiaomin Xie","Yudong Chen","Weina Wang"],"reviews":0,"subject":"cs.LG","summary":"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/\\sqrt{N})$ optimality gap under general conditions, and has further identified conditions under which policies can achieve a better-than-$1/\\sqrt{N}$ optimality gap.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}