Many strategic decision-making problems, such as environment design for warehouse robots, can be naturally formulated as bi-level reinforcement learning (RL), where a leader agent optimizes its objective while a follower solves a Markov decision process (MDP) conditioned on the leader's decisions. In many situations, a fundamental challenge arises when the leader cannot intervene in the follower's optimization process; it can only observe the optimization outcome. We address this decentralized setting by deriving the hypergradient of the leader's objective, i.e., the gradient of the leader's strategy that accounts for changes in the follower's optimal policy. Unlike prior hypergradient-based methods that require extensive data for repeated state visits or rely on gradient estimators whose complexity can increase substantially with the high-dimensional leader's decision space, we leverage the Boltzmann covariance trick to derive an alternative hypergradient formulation. This enables efficient hypergradient estimation solely from interaction samples, even when the leader's decision space is high-dimensional. Additionally, to our knowledge, this is the first method that enables hypergradient-based optimization for 2-player Markov games in decentralized settings. Experiments highlight the impact of hypergradient updates and demonstrate our method's effectiveness in both discrete and continuous state tasks.
Figures & tables
Figure 1: Four-Rooms Environment
Figure 2: Results on Four-Rooms Task ( BatchSize=100 ).
Figure 3: Results on Building Thermal Control.
Figure 4: Task Description and Results on ToyMarkovGame.
Figure 5: Results on the Bi-Level LQR Task.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Four-Rooms Task Results across Different BatchSizes ( 100,200,400,1000 ) and Entropy Regularization Parameters β ( 1×10−3,3×10−3,5×10−3 ). HPGD (oracle) uses additional trajectories of size 104 per outer iteration sampled from uniformly distributed initial states.
follower’s entropy regularization β
5×10−2
mini-batch size
64
actor learning rate
1×10−4
critic learning rate
1×10−3
leader’s discount rate γL
0.99
follower’s discount rate γF
0.99
target network smoothing factor
1×10−2
Appendix
Table 1: Hyperparameters in Toy Markov Game Task
Figure 7: Parameter Sensitivity in the Toy Markov Game Task
Figure 8: Histogram of the Leader’s Objective Value in the Building Thermal Control Task. This plots the 104 uniformly random leader parameters according to each leader’s discounted cumulative reward under the best response.
follower’s entropy regularization β
1×10−1
batch size per outer iteration
104
learning rate for function approximator
1×10−4
leader’s discount rate γL
0.9
follower’s discount rate γF
0.9
maximum Riccati iterations
5×104
Appendix
Table 2: Hyperparameters in Building Thermal Control
Figure 9: Results of n -Zone Building Thermal Control Task on Each Hyperparameter (Learning Rate in {10−1,10−2,10−3} ). The top figures show the leader’s discounted cumulative reward, and the others show the discounted cumulative values of the four components of the leader’s reward. The return and stability are aimed to be maximized; the costs are aimed to be minimized.
Figure 10: Histogram of the Cumulative Rewards of the Leader’s Policies with a Fixed Initial State on the Bi-Level LQR Task ( proposed : BC-HG , baseline : Naive-PGD (on-policy) ). The best policies in terms of the average performance for the proposed and baseline approaches are taken.
follower’s entropy regularization β
1×10−1
mini-batch size
64
actor/critic learning rate
1×10−1
leader’s discount rate γL
0.99
follower’s discount rate γF
0.95
maximum Riccati iterations
103
target network smoothing factor
1×10−2
Appendix
Table 3: Hyperparameters in Bi-Level LQR in Markov Games
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 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.
Reinforcement learning (RL) often has a hierarchical structure, where an upper-level (UL) learner selects model parameters and a lower-level (LL) decision-making process responds, naturally leading to a bilevel optimization problem. Most existing bilevel RL methods assume a single-policy LL Markov decision process (MDP), and therefore fail to capture competitive structures arising in applications such as incentive design, where multiple policies interact. We study bilevel optimization problems in which the LL problem is a regularized min-max zero-sum Markov game and the UL objective is optimized through the saddle-point equilibrium induced by the LL game. In this work, we propose penalty-augmented Nikaido-Isoda descent-ascent (PANDA), a penalty-based first-order policy-gradient method based on the Nikaido-Isoda function. By exploiting the min-max game structure, PANDA avoids computing UL hypergradients and does not require second-order information. We prove that PANDA converges to stationary points without convexity assumptions on either the UL or LL objectives. Moreover, PANDA reaches an ε-stationary point in O~(ε−1) iterations with sample complexity O~(ε−3), matching the best-known rates for bilevel RL with single-policy LL MDPs. Experiments demonstrate the superior performance of PANDA over closely related baselines.
Zihao Zheng, Irwin King, Songtao Lu
Department of Computer Science and Engineering, The Chinese University of Hong Kong · Shun Hing Institute of Advanced Engineering, The Chinese University of Hong Kong
Inverse reinforcement learning (IRL) aims to recover a reward function under which the resulting policy reproduces the behavior observed in expert demonstrations. A natural approach is to formulate IRL as a bilevel optimization problem, in which the inner level corresponds to policy optimization under the learned reward and the outer level measures the discrepancy between the induced policy and expert data. However, this formulation is computationally challenging in practice because the outer update requires a hypergradient involving an inverse-Hessian-vector product for the inner objective. We address this challenge by showing that, at the inner optimum, the Hessian of the inner objective is proportional to the Fisher information matrix of the policy, yielding a structured Fisher-based hypergradient closely related to Natural Hypergradient Descent. To address the resulting scalability bottleneck associated with large Fisher matrices, we approximate the required inverse-Fisher-vector product using a streaming spectral sketch, avoiding explicit construction of the Fisher matrix. We evaluate our approach against a first-order stochastic bilevel baseline across discrete- and continuous-control environments. The results demonstrate competitive policy performance and strong reward-ranking quality, while Fisher sketching reduces curvature-storage complexity and can improve computational efficiency relative to an explicit Fisher solver.
Nikita Sevriukov, Anna Barabanova, Uliana Gagarina +4