The Sample Complexity of Policy Learning with Mu-Resets
Not on the map. Why?
Abstract (arXiv)
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(Omega(H)) sample complexity lower bound; with bounded pushforward concentrability, we show the dependence on horizon is tightly characterized as exp(Theta(√ H)).
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 6 of its 8 references that are in the map. First posted on arXiv 7 Aug 2026.
Builds on
6 of 8 references.
References · 6
- 2020Batch Value-function Approximation with Only Realizabilitycited by 103
- 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
- 2021Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observationscited by 13
- 2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Datacited by 11
- 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
- 2025The Role of Environment Access in Agnostic Reinforcement Learningcited by 3
Built on by
Not cited yet.