mlsanityData to 14 Oct 2026

Bi-Level Policy Optimization with Nystr"om Hypergradients

arXiv 2505.11714 ↗First posted 16 May 2025cs.LG cs.AI cs.GTcited by 3

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

The dependency of the actor on the critic in actor-critic (AC) reinforcement learning means that AC can be characterized as a bilevel optimization (BLO) problem, also called a Stackelberg game. This characterization motivates two modifications to vanilla AC algorithms. First, the critic's update should be nested to learn a best response to the actor's policy. Second, the actor should update according to a hypergradient that takes changes in the critic's behavior into account. Computing this hypergradient involves finding an inverse Hessian vector product, a process that can be numerically unstable. We thus propose a new algorithm, Bilevel Policy Optimization with Nystr"om Hypergradients (BLPO), which uses nesting to account for the nested structure of BLO, and leverages the Nystr"om method to compute the hypergradient. Theoretically, we prove BLPO converges to (a point that satisfies the necessary conditions for) a local strong Stackelberg equilibrium in polynomial time with high probability, assuming a linear parametrization of the critic's objective. Empirically, we demonstrate that BLPO performs on par with or better than PPO on a variety of discrete and continuous control tasks.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 25 of its 54 references that are in the map. First posted on arXiv 16 May 2025.

Builds on

25 of 54 references.

References · 25

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  4. 2015Continuous control with deep reinforcement learningcited by 3,407
  5. 2015Trust Region Policy Optimizationcited by 2,580
  6. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,417
  7. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  8. 2019Meta-Learning with Implicit Gradientscited by 525
  9. 2021Brax -- A Differentiable Physics Engine for Large Scale Rigid Body Simulationcited by 407
  10. 2019Optimizing Millions of Hyperparameters by Implicit Differentiationcited by 304
  11. 2019An Investigation into Neural Net Optimization via Hessian Eigenvalue Densitycited by 292
  12. 2018Approximation Methods for Bilevel Programmingcited by 236
13 more
  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  2. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 222
  3. 2016Eigenvalues of the Hessian in Deep Learning: Singularity and Beyondcited by 159
  4. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 144
  5. 2022Discovered Policy Optimisationcited by 104
  6. 2023PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedbackcited by 40
  7. 2022On Implicit Bias in Overparameterized Bilevel Optimizationcited by 30
  8. 2024SAIL: Self-Improving Efficient Online Alignment of Large Language Modelscited by 20
  9. 2022The Curse of Unrolling: Rate of Differentiating Through Optimizationcited by 16
  10. 2021Characterizing the Gap Between Actor-Critic and Policy Gradientcited by 9
  11. 2023Nystrom Method for Accurate and Scalable Implicit Differentiationcited by 8
  12. 2019Computing Stackelberg Equilibria of Large General-Sum Gamescited by 3
  13. 2016Achieving an optimal trade-off between revenue and energy peak within a smart grid environmentcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Explaining and Preventing Alignment Collapse in Iterative RLHFcited by 4
  2. 2026Natural Hypergradient Descent: Algorithm Design, Convergence Analysis, and Parallel Implementationcited by 1
  3. 2026Active Inference as Context Acquisition for AI Agentscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026A Hessian-Free Actor-Critic Algorithm for Bi-Level Reinforcement Learning with Applications to LLM Fine-Tuning
  2. 2026Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity
  3. 2026Bilevel Optimization over Saddle Points of Zero-Sum Markov Games
  4. 2024Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity
  5. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF
  6. 2026Second-Order Actor-Critic Methods for Discounted MDPs via Policy Hessian Decomposition
  7. 2026Sample Complexity Analysis for Constrained Bilevel Reinforcement Learning
  8. 2025Learning in Stackelberg Mean Field Games: A Non-Asymptotic Analysis