Pith. sign in

REVIEW 3 major objections 5 minor 99 references

Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity

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

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

Pith's one-line read Bilevel reinforcement learning can be solved with a Hessian-free approximate hypergradient built on Boltzmann optimality, achieving Õ(ε⁻²) sample complexity and dropping the outer-level PL condition.

desk verdict The algorithmic idea is plausible, but the central error bound in Theorem 3.3 does not follow from Assumption 3.1, so the advertised sample-complexity claim is not established. read the letter →

arxiv 2607.28849 v1 pith:VAF2JTV2 submitted 2026-07-30 cs.LG cs.AI

Naman Saxena , Mudit Gaur , Vaneet Aggarwal This is my paper · ORCID
classification cs.LGcs.AI MSC 90C4068T05
keywords bilevelreinforcementlearningsamplecomplexityhypergradientHessian-freeoptimizationBoltzmannpolicyoptimalityentropy-regularizedMDPRLHFconvergenceanalysis
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

This paper tries to establish that bilevel reinforcement learning—where an outer objective such as preference-based reward learning sits on top of an inner policy optimization—can be solved efficiently without forming or inverting a Hessian of the inner problem. It proposes the Approximate Hypergradient Optimization (AHO) algorithm, which uses the fact that the entropy-regularized RL objective has a Boltzmann optimal policy to close the hypergradient expression. This removes the Hessian-inverse term and allows an error decomposition without the gradient-approximation/sampling tradeoff of prior penalty methods, yielding iteration complexity O(ε⁻¹) and sample complexity Õ(ε⁻²) for continuous-state, continuous-action problems. The analysis also removes the outer-level Polyak–Łojasiewicz condition used in prior work, keeping PL only on the inner policy objective and replacing uniqueness of the inner minimizer with a local nondegeneracy assumption.

What carries the argument

The central object is Boltzmann policy optimality: for the entropy-regularized discounted RL objective, the optimal policy is the Boltzmann policy π_B(a|s,θ,x) = exp(Q/τ)/exp(V_B/τ). This closed form yields a relation between the gradient of the Boltzmann value function and the gradient of Q, eliminating the Hessian-inverse term that normally appears in hypergradients. To make this usable when the parameterized policy class cannot represent every Boltzmann policy, the paper introduces gradient-shifted value functions U and W—discounted sums of reward gradients rolled out under the Boltzmann policy—as surrogates for ∇V^{π,B} and ∇Q^π, with error O(τ(ε_kl + ε_fd)) under Assumption 3.1. The app

What would settle it

Take a simple continuous MDP with a deliberately non-realizable Gaussian policy class, compute the true bilevel gradient by implicit differentiation through the inner optimality condition, and compare it with the approximate hypergradient of Eq. (10) at θ*(x). If the difference exceeds the claimed O(ε_kl) + O(ε_fd) by an amount that grows with 1/(1−γ), then the key error bound in Theorem 3.3 fails for that setting.

Watch

Extended reading notes

Core claim

The paper claims that a Hessian-free, batch-based hypergradient, defined through two gradient-shifted value functions U and W, approximates the true bilevel gradient within O(ε_kl) + O(ε_fd), and that this approximation error still allows first-order stationary convergence. Under smoothness, boundedness, inner-level PL, and a local implicit-function regularity condition, AHO's iterates satisfy (1/T) Σ ||∇Φ(x_t)||² ≤ O(1/T) + O(ε_kl²) + O(ε_fd²) + O(1/B) + O(ε_approx²) + O(exp(−K)) + O(γ^{2H}/B) + O(γ^{2H}) + O(ε_approx) + O(ε_kl). Choosing T = Θ(ε⁻¹), B = Θ(ε⁻¹), K = Θ(log(ε⁻¹)), H = Θ(log(ε⁻¹)/log(γ⁻¹)) yields iteration complexity O(ε⁻¹) and total sample complexity T·K·B·H = Õ(ε⁻²), which t

Load-bearing premise

The load-bearing premise is that, for the unrealizable policy class used in practice, the gradient-shifted value functions W and U at the inner optimum remain within O(ε_kl) + O(ε_fd) of ∇Q and ∇V^{π,B}; if that closeness fails, the approximate hypergradient's claimed O(ε_fd) + O(ε_kl) error bound is not guaranteed.

Editorial extensions

