Agnostic Reinforcement Learning: Foundations and Algorithms

Gene Li

REVIEW 2 major objections 3 minor 2 references

Agnostic Reinforcement Learning: Foundations and Algorithms

T0 review · 2 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2506.01884 v1 pith:GJSI57FH submitted 2025-06-02 cs.LG cs.AIstat.ML

Gene Li This is my paper

classification cs.LGcs.AIstat.ML MSC 68Q3290C40

keywords agnosticpolicylearningspanningcapacitysunflowerpropertyminimaxsamplecomplexitygenerativemodelRLonlinereinforcementcoverabilityeluderdimension

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What 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.

The 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.

Who 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.

Referee Report

2 major / 3 minor

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.

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 (2)

[Section 2.4.2, Lemma 2.1] 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.
[Sections 5.3.1 and 5.5.2, Theorem 5.2] 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.

minor comments (3)

[Section 5.4] 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 4.2.1] 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.
[Table 1.1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: complexity measures are structural, and the sample-complexity bounds are proven theorems rather than fitted inputs disguised as predictions.

full rationale

The thesis does not exhibit circularity. The central complexity measure, spanning capacity (Definition 2.4), is a purely structural parameter of the policy class, and Theorem 4.1 proves an upper bound by constructing unbiased trajectory-tree estimates whose per-tree query count is bounded by H·C(Π) directly from the definition of C(Π). Theorem 4.2 gives a matching lower bound by embedding a C(Π)-armed bandit into a deterministic MDP witnessing C(Π); neither direction fits a parameter to a subset of data and then 'predicts' a closely related quantity. The sunflower property (Definition 5.3) is introduced as a representational assumption, and Theorem 5.2's POPLER analysis proves the sample-complexity bound rather than assuming it. The disclosed reliance on the author's prior publications in Section 1.3 is not load-bearing in a circular sense: the load-bearing results, such as the spanning-capacity/worst-case-coverability equivalence in Lemma 2.1 and the block-free matrix construction in Lemma 5.1, are proven within the thesis or in externally checkable papers, so the derivation does not reduce to an unverified self-citation. The skeptical observation that the proof of Lemma 2.1 contains a suspect equality after swapping suprema and sums is a correctness risk in the written proof, not a circularity; a repaired proof would still use a C(Π) defined independently of the theorem being proved. No pattern from self-definitional, fitted-input-called-prediction, self-citation-load-bearing, imported uniqueness, ansatz-via-citation, or renaming-known-result applies, so the central claims have independent content.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

No free parameters are fitted to data; all bounds are with respect to structural complexity measures. The axioms are standard modeling choices plus the newly introduced sunflower assumption. The invented entities are algorithmic tools, not physical postulates.

assumptions (5)

domain assumption Finite-horizon MDP with layered state space and rewards normalized to sum at most 1.
Standard model in RL theory, stated in Section 2.1.
domain assumption The learner is given the policy class Π and, in algorithms, the sunflower decomposition (Π_core, {X_π}).
Algorithms POPLER and TrajectoryTree rely on knowing Π and its structure; this is a modeling assumption about access.
ad hoc to paper The policy class admits a (K,D)-sunflower decomposition for the online RL upper bound.
Definition 5.3 imposes a structural condition on Π that is not universal; this assumption is necessary for Theorem 5.2.
domain assumption In lower bounds, the learner has no decoder/emission class Φ containing the true decoder (no decoder realizability).
The Block MDP constructions in Theorems 4.3 and 7.5 assume the decoder is unknown and unlearnable; this models the agnostic setting.
standard math Standard concentration inequalities and information-theoretic lower-bound tools (Hoeffding, Chernoff, Le Cam) are valid.
Used throughout proofs; assumed background.

invented entities (2)

Policy-specific Markov Reward Process (MRP)
purpose: Compresses the original MDP into a small MRP for each policy to enable simultaneous policy evaluation via importance sampling.
Introduced in Section 5.3.1 as a technical tool in POPLER; it is a mathematical construction, not a falsifiable physical entity.
Policy emulator
purpose: Used in Chapter 8 to model the behavior of a policy in a Block MDP for the PLHR algorithm.
Introduced in Definition 8.1 as a technical concept; no independent empirical prediction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Agnostic Reinforcement Learning: Foundations and Algorithms." pith.science (2026). https://pith.science/paper/GJSI57FH

@misc{pith2026250601884,
  author       = {Pith},
  title        = {Pith review of: Agnostic Reinforcement Learning: Foundations and Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GJSI57FH}},
  note         = {Machine review of arXiv:2506.01884}
}

abstract

Reinforcement Learning (RL) has demonstrated tremendous empirical success across numerous challenging domains. However, we lack a strong theoretical understanding of the statistical complexity of RL in environments with large state spaces, where function approximation is required for sample-efficient learning. This thesis addresses this gap by rigorously examining the statistical complexity of RL with function approximation from a learning theoretic perspective. Departing from a long history of prior work, we consider the weakest form of function approximation, called agnostic policy learning, in which the learner seeks to find the best policy in a given class $\Pi$, with no guarantee that $\Pi$ contains an optimal policy for the underlying task. We systematically explore agnostic policy learning along three key axes: environment access -- how a learner collects data from the environment; coverage conditions -- intrinsic properties of the underlying MDP measuring the expansiveness of state-occupancy measures for policies in the class $\Pi$, and representational conditions -- structural assumptions on the class $\Pi$ itself. Within this comprehensive framework, we (1) design new learning algorithms with theoretical guarantees and (2) characterize fundamental performance bounds of any algorithm. Our results reveal significant statistical separations that highlight the power and limitations of agnostic policy learning.

