Bilevel reinforcement learning (RL), which features intertwined two-level
problems, has attracted growing interest recently. The inherent non-convexity
of the lower-level RL problem is, however, to be an impediment to developing
bilevel optimization methods. By employing the fixed point equation associated
with the regularized RL, we characterize the hyper-gradient via fully
first-order information, thus circumventing the assumption of lower-level
convexity. This, remarkably, distinguishes our development of hyper-gradient
from the general AID-based bilevel frameworks since we take advantage of the
specific structure of RL problems. Moreover, we propose both model-based and
model-free bilevel reinforcement learning algorithms, facilitated by access to
the fully first-order hyper-gradient. Both algorithms are provable to enjoy the
convergence rate $\mathcal{O}(\epsilon^{-1})$. To the best of our knowledge,
this is the first time that AID-based bilevel RL gets rid of additional
assumptions on the lower-level problem. In addition, numerical experiments
demonstrate that the hyper-gradient indeed serves as an integration of
exploitation and exploration.

通过使用与规则化 RL 相关的固定点方程，我们以全一阶信息表征超梯度，从而回避了对低级凸性的假设，并提出了基于模型和无模型的双层强化学习算法，都被证明具有收敛速度 O (ε^(-1))。

基于超梯度的双层强化学习方法并避免较低级别的凸性

Bilevel reinforcement learning via the development of hyper-gradient  without lower-level convexity

Bilevel optimization, with broad applications in machine learning, has an
intricate hierarchical structure. Gradient-based methods have emerged as a
common approach to large-scale bilevel problems. However, the computation of
the hyper-gradient, which involves a Hessian inverse vector product, confines
the efficiency and is regarded as a bottleneck. To circumvent the inverse, we
construct a sequence of low-dimensional approximate Krylov subspaces with the
aid of the Lanczos process. As a result, the constructed subspace is able to
dynamically and incrementally approximate the Hessian inverse vector product
with less effort and thus leads to a favorable estimate of the hyper-gradient.
Moreover, we propose a~provable subspace-based framework for bilevel problems
where one central step is to solve a small-size tridiagonal linear system. To
the best of our knowledge, this is the first time that subspace techniques are
incorporated into bilevel optimization. This successful trial not only enjoys
$\mathcal{O}(\epsilon^{-1})$ convergence rate but also demonstrates efficiency
in a synthetic problem and two deep learning tasks.

通过 Lanczos 方法构建低维近似 Krylov 子空间，解决偏导数求逆问题，提高双层优化问题的效率，并在合成问题和深度学习任务中展示了收敛速度和效率。

LancBiO：基于 Krylov 子空间的动态 Lanczos 辅助双层优化

LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace

In this paper, we propose a new Hessian inverse free Fully Single Loop
Algorithm (FSLA) for bilevel optimization problems. Classic algorithms for
bilevel optimization admit a double loop structure which is computationally
expensive. Recently, several single loop algorithms have been proposed with
optimizing the inner and outer variable alternatively. However, these
algorithms not yet achieve fully single loop. As they overlook the loop needed
to evaluate the hyper-gradient for a given inner and outer state. In order to
develop a fully single loop algorithm, we first study the structure of the
hyper-gradient and identify a general approximation formulation of
hyper-gradient computation that encompasses several previous common approaches,
e.g. back-propagation through time, conjugate gradient, \emph{etc.} Based on
this formulation, we introduce a new state variable to maintain the historical
hyper-gradient information. Combining our new formulation with the alternative
update of the inner and outer variables, we propose an efficient fully single
loop algorithm. We theoretically show that the error generated by the new state
can be bounded and our algorithm converges with the rate of $O(\epsilon^{-2})$.
Finally, we verify the efficacy our algorithm empirically through multiple
bilevel optimization based machine learning tasks.

本文提出了一种新的基于 Hessian 的、不需要求逆的完全单循环算法 (FSLA) 用于双层优化问题，并理论和实践上验证了该算法的有效性。