Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity

arXiv cs.LG Papers
bilevel-rl hypergradient sample-complexity reinforcement-learning hessian-free arxiv

Summary

This paper proposes a Hessian-free hypergradient-based bilevel reinforcement learning algorithm that achieves state-of-the-art sample complexity and removes the PL condition assumption in convergence analysis.

arXiv:2607.28849v1 Announce Type: new 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.
Original Article
View Cached Full Text

Cached at: 08/03/26, 07:32 AM 

# Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity
Source: [https://arxiv.org/abs/2607.28849](https://arxiv.org/abs/2607.28849)
[View PDF](https://arxiv.org/pdf/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\.

## Submission history

From: Naman Saxena \[[view email](https://arxiv.org/show-email/ef424510/2607.28849)\] **\[v1\]**Thu, 30 Jul 2026 21:21:52 UTC \(169 KB\)

Similar Articles

Boundary-Seeking Policy Gradient for Safe Reinforcement Learning

arXiv cs.LG

Introduces Boundary-Seeking Policy Gradient (BSPG), a first-order method for safe reinforcement learning that actively drives the policy toward the constraint boundary, with convergence guarantees and improved reward/boundary tracking on a Safety-Gymnasium task.