Figures

Figures reproduced from arXiv: 2506.01884 by the authors.

**Figure 2.1.** Relationships between interaction protocols. An arrow A → B implies that protocol B can be simulated with protocol A. Before we can begin to discuss the statistical complexity of RL, we first need to formalize what a “sample” is, and how it is collected. In the standard PAC learning framework for supervised learning, each sample is assumed to be i.i.d. drawn from some underlying distribution D. However, the MDP … view at source ↗

**Figure 3.** [PITH_FULL_IMAGE:figures/full_fig_p031_3.png] view at source ↗

Figures from the paper (19 more)

**Figure 3.1.** Figure 3.1: Illustration of witnessing sequences of length [PITH_FULL_IMAGE:figures/full_fig_p032_3_1.png]

**Figure 3.** Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p033_3.png]

**Figure 3.2.** Figure 3.2: An example illustrating the connection between the upper bound and Ramsey [PITH_FULL_IMAGE:figures/full_fig_p034_3_2.png]

**Figure 4.1.** Figure 4.1: Construction used for proof of Theorem 4.3 [PITH_FULL_IMAGE:figures/full_fig_p049_4_1.png]

**Figure 4.** Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p050_4.png]

**Figure 5.** Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p065_5.png]

**Figure 5.1.** Figure 5.1: Illustration of the lower bound from Theorem 5.1. Blue arrows represent taking the action π ⋆ (x), while red arrows represent taking the action 1−π ⋆ (x). Purple arrows denote uniform transition to the states in the next layer, regardless of action. The MDP Mπ⋆,ϕ is …

**Figure 5.** Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p075_5.png]

**Figure 5.** Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p091_5.png]

**Figure 5.2.** Figure 5.2: Illustration of an MRP Mπ Xrch with Xπ = {x1, x2, x3} and X rch = {x1, x2}. In the original MDP M, x1 ∈ X1, x2 ∈ X3, and x3 ∈ X2. The edges are labeled with the values of P π x→x′ and Rπ x→x′. Notice that (1) there are no edges from x2 → x3 or x3 → x2 because traject…

**Figure 7.** Figure 7 [PITH_FULL_IMAGE:figures/full_fig_p114_7.png]

**Figure 7.1.** Figure 7.1: Lower bound for PSDP without policy completeness. Red arrows represent action 0 and blue arrows represent action 1. In purple we denote the expectation of the stochastic reward. Let γ > 0 be an arbitrarily small constant. At layer h = 2, with constant probability, PS…

**Figure 7.** Figure 7 [PITH_FULL_IMAGE:figures/full_fig_p119_7.png]

**Figure 7.2.** Figure 7.2: Lower bound construction for Theorem 7.4. To avoid clutter, we do not illustrate the highway states as well as any boring states which are only reachable by taking highway actions ai at layer 0, since their role is only to make sure that the construction satisfies ad…

**Figure 7.3.** Figure 7.3: Construction used for Theorem 7.5. Key Ideas for Theorem 7.5. An example can be found in [PITH_FULL_IMAGE:figures/full_fig_p123_7_3.png]

**Figure 8.1.** Figure 8.1: Illustration of how certifying accuracy of test policies prevents error amplification. [PITH_FULL_IMAGE:figures/full_fig_p145_8_1.png]

**Figure 8.** Figure 8 [PITH_FULL_IMAGE:figures/full_fig_p145_8.png]

**Figure 8.** Figure 8 [PITH_FULL_IMAGE:figures/full_fig_p150_8.png]

**Figure 8.2.** Figure 8.2: Confidence set construction example with [PITH_FULL_IMAGE:figures/full_fig_p151_8_2.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

2 extracted references · 2 linked inside Pith

[1]

Apprenticeship learning via inverse re- inforcement learning.International Conference on Machine learning, 2004 (cited on page 102)

[AN04] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse re- inforcement learning.International Conference on Machine learning, 2004 (cited on page 102). [AHKS20] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pc-pg: policy cover directed exploration for provable policy gradient learning.Advances in Neural Information Processing ...

arXiv 2004
[101]

Math, 1951 (cited on page 76)

Colloq. Math, 1951 (cited on page 76). [ZCHCLC23] Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D Lee, and Yuejie Chi. Policy mirror descent for regularized reinforcement learning: a gen- eralized framework with linear convergence.SIAM Journal on Optimization, 2023 (cited on page 131). 193 BIBLIOGRAPHY [ZHHJL22] Wenhao Zhan, Baihe Huang, Audrey...

arXiv 1951

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Apprenticeship learning via inverse re- inforcement learning.International Conference on Machine learning, 2004 (cited on page 102)

[AN04] Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse re- inforcement learning.International Conference on Machine learning, 2004 (cited on page 102). [AHKS20] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pc-pg: policy cover directed exploration for provable policy gradient learning.Advances in Neural Information Processing ...

arXiv 2004

[2] [101]

Math, 1951 (cited on page 76)

Colloq. Math, 1951 (cited on page 76). [ZCHCLC23] Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D Lee, and Yuejie Chi. Policy mirror descent for regularized reinforcement learning: a gen- eralized framework with linear convergence.SIAM Journal on Optimization, 2023 (cited on page 131). 193 BIBLIOGRAPHY [ZHHJL22] Wenhao Zhan, Baihe Huang, Audrey...

arXiv 1951