Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs (extended abstract)
Wu Tianhao, Matthew Zurek, Weina Wang, Qiaomin XieProceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6852-6857, 2026.
Abstract
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/\sqrt{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.
Cite this Paper
BibTeX
@InProceedings{pmlr-v336-tianhao26a,
title = {Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs (extended abstract)},
author = {Tianhao, Wu and Zurek, Matthew and Wang, Weina and Xie, Qiaomin},
booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory},
pages = {6852--6857},
year = {2026},
editor = {Hanneke, Steve and Lattimore, Tor},
volume = {336},
series = {Proceedings of Machine Learning Research},
month = {29 Jun--03 Jul},
publisher = {PMLR},
pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/tianhao26a/tianhao26a.pdf},
url = {https://proceedings.mlr.press/v336/tianhao26a.html},
abstract = {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/\sqrt{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.}
}
Endnote
%0 Conference Paper
%T Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs (extended abstract)
%A Wu Tianhao
%A Matthew Zurek
%A Weina Wang
%A Qiaomin Xie
%B Proceedings of Thirty Ninth Conference on Learning Theory
%C Proceedings of Machine Learning Research
%D 2026
%E Steve Hanneke
%E Tor Lattimore
%F pmlr-v336-tianhao26a
%I PMLR
%P 6852--6857
%U https://proceedings.mlr.press/v336/tianhao26a.html
%V 336
%X 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/\sqrt{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.
APA
Tianhao, W., Zurek, M., Wang, W. & Xie, Q.. (2026). Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs (extended abstract). Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:6852-6857 Available from https://proceedings.mlr.press/v336/tianhao26a.html.