# Bi-Level Policy Optimization with Nystr"om Hypergradients

arXiv: https://arxiv.org/abs/2505.11714 · HTML: https://mlsanity.com/paper/2505.11714/

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

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 25 of 25)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Brax -- A Differentiable Physics Engine for Large Scale Rigid Body Simulation](https://mlsanity.com/paper/2106.13281/) (2021)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019)
- [An Investigation into Neural Net Optimization via Hessian Eigenvalue Density](https://mlsanity.com/paper/1901.10159/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond](https://mlsanity.com/paper/1611.07476/) (2016)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Discovered Policy Optimisation](https://mlsanity.com/paper/2210.05639/) (2022)
- [PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2308.02585/) (2023)
- [On Implicit Bias in Overparameterized Bilevel Optimization](https://mlsanity.com/paper/2212.14032/) (2022)
- [SAIL: Self-Improving Efficient Online Alignment of Large Language Models](https://mlsanity.com/paper/2406.15567/) (2024)
- [The Curse of Unrolling: Rate of Differentiating Through Optimization](https://mlsanity.com/paper/2209.13271/) (2022)
- [Characterizing the Gap Between Actor-Critic and Policy Gradient](https://mlsanity.com/paper/2106.06932/) (2021)
- [Nystrom Method for Accurate and Scalable Implicit Differentiation](https://mlsanity.com/paper/2302.09726/) (2023)
- [Computing Stackelberg Equilibria of Large General-Sum Games](https://mlsanity.com/paper/1909.03319/) (2019)
- [Achieving an optimal trade-off between revenue and energy peak within a smart grid environment](https://mlsanity.com/paper/1601.05678/) (2016)

## Built on by (most cited first, 3 of 3)

- [Explaining and Preventing Alignment Collapse in Iterative RLHF](https://mlsanity.com/paper/2605.04266/) (2026)
- [Natural Hypergradient Descent: Algorithm Design, Convergence Analysis, and Parallel Implementation](https://mlsanity.com/paper/2602.10905/) (2026)
- [Active Inference as Context Acquisition for AI Agents](https://mlsanity.com/paper/2608.19202/) (2026)

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