# Reoptimization Nearly Solves Weakly Coupled Markov Decision Processes

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2022.

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

- [Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption](https://mlsanity.com/paper/2405.17882/) (2024)
- [Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs](https://mlsanity.com/paper/2502.06072/) (2025)
- [Indexability of Finite State Restless Multi-Armed Bandit and Rollout Policy](https://mlsanity.com/paper/2305.00410/) (2023)
- [Model Predictive Control is Almost Optimal for Restless Bandit](https://mlsanity.com/paper/2410.06307/) (2024)
- [Fair Resource Allocation in Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2411.09804/) (2024)
- [Multi-agent Markov Entanglement](https://mlsanity.com/paper/2506.02385/) (2025)
- [Fair Policy Optimization in Major-Minor Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2609.36174/) (2026)
- [Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs](https://mlsanity.com/paper/2609.38132/) (2026)

## Abstract (arXiv)

We propose a new policy, called the LP-update policy, to solve finite horizon weakly-coupled Markov decision processes. The latter can be seen as multi-constraint multi-action bandits, and generalize the classical restless bandit problems. Our solution is based on re-solving periodically a relaxed version of the original problem, that can be cast as a linear program (LP). When the problem is made of N statistically identical sub-components, we show that the LP-update policy becomes asymptotically optimal at rate O(T2/√N). This rate can be improved to O(T/√N) if the problem satisfies some ergodicity property and to O(1/N) if the problem is non-degenerate. The definition of non-degeneracy extends the same notion for restless bandits. By using this property, we also improve the computational efficiency of the LP-update policy. We illustrate the performance of our policy on randomly generated examples, as well as a generalized applicant screening problem, and show that it outperforms existing heuristics.