Pith. sign in

REVIEW 3 major objections 5 minor 60 references

Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Agnostic reinforcement learning can be sample-efficient under a single gradient-dominance condition, not just completeness and coverage.

desk verdict Good framework, but Theorem 5 has an inverted step-size dependence that the SDPO/PMD guarantees inherit, so the main results are not proved as written. read the letter →

arxiv 2507.04406 v1 pith:QPNGJ2EI submitted 2025-07-06 cs.LG math.OCstat.ML

Uri Sherman , Tomer Koren , Yishay Mansour This is my paper · ORCID
classification cs.LGmath.OCstat.ML MSC 68Q3290C2590C40
keywords agnosticreinforcementlearningvariationalgradientdominancesamplecomplexitypolicyoptimizationconservativeiterationmirrordescentconstrainednon-EuclideanFrank-Wolfe
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 paper tries to establish that agnostic policy learning—finding a policy competitive with the best in a given class, without assuming the class contains the optimal policy—is sample-efficient under a single structural condition called variational gradient dominance (VGD). If true, this would replace the much stronger completeness and coverage assumptions that have dominated RL theory, and would justify the practical success of first-order policy optimization methods in agnostic settings. The paper proposes a reduction of agnostic RL to constrained non-Euclidean (non-convex) first-order optimization, and uses it to derive sample complexity upper bounds for a new algorithm (SDPO), an improved analysis of CPI, and a parameterization-independent guarantee for PMD. It also provides an empirical evaluation of the VGD condition in several benchmark environments, suggesting the parameters remain moderate in practice.

What carries the argument

The variational gradient dominance (VGD) condition (Definition 1, Eq. (5)) is the central object: for every π ∈ Π, the suboptimality V(π) − min_{Π} V is bounded by ν times the maximum in-class improvement ⟨∇V(π), π − π̃⟩ plus an error floor ε_vgd. This condition is strictly weaker than completeness plus coverage (Lemma 1), yet it directly bounds the progress of first-order methods in policy space. The argument is carried by the reduction to constrained non-Euclidean optimization: (i) the value function is locally β-smooth with respect to local norms of the form ‖·‖_{L2(μ_k),·} (or globally smooth w.r.t. ‖·‖_{∞,1} for CPI), with β depending only on H, A and ε_ex, not on |S|; (ii) the policy gradient theorem (Lemma 7) makes each algorithm's update an approximate gradient step on the value function; and (iii) a concentration argument (Lemma 15) bounds the generalization error in terms of the log-covering number of Π. The constrained steepest descent analysis introduces the notion of potential gradient mappings G_x and steepest descent magnitude δ_x (Eqs. (15)–(16)) to handle non-Euclidean constraints, and the Frank-Wolfe analysis replaces convexity in the standard proof with the VGD inequality, yielding improved rates for CPI.

What would settle it

Run a first-order policy optimization algorithm (e.g., SDPO or PMD) on a task where the policy class Π is known to be agnostic (the optimal policy is provably outside Π), and measure V(π_k) − V⋆(Π) for iterates while checking the VGD inequality pointwise. If there exists any iterate where suboptimality is large but the maximum in-class gradient improvement is zero, VGD is violated and the bounds cannot apply; iterating this over many random seeds and comparing against the paper's claimed $n^{{-2/15}}$ sample rates would settle the practical reach of the condition.

Watch

Extended reading notes

Core claim

The central claim is that, for a convex policy class Π satisfying a (ν, ε_vgd)-variational gradient dominance condition, three policy learning algorithms achieve sample complexity upper bounds that scale with the log-covering number of Π and are independent of the state-space size. Specifically: (i) Steepest Descent Policy Optimization (SDPO), derived from a constrained steepest descent method for non-convex, non-Euclidean optimization, attains an O(ν²AH⁴/$K^{{2/3}}$ + νH³√A $K^{{1/6}}$√ε + ε_vgd) suboptimality after K iterations; (ii) Conservative Policy Iteration (CPI), reinterpreted as Frank-Wolfe, attains O((2ν²+1)H³/K + 2νε + ε_vgd) with step sizes η_k = 2ν/(k+2)—a strict improvement over the classical O(1/√K) for CPI; and (iii) Policy Mirror Descent (PMD) with an L2 regularizer attains O($ν²A^{{3/2}}$H³/$K^{{2/3}}$ + (ν + H²A $K^{{1/6}}$)$ε^{{1/4}}$) and, for the first time, has a sample complexity bound independent of the policy class parametrization. The reduction, which is independent of parametrization, casts policy learning as minimizing a value function that is locally smooth with respect to norms induced by on-policy occupancy measures, and uses the policy gradient theorem plus an importance-sampling estimator to turn each update into an approximate gradient step on the value function.

