Related papers: Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity

Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity

URL: http://arxiv.org/abs/2607.28849v1
Date: Thu, 30 Jul 2026 21:21:52 GMT
Title: Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity
Abstract summary: We propose a hypergradient-based bilevel RL algorithm using the optimality of the Boltzmann policy for the entropy regularized discounted RL objective function.<n>Our proposed algorithm is Hessian-free and obtains an iteration complexity of $O(-1)$ and state-of-the-art sample complexity of $tildeO(-2)$ under mild regularity conditions.
Score: 44.384258745074646
License: http://creativecommons.org/licenses/by/4.0/
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(ε^{-1})$ and state-of-the-art sample complexity of $\tilde{O}(ε^{-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.

Related papers

Sample Efficient Hierarchical Reinforcement Learning via Best Policy Identification [11.621402971675835]
We present HBPI-UCRL, a model-based algorithm for hierarchical reinforcement learning (HRL) that learns high-level and low-level policies in parallel.<n>In the sparse-reward, goal-directed setting, our sample upper bound for HBPI-UCRL is strictly lower than that of its non-hierarchical counterpart.
arXiv Detail & Related papers (2026-07-31T11:12:31Z)
Sample Complexity Analysis for Constrained Bilevel Reinforcement Learning [47.66330599017582]
We analyse the sample complexity of a constrained bilevel RL algorithm, building on the progress in the unconstrained setting.<n>We are the first ones to analyse the generally parameterized policy-based RL algorithm with a non-smooth objective function.
arXiv Detail & Related papers (2026-01-30T20:10:21Z)
A Regularized Actor-Critic Algorithm for Bi-Level Reinforcement Learning [24.969317765059174]
We study a structured bi-level optimization problem where the upper-level objective is a smooth function and the lower-level problem is policy optimization in a Markov decision process (MDP)<n>Existing methods for bi-level optimization and RL often require second-order information, impose strong regularization at the lower level, or inefficiently use samples through nested-loop procedures.<n>We propose a single-loop, first-order actor-critic algorithm that optimize the bi-level objective via a penalty-based reformulation.
arXiv Detail & Related papers (2026-01-23T02:12:24Z)
On The Sample Complexity Bounds In Bilevel Reinforcement Learning [49.19950489963245]
Bilevel reinforcement learning (BRL) has emerged as a powerful framework for aligning generative models.<n>We present the first sample of $mathcalO(epsilon)$ in continuous state-action complexity.<n>Our analysis also extends complexity improving upon existing bounds of $mathcalO(epsilon)$.
arXiv Detail & Related papers (2025-03-22T04:22:04Z)
Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity [4.917399520581689]
Bilevel reinforcement learning (RL) features intertwined two-level problems.<n>Non-level convex information is an impediment to developing bilevel optimization methods.<n>Hyper-gradient serves as an integration of exploitation and exploration.
arXiv Detail & Related papers (2024-05-30T05:24:20Z)
A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation [67.66904892192794]
We propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for reinforcement learning.<n>MQL-UCB achieves minimax optimal regret of $tildeO(dsqrtHK)$ when $K$ is sufficiently large and near-optimal policy switching cost.<n>Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation.
arXiv Detail & Related papers (2023-11-26T08:31:57Z)
Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
In this paper, we establish an efficient online sub-sampling framework that measures the information gain of data points collected by an RL algorithm. For a value-based method with complexity-bounded function class, we show that the policy only needs to be updated for $proptooperatornamepolylog(K)$ times. In contrast to existing approaches that update the policy for at least $Omega(K)$ times, our approach drastically reduces the number of optimization calls in solving for a policy.
arXiv Detail & Related papers (2021-06-14T07:36:25Z)
On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
arXiv Detail & Related papers (2020-11-09T18:32:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.