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

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.