Load-bearing premise

The whole result rests on the assumption that every policy in the class Π satisfies the variational gradient dominance inequality with a small and attainable ν and a small error floor ε_vgd; if VGD fails for even one policy in Π, none of the sample complexity bounds hold.

Editorial extensions

If this is right

  • If the VGD-based bounds are correct, agnostic policy learning is sample-efficient (log-covering, state-space-independent) under a weaker and more measurable condition than completeness and coverage, widening the set of provably tractable RL problems.
  • The improved CPI rate O(1/K) with step sizes 2ν/(k+2) would replace the classical O(1/√K) guarantee, suggesting that even the classical CPI algorithm is more efficient than previously known whenever VGD holds.
  • The SDPO and DA-CPI analyses introduce the first convergence guarantees for a constrained non-Euclidean steepest descent method and for a doubly-approximate Frank-Wolfe variant, which may transfer to other non-convex constrained optimization problems.
  • The sample complexity bounds for PMD, independent of the policy-class parameterization, provide the first such guarantee and open the door to practical parametrization-free analyses of mirror-descent policy optimization.

Reading between the lines

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

  • The paper's own experiments estimate ν only along the algorithm's trajectory and measure suboptimality relative to the algorithm's best-found value, not the true in-class optimum; this leaves open whether VGD holds globally in the tested environments. A testable extension would measure VGD on random or adversarial policies outside the trajectory, not just iterates.
  • The error floor ε_vgd, which is proportional to ν times the completeness error under coverage reductions, may in practice be as hard to verify as completeness itself; careful readers should separate the iteration-complexity improvement (which is robust) from the agnostic-tractability claim (which inherits the difficulty of certifying ε_vgd).
  • Because the reduction is parametrization-free, the same framework may apply to other first-order methods (e.g., NPG, trust-region methods) under VGD, and may be extended to function approximation with general policy classes, but such extensions are not established in this paper and would require new analyses of local smoothness and concentration.
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.

Referee Report

3 major / 5 minor

Summary. The paper studies agnostic policy learning under a variational gradient dominance (VGD) condition. It proposes a reduction of agnostic RL to constrained non-Euclidean first-order optimization and claims iteration and sample-complexity bounds for Steepest Descent Policy Optimization (SDPO), Conservative Policy Iteration (CPI), a doubly approximate variant (DA-CPI), and Policy Mirror Descent (PMD), with rates that scale with the log-covering number rather than the state-space size. It also reports proof-of-concept experiments estimating VGD parameters in Cartpole, Acrobot, and two MinAtar environments. The central optimization theorem (Theorem 5) contains a false inequality in its Case 1, and the subsequent SDPO proof has algebraic inconsistencies with the stated theorem; because the sample-complexity theorems are derived from these results, the paper's main guarantees are not established as written.

Significance. If the claimed bounds were correct, the paper would be a substantial contribution: it would place agnostic policy learning under a condition strictly weaker than completeness and coverage, unify several algorithms under one optimization framework, and improve on the recent PMD analysis of Sherman et al. (2025) by replacing a fourth-root error dependence with a square-root dependence. The paper also has the virtue of making the VGD condition explicit and attempting to measure it empirically, and it is honest about the actor-oracle-efficiency limitations of CPI. However, the central proof error is load-bearing: the optimization theorem's error floor has the step-size dependence inverted, and the SDPO/PMD sample-complexity results inherit this error. As a result, the advertised rates are unsupported as written, and the experimental section does not validate the global VGD assumption.

