{"id":"arxiv/2606.14095","url":"https://arxiv.org/abs/2606.14095","tags":["cs.LG","math.OC","math.PR","stat.ML"],"score":0,"title":"Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs","domain":"cs.LG","source":"arxiv","authors":["Tianhao Wu","Matthew Zurek","Weina Wang","Qiaomin Xie"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-12","reactions":{}}