{"id":"5185047a-43e0-46f3-bb36-b4f07f31d153","arxiv_id":"2608.07772","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under mu-resets and policy realizability, sample complexity is exp(Theta(H)) under all-policy concentrability and exp(Theta(sqrt H)) under pushforward concentrability.","lead":"This paper characterizes how many trajectories are needed to learn a near-optimal policy when the learner can reset to an exploratory state distribution. It shows the horizon dependence is exponential under one coverage condition, and exactly exponential in the square root of the horizon under another.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Both lower-bound theorems depend on an omitted fresh-observation argument; until the random-decoder coupling is proven, the exp(Omega(H)) and exp(Omega(sqrt H)) lower bounds are not established.","rationale":"The paper's upper bound (Theorem 2) is a genuine contribution: BlockPSDP with blockwise importance sampling and error propagation across block boundaries is concrete, and the proof of Lemma 1 checks out under pushforward concentrability. The central risk is entirely in the two lower-bound constructions. Both are presented as sketches, and both rely on the same unproven premise: a large random decoder makes transition observations statistically uninformative. This is not a formality that can be assumed; in the proposed constructions the reset distribution is not an arbitrary uninformative distribution but one that places known weights on latent states whose identities are hidden only by the decoder. A learner who could detect, from the distribution of next observations, which preimage a reset state came from would obtain direct information about theta without needing the reward gaps. The omitted analysis must rule this out uniformly for n=2^{o(H)} (Theorem 1) and n=2^{o(sqrt H)} (Theorem 3). Additionally, the value claim in Section 4 is false as written: policies matching block 1 but not the rest of theta achieve value p_1, so the statement 'V^{pi_vartheta}=0 for every vartheta != theta' cannot be correct. The lower-bound magnitude survives because matching block 1 is itself a needle-in-haystack requiring 2^{Omega(L)} samples from the initial distribution, but the proof sketch should be corrected. Overall, the characterization is plausible and the upper bound is solid, but the central claim is conditional on supplying the missing information-theoretic arguments. The reader's CONDITIONAL verdict is appropriate; no change.","tokens_in":8724,"tokens_out":28239,"duration_ms":277845,"concrete_test":"Write out the omitted information-theoretic lemma for the Theorem 3 construction: prove that for n=2^{o(sqrt H)} trajectories, after randomizing the decoder phi, the distribution of all reset and transition observations is within o(1) total variation of a distribution independent of theta; equivalently, construct a coupling that re-labels every observed state without reference to theta. If no such argument can be given for resets at intermediate layers, the exp(Omega(sqrt H)) lower bound is unsupported. As a sanity check, recompute V^{pi_vartheta} for a policy vartheta that matches theta on block 1 but differs on block 2; it is p_1, not 0.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Both Theorem 1 and Theorem 3 hinge on the claim that, with a random decoder, every observed state is fresh, so transition data carries no information about the hidden key and the learner can only use rewards. Sections 2 and 4 explicitly defer this: 'We omit the formal information-theoretic arguments.' This is load-bearing because the reset distributions put mass on states whose transition statistics depend on the key. In Theorem 3, for a reset at layer h in block k, the distribution of the next observation under action 0 versus action 1 is a different mixture over preimages of sizes m, 2m, and 4m; if that difference is statistically visible with 2^{o(sqrt H)} samples, the learner could infer theta from transitions and the lower bound collapses. The needed lemma is a coupling showing the full observation process is within o(1) total variation of a theta-independent process. A separate internal error: Section 4 claims V^{pi_theta}=1/4 and V^{pi_vartheta}=0 for every vartheta != theta, but any vartheta matching theta on block 1 reaches Collect(p_1) and has value p_1=1/4. This does not change the 2^{Omega(sqrt H)} magnitude, since finding block 1 is already a needle-in-haystack, but the written proof needs correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8937,"tokens_out":22030,"duration_ms":216160,"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":[{"comment":"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":"Sections 2 and 4"},{"comment":"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.","section":"Section 3, Lemma 1"}],"minor_comments":[{"comment":"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).","section":"Section 4"},{"comment":"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":"Theorems 1 and 3"},{"comment":"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":"Section 3, Eq. (1)"},{"comment":"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.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"This is a promising theory paper, but in its current form the two lower-bound theorems are not fully proved: the crucial fresh-observation argument is explicitly omitted, and the upper bound relies on a pointwise optimality assumption that is not stated in Theorem 2. I recommend asking the authors to supply complete proofs or detailed reductions for the lower bounds and to clarify the assumptions in Theorem 2 before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one. The upper bound is the real contribution; the lower bounds are sketches with a load-bearing hole.\n\nThe genuinely new thing is BlockPSDP, a blockwise PSDP variant that importance-samples L consecutive layers at once and pays error amplification only across block boundaries. The proof of Theorem 2 is complete and careful, and the exp(Theta(sqrt H)) upper bound under pushforward concentrability is a real advance over the exp(Theta(H)) of PSDP. That part is solid.\n\nThe lower-bound constructions are clever—the all-policy one uses a standard rich-observation combination lock, and the pushforward one adds recursive decoy locks. But both Theorems 1 and 3 depend on an assertion that is not proved: with a random decoder, every observed state is fresh, so transitions leak no information about the hidden key. That is a coupling or total-variation argument, and it is not obvious. In the Theorem 3 construction, a reset at layer h in block k gives, under action 0 versus action 1, different mixtures over preimages of sizes m, 2m, and 4m. If that difference is statistically visible with 2^{o(sqrt H)} samples, the learner could infer theta from transitions. The paper says \"we omit the formal information-theoretic arguments\"—that is exactly the missing piece. As written, the lower bounds are not established.\n\nThere is also a concrete error in Section 4. The text claims V^{pi_vartheta}=0 for every vartheta != theta, but any vartheta that matches theta on block 1 reaches Collect(p_1) and gets value p_1 = 1/4. The intended lower-bound magnitude may survive because finding block 1 is already exponentially hard, but the written claim is false and the proof needs repair.\n\nThe AI-use statement is unusual (\"Results were obtained via GPT 5.6 Pro\"). Given the omitted lower-bound proofs, you would want author clarification about which parts were machine-generated and whether the information-theoretic claims were independently checked.\n\nIf the omitted arguments are supplied and the Section 4 bug fixed, this would be a significant paper. Right now it is a strong upper bound plus two plausible but unproven lower bounds. That deserves a serious referee, not a desk reject, but the verdict should be conditional on major revision.","headline":"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.","tokens_in":9474,"tokens_out":6208,"would_cite":false,"duration_ms":58529,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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)).","keywords":["reinforcement learning","mu-resets","policy realizability","sample complexity","concentrability","rich-observation combination locks","policy search by dynamic programming","BlockPSDP"],"falsifier":"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.","tokens_in":8479,"feed_emoji":"🎲","tokens_out":6707,"duration_ms":54837,"temperature":0.7,"pith_summary":"The paper resolves the open question of whether policy realizability makes the μ-resets protocol of Kakade and Langford sample-efficient. It establishes that the answer depends on which concentrability assumption is placed on the reset distribution: with bounded all-policy concentrability, any proper deterministic algorithm still needs exp(Ω(H)) trajectories, so realizability alone buys nothing; with bounded pushforward concentrability, the horizon dependence is tightly characterized as exp(Θ(√H)). The upper bound is achieved by BlockPSDP, a blockwise variant of PSDP that importance-samples trajectories within blocks and only pays error amplification across block boundaries. If the results are right, they give the first information-theoretic characterization of this setting and show that PSDP, which requires exp(Θ(H)) samples, is suboptimal.","feed_headline":"Even with realizable policies, mu-resets need exp(H) samples","feed_subtitle":"Pushforward concentrability is the exception: it tightens the horizon dependence to exp(Θ(√H)) and beats PSDP.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the μ-resets interaction protocol and the Conservative Policy Iteration algorithm that this paper builds on.","marker":"[KL02]"},{"why":"Raises the open question of policy realizability under μ-resets and supplies the agnostic exp(Ω(H)) lower bound and the PSDP analysis that these results extend and strengthen.","marker":"[KLS25]"},{"why":"Supplies the rich-observation combination lock construction with a large random decoder class used in both lower bounds.","marker":"[SDM+21]"},{"why":"Provides the importance-sampling concentration inequality for trajectory rewards used in the BlockPSDP upper-bound analysis.","marker":"[JLR+23]"},{"why":"Defines PSDP, the algorithm whose per-layer error amplification motivates the blockwise variant BlockPSDP.","marker":"[BKSN03]"}],"fun_headline_variants":["Coverage type decides mu-reset sample complexity: exp(H) vs exp(√H)","Pushforward concentrability reduces mu-reset samples to exp(√H)","Realizable mu-resets: exp(H) for all-policy, exp(√H) for pushforward","mu-reset policy learning: coverage assumption changes horizon exponent","All-policy coverage forces exp(H) mu-reset samples; pushforward only exp(√H)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Coverage type decides mu-reset sample complexity: exp(H) vs exp(√H)","Pushforward concentrability reduces mu-reset samples to exp(√H)","Realizable mu-resets: exp(H) for all-policy, exp(√H) for pushforward","mu-reset policy learning: coverage assumption changes horizon exponent","All-policy coverage forces exp(H) mu-reset samples; pushforward only exp(√H)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001023,"raw_usage":{"total_tokens":4298,"prompt_tokens":909,"completion_tokens":3389,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":525,"completion_tokens_details":{"reasoning_tokens":3278}},"tokens_in":525,"tokens_out":3389,"duration_ms":23061,"temperature":1.0,"reasoning_tokens":3278,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T00:19:21.352213+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}