major comments (3)
  1. [Appendix C.1, proof of Theorem 5, Case 1] The display 'E_{K+1} ≤ sqrt(2ε/ω0) + ε ≤ 4νMD√η√ε' is false. Since ω0 := η(2νMD)^{-2}, direct substitution gives sqrt(2ε/ω0) = 2√2 νMD sqrt(ε/η), placing η in the denominator rather than the numerator. The additive ε term is also not bounded by 4νMD√η√ε for the small step sizes η ≤ 1/β allowed by the theorem. This invalidates the stated error floor of Theorem 5. The SDPO proof in Appendix D.2 invokes exactly the incorrect √η√ε term to obtain the K^{1/6}√ε term of Theorem 1, so the error propagates to the paper's main sample-complexity guarantee.
  2. [Appendix D.2, proof of Theorem 1] After substituting η = √εex/(2H³√A) and εex = H²/K^{2/3}, the proof concludes V(π_{K+1}) − V⋆(Π) ≲ ν²AH⁶/K^{2/3} + νH⁵√A K^{1/6}√ε + ε_vgd, whereas Theorem 1 states O(ν²AH⁴/K^{2/3} + νH³√A K^{1/6}√ε). The intermediate term νH⁵A^{1/4}/εex^{1/4}√ε does not follow from νH²√η√ε with the stated η; the H and A powers in the derivation are inconsistent with the theorem statement. Since Theorem 11 derives the sample-complexity upper bound directly from Theorem 1, these mismatches mean the sample-complexity claims are unsupported as written.
  3. [Section 5 and Appendix F] The experiments estimate ν by the ratio (V(πk) − V_best) / max_{π∈Π}⟨∇V(πk), πk − π⟩, using the algorithm's best found value as V_best and, for the MinAtar environments, explicitly allowing V_best ≠ V⋆(Π). This measures only a trajectory-dependent effective parameter, not the global (ν, ε_vgd)-VGD condition of Definition 1. The plots therefore do not substantiate the claim that VGD holds globally in these environments; they only show that the ratio stays moderate along the executed path.
minor comments (5)
  1. [Equation (3)] Equation (3) writes V⋆(Π) := arg min_{π⋆∈Π} V(π⋆) and similarly for V⋆; these should be min, not arg min.
  2. [Theorem 2] The stated constant 8(2ν² + 1)H³/K differs from the proof's (16ν² + 1)H³/K; the constants should be reconciled.
  3. [Lemma 4] The statement 'δx(u) = 1/2⟨∇f(x),u⟩² ⟨∇f(x),u⟩ u ∈ Gx' is garbled; the two cases need to be written with proper punctuation and explicit conditions.
  4. [Lemma 21 and Appendix E] The notation 'Net(εnet, Π)' and the abbreviation 'R V' appear to be artifacts or undefined notation; all such terms should be defined at first use.
  5. [Theorem 11] The lower bound on εnet is stated as Ω(1/(log(n/δ)n)) in the theorem statement but as Ω(1/(log(n/δ)n^{2/5})) in the proof; one of these is a typo and should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: VGD is a stated assumption and the theoretical bounds are derived, not fitted or renamed inputs.

full rationale

The derivation chain is self-contained with respect to the paper's target claims. The (nu, eps_vgd)-VGD condition (Definition 1, Eq. 5) is an explicitly stated assumption, not an output of the analysis, and no parameter is fitted in the theory: Theorem 1, Theorem 2, Theorem 3, and Theorem 4 each verify Assumption 1 (smoothness, Lipschitzness, VGD, diameter) and then invoke the corresponding optimization theorem from Appendix C. The sample-complexity results (Theorems 11-14) translate iteration bounds into sample bounds through a concentration lemma (Lemma 15) whose proof uses standard sub-exponential Bernstein arguments, not by construction of the answer. The paper does rely on several lemmas from the authors' prior work (Sherman et al. 2025), including local smoothness (Lemma 8), the VGD behavior of exploratory policy classes (Lemma 9), and the Bregman proximal-point convergence theorem (Theorem 9). These are imported optimization results with stated assumptions that do not include the target suboptimality or sample-complexity bounds, so they constitute independent support rather than a self-citation chain that forces the conclusions. The experimental section estimates nu via the defining ratio (Eq. 9) and explicitly notes the estimator is an overestimate and that local optima imply an execution-specific eps_vgd = V_best - V^*(Pi); this is an empirical sanity check and is not used as an input to any theoretical guarantee, so it is not circular. The skeptical reviewer's algebraic concern about the step-size dependence in Theorem 5's error floor is a potential correctness issue, not a circularity issue, and is outside the scope of this circularity pass.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The theory introduces no fitted constants and no new physical or conceptual entities. Its weight is carried by the VGD assumption, by imported lemmas from the authors' prior work, and by convexity and oracle assumptions. Step sizes and exploration parameters are explicitly scheduled by the theorems rather than fitted to data.

