{"id":"65ffc287-6c1a-4643-a7af-2d445038a2b6","arxiv_id":"2506.01884","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The minimax sample complexity of agnostic policy learning is governed by the spanning capacity of the policy class, and efficient online learning additionally requires a sunflower structural condition.","lead":"This thesis characterizes the sample complexity of finding the best policy in a given class when the optimal policy may not be in the class. It introduces a new 'spanning capacity' measure and proves strict separations between learning with a simulator, online RL, and other interaction protocols.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.1's proof contains a false equality used to bound POPLER's state count; Theorem 5.2 is not fully justified as written.","rationale":"The reader's strongest claim about spanning capacity characterizing the generative-model setting (Theorems 4.1 and 4.2) is not directly affected by this concern: those proofs do not rely on Lemma 2.1. I found no significant flaw in the unbiasedness argument for TrajectoryTree or in the lower-bound reduction to multi-armed bandits. However, the thesis also presents Theorem 5.2 as a central positive result for online RL, and its proof relies on Lemma 2.1 to bound the number of discovered petal states. The proof of Lemma 2.1 contains a concrete false equality, as shown by a simple two-policy, two-layer counterexample. Because the lemma itself is true and admits a short coupling proof, the correct disposition is to request a proof repair rather than reject the work. This is a good-faith, technical concern: it is not an attack on the authors, and it does not manufacture doubt about the generative-model minimax characterization. The proposed concrete test decisively settles whether the proof step lands, and the recommended verdict CONDITIONAL reflects that the manuscript's current written proof is incomplete for a load-bearing step of the online RL upper bound.","tokens_in":63898,"tokens_out":36418,"duration_ms":384897,"concrete_test":"Verify the disputed display for the counterexample above: compute ∑_{a1∈{0,1}} sup_{x2∈X2} ∑_{a2∈{0,1}} 1{∃π∈Π: π(x1)=a1, π(x2)=a2} = 2, while C_2(Π)=1, so the equality in Lemma 2.1's proof fails. Then check whether the corrected coupling argument — sup_π P[π visits (x,a)] ≤ P[some π visits (x,a)] and each realized deterministic MDP has at most C_h(Π) reachable pairs — restores the bound |T|≤O(D·C(Π)/ε). If the corrected proof goes through, the issue is a fixable proof gap rather than a false theorem.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 2.1 (spanning capacity equals worst-case coverability) is used in Section 5.3.1 to argue that the number of petal states discovered by POPLER is at most O(D·C(Π)/ε), an essential step in the Theorem 5.2 sample-complexity bound. The proof of Lemma 2.1 is invalid as written: after swapping suprema and sums, it claims ∑_{a1} sup_{x2} ∑_{a2} ... sup_{xh} ∑_{ah} 1{∃π: π⇝(x1:h,a1:h)} = C_h(Π). This equality is false. Example: X1={x1}, X2={x2}, A={0,1}, Π={π0,π1}, where π0(x1)=0, π0(x2)=0, π1(x1)=1, π1(x2)=0. The left side equals 2 (one for each a1) while C_2(Π)=1. The earlier inequality (iii) already overcounts by summing over a1 the same reachable (x2,a2) pair. The lemma is true and can be proved by coupling Γ_h with a random deterministic MDP and noting each realized tree has at most C_h(Π) reachable pairs; but the proof as presented does not establish it, so the |T| bound in Theorem 5.2 is unsupported unless the proof is repaired.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This PhD thesis studies agnostic PAC reinforcement learning, in which the learner is given a policy class Π and must return a policy that competes with the best policy in Π without assuming that Π contains an optimal policy. The main contributions are: a new structural complexity measure called spanning capacity C(Π); minimax sample-complexity bounds for the generative model and local simulator (Theorems 4.1 and 4.2); a lower bound showing that adapting to coverability is statistically intractable (Theorem 4.3); a lower bound for online RL showing that bounded spanning capacity alone is insufficient (Theorem 5.1); and a positive online RL result for policy classes satisfying a sunflower property, achieved by the POPLER algorithm (Theorem 5.2). Additional chapters treat imitation learning, µ-resets, and hybrid resets, with a new algorithmic tool called the policy emulator.","tokens_in":64168,"tokens_out":10119,"duration_ms":116807,"significance":"If the results hold, this thesis provides a substantial step toward a learning-theoretic account of agnostic RL with function approximation. It introduces clean, policy-class-only complexity measures, establishes minimax characterizations for simulator access, and demonstrates sharp separations between interaction protocols. Strengths include the detailed information-theoretic lower-bound constructions, the careful treatment of infinite policy classes via Natarajan dimension, and the explicit algorithmic tools (policy-specific MRPs, POPLER, PLHR). The manuscript is also honest about its open problems and its reliance on prior published work. The main reservation is that one foundational lemma used to support the online upper bound has an invalid proof as written; the lemma may be true and repairable, but the current text does not establish it.","major_comments":[{"comment":"The proof of Lemma 2.1 contains a false equality in the final \"derandomization\" step. After swapping suprema and sums, the proof claims that ∑_{a1} sup_{x2} ∑_{a2} ... sup_{xh} ∑_{ah} 1{∃π: π⇝(x_{1:h},a_{1:h})} equals C_h(Π). This is not correct, because the same state-action pair can be counted multiple times for different action prefixes. For example, take X1={x1}, X2={x2}, A={0,1}, and Π={π0,π1} with π0(x1)=π0(x2)=0 and π1(x1)=1, π1(x2)=0. The displayed expression equals 2, while C_2(Π)=1. This step is load-bearing: Section 5.3.1 uses Lemma 2.1 to argue that the number of petal states discovered by POPLER is at most O(D·C(Π)/ε), an essential ingredient in the Theorem 5.2 sample-complexity bound. The lemma may be true, and a coupling argument may repair it, but the proof as written does not establish it. Please replace the proof with a correct one or cite a correct proof.","section":"Section 2.4.2, Lemma 2.1"},{"comment":"The proof of Theorem 5.2 is presented as a deferred proof sketch, and the version of the manuscript does not make all steps verifiable. In particular, the bound on the number of reachable petal states, |T|≤O(D·C(Π)/ε), is stated in Section 5.3.1 as a consequence of Lemma 2.1; since the proof of Lemma 2.1 is currently invalid, this part of the argument is unsupported unless the lemma is repaired. Because Theorem 5.2 is the central positive result of Chapter 5, the deferred proof in Section 5.5.2 should be written out in full and checked carefully for the reachable-state counting step as well as for the bias-variance decomposition of the policy-specific MRP estimates.","section":"Sections 5.3.1 and 5.5.2, Theorem 5.2"}],"minor_comments":[{"comment":"The displayed formula in Question 5.1 is malformed: \"non(Π;ε,δ) ≲ 1/ε^{O(log C(Π)· log|Π|/δ}\" is missing a closing parenthesis and the intended dependence is not clear. Please correct the expression.","section":"Section 5.4"},{"comment":"The pseudodimension argument replacing log|Π| with the Natarajan dimension is only sketched. A short formal statement of the relevant shattering bound for trajectory trees would improve readability, though the steps are plausible.","section":"Section 4.2.1"},{"comment":"The row for \"Gen/Local Sim.\" writes \"≲ C, ≳ C\" without explicitly separating upper and lower bounds; this is understandable in context but could be clarified for readers.","section":"Table 1.1"}],"recommendation":"major_revision","confidential_remarks":"This is a thesis-style manuscript assembled from three prior papers. The synthesis is valuable, but the editor should ensure that the thesis version is not merely a reprint of those papers and that the new exposition stands on its own. The Lemma 2.1 proof issue is fixable and does not appear to undermine the qualitative claims, but it must be resolved before the paper can be recommended for acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take on arXiv:2506.01884. This is a PhD thesis that reorganizes three of the author's papers (NeurIPS 22, NeurIPS 23, COLT 25) into one treatment of agnostic policy learning. If you are looking for new theorems, there are none; Section 1.3 says so plainly. The value is in the synthesis: a clean taxonomy of interaction protocols, consistent notation, a unified treatment of spanning capacity, and a set of open problems that are genuinely useful for the subfield. The minimax results for generative/local simulator, the online RL separation, and the sunflower/POPLER result are already published, and the thesis does not change their status.\n\nWhat the thesis does well is the job of a thesis: the proofs in Chapters 3 and 4 are detailed and I did not find a substantive gap. The online chapter is honestly flagged as carrying a proof sketch with details deferred, which is the right call. The lower-bound constructions in Chapters 4 and 7 (rich-observation combination locks) read much more clearly here than in the underlying papers. That is real service to the community.\n\nThe main soft spot is Lemma 2.1. The stress-test note you passed along claimed a concrete false equality in its proof; I checked the example and the arithmetic does not work—C_2 for their construction is 2, not 1. So that particular counterexample should not go into a referee report. But the underlying worry survives: the proof replaces sums over stochastic transitions by a derandomized expression, and that expression looks like it counts reachable prefixes rather than distinct state-action pairs. For layered state spaces with merging, that could overcount unless a separate argument rules it out. I would not bet against the lemma—it comes from prior work and the statement is plausible—but the proof as written needs a line or two justifying the derandomization step, or a pointer to the original proof if it is correct there. Since the bound on |T| in Theorem 5.2 leans on this lemma, the self-contained status of the thesis depends on this being patched.\n\nWho is this for? Researchers who want a unified reference on agnostic policy learning and the landscape of interaction protocols. Specialists already know the results, but the thesis is a good entry point, and the open problems are worth having in one place. A serious referee should engage with it, mainly to verify the claims are faithful to the original papers and to check the deferred proofs in Chapter 5. My recommendation: treat it as a dissertation-style manuscript rather than a new-results submission, and ask for the Lemma 2.1 proof to be repaired before archival publication.","headline":"A clean, honest thesis-level synthesis of three strong papers on agnostic policy learning, with no new theorems but real value as a unified reference; the one proof I would ask to patch is Lemma 2.1, and the posted counterexample to it does not hold up.","tokens_in":64681,"tokens_out":7685,"would_cite":false,"duration_ms":87710,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","90C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This thesis characterizes agnostic policy learning by showing that a single structural quantity of the policy class—the spanning capacity—sets the minimax sample complexity for simulator access, while online reinforcement learning needs…","keywords":["agnostic policy learning","spanning capacity","sunflower property","minimax sample complexity","generative model RL","online reinforcement learning","coverability","policy eluder dimension"],"falsifier":"For the online lower bound, instantiate the constructed class at ε = $2^{{-√H}}$ and ℓ = √H and check whether any algorithm can succeed with $2^{{o(H)}}$ trajectories; if one can, the claimed $ε^{{-Ω(log C)}}$ lower bound is false.","tokens_in":63656,"feed_emoji":"🧭","tokens_out":5637,"duration_ms":63179,"temperature":0.7,"pith_summary":"The thesis asks when a learner can find the best policy inside a fixed policy class when the class is not guaranteed to contain the optimal policy, a minimal assumption called agnostic policy learning. It establishes that with a generative model or local simulator, the minimax sample complexity is exactly governed by the spanning capacity of the policy class, up to polynomial factors in horizon and class size. It then shows that spanning capacity alone does not suffice for online interactive learning: a constructed policy class with small spanning capacity still requires a superpolynomial number of trajectories. On the positive side, adding a structural condition called the sunflower property restores polynomial sample complexity through a new algorithm, POPLER. The overall message is that the interaction protocol decides whether representation complexity or exploration difficulty dominates.","feed_headline":"One number sets simulator RL cost; online RL is harder","feed_subtitle":"Spanning capacity exactly governs sample complexity with resets, but online exploration needs extra structure.","key_machinery":"The central object is the spanning capacity C(Π), defined as the maximum, over deterministic MDPs and layers, of the number of state-action pairs reached at that layer by some policy in Π; an equivalent lemma shows it equals worst-case coverability over all stochastic MDPs. The generative-model upper bound uses a modified TrajectoryTree algorithm that samples only Π-reachable state-action pairs, while the lower bound embeds a multi-armed bandit into the reachable set. For online RL, the new machinery is the sunflower property, which decomposes a policy class into a small core Πcore plus per-policy petal states, and the policy-specific Markov reward process, which collapses the MDP into a small tabular process per policy so that importance sampling can estimate all policies' values with controlled bias and variance.","core_discovery":"The central claim is that bounded spanning capacity—the largest number of state-action pairs reachable at any layer by any policy in the class, maximized over deterministic MDPs—is necessary and sufficient for agnostic PAC policy learning with generative model or local simulator access. The minimax sample complexity is Θ(C(Π)/ε² · log(1/δ)) up to H log|Π| factors. For online RL, this characterization fails: a lower bound constructs a policy class with C(Π) polynomial in the horizon yet requiring $ε^{{-Ω(log C(Π))}}$ samples, proving that spanning capacity is insufficient for online interaction. When the policy class additionally satisfies the (K,D)-sunflower property, a new algorithm called POPLER achieves poly(C(Π), K, D, 1/ε, log|Π|) sample complexity by evaluating all policies simultaneously through a policy-specific Markov reward process.","pith_inferences":["If the sunflower property turns out to be necessary as well as sufficient, then online agnostic policy learning algorithms should be designed by first searching over sunflower decompositions of the policy class.","The lower-bound constructions are Block MDPs with tiny latent state spaces, so the hardness is not an artifact of complex latent dynamics; it persists even when the environment has low intrinsic complexity.","A practical reading of the generative-versus-online separation is that when resets are unavailable, policy search methods should either explicitly memorize reachable states or switch to value- and model-based function approximation.","The sunflower frontier suggests a testable design principle: evaluate whether a policy class can be approximated by a small core plus a few exceptional states before committing to an exploration strategy."],"forward_implications":["With a simulator, learning a policy class needs only enough samples to cover the state-action pairs reachable by the class, not the entire state space.","Spanning capacity is the right minimax statistic for generative and local-simulator access, settling the sample complexity up to H log|Π| factors.","Online RL is strictly harder than simulator RL, and stochastic environments are strictly harder than deterministic ones for agnostic policy learning.","Policy classes with shared structure, such as singleton, ℓ-ton, and active policies, are efficiently learnable online because they satisfy the sunflower property with small parameters.","Adapting to good coverage is statistically intractable for policy learning even with generative access, in contrast to value-based methods."],"supporting_citations":[{"why":"Supplies the TrajectoryTree algorithm and the unbiased trajectory-tree sampling used in the generative-model upper bound.","marker":"[KMN99]"},{"why":"Supplies the K-armed bandit PAC lower bound that the spanning-capacity lower bound reduces to.","marker":"[MT04]"},{"why":"Defines coverability and shows value-based methods can adapt to it, serving as the benchmark for the negative adaptation result.","marker":"[XFBJK22]"},{"why":"Provides a value-based local-simulator algorithm with poly(Ccov) sample complexity, the contrast that makes the policy-learning lower bound striking.","marker":"[MFR24]"},{"why":"Introduces rich-observation combination locks used in the exponential lower-bound constructions.","marker":"[SDMMS21]"},{"why":"Introduces spanning capacity as worst-case coverability and establishes the equivalence in Lemma 2.1.","marker":"[JLRSS23]"},{"why":"Gives the linear-policy lower bound that the spanning-capacity results recover, positioning the new bounds relative to prior hardness.","marker":"[DKWY19]"},{"why":"Supplies the stopping-time lemma used in the online lower bound argument.","marker":"[GMS19]"}],"fun_headline_variants":["Spanning capacity exactly sets simulator RL sample cost","Generative RL complexity pinned; online RL needs more","Agnostic RL sample complexity: C(Pi) suffices with resets","Online RL breaks simple coverage law","New sunflower trick tames online agnostic RL"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the positive online result, everything rests on the policy class admitting a small sunflower decomposition—a small core of policies plus a few exceptional states per policy—and no polynomial guarantee is known when that decomposition is exponential.","fun_headline_variants_meta":{"raw":{"variants":["Spanning capacity exactly sets simulator RL sample cost","Generative RL complexity pinned; online RL needs more","Agnostic RL sample complexity: C(Pi) suffices with resets","Online RL breaks simple coverage law","New sunflower trick tames online agnostic RL"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000233,"raw_usage":{"total_tokens":1489,"prompt_tokens":936,"completion_tokens":553,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":552,"completion_tokens_details":{"reasoning_tokens":476}},"tokens_in":552,"tokens_out":553,"duration_ms":6114,"temperature":1.0,"reasoning_tokens":476,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:31:35.935284+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the online lower bound, instantiate the constructed class at ε = $2^{{-√H}}$ and ℓ = √H and check whether any algorithm can succeed with $2^{{o(H)}}$ trajectories; if one can, the claimed $ε^{{-Ω(log C)}}$ lower bound is false.","supporting_citations":[],"review_version":1}