# Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 52 references that are in the map.
- First posted on arXiv 12 Jun 2026.

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

- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Thompson Sampling in Non-Episodic Restless Bandits](https://mlsanity.com/paper/1910.05654/) (2019)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Optimal Sample Complexity for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2310.08833/) (2023)
- [Near-Optimal Sample Complexity for MDPs via Anchoring](https://mlsanity.com/paper/2502.04477/) (2025)
- [Finding good policies in average-reward Markov Decision Processes without prior knowledge](https://mlsanity.com/paper/2405.17108/) (2024)
- [The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis](https://mlsanity.com/paper/2410.07616/) (2024)
- [Unichain and Aperiodicity are Sufficient for Asymptotic Optimality of Average-Reward Restless Bandits](https://mlsanity.com/paper/2402.05689/) (2024)
- [Achieving Exponential Asymptotic Optimality in Average-Reward Restless Bandits without Global Attractor Assumption](https://mlsanity.com/paper/2405.17882/) (2024)
- [Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL](https://mlsanity.com/paper/2502.11238/) (2025)
- [Lagrangian Index Policy for Restless Bandits with Average Reward](https://mlsanity.com/paper/2412.12641/) (2024)
- [Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs](https://mlsanity.com/paper/2502.06072/) (2025)
- [Achieving tildeO(1/N) Optimality Gap in Restless Bandits through Gaussian Approximation](https://mlsanity.com/paper/2410.15003/) (2024)

## Abstract (arXiv)

We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction to a tabular MDP leads to high complexity bounds as the state-action space is exponentially large in the number of arms N. By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample and computational complexities that are polynomial in N. Specifically, we analyze the plug-in approach, which applies an efficient planning algorithm to an empirical model estimated from data. For fully heterogeneous WCMDPs, we establish the first finite-sample PAC guarantee with polynomial complexity and an O(1/√N) optimality gap. For homogeneous RBs, we further prove that a smaller optimality gap is achievable under mild structural assumptions. A primary technical contribution of our work is a novel Lyapunov-based analysis framework. Unlike classical approaches that rely on the difficult-to-control bias function, our framework uses an explicitly constructed Lyapunov function along with a drift transfer technique between the true and empirical models. A key step of independent interest in our framework is a fine-grained perturbation analysis for the underlying linear programming (LP) relaxation, which provides a general tool for analyzing LP-based policies and weakly-coupled systems.