Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity

Researchers propose a Hessian-free hypergradient-based bilevel reinforcement learning algorithm that achieves an iteration complexity of O(ε⁻¹) and state-of-the-art sample complexity of Õ(ε⁻²) under mild regularity conditions, removing the Polyak-Lojasiewicz condition assumption on the outer-level objective function. The method leverages the optimality of the Boltzmann policy for entropy-regularized discounted RL objectives, addressing scalability and sample complexity issues in bilevel RL frameworks such as meta-learning and RL from human feedback.

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.