Safety
Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs
arXiv:2609.38132v1 Announce Type: new Abstract: We study average-reward weakly-coupled Markov decision processes (WCMDPs), where a WCMDP consists of N smaller MDPs, called arms, that share multiple pe
arXiv:2609.38132v1 Announce Type: new 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/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. However, for general WCMDPs, no prior result achieves an optimality gap better than 1/sqrt{N}. In this paper, we identify conditions analogous to those for RBs under which a better-than-1/sqrt{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
- Fair Policy Optimization in Major-Minor Weakly Coupled Markov Decision Processes
- Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
- Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes
Source: arXiv cs.LG | 2026-09-30