REVIEW 2 major objections 4 minor 8 references
The Sample Complexity of Policy Learning with Mu-Resets
T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read Under μ-resets, a realizable policy class still faces exp(Ω(H)) sample complexity unless the reset distribution has bounded pushforward concentrability, in which case the bound tightens to exp(Θ(√H)).
desk verdict The upper bound is a genuine, complete result; the two lower bounds rest on an omitted information-theoretic argument and one of the value claims in Section 4 is false as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The two load-bearing constructions are rich-observation combination locks with random decoder classes: each layer's observed state is drawn uniformly from a large set, and a randomly drawn decoder assigns equal numbers of observations to each latent state, so with high probability every visited observation is fresh and reveals nothing about the hidden key. The upper bound is carried by BlockPSDP, which partitions the horizon into K blocks of length L, at each block importance-samples trajectories that explore uniformly within the block and follow the already learned suffix, and propagates error only across block boundaries via pushforward concentrability; the key recursion is e_k ≤ η + Cpush e_{k+1}, balancing A^L sample cost against $Cpush^{{K}}$ amplification.
What would settle it
For the Theorem 1 construction, compute the probability that two trajectories rolled out from resets at layer h observe the same state, for the stated state-space size m = $2^{{cH}}$; if this collision probability is non-negligible, or if any statistical test can distinguish two decoders from transition data, the fresh-observation assumption fails and the lower bound collapses.
Extended reading notes
Core claim
The paper's central claim is that under μ-resets with a realizable policy class, the sample complexity is exp(Θ(H)) whenever the reset distribution has bounded all-policy concentrability (Call ≤ O(1)) and exp(Θ(√H)) whenever it has bounded pushforward concentrability (Cpush ≤ O(1)). The exp(Ω(H)) lower bound (Theorem 1) uses a rich-observation combination lock with a decoder class of size exponential in H, so that every observed state is fresh and transition data carries no information about the hidden optimal policy; the learner is left with reward observations that require $2^{{Ω(H)}}$ guesses. The exp(Θ(√H)) characterization (Theorems 2 and 3) uses a recursive combination lock that poisons reward information at a scale of $4^{{-k}}$ per block, together with a blockwise PSDP algorithm that balances sample cost A^L within blocks against Cpush error amplification across K = H/L boundaries; setting K = L = √H gives the bound. The paper also shows that realizability yields an exponential improvement over the agnostic setting under pushforward coverage, and that PSDP is suboptimal.
Load-bearing premise
Both lower bounds depend on the fresh-observation property of the random decoder class: the paper asserts, without the formal information-theoretic proof, that with a decoder class of exponential statistical complexity, every observed state is fresh, so transition data leaks nothing about the hidden key; if that assertion fails for resets at intermediate layers, the exp(Ω(H)) and exp(Ω(√H)) lower bounds do not follow.
Editorial extensions
If this is right
- Realizability does not automatically make μ-resets sample-efficient: under bounded all-policy concentrability, the exp(Ω(H)) lower bound matches the agnostic setting, so policy completeness or another structural assumption remains necessary.
- Under bounded pushforward concentrability, realizability improves the horizon dependence from exp(Θ(H)) to exp(Θ(√H)), an exponential improvement over the agnostic lower bound.
- PSDP is suboptimal under realizability and pushforward coverage: it requires exp(Θ(H)) samples, while the new BlockPSDP achieves exp(Θ(√H)).
- The lower bound of Theorem 3 is an information-theoretic strengthening of the algorithm-dependent lower bound of [KLS25], now built on √H-length combination locks.
Reading between the lines
- The recursive poisoning structure suggests a general principle: when coverage is limited to pushing the state distribution one step forward, each block of length L can only be learned by brute-force search over A^L action sequences, and the optimal block length trades this search cost against the number of blocks over which error amplifies; the same tradeoff may apply to other block-decomposable R
- If the omitted fresh-observation argument is made fully rigorous, the rich-observation decoder technique would transfer directly to any realizable policy-learning problem with large observation spaces, including offline settings where the reset distribution plays the role of the data distribution.
- The bound's dependence on Cpush enters as (A Cpush)^{2√H}, so an algorithm that reduced the coverage dependence to polynomial in Cpush while keeping the exp(Θ(√H)) horizon dependence would be a meaningful further step; the current recursion suggests such a reduction would require a different error-propagation mechanism.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the sample complexity of policy learning under the μ-resets interaction protocol with a realizable policy class. It claims two main results: (i) under bounded all-policy concentrability, any proper algorithm requires exp(Ω(H)) samples even with realizability (Theorem 1); (ii) under bounded pushforward concentrability, the sample complexity is exp(Θ(√H)), with a new algorithm BlockPSDP giving the upper bound (Theorem 2) and a combination-lock construction giving the lower bound (Theorem 3). The paper argues that this resolves an open question from KLS25 and gives a quantitative separation between all-policy and pushforward concentrability. The upper-bound proof is written out in detail, while the two lower-bound sections are presented as sketches that explicitly defer the formal information-theoretic arguments.
Significance. If the results are correct, they settle a natural question about policy realizability under μ-resets and provide a tight characterization in terms of pushforward concentrability. The BlockPSDP algorithm is a clean and potentially reusable idea, and the recursive poison-lock construction for the pushforward lower bound is conceptually appealing. The claimed separation between all-policy and pushforward concentrability, and the exponential improvement over the agnostic setting, are significant. However, the lower-bound proofs are currently incomplete in a way that is load-bearing for the paper's central claims, and the upper-bound proof relies on a pointwise optimality condition that is not stated in the theorem. The contribution is promising, but the manuscript needs substantial revision before the results can be considered established.
major comments (2)
- [Sections 2 and 4] Both lower-bound proofs are only sketches: Section 2 explicitly states 'We omit the formal information-theoretic arguments' and Section 4 similarly defers to 'a standard random-decoder analysis.' This omission is not cosmetic. The claim that 'with high probability, every observed state is a fresh, nonrepeated observation' is the sole argument for why transition data leaks no information about the hidden key, and it is asserted without proof. In the Section 2 construction, resets at layers 2≤h≤H/2 have transition statistics that depend on whether the latent state is good, bad, verifier, or neutral, and the reward-mixture calculation implicitly assumes the learner cannot identify the latent state from the observed state. Without a formal coupling or information-theoretic argument showing that the entire observation process is within o(1) total variation of a key-independent process, the exp(Ω(H)) lower bound of Theorem 1 is not established. The same issue affects Theorem 3: the reward identity in Section 4 is used to conclude that only the action sequence matching the remaining suffix of Block k and all of Block k+1 produces a different reward law, but this conclusion assumes that transitions starting from reset states cannot themselves reveal information about θ. A complete proof of the fresh-observation property, or a reduction to a known hard problem that includes it, is necessary for both lower-bound theorems.
- [Section 3, Lemma 1] The proof of Lemma 1 bounds the continuation gap E_{ν_{k+1}}[V^{π⋆}_{startk+1}(x)-V^{\hatπ}_{startk+1}(x)] by C_push e_{k+1}. This step uses the inequality ∫ f dν ≤ C_push ∫ f dμ_{startk+1}, which is valid only when the integrand f is pointwise nonnegative. The proof invokes 'the optimality of π⋆' to ensure this, but Theorem 2 only assumes Π is realizable, i.e., π⋆ maximizes V^π(d1) over Π. That condition does not imply π⋆ is optimal from every state, so V^{π⋆}(x)-V^{\hatπ}(x) can be negative on states reached by resets. If the authors intend the stronger assumption that π⋆ is optimal from every state—as in their lower-bound constructions—it must be stated in Theorem 2. Otherwise the error-propagation inequality (3) and therefore the sample-complexity guarantee of Theorem 2 do not follow from the stated assumptions.
minor comments (4)
- [Section 4] The statement that V^{πϑ}=0 for every ϑ≠θ is correct, but only because πϑ repeats the same length-L sequence in every block, so block 1 already contains all L bits of ϑ; the paper should state this explicitly to avoid confusion, since at first glance a policy matching θ on block 1 but differing later might appear to reach Collect(p_1).
- [Theorems 1 and 3] The theorem statements say 'known reset distribution μ,' but the constructions define μ via the decoder ϕ, so μ may depend on the instance. The authors should clarify whether μ is a single fixed distribution for the whole family or a per-instance known distribution, and in the latter case should state that the algorithm receives μ as input.
- [Section 3, Eq. (1)] The importance-sampling concentration bound is quoted from [JLR+23] without stating the exact concentration inequality; since the importance weights are unbounded (up to A^L), the dependence on A^L and η in Eq. (1) should be justified by an explicit Bernstein-type or related bound.
- [Section 4] The notation m is reused with different meanings: in Section 2, m is the total size of the observation space, while in Section 4, m is the size of one decoder preimage and |X_h|=8m. This should be harmonized.
Circularity Check
No circularity is present; the central bounds are new constructions, and the self-citations to KLS25 and JLR+23 serve as independent, non-target-supporting evidence.
full rationale
The paper's central claims—the exp(Omega(H)) lower bound under all-policy concentrability, the exp(Theta(sqrt H)) characterization under pushforward concentrability, and the BlockPSDP upper bound—are new constructions and analyses that are not defined in terms of their own conclusions. The lower bounds use rich-observation combination locks with random decoder classes; the required 'fresh observation' property is deferred to 'the standard analysis for rich-observation combination locks [SDM+21; JLR+23; KLS25]'. Although the author is a coauthor of two of the cited works, those citations are real evidence: they are peer-reviewed frameworks whose assumptions do not include the target result, so they do not raise the circularity score. The upper bound's importance-sampling guarantee similarly cites 'Standard concentration for importance sampling [JLR+23]' as a reusable lemma, and the recursion over blocks, boundary error propagation, and balancing of A^L and K are new, so no prediction reduces to a fit or to an earlier result by construction. I found no fitted-input-as-prediction, renamed known result, or imported uniqueness claim. Two non-circular proof-quality flags should be recorded separately: (i) Theorem 1 and Theorem 3 both state 'We omit the formal information-theoretic arguments' for the decisive fresh-observation claim, so the lower-bound proofs are incomplete as written even though not circular; and (ii) Section 4's assertion that 'V^{pi_vartheta}=0 for every vartheta != theta' is internally inconsistent, since any policy matching theta on Block 1 reaches Collect(p1) and has value p1=1/4, though this does not change the 2^{Omega(sqrt H)} magnitude. These are correctness risks, not circularity.
Assumptions & free parameters
assumptions (5)
- domain assumption Episodic finite-horizon layered MDP with cumulative reward in [0,1].
- domain assumption The reset distribution mu is known and sampleable, with mu_1 = d_1.
- domain assumption Realizability: the optimal policy pi* belongs to the policy class Pi.
- domain assumption The reset distribution satisfies bounded all-policy concentrability (Theorem 1) or bounded pushforward concentrability (Theorems 2 and 3).
- standard math Importance-sampling concentration bound: n >= c A^L / eta^2 log(2|Pi|/delta) from [JLR+23].
Cite this review
Pith. "Pith review of The Sample Complexity of Policy Learning with Mu-Resets." pith.science (2026). https://pith.science/paper/CQNYUTN6
@misc{pith2026260807772,
author = {Pith},
title = {Pith review of: The Sample Complexity of Policy Learning with Mu-Resets},
year = {2026},
howpublished = {\url{https://pith.science/paper/CQNYUTN6}},
note = {Machine review of arXiv:2608.07772}
}
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 $\exp(\Omega(H))$ sample complexity lower bound; with bounded pushforward concentrability, we show the dependence on horizon is tightly characterized as $\exp(\Theta(\sqrt H))$.
Figures
Reference graph
Works this paper leans on
-
[1]
J. A. Bagnell, S. M. Kakade, J. G. Schneider, and A. Y. Ng. Policy search by dynamic programming. In Advances in Neural Information Processing Systems 16, pages 831--838, 2003
work page 2003
-
[2]
D. J. Foster, A. Krishnamurthy, D. Simchi-Levi, and Y. Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. In Proceedings of the 35th Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, page 3489, 2022. Full version: arXiv:2111.10919
arXiv 2022
-
[3]
Z. Jia, G. Li, A. Rakhlin, A. Sekhari, and N. Srebro. When is agnostic reinforcement learning statistically tractable? In Advances in Neural Information Processing Systems 36, 2023
work page 2023
-
[4]
Z. Jia, A. Rakhlin, A. Sekhari, and C.-Y. Wei. Offline reinforcement learning: Role of state aggregation and trajectory data. In Proceedings of the 37th Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 2644--2719, 2024
work page 2024
-
[5]
S. M. Kakade and J. Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the 19th International Conference on Machine Learning, pages 267--274, 2002
work page 2002
-
[6]
A. Krishnamurthy, G. Li, and A. Sekhari. The role of environment access in agnostic reinforcement learning. In Proceedings of the 38th Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 3405--3406, 2025. Full version: arXiv:2504.05405
arXiv 2025
-
[7]
A. Sekhari, C. Dann, M. Mohri, Y. Mansour, and K. Sridharan. Agnostic reinforcement learning with low-rank MDPs and rich observations. In Advances in Neural Information Processing Systems 34, 2021
work page 2021
- [8]
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.