Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

Tianhao Wu; Matthew Zurek; Weina Wang; Qiaomin Xie

cs.LGJun 12, 2026

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

Authors: Tianhao Wu, Matthew Zurek, Weina Wang, Qiaomin Xie

Organizations: Department of Industrial and Systems Engineering, University of Wisconsin-Madison · Department of Computer Sciences, University of Wisconsin-Madison · Computer Science Department, Carnegie Mellon University

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.

Explore similar work

Jun 15, 2026cs.LG

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process

While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited, and most existing works rely on restrictive assumptions such as ergodicity or access to a generative model. In this work, we establish the first finite sample complexity guarantees from a single trajectory for weakly communicating average-reward MDPs. To this end, we study the dynamics of a single trajectory in weakly communicating MDPs and based on this analysis, we develop novel model-free methods. Notably, our value-based and policy-based methods provide finite sample complexity guarantees of

\widetilde{O}(1/\varepsilon^2)

and

\widetilde{O}(1/\varepsilon^4)

from a single trajectory in weakly communicating MDPs, respectively. Furthermore, we introduce the first model-free method that requires no prior knowledge of problem-dependent quantities for communicating MDPs.

Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal

Markov Decision Processes Model-Free Reinforcement Learning Reinforcement-Learning Policies Optimal Sample Complexity

Ask PDF

Aug 6, 2026cs.LG

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty. We study how many samples are necessary and sufficient to learn an

\varepsilon

-optimal robust policy under the average-reward criterion. A generative model provides samples from the nominal transition kernel, whereas policy performance is evaluated over

(s,a)

-rectangular total-variation uncertainty sets of radius at most

σ

. Let

H_0

and

H_σ

denote the nominal and robust optimal bias spans, respectively. We identify

σH_0

as the perturbation scale separating high- and low-tolerance regimes. Our matching upper and lower bounds show that, up to logarithmic factors, the minimax total sample complexity is

NSA \asymp \frac{SA}{\varepsilon^2}\begin{cases} \min\{H_0,H_σ\}, & \varepsilon\gtrsimσH_0,\\ \min\{H_0,H_σ\}+σH_σ^2, & \varepsilon\lesssimσH_0. \end{cases}

Here

S

and

A

are the numbers of states and actions, and

N

is the number of samples per state-action pair. The sample complexity consists of a linear-span term that resembles the nominal AMDP results and a robustness-specific term that appears only in the low-tolerance regime. We attain these rates using reduction-based plug-in procedures that select the reduction---nominal or robust---and its discount factor: a span-informed procedure that makes these choices using known span parameters, and a span-agnostic procedure that calibrates both choices from data.

Yuepeng Yang, Yuxin Chen, Yuejie Chi

Markov Decision Processes Optimal Policies Sample Complexity Decisions

Ask PDF

May 12, 2026cs.LG

Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret

We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Our contributions are twofold. First, we establish strong duality for weakly communicating average-reward CMDPs over stationary policies with finite state and action spaces. Despite the absence of a linear programming formulation and the resulting nonconvexity under the weakly communicating setting, we show that strong duality still holds by carefully exploiting the geometric structure of the occupation measure set. Second, building on this result, we propose a primal--dual clipped value iteration algorithm for learning weakly communicating average-reward linear CMDPs. Our algorithm achieves regret and constraint violation bounds of

\widetilde{\mathcal{O}}(T^{2/3})

, improving upon the best known bounds, where

T

denotes the number of interactions. Our approach extends clipped value iteration to the constrained setting and adapts it to a finite-horizon approximation, which stabilizes the dual variable and is crucial for achieving improved regret bounds. To analyze this, we develop a novel approach based on strong duality that enables the decomposition of the composite Lagrangian regret into separate bounds on regret and constraint violation.

Kihyun Yu, Beomhan Baek, Dabeen Lee

Markov Decision Processes Linear Regret Primal-Dual Methods Regret

Ask PDF