The Sample Complexity of Policy Learning with Mu-Resets

Gene Li

cs.LGAug 7, 2026

The Sample Complexity of Policy Learning with Mu-Resets

Authors: Gene Li

Abstract

We study policy-based reinforcement learning under the $μ$ -resets interaction protocol of Kakade and Langford [KL02]. This interaction protocol enables the learner to sample trajectories from a given exploratory reset distribution $μ$ , in addition to the starting distribution. We resolve the question raised by [KLS25] on the role of policy realizability for the sample complexity of this problem. Critically, the dependence on horizon $H$ is governed by the notion of coverage assumed of the reset distribution. Under bounded all-policy concentrability, we show a $\exp(Ω(H))$ sample complexity lower bound; with bounded pushforward concentrability, we show the dependence on horizon is tightly characterized as $\exp(Θ(\sqrt H))$ .

Explore similar work

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
Jun 12, 2026Tianhao Wu, Matthew Zurek, Weina Wang +1Markov Decision Processes Sample Complexity
Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions
May 13, 2026Ishaq Hamza, Zaiwei ChenSoft Actor-Critic Optimal Policies
Tight Sample Complexity Bounds for Entropic Best Policy Identification
May 13, 2026Amer Essakine, Claire VernadeEntropy Regularized Reinforcement Learning Optimal Policies

Jun 12, 2026 · cs.LGJ/K move · Enter open · S save

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

Tianhao Wu, Matthew Zurek, Weina Wang, Qiaomin Xie

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

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.

Markov Decision Processes Sample Complexity Lyapunov Function

Open paper Ask about it PDF

Abstract

Explore similar work

Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs

Achieving ε−2ε^{-2}ε−2 Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Tight Sample Complexity Bounds for Entropic Best Policy Identification

Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions