Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

• URL: http://arxiv.org/abs/2606.14095v2
• Date: Mon, 15 Jun 2026 02:53:05 GMT
• Title: Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
• Abstract summary: We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs)<n>By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample complexity and computational complexities in $N$.
• Score: 20.54731804867887
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process [66.74725576150941]
  We study the dynamics of a single trajectory in weakly communicating MDPs.<n>We introduce the first model-free method that requires no prior knowledge of problem-dependent quantities.
  arXiv  Detail & Related papers  (2026-06-15T13:53:19Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Provably Sample-Efficient Robust Reinforcement Learning with Average Reward [4.530028899565083]
  We propose a new algorithm designed for robust Markov Decision Processes (MDPs) with transition uncertainty characterized by $ell_p$-norm and contamination models.<n>Our algorithm operates without requiring any prior knowledge of the robust MDP.<n>Our work provides essential theoretical understanding of sample efficiency of robust average reward RL.
  arXiv  Detail & Related papers  (2025-05-18T15:34:45Z)
• On The Sample Complexity Bounds In Bilevel Reinforcement Learning [49.19950489963245]
  Bilevel reinforcement learning (BRL) has emerged as a powerful framework for aligning generative models.<n>We present the first sample of $mathcalO(epsilon)$ in continuous state-action complexity.<n>Our analysis also extends complexity improving upon existing bounds of $mathcalO(epsilon)$.
  arXiv  Detail & Related papers  (2025-03-22T04:22:04Z)
• Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL [57.745700271150454]
  We study the sample complexity of reinforcement learning in Mean-Field Games (MFGs) with model-based function approximation. We introduce the Partial Model-Based Eluder Dimension (P-MBED), a more effective notion to characterize the model class complexity.
  arXiv  Detail & Related papers  (2024-02-08T14:54:47Z)
• Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage [15.858892479232656]
  We study robust offline reinforcement learning (robust offline RL) We propose a generic algorithm framework called Doubly Pessimistic Model-based Policy Optimization ($P2MPO$) We show that $P2MPO$ enjoys a $tildemathcalO(n-1/2)$ convergence rate, where $n$ is the dataset size.
  arXiv  Detail & Related papers  (2023-05-16T17:58:05Z)
• Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints [26.008426384903764]
  offline reinforcement learning (RL) aims to find an optimal policy for Markov decision processes (MDPs) using a pre-collected dataset.<n>In this work, we revisit the linear programming (LP) reformulation of Markov decision processes for offline RL.
  arXiv  Detail & Related papers  (2022-12-28T15:28:12Z)
• PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
  We study online Reinforcement Learning (RL) in partially observable dynamical systems. We focus on the Predictive State Representations (PSRs) model, which is an expressive model that captures other well-known models. We develop a novel model-based algorithm for PSRs that can learn a near optimal policy in sample complexity scalingly.
  arXiv  Detail & Related papers  (2022-07-12T17:57:17Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• Pessimistic Model-based Offline RL: PAC Bounds and Posterior Sampling under Partial Coverage [33.766012922307084]
  We study model-based offline Reinforcement Learning with general function approximation. We present an algorithm named Constrained Policy Optimization (CPPO) which leverages a general function class and uses a constraint to encode pessimism.
  arXiv  Detail & Related papers  (2021-07-13T16:30:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.