Achieving constant rate optimality gap in budget constrained decision systems
Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs
Machine Learning
Summary
This paper looks at a complex decision-making problem where many smaller units, called arms, share limited resources while making choices. Previous work could only guarantee that the difference between a chosen strategy and the best strategy shrinks slowly as the number of units grows. The authors identify specific conditions where this difference shrinks much faster, and they design a new strategy to achieve this better rate. Unlike past methods that rank choices by priority, their approach uses a smoother, linear dynamic to guide decisions.
What this means in practice
- •For network schedulers: Design scheduling policies for large-scale resource-sharing networks to improve average long-term performance with strict per-step constraints.
- •For inventory control teams: Coordinate multiple inventory systems sharing budget limits to reduce the gap between implemented and optimal stocking policies as system size grows.
Authors
Yige Hong, Xiangcheng Zhang, Qiaomin Xie, Yudong Chen, Weina Wang
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.