# Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 58 references that are in the map.
- First posted on arXiv 9 Feb 2025.

## Builds on (most cited first, 21 of 21)

- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare](https://mlsanity.com/paper/2105.07965/) (2021)
- [NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL](https://mlsanity.com/paper/2110.02128/) (2021)
- [Q-Learning Lagrange Policies for Multi-Action Restless Bandits](https://mlsanity.com/paper/2106.12024/) (2021)
- [An Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits](https://mlsanity.com/paper/1707.00205/) (2017)
- [Restless Bandits with Many Arms: Beating the Central Limit Theorem](https://mlsanity.com/paper/2107.11911/) (2021)
- [Deadline Scheduling as Restless Bandits](https://mlsanity.com/paper/1610.00399/) (2016)
- [Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximation](https://mlsanity.com/paper/2310.02147/) (2023)
- [LP-based policies for restless bandits: necessary and sufficient conditions for (exponentially fast) asymptotic optimality](https://mlsanity.com/paper/2106.10067/) (2021)
- [Indexability is Not Enough for Whittle: Improved, Near-Optimal Algorithms for Restless Bandits](https://mlsanity.com/paper/2211.00112/) (2022)
- [Near-optimality for infinite-horizon restless bandits with many arms](https://mlsanity.com/paper/2203.15853/) (2022)
- [Restless Bandits with Average Reward: Breaking the Uniform Global Attractor Assumption](https://mlsanity.com/paper/2306.00196/) (2023)
- [Reoptimization Nearly Solves Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2211.01961/) (2022)
- [Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2107.01689/) (2021)
- [DeepTOP: Deep Threshold-Optimal Policy for MDPs and RMABs](https://mlsanity.com/paper/2209.08646/) (2022)
- [Weakly Coupled Deep Q-Networks](https://mlsanity.com/paper/2310.18803/) (2023)
- [Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits](https://mlsanity.com/paper/2402.05689/) (2024)
- [An Optimal-Control Approach to Infinite-Horizon Restless Bandits: Achieving Asymptotic Optimality with Minimal Assumptions](https://mlsanity.com/paper/2403.11913/) (2024)
- [Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption](https://mlsanity.com/paper/2405.17882/) (2024)
- [Asymptotically Optimal Policies for Weakly Coupled Markov Decision Processes](https://mlsanity.com/paper/2406.04751/) (2024)
- [RL-MPCA: A Reinforcement Learning Based Multi-Phase Computation Allocation Approach for Recommender Systems](https://mlsanity.com/paper/2401.01369/) (2023)

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

- [Neural Index Policies for Restless Multi-Action Bandits with Heterogeneous Budgets](https://mlsanity.com/paper/2510.22069/) (2025)
- [Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs](https://mlsanity.com/paper/2606.14095/) (2026)
- [Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs](https://mlsanity.com/paper/2609.38132/) (2026)

## Abstract (arXiv)

Heterogeneity poses a fundamental challenge for many real-world large-scale decision-making problems but remains largely understudied. In this paper, we study the fully heterogeneous setting of a prominent class of such problems, known as weakly-coupled Markov decision processes (WCMDPs). Each WCMDP consists of N arms (or subproblems), which have distinct model parameters in the fully heterogeneous setting, leading to the curse of dimensionality when N is large. We show that, under mild assumptions, an efficiently computable policy achieves an O(1/√N) optimality gap in the long-run average reward per arm for fully heterogeneous WCMDPs as N becomes large. This is the first asymptotic optimality result for fully heterogeneous average-reward WCMDPs. Our main technical innovation is the construction of projection-based Lyapunov functions that certify the convergence of rewards and costs to an optimal region, even under full heterogeneity.