If this is right

  • Reward-model training from pairwise preferences becomes practical at large scale, because each outer-level step is a backward pass through the reward network rather than a Hessian inverse or Hessian-vector products.
  • The outer-level objective no longer needs a PL condition, so the algorithm applies to a wider class of nonconvex outer objectives.
  • Sample complexity drops from Õ(ε⁻³) to Õ(ε⁻²) by avoiding the O(σ²)-vs-O(1/(σ²B)) tradeoff of penalty-based gradient approximation.
  • If the policy class is expressive enough to represent Boltzmann policies, the approximation errors ε_kl and ε_fd vanish and the convergence bound simplifies to O(ε) plus standard sampling and function-approximation terms.
  • The guarantee is first-order stationarity in gradient norm, matching the standard practical objective for nonconvex RL and bilevel optimization.

Reading between the lines

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

  • The same Hessian-free reduction could extend to other differentiable outer-level objectives beyond the Bradley–Terry preference model, since Theorem 3.3 only needs differentiable log-likelihoods and the Boltzmann structure of the inner solution.
  • Because Assumption 3.1 ties the hypergradient error to policy-class capacity, architecture choice may act as a tunable knob for outer-level accuracy—an effect the paper does not test experimentally.
  • A natural testable extension is to grow the policy class during inner optimization so that ε_kl and ε_fd shrink online, potentially driving the residual terms in Theorem 4.6 to zero and leaving O(ε) plus sampling error.
  • The analysis likely inherits sensitivity to the local nondegeneracy assumption on the selected inner minimizer; whether Assumption 4.5 can be replaced by a weaker value-suboptimality condition is left open.
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 proposes AHO, a Hessian-free hypergradient-based algorithm for bilevel RL, using the optimality of the Boltzmann policy for the entropy-regularized discounted RL objective. The main theoretical claim is an iteration complexity of O(ε^{-1}) and a state-of-the-art sample complexity of Õ(ε^{-2}) (Theorem 4.6), achieved without a Polyak-Łojasiewicz condition on the outer objective and, the authors claim, without a unique-minimizer assumption on the inner level. The algorithm alternates inner-level policy updates with outer-level reward-parameter updates, using gradient-shifted value functions U^π and W^π as surrogates for ∇V^{π,B} and ∇Q^π. The paper also includes experiments on DM Control tasks comparing AHO with the penalty-based baseline of Gaur et al. (2025).

Significance. If the main theorem were correct, the claimed Õ(ε^{-2}) sample complexity would be a meaningful advance over the prior Õ(ε^{-3}) bound, and removing the outer-level PL condition would broaden the applicability of bilevel RL theory. The paper is also transparent in stating its non-realizability assumptions and includes an empirical demonstration with a reproducible implementation. However, the central hypergradient approximation error bound — the load-bearing step for Theorem 4.6 — rests on a derivative mismatch between total and partial derivatives, and the inner-level suboptimality argument relies on a quadratic-growth condition with a unique minimizer despite the paper's claim to remove that assumption. As written, the advertised convergence and sample-complexity guarantees are not established.

major comments (3)
  1. [Section 3.2, Lemma C.3, Eq. (50)] Under the paper's own convention (Section 3), ∇ is the total derivative with respect to x and ∇x is the partial derivative. In Eq. (50), the integrand ∥∇logπ(a|s,θ*(x)) − ∇logπB(a|s,θ*(x),x)∥ is a total-derivative gap. Since π(a|s,θ) has no explicit x-dependence, d/dx logπ(a|s,θ*(x)) = ∇θ logπ(a|s,θ*)·∇xθ*(x), while d/dx logπB = ∇x logπB + ∇θ logπB·∇xθ*. Their difference is (∇θ logπ − ∇θ logπB)·∇xθ* − ∇x logπB. Assumption 3.1(2) bounds only ∫π∥∇x logπB − ∇x logπ∥, which is effectively ∫π∥∇x logπB∥; it does not control the leading (∇θ logπ − ∇θ logπB)·∇xθ* term. Thus the bound ∥Ψ1∥ ≤ ClIH ε_fd does not follow, and the O(ε_fd)+O(ε_kl) approximation-error claim of Theorem 3.3 is unsupported.
  2. [Lemma C.5, Eq. (66), steps (2)–(3)] The same total/partial derivative mismatch appears in the bound on ∆(s,θ*(x)) = τ∇D_KL(π‖πB). Step (2) correctly produces a term ∫π∥∇logπ − ∇logπB∥, but step (3) replaces this total-derivative gap with ε_fd using Assumption 3.1(2), which is a partial-derivative bound. The resulting inequality ∥∆∥ ≤ τ(L_{π,log}C_θ ε_kl + ε_fd) is therefore unjustified. This ∆ bound is used to prove Lemma 3.2's surrogate error bounds and then feeds into Ψ2 in Lemma C.3. The entire error decomposition of Theorem 3.3 relies on this invalid identification.
  3. [Definition 4.10 and Lemma D.6] The paper advertises removal of the unique-minimizer assumption (Section 1, contribution 4), and Assumption 4.5 only assumes a local differentiable selection. However, Definition 4.10 defines Quadratic Growth only for a function with a unique global minimizer, and Lemma D.6 uses it globally: ∥θK_t−θ*(xt)∥² ≤ (2/µ)∥J(θ*(xt),xt)−J(θK_t,xt)∥. Assumption 4.4 (PL on the inner objective) does not imply a unique global minimizer, and the local nonsingularity in Assumption 4.5 gives only local strong convexity. No argument shows that the iterates stay in a region where QG holds or that the selected θ*(x) is the unique minimizer. Hence Lemma 4.9/D.6 is not established, and the claimed removal of the unique-minimizer assumption is not supported by the proof.
minor comments (5)
  1. [Appendix B, Algorithm 4, line 10] The projection is written as Γ_{z0,(1−γ)^{-1}}(Z'_l), but the variable is z'_l, not Z'_l.
  2. [Appendix B, Eq. (24)] Eq. (24) writes ∇θ π(a_j|s_j,θ^k_t), while Eq. (12) and the surrounding text use ∇θ log π(a_j|s_j,θ^k_t). This inconsistency is confusing.
  3. [Lemma C.1] The lemma uses F for the lower-level loss but does not define it; it should be identified with −J (or J, depending on the sign convention) from Section 2.
  4. [Appendix B.2.3] The statement that the experiments 'empirically support' the sample-complexity improvement is an overclaim: the experiments report total episode reward, not sample-complexity scaling, and do not measure the theoretical rates.
  5. [Throughout] There are several typographical issues, e.g., 'samplping' in the proof sketch before Eq. (21), and inconsistent use of 'ϵ' vs 'ε' in the text.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the central error bounds are propagated from stated assumptions and prior convergence results, not restated as predictions; the derivative-convention gap is a correctness issue, not a circular reduction.

full rationale

The paper's main derivation chain is not circular. The approximate hypergradient (Eq. 10) is explicitly constructed from the gradient-shifted functions U^π and W^π (Eq. 7), and the claimed bound ∥Ψ∥=O(ε_fd)+O(ε_kl) in Theorem 3.3 is obtained by propagating the unrealizability errors in Assumption 3.1 through Lemma C.5 and Lemma C.3. This is an assumption-propagation argument, not a case in which the conclusion is identical by construction to an input. The inner-level iterate bound (Lemma 4.9/D.6) invokes prior work by the same group (Gaur et al., 2024; Gaur et al., 2025), but those citations concern standard Q-learning/actor-critic convergence and are not the paper's novel sample-complexity claim; they are load-bearing but not circular. The skeptic's identified issue—Assumption 3.1(2) bounds partial x-derivatives while Lemma C.3/Eq. (50) uses full derivatives—is a genuine derivational gap that would undermine the O(ε_fd) propagation, but it is a proof/rigor defect rather than a circularity: the bound is not equivalent by construction to an assumed conclusion. The empirical comparison is not used to fit or redefine any theoretical quantity. Therefore no circular step is scored; the low nonzero score reflects only the presence of minor, non-load-bearing self-citations in the supporting lemmas.

Assumptions & free parameters 1 free parameters · 7 assumptions · 0 invented entities

The central claim depends on strong regularity assumptions: inner-level PL, nondegenerate local selection, Q-function approximation error, and a non-realizability error bound. The paper contributes no new physical entities; the mathematical constructs (gradient-shifted value functions) are tools, not entities. The ad hoc use of Assumption 3.1.2 is the load-bearing weakness.

free parameters (1)
  • temperature τ = Θ(1) in theory; 100.0 in experiments
    Temperature in the entropy-regularized objective and Boltzmann policy. The convergence proof sets τ=Θ(1) (Eq. 192), while experiments use τ=100.0, an inconsistency. Not fitted to data but chosen by hand.
assumptions (7)
  • domain assumption Assumption 4.1: Lipschitz continuity of V, Q, π, logπ, and r in θ and x
    Standard smoothness regularity in bilevel RL, used throughout the proof of L-smoothness and hypergradient estimation.
  • domain assumption Assumption 4.2: bounded reward and log-probability
    Ensures well-defined bounded returns; standard in discounted RL.
  • domain assumption Assumption 4.3: Q-function approximation error bounded by ε_approx
    Standard function-approximation assumption in RL, needed for the Q-learning subroutine convergence.
  • domain assumption Assumption 4.4: PL condition on the inner objective −J(θ,x) w.r.t. θ
    A strong non-convex regularity condition; the paper claims to remove outer PL but substitutes inner PL, which is not mild for continuous state/action RL with function approximation.
  • domain assumption Assumption 4.5: nondegenerate local selection θ*(x) with bounded sensitivity
    Used to invoke the implicit function theorem and obtain a local differentiable response map; standard for implicit-differentiation bilevel analysis.
  • ad hoc to paper Assumption 3.1: non-realizability error bounds ε_kl and ε_fd
    The assumption bounds the KL and partial-gradient mismatch between the optimal parameterized policy and its Boltzmann counterpart. The second part is degenerate for parameterized policies (∇_x logπ=0) and is used to bound a total-derivative mismatch, so it is ad hoc and likely insufficient.
  • ad hoc to paper Definition 4.10: Quadratic Growth with a unique minimizer
    Used in Lemma 4.9 to convert value suboptimality to iterate distance. Assumes a unique minimizer, contradicting the paper's stated removal of the unique-minimizer assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity." pith.science (2026). https://pith.science/paper/VAF2JTV2

@misc{pith2026260728849,
  author       = {Pith},
  title        = {Pith review of: Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VAF2JTV2}},
  note         = {Machine review of arXiv:2607.28849}
}
abstract