assumptions (8)
  • standard math Policy gradient theorem (Sutton et al. 1999)
    Used in Section 3 and Lemma 7 to express gradients of V in terms of occupancy measures and Q-functions.
  • standard math Value difference lemma (Kakade and Langford 2002)
    Used in Lemmas 6 and 13 to relate value differences to expected advantage.
  • domain assumption Local smoothness of the value function under eps_ex exploration (Sherman et al. 2025, Lemma 8)
    Imported as a black box; it supplies the non-Euclidean smoothness constant needed for SDPO, DA-CPI, and PMD.
  • domain assumption Exploratory policy class preserves VGD with inflated eps_vgd (Sherman et al. 2025, Lemma 9)
    Imported; used to apply the optimization theorems to Pi^{eps_ex} and absorb the exploration cost into the error floor.
  • domain assumption Bregman proximal point convergence guarantee (Sherman et al. 2025, Theorem 9)
    Used for the PMD iteration complexity bound in Theorem 4 and Theorem 10.
  • domain assumption Convexity of the policy class Pi for SDPO, DA-CPI, and PMD
    Required for the constrained steepest descent and doubly approximate analyses; not satisfied by typical neural network policy parameterizations.
  • domain assumption Existence of an optimization oracle returning an eps-approximate minimizer over Pi or Pi^{eps_ex}
    The learning model assumes this oracle; the computational cost of producing such minimizers is not analyzed.
  • domain assumption Discount factor gamma <= 1/2 in the sample complexity results
    Assumed in Section E to simplify sub-exponential concentration arguments; the stated sample complexity guarantees formally hold only in this regime.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning." pith.science (2026). https://pith.science/paper/QPNGJ2EI

@misc{pith2026250704406,
  author       = {Pith},
  title        = {Pith review of: Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QPNGJ2EI}},
  note         = {Machine review of arXiv:2507.04406}
}
abstract

We study reinforcement learning (RL) in the agnostic policy learning setting, where the goal is to find a policy whose performance is competitive with the best policy in a given class of interest $\Pi$ -- crucially, without assuming that $\Pi$ contains the optimal policy. We propose a general policy learning framework that reduces this problem to first-order optimization in a non-Euclidean space, leading to new algorithms as well as shedding light on the convergence properties of existing ones. Specifically, under the assumption that $\Pi$ is convex and satisfies a variational gradient dominance (VGD) condition -- an assumption known to be strictly weaker than more standard completeness and coverability conditions -- we obtain sample complexity upper bounds for three policy learning algorithms: \emph{(i)} Steepest Descent Policy Optimization, derived from a constrained steepest descent method for non-convex optimization; \emph{(ii)} the classical Conservative Policy Iteration algorithm \citep{kakade2002approximately} reinterpreted through the lens of the Frank-Wolfe method, which leads to improved convergence results; and \emph{(iii)} an on-policy instantiation of the well-studied Policy Mirror Descent algorithm. Finally, we empirically evaluate the VGD condition across several standard environments, demonstrating the practical relevance of our key assumption.

Figures

Figures reproduced from arXiv: 2507.04406 by the authors.

Figure 1
Figure 1. Completeness + coverage allows for sam￾ple efficient policy learning (Kakade and Langford, 2002). These conditions imply in particular, realiz￾ability. VGD allows for sample efficient learn￾ing, and in particular accommodates agnostic (non￾realizable) setups. In this work, we adopt instead the assumption that Π satisfies a variational gradient dominance condition (Agarwal et al., 2021; Xiao, 2022; Bhandari and Russo… view at source ↗
Figure 2
Figure 2. Training plots for all environments. In each experiment, a single set of minimally tuned hyper-parameters [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 48 canonical work pages

  1. [1]

    Agarwal, N

    A. Agarwal, N. Jiang, S. M. Kakade, and W. Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32: 0 96, 2019

    work page 2019

  2. [2]

    Agarwal, S

    A. Agarwal, S. Kakade, A. Krishnamurthy, and W. Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33: 0 20095--20107, 2020

    work page 2020

  3. [3]

    Agarwal, S

    A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22 0 (98): 0 1--76, 2021

    work page 2021

  4. [4]

    Akkaya, M

    I. Akkaya, M. Andrychowicz, M. Chociej, M. Litwin, B. McGrew, A. Petron, A. Paino, M. Plappert, G. Powell, R. Ribas, et al. Solving rubik's cube with a robot hand. arXiv preprint arXiv:1910.07113, 2019

    arXiv 1910

  5. [5]

    Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrization

    C. Alfano and P. Rebeschini. Linear convergence for natural policy gradient with log-linear policy parametrization. arXiv preprint arXiv:2209.15382, 2022

    work page Pith review arXiv 2022

  6. [6]

    Alfano, R

    C. Alfano, R. Yuan, and P. Rebeschini. A novel framework for policy mirror descent with general parameterization and linear convergence. Advances in Neural Information Processing Systems, 36: 0 30681--30725, 2023

    work page 2023

  7. [7]

    Bagnell, S

    J. Bagnell, S. M. Kakade, J. Schneider, and A. Ng. Policy search by dynamic programming. Advances in neural information processing systems, 16, 2003

    work page 2003

  8. [8]

    Beck and M

    A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31 0 (3): 0 167--175, 2003

    work page 2003

Show all 60 references
  1. [9]

    Bertsekas and J

    D. Bertsekas and J. N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996

    1996

  2. [10]

    Bhandari and D

    J. Bhandari and D. Russo. Global optimality guarantees for policy gradient methods. Operations Research, 2024

    2024

  3. [11]

    Brockman, V

    G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym. arXiv preprint arXiv:1606.01540, 2016

    2016 arXiv

  4. [12]

    Chen and N

    J. Chen and N. Jiang. Information-theoretic considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042--1051. PMLR, 2019

    2019

  5. [13]

    K. Dong, J. Peng, Y. Wang, and Y. Zhou. Root-n-regret for learning in markov decision processes with function approximation and low bellman rank. In Conference on Learning Theory, pages 1554--1557. PMLR, 2020

    2020

  6. [14]

    S. Du, S. Kakade, J. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826--2836. PMLR, 2021

    2021

  7. [15]

    Even-Dar, S

    E. Even-Dar, S. M. Kakade, and Y. Mansour. Online markov decision processes. Mathematics of Operations Research, 34 0 (3): 0 726--736, 2009

    2009

  8. [16]

    Frank and P

    M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3 0 (1-2): 0 95--110, 1956

    1956

  9. [17]

    Geist, B

    M. Geist, B. Scherrer, and O. Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning, pages 2160--2169. PMLR, 2019

    2019

  10. [18]

    Grudzien, C

    J. Grudzien, C. A. S. De Witt, and J. Foerster. Mirror learning: A unifying framework of policy optimisation. In International Conference on Machine Learning, pages 7825--7844. PMLR, 2022

    2022

  11. [19]

    Z. Jia, G. Li, A. Rakhlin, A. Sekhari, and N. Srebro. When is agnostic reinforcement learning statistically tractable? Advances in Neural Information Processing Systems, 36: 0 27820--27879, 2023

    2023

  12. [20]

    Jiang, A

    N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages 1704--1713. PMLR, 2017

    2017

  13. [21]

    C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137--2143. PMLR, 2020

    2020

  14. [22]

    C. Jin, Q. Liu, and S. Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 34: 0 13406--13418, 2021

    2021

  15. [23]

    Johnson, C

    E. Johnson, C. Pike-Burke, and P. Rebeschini. Optimal convergence rate for exact policy mirror descent in discounted markov decision processes. Advances in Neural Information Processing Systems, 36: 0 76496--76524, 2023

    2023

  16. [24]

    Ju and G

    C. Ju and G. Lan. Policy optimization over general state and action spaces. arXiv preprint arXiv:2211.16715, 2022

    2022

  17. [25]

    Kakade and J

    S. Kakade and J. Langford. Approximately optimal approximate reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267--274, 2002

    2002

  18. [26]

    S. M. Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001

    2001

  19. [27]

    S. M. Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003

    2003

  20. [28]

    J. A. Kelner, Y. T. Lee, L. Orecchia, and A. Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 217--226. SIAM, 2014

    2014

  21. [29]

    Krishnamurthy, A

    A. Krishnamurthy, A. Agarwal, and J. Langford. Pac reinforcement learning with rich observations. Advances in Neural Information Processing Systems, 29, 2016

    2016

  22. [30]

    Krishnamurthy, G

    A. Krishnamurthy, G. Li, and A. Sekhari. The role of environment access in agnostic reinforcement learning. arXiv preprint arXiv:2504.05405, 2025

    2025 arXiv

  23. [31]

    G. Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 198 0 (1): 0 1059--1106, 2023

    2023

  24. [32]

    R. T. Lange. gymnax : A JAX -based reinforcement learning environment library, 2022. URL http://github.com/RobertTLange/gymnax

    2022

  25. [33]

    Lillicrap

    T. Lillicrap. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971, 2015

    2015 arXiv

  26. [34]

    C. Lu, J. Kuba, A. Letcher, L. Metz, C. Schroeder de Witt, and J. Foerster. Discovered policy optimisation. Advances in Neural Information Processing Systems, 35: 0 16455--16468, 2022

    2022

  27. [35]

    Mannor, Y

    S. Mannor, Y. Mansour, and A. Tamar. Reinforcement Learning: Foundations. -, 2022. URL https://sites.google.com/view/rlfoundations/home

    2022

  28. [36]

    J. Mei, C. Xiao, C. Szepesvari, and D. Schuurmans. On the global convergence rates of softmax policy gradient methods. In International conference on machine learning, pages 6820--6829. PMLR, 2020

    2020

  29. [37]

    J. Mei, Y. Gao, B. Dai, C. Szepesvari, and D. Schuurmans. Leveraging non-uniformity in first-order non-convex optimization. In International Conference on Machine Learning, pages 7555--7564. PMLR, 2021

    2021

  30. [38]

    Mu and D

    S. Mu and D. Klabjan. On the second-order convergence of biased policy gradient algorithms. In Forty-first International Conference on Machine Learning, 2024

    2024

  31. [39]

    R. Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pages 560--567. Citeseer, 2003

    2003

  32. [40]

    R. Munos. Error bounds for approximate value iteration. In Proceedings of the National Conference on Artificial Intelligence, volume 20, page 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005

    1999

  33. [41]

    A. S. Nemirovskij and D. B. Yudin. Problem complexity and method efficiency in optimization, 1983

    1983

  34. [42]

    Ouyang, J

    L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35: 0 27730--27744, 2022

    2022

  35. [43]

    M. L. Puterman. Markov decision processes: Discrete stochastic dynamic programming, 1994

    1994

  36. [44]

    Scherrer

    B. Scherrer. Approximate policy iteration schemes: A comparison. In International Conference on Machine Learning, pages 1314--1322. PMLR, 2014

    2014

  37. [45]

    Scherrer and M

    B. Scherrer and M. Geist. Local policy search in a convex space and conservative policy iteration as boosted policy search. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, pages 35--50. Springer, 2014

    2014

  38. [46]

    Schulman, P

    J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02438, 2015

    2015 arXiv

  39. [47]

    Sekhari, C

    A. Sekhari, C. Dann, M. Mohri, Y. Mansour, and K. Sridharan. Agnostic reinforcement learning with low-rank mdps and rich observations. Advances in Neural Information Processing Systems, 34: 0 19033--19045, 2021

    2021

  40. [48]

    Sherman, T

    U. Sherman, T. Koren, and Y. Mansour. Convergence of policy mirror descent beyond compatible function approximation. arXiv preprint arXiv:2502.11033, 2025

    2025 arXiv

  41. [49]

    R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018

    2018

  42. [50]

    R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999

    1999

  43. [51]

    Tomar, L

    M. Tomar, L. Shani, Y. Efroni, and M. Ghavamzadeh. Mirror descent policy optimization. arXiv preprint arXiv:2005.09814, 2020

    2005 arXiv

  44. [52]

    Vershynin

    R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  45. [53]

    L. Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23 0 (282): 0 1--36, 2022

    2022

  46. [54]

    Yang and M

    L. Yang and M. Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995--7004. PMLR, 2019

    2019

  47. [55]

    Yang and M

    L. Yang and M. Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746--10756. PMLR, 2020

    2020

  48. [56]

    Young and T

    K. Young and T. Tian . Minatar: An atari-inspired testbed for thorough and reproducible reinforcement learning experiments. arXiv preprint arXiv:1903.03176, 2019

    1903 arXiv

  49. [57]

    R. Yuan, R. M. Gower, and A. Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332--3380. PMLR, 2022

    2022

  50. [58]

    R. Yuan, S. S. Du, R. M. Gower, A. Lazaric, and L. Xiao. Linear convergence of natural policy gradient methods with log-linear policies. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023 . OpenReview.net, 2023

    2023

  51. [59]

    W. Zhan, S. Cen, B. Huang, Y. Chen, J. D. Lee, and Y. Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. SIAM Journal on Optimization, 33 0 (2): 0 1061--1091, 2023

    2023

  52. [60]

    Zhang, A

    K. Zhang, A. Koppel, H. Zhu, and T. Basar. Global convergence of policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58 0 (6): 0 3586--3612, 2020

    2020

Pith tools

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