# The Sample Complexity of Policy Learning with Mu-Resets

arXiv: https://arxiv.org/abs/2608.07772 · HTML: https://mlsanity.com/paper/2608.07772/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 6 of its 8 references that are in the map.
- First posted on arXiv 7 Aug 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 6 of 6)

- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations](https://mlsanity.com/paper/2106.11519/) (2021)
- [Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data](https://mlsanity.com/paper/2403.17091/) (2024)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [The Role of Environment Access in Agnostic Reinforcement Learning](https://mlsanity.com/paper/2504.05405/) (2025)

## 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)).