The Sample Complexity of Policy Learning with Mu-Resets
Gene Li
cs.LG
Submitted: 2026-08-07
Updated: 2026-08-11
Comments: comments welcome
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study policy-based reinforcement learning under the mu-resets interaction protocol of Kakade and Langford [KL02].
Terminology
Abstract
We study policy-based reinforcement learning under the mu-resets interaction protocol of Kakade and Langford [KL02]. This interaction protocol enables the learner to sample trajectories from a given exploratory reset distribution mu, 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 ((H)) sample complexity lower bound; with bounded pushforward concentrability, we show the dependence on horizon is tightly characterized as ((sqrt H)).
Sources
- Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
- The Role of Environment Access in Agnostic Reinforcement Learning
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks