# Asymptotically Optimal Policies for Weakly Coupled Markov Decision Processes

arXiv: https://arxiv.org/abs/2406.04751 · HTML: https://mlsanity.com/paper/2406.04751/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2024.

## Built on by (most cited first, 4 of 4)

- [Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs](https://mlsanity.com/paper/2502.06072/) (2025)
- [Model Predictive Control is Almost Optimal for Restless Bandit](https://mlsanity.com/paper/2410.06307/) (2024)
- [Neural Index Policies for Restless Multi-Action Bandits with Heterogeneous Budgets](https://mlsanity.com/paper/2510.22069/) (2025)
- [Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs](https://mlsanity.com/paper/2609.38132/) (2026)

## Abstract (arXiv)

We consider the problem of maximizing the expected average reward obtained over an infinite time horizon by n weakly coupled Markov decision processes. Our setup is a substantial generalization of the multi-armed restless bandit problem that allows for multiple actions and constraints. We establish a connection with a deterministic and continuous-variable control problem where the objective is to maximize the average reward derived from an occupancy measure that represents the empirical distribution of the processes when n → ∞. We show that a solution of this fluid problem can be used to construct policies for the weakly coupled processes that achieve the maximum expected average reward as n → ∞, and we give sufficient conditions for the existence of solutions. Under certain assumptions on the constraints, we prove that these conditions are automatically satisfied if the unconstrained single-process problem admits a suitable unichain and aperiodic policy. In particular, the assumptions include multi-armed restless bandits and a broad class of problems with multiple actions and inequality constraints. Also, the policies can be constructed in an explicit way in these cases. Our theoretical results are complemented by several concrete examples and numerical experiments, which include multichain setups that are covered by the theoretical results.