Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs
A new non-priority policy achieves an O(1/N) optimality gap for average-reward weakly-coupled MDPs.
The paper studies average-reward weakly-coupled Markov decision processes made of N identical arms that share multiple per-step budget constraints, with multiple actions and state- and action-dependent costs. For restless bandits, a special case, prior policies reach an O(1/sqrt(N)) gap and sometimes better; for general WCMDPs, nothing better than 1/sqrt(N) was known. The authors identify conditions, analogous to the restless-bandit case, under which a stronger rate is possible and design a non-priority policy that attains an O(1/N) optimality gap by inducing locally linear mean-field dynamics.
- Setting is average-reward weakly-coupled MDPs with N identical arms and shared budgets.
- Prior general WCMDP results did not beat a 1/sqrt(N) optimality gap.
- New non-priority policy achieves an O(1/N) gap under identified conditions.
- Policy induces locally linear mean-field dynamics rather than a priority ordering.
From the original article
1 min read at arxiv.orgWe 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.
By Yige Hong · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.