Reproduce “Model Predictive Control is Almost Optimal for Restless Bandit” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Nicolas Gast, Dheeraj Narasimha
The LP-update policy allocates activations among arms by solving a finite-horizon linear program, taking its first action, then replanning after observing new states. Under a transition-mixing condition, its average reward approaches the relaxed LP upper bound as the horizon and number of arms grow. For fixed accuracy, the guarantee retains a 2ε residual and finite-population terms that shrink with N.
Key insights
- The core technical innovation is the application of "dissipativity" from dynamic control theory to RMABs, providing a novel framework to connect finite-horizon optimal control problems with infinite-horizon average reward objectives.
- By transforming the reward maximization into an equivalent "rotated cost" minimization, the dissipativity framework allows for a robust analysis that bypasses the need for the restrictive Uniform Global Attractor Property (UGAP).
- Strong convergence guarantees can be established for MPC-based policies under significantly weaker assumptions, primarily a general mixing condition, pushing the boundaries of theoretical tractability for RMABs.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.