Bilevel reinforcement learning (RL) is an important framework within the literature of RL that can be used to formalize various categories of problems, such as meta-learning, hierarchical task decomposition, and reinforcement learning from human feedback (RL-HF). Most of the bilevel RL algorithms are either not scalable because of using hypergradient with Hessian, or they suffer from high sample complexity because of using penalty-based approximation methods. In this work, we propose a hypergradient-based bilevel RL algorithm using the optimality of the Boltzmann policy for the entropy regularized discounted RL objective function. Our proposed algorithm is Hessian-free and obtains an iteration complexity of $O(\epsilon^{-1})$ and state-of-the-art sample complexity of $\tilde{O}(\epsilon^{-2})$ under mild regularity conditions. Further, in our convergence analysis, we are able to remove the assumption of the Polyak-Lojasiewicz (PL) condition on the outer-level objective function present in the prior state-of-the-art sample complexity work.

Figures

Figures reproduced from arXiv: 2607.28849 by the authors.

Figure 1
Figure 1. Total episode reward during evaluation for walker-walk (left) and cheetah-run (right). Solid [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

99 extracted references · 7 linked inside Pith

  1. [1]

    International conference on machine learning , pages=

    Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor , author=. International conference on machine learning , pages=. 2018 , organization=

    2018

  2. [2]

    Advances in neural information processing systems , volume=

    Bridging the gap between value and policy based reinforcement learning , author=. Advances in neural information processing systems , volume=

  3. [3]

    International conference on machine learning , pages=

    Bilevel programming for hyperparameter optimization and meta-learning , author=. International conference on machine learning , pages=. 2018 , organization=

    2018

  4. [4]

    Transactions of the American Mathematical Society , volume=

    Partial subdifferentials, derivates and Rademacher’s theorem , author=. Transactions of the American Mathematical Society , volume=

  5. [5]

    Advances in neural information processing systems , volume=

    Policy gradient methods for reinforcement learning with function approximation , author=. Advances in neural information processing systems , volume=

  6. [6]

    ACM Computing Surveys , volume=

    Rlhf deciphered: A critical analysis of reinforcement learning from human feedback for llms , author=. ACM Computing Surveys , volume=. 2025 , publisher=

    2025

  7. [7]

    International conference on machine learning , pages=

    Model-agnostic meta-learning for fast adaptation of deep networks , author=. International conference on machine learning , pages=. 2017 , organization=

    2017

  8. [8]

    Discrete event dynamic systems , volume=

    Recent advances in hierarchical reinforcement learning , author=. Discrete event dynamic systems , volume=. 2003 , publisher=

    2003

Show all 99 references
  1. [9]

    Proceedings of the AAAI Conference on Artificial Intelligence , author=

    Bi-Level Actor-Critic for Multi-Agent Coordination , volume=. Proceedings of the AAAI Conference on Artificial Intelligence , author=. 2020 , month=

    2020

  2. [10]

    Proceedings of The 25th International Conference on Artificial Intelligence and Statistics , pages =

    Nuances in Margin Conditions Determine Gains in Active Learning , author =. Proceedings of The 25th International Conference on Artificial Intelligence and Statistics , pages =. 2022 , editor =

    2022

  3. [11]

    The Annals of Statistics , volume=

    Optimal aggregation of classifiers in statistical learning , author=. The Annals of Statistics , volume=. 2004 , publisher=

    2004

  4. [12]

    Fast learning rates for plug-in classifiers , author=

  5. [13]

    Journal of Machine Learning Research , volume=

    Principled penalty-based methods for bilevel reinforcement learning and rlhf , author=. Journal of Machine Learning Research , volume=

  6. [14]

    SIAM Journal on Optimization , volume=

    A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic , author=. SIAM Journal on Optimization , volume=. 2023 , publisher=

    2023

  7. [15]

    The Thirty-ninth Annual Conference on Neural Information Processing Systems , year=

    On the Sample Complexity Bounds of Bilevel Reinforcement Learning , author=. The Thirty-ninth Annual Conference on Neural Information Processing Systems , year=

  8. [16]

    Advances in Neural Information Processing Systems , volume=

    Contextual bilevel reinforcement learning for incentive alignment , author=. Advances in Neural Information Processing Systems , volume=

  9. [17]

    International Conference on Artificial Intelligence and Statistics , pages=

    Bilevel Reinforcement Learning via the Development of Hyper-gradient without Lower-Level Convexity , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2025 , organization=

    2025

  10. [18]

    Souradip Chakraborty and Amrit Bedi and Alec Koppel and Huazheng Wang and Dinesh Manocha and Mengdi Wang and Furong Huang , booktitle=

  11. [19]

    Achieving

    Yang, Yifan and Xiao, Peiyao and Ji, Kaiyi , journal=. Achieving

  12. [20]

    The Thirty Seventh Annual Conference on Learning Theory , pages=

    On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis , author=. The Thirty Seventh Annual Conference on Learning Theory , pages=. 2024 , organization=

    2024

  13. [21]

    International conference on machine learning , pages=

    On penalty-based bilevel gradient descent method , author=. International conference on machine learning , pages=. 2023 , organization=

    2023

  14. [22]

    The Twelfth International Conference on Learning Representations , year=

    On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation , author=. The Twelfth International Conference on Learning Representations , year=

  15. [23]

    International Conference on Artificial Intelligence and Statistics , pages=

    A single-timescale method for stochastic bilevel optimization , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2022 , organization=

    2022

  16. [24]

    Advances in Neural Information Processing Systems , volume=

    Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems , author=. Advances in Neural Information Processing Systems , volume=

  17. [26]

    Advances in Neural Information Processing Systems , volume=

    Provably faster algorithms for bilevel optimization , author=. Advances in Neural Information Processing Systems , volume=

  18. [27]

    Advances in neural information processing systems , volume=

    A near-optimal algorithm for stochastic bilevel optimization via double-momentum , author=. Advances in neural information processing systems , volume=

  19. [28]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    A fully single loop algorithm for bilevel optimization without hessian inverse , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

  20. [29]

    Advances in Neural Information Processing Systems , volume=

    On the convergence theory for hessian-free bilevel algorithms , author=. Advances in Neural Information Processing Systems , volume=

  21. [30]

    International Conference on Machine Learning , pages=

    A fully first-order method for stochastic bilevel optimization , author=. International Conference on Machine Learning , pages=. 2023 , organization=

    2023

  22. [31]

    Advances in neural information processing systems , volume=

    Bome! bilevel optimization made easy: A simple first-order approach , author=. Advances in neural information processing systems , volume=

  23. [32]

    International conference on machine learning , pages=

    A value-function-based interior-point method for non-convex bi-level optimization , author=. International conference on machine learning , pages=. 2021 , organization=

    2021

  24. [33]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Efficient gradient approximation method for constrained bilevel optimization , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

  25. [34]

    International Conference on Machine Learning , pages=

    Linearly constrained bilevel optimization: A smoothed implicit gradient approach , author=. International Conference on Machine Learning , pages=. 2023 , organization=

    2023

  26. [35]

    arXiv preprint arXiv:2203.01123 , pages=

    A constrained optimization approach to bilevel optimization with multiple inner minima , author=. arXiv preprint arXiv:2203.01123 , pages=

    arXiv

  27. [36]

    Advances in Neural Information Processing Systems , volume=

    First-order methods for linearly constrained bilevel optimization , author=. Advances in Neural Information Processing Systems , volume=

  28. [37]

    arXiv preprint arXiv:2401.16164 , year=

    Constrained bi-level optimization: Proximal lagrangian value function approach and hessian-free algorithm , author=. arXiv preprint arXiv:2401.16164 , year=

    arXiv

  29. [38]

    International Conference on Artificial Intelligence and Statistics , pages=

    Alternating projected sgd for equality-constrained bilevel optimization , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2023 , organization=

    2023

  30. [39]

    arXiv preprint arXiv:2406.10148 , year=

    A primal-dual-assisted penalty approach to bilevel optimization with coupled constraints , author=. arXiv preprint arXiv:2406.10148 , year=

    arXiv

  31. [40]

    arXiv preprint arXiv:2406.01992 , year=

    Overcoming lower-level constraints in bilevel optimization: A novel approach with regularized gap functions , author=. arXiv preprint arXiv:2406.01992 , year=

    arXiv

  32. [41]

    ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , pages=

    An implicit gradient-type method for linearly constrained bilevel problems , author=. ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , pages=. 2022 , organization=

    2022

  33. [42]

    IEEE Transactions on Pattern Analysis and Machine Intelligence , volume=

    Value-function-based sequential minimization for bi-level optimization , author=. IEEE Transactions on Pattern Analysis and Machine Intelligence , volume=. 2023 , publisher=

    2023

  34. [43]

    International Conference on Machine Learning , pages=

    Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-Loop and Hessian-Free Solution Strategy , author=. International Conference on Machine Learning , pages=. 2024 , organization=

    2024

  35. [44]

    arXiv preprint arXiv:2306.16761 , year=

    Moreau envelope based difference-of-weakly-convex reformulation and algorithm for bilevel programs , author=. arXiv preprint arXiv:2306.16761 , year=

    arXiv

  36. [45]

    The 41st Conference on Uncertainty in Artificial Intelligence , year=

    Order-optimal global convergence for actor-critic with general policy and neural critic parametrization , author=. The 41st Conference on Uncertainty in Artificial Intelligence , year=

  37. [46]

    Advances in Neural Information Processing Systems , volume=

    An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods , author=. Advances in Neural Information Processing Systems , volume=

  38. [47]

    Journal of Machine Learning Research , volume=

    On the theory of policy gradient methods: Optimality, approximation, and distribution shift , author=. Journal of Machine Learning Research , volume=

  39. [48]

    Advances in Neural Information Processing Systems , volume=

    Sample-efficient constrained reinforcement learning with general parameterization , author=. Advances in Neural Information Processing Systems , volume=

  40. [49]

    Advances in Neural Information Processing Systems , volume=

    Finite-time analysis of single-timescale actor-critic , author=. Advances in Neural Information Processing Systems , volume=

  41. [50]

    Advances in Neural Information Processing Systems , volume=

    On the convergence and sample efficiency of variance-reduced policy gradient method , author=. Advances in Neural Information Processing Systems , volume=

  42. [51]

    Journal of Machine Learning Research , volume=

    On the convergence rates of policy gradient methods , author=. Journal of Machine Learning Research , volume=

  43. [52]

    International conference on machine learning , pages=

    On the global convergence rates of softmax policy gradient methods , author=. International conference on machine learning , pages=. 2020 , organization=

    2020

  44. [53]

    International Conference on Learning Representations , year=

    Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy , author=. International Conference on Learning Representations , year=

  45. [54]

    International Conference on Learning Representations , year=

    Neural Policy Gradient Methods: Global Optimality and Rates of Convergence , author=. International Conference on Learning Representations , year=

  46. [55]

    International Conference on Machine Learning , pages=

    Closing the Gap: Achieving Global Convergence (Last Iterate) of Actor-Critic under Markovian Sampling with Neural Network Parametrization , author=. International Conference on Machine Learning , pages=. 2024 , organization=

    2024

  47. [56]

    Proximit

    Moreau, Jean-Jacques , journal=. Proximit

  48. [57]

    Journal of Machine Learning Research , volume=

    Bilevel optimization with a lower-level contraction: Optimal sample complexity without warm-start , author=. Journal of Machine Learning Research , volume=

  49. [58]

    Stochastic subgradient method converges at the rate O (k^

    Davis, Damek and Drusvyatskiy, Dmitriy , journal=. Stochastic subgradient method converges at the rate O (k^

  50. [59]

    1998 , publisher=

    Variational analysis , author=. 1998 , publisher=

    1998

  51. [60]

    Linear convergence of gradient and proximal-gradient methods under the polyak-

    Karimi, Hamed and Nutini, Julie and Schmidt, Mark , booktitle=. Linear convergence of gradient and proximal-gradient methods under the polyak-. 2016 , organization=

    2016

  52. [61]

    Journal of optimization theory and applications , volume=

    Variable smoothing for weakly convex composite functions , author=. Journal of optimization theory and applications , volume=. 2021 , publisher=

    2021

  53. [62]

    Bolte, J. The. SIAM Journal on Optimization , volume=. 2007 , publisher=

    2007

  54. [63]

    the method of paired comparisons , author=

    Rank analysis of incomplete block designs: I. the method of paired comparisons , author=. Biometrika , volume=. 1952 , publisher=

    1952

  55. [64]

    International conference on artificial intelligence and statistics , pages=

    Optimizing millions of hyperparameters by implicit differentiation , author=. International conference on artificial intelligence and statistics , pages=. 2020 , organization=

    2020

  56. [65]

    International Conference on Learning Representations , year=

    Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions , author=. International Conference on Learning Representations , year=

  57. [67]

    Advances in neural information processing systems , volume=

    Deep reinforcement learning from human preferences , author=. Advances in neural information processing systems , volume=

  58. [68]

    Bradley, R. A. and Terry, M. E. (1952). Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika , 39(3/4):324--345

    1952

  59. [69]

    Chakraborty, S., Bedi, A., Koppel, A., Wang, H., Manocha, D., Wang, M., and Huang, F. (2024). PARL : A unified framework for policy alignment in reinforcement learning from human feedback. In The Twelfth International Conference on Learning Representations

    2024

  60. [70]

    Chen, L., Xu, J., and Zhang, J. (2024). On finding small hyper-gradients in bilevel optimization: Hardness results and improved analysis. In The Thirty Seventh Annual Conference on Learning Theory , pages 947--980. PMLR

    2024

  61. [71]

    Chen, T., Sun, Y., Xiao, Q., and Yin, W. (2022). A single-timescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics , pages 2466--2488. PMLR

    2022

  62. [72]

    Chen, T., Sun, Y., and Yin, W. (2021). Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems , 34:25294--25307

    2021

  63. [73]

    and Zhao, L

    Chen, X. and Zhao, L. (2023). Finite-time analysis of single-timescale actor-critic. Advances in Neural Information Processing Systems , 36:7017--7049

    2023

  64. [74]

    F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D

    Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. (2017). Deep reinforcement learning from human preferences. Advances in neural information processing systems , 30

    2017

  65. [75]

    Fu, Z., Yang, Z., and Wang, Z. (2021). Single-timescale actor-critic provably finds globally optimal policy. In International Conference on Learning Representations

    2021

  66. [76]

    U., and Aggarwal, V

    Ganesh, S., Chen, J., Mondal, W. U., and Aggarwal, V. (2025). Order-optimal global convergence for actor-critic with general policy and neural critic parametrization. In The 41st Conference on Uncertainty in Artificial Intelligence

    2025

  67. [77]

    Gaur, M., Bedi, A., Wang, D., and Aggarwal, V. (2024). Closing the gap: Achieving global convergence (last iterate) of actor-critic under markovian sampling with neural network parametrization. In International Conference on Machine Learning , pages 15153--15179. PMLR

    2024

  68. [78]

    S., Pasupathy, R., and Aggarwal, V

    Gaur, M., Singh, U., Bedi, A. S., Pasupathy, R., and Aggarwal, V. (2025). On the sample complexity bounds of bilevel reinforcement learning. In The Thirty-ninth Annual Conference on Neural Information Processing Systems

    2025

  69. [79]

    and Wang, M

    Ghadimi, S. and Wang, M. (2018). Approximation methods for bilevel programming. arXiv preprint arXiv:1802.02246

    2018 arXiv

  70. [80]

    Grazzi, R., Pontil, M., and Salzo, S. (2023). Bilevel optimization with a lower-level contraction: Optimal sample complexity without warm-start. Journal of Machine Learning Research , 24(167):1--37

    2023

  71. [81]

    Hong, M., Wai, H.-T., Wang, Z., and Yang, Z. (2023). A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization , 33(1):147--180

    2023

  72. [82]

    Khanduri, P., Zeng, S., Hong, M., Wai, H.-T., Wang, Z., and Yang, Z. (2021). A near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in neural information processing systems , 34:30271--30283

    2021

  73. [83]

    Kwon, J., Kwon, D., Wright, S., and Nowak, R. D. (2023). A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning , pages 18083--18113. PMLR

    2023

  74. [84]

    Kwon, J., Kwon, D., Wright, S., and Nowak, R. D. (2024). On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In The Twelfth International Conference on Learning Representations

    2024

  75. [85]

    Li, J., Gu, B., and Huang, H. (2022). A fully single loop algorithm for bilevel optimization without hessian inverse. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 36, pages 7426--7434

    2022

  76. [86]

    Liu, B., Ye, M., Wright, S., Stone, P., and Liu, Q. (2022). Bome! bilevel optimization made easy: A simple first-order approach. Advances in neural information processing systems , 35:17248--17262

    2022

  77. [87]

    Liu, R., Liu, X., Yuan, X., Zeng, S., and Zhang, J. (2021). A value-function-based interior-point method for non-convex bi-level optimization. In International conference on machine learning , pages 6882--6892. PMLR

    2021

  78. [88]

    Liu, Y., Zhang, K., Basar, T., and Yin, W. (2020). An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems , 33:7624--7636

    2020

  79. [89]

    Lorraine, J., Vicol, P., and Duvenaud, D. (2020). Optimizing millions of hyperparameters by implicit differentiation. In International conference on artificial intelligence and statistics , pages 1540--1552. PMLR

    2020

  80. [90]

    Mackay, M., Vicol, P., Lorraine, J., Duvenaud, D., and Grosse, R. (2019). Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. In International Conference on Learning Representations

    2019

  81. [91]

    Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D. (2017). Bridging the gap between value and policy based reinforcement learning. Advances in neural information processing systems , 30

    2017

  82. [92]

    and Chen, T

    Shen, H. and Chen, T. (2023). On penalty-based bilevel gradient descent method. In International conference on machine learning , pages 30992--31015. PMLR

    2023

  83. [93]

    Shen, H., Yang, Z., and Chen, T. (2025). Principled penalty-based methods for bilevel reinforcement learning and rlhf. Journal of Machine Learning Research , 26(114):1--49

    2025

  84. [94]

    Sow, D., Ji, K., and Liang, Y. (2022). On the convergence theory for hessian-free bilevel algorithms. Advances in Neural Information Processing Systems , 35:4136--4149

    2022

  85. [95]

    S., McAllester, D., Singh, S., and Mansour, Y

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

    1999

  86. [96]

    Tassa, Y., Doron, Y., Muldal, A., Erez, T., Li, Y., Casas, D. d. L., Budden, D., Abdolmaleki, A., Merel, J., Lefrancq, A., et al. (2018). Deepmind control suite. arXiv preprint arXiv:1801.00690

    2018 arXiv

  87. [97]

    Thoma, V., P \'a sztor, B., Krause, A., Ramponi, G., and Hu, Y. (2024). Contextual bilevel reinforcement learning for incentive alignment. Advances in Neural Information Processing Systems , 37:127369--127435

    2024

  88. [98]

    Wang, L., Cai, Q., Yang, Z., and Wang, Z. (2020). Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations

    2020

  89. [99]

    Yang, J., Ji, K., and Liang, Y. (2021). Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems , 34:13670--13682

    2021

  90. [100]

    Yang, Y., Gao, B., and Yuan, Y.-x. (2025). Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity. In International Conference on Artificial Intelligence and Statistics , pages 4780--4788. PMLR

    2025

  91. [101]

    Yang, Y., Xiao, P., and Ji, K. (2023). Achieving O ( ^ -1.5 ) complexity in hessian/jacobian-free stochastic bilevel optimization. Advances in Neural Information Processing Systems , 36:39491--39503

    2023

Pith tools

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