cs.LGMar 16, 2026

Sample-Efficient Hypergradient Estimation for Decentralized Bi-Level Reinforcement Learning

Authors: Mikoto Kudo, Takumi Tanabe, Akifumi Wachi, Youhei Akimoto

Organizations: University of Tsukuba · RIKEN AIP · LY Corporation

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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\text{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,1000100,200,400,1000 ) and Entropy Regularization Parameters β\beta ( 1×10−3,3×10−3,5×10−31\times 10^{-3},3\times 10^{-3},5\times 10^{-3} ). HPGD (oracle) uses additional trajectories of size 10410^{4} per outer iteration sampled from uniformly distributed initial states.
follower’s entropy regularization β\beta5×10−25\times 10^{-2}
mini-batch size64
actor learning rate1×10−41\times 10^{-4}
critic learning rate1×10−31\times 10^{-3}
leader’s discount rate γL\gamma_{L}0.99
follower’s discount rate γF\gamma_{F}0.99
target network smoothing factor1×10−21\times 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 10410^{4} uniformly random leader parameters according to each leader’s discounted cumulative reward under the best response.
follower’s entropy regularization β\beta1×10−11\times 10^{-1}
batch size per outer iteration10410^{4}
learning rate for function approximator1×10−41\times 10^{-4}
leader’s discount rate γL\gamma_{L}0.9
follower’s discount rate γF\gamma_{F}0.9
maximum Riccati iterations5×1045\times 10^{4}
Appendix
Table 2: Hyperparameters in Building Thermal Control
Figure 9: Results of nn -Zone Building Thermal Control Task on Each Hyperparameter (Learning Rate in {10−1,10−2,10−3}\{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 β\beta1×10−11\times 10^{-1}
mini-batch size64
actor/critic learning rate1×10−11\times 10^{-1}
leader’s discount rate γL\gamma_{L}0.99
follower’s discount rate γF\gamma_{F}0.95
maximum Riccati iterations10310^{3}
target network smoothing factor1×10−21\times 10^{-2}
Appendix
Table 3: Hyperparameters in Bi-Level LQR in Markov Games
More in this topic

Hypergradient Optimization

See all 12 papers

Explore similar work

CardsList

  1. Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity

    Jul 30, 2026Naman Saxena, Mudit Gaur, Vaneet AggarwalReinforcement LearningHypergradient Optimization

    Purdue University West Lafayette, IN 47907

  2. Bilevel Optimization over Saddle Points of Zero-Sum Markov Games

    May 26, 2026Zihao Zheng, Irwin King, Songtao LuGame TheoryZero-Sum Games

    Department of Computer Science and Engineering, The Chinese University of Hong Kong · Shun Hing Institute of Advanced Engineering, The Chinese University of Hong Kong

  3. Efficient Hypergradient Descent for Inverse Reinforcement Learning

    Aug 11, 2026Nikita Sevriukov, Anna Barabanova, Uliana Gagarina +4Reinforcement LearningGradient Descent

    HSE University Moscow, Russia