Contextual Bilevel Reinforcement Learning for Incentive Alignment
Authors: Vinzenz Thoma
Barna Pásztor
Andreas Krause
Giorgia Ramponi
Yifan Hu
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement Learning
Bilevel Optimization
Contextual MDPs
Environment Design
Model Design
Primary area: reinforcement_learning

Abstract: The optimal policy in various real-world strategic decision-making problems depends both on the environmental configuration and exogenous events. For these settings, we introduce Contextual Bilevel Reinforcement Learning (CB-RL), a stochastic bilevel decision-making model, where the lower level consists of solving a contextual Markov Decision Process (CMDP). CB-RL can be viewed as a Stackelberg Game where the leader and a random context beyond the leader’s control together decide the setup of many MDPs that potentially multiple followers best respond to. This framework extends beyond traditional bilevel optimization and finds relevance in diverse fields such as RLHF, tax design, reward shaping, contract theory and mechanism design. We propose a stochastic Hyper Policy Gradient Descent (HPGD) algorithm to solve CB-RL, and demonstrate its convergence. Notably, HPGD uses stochastic hypergradient estimates, based on observations of the followers’ trajectories. Therefore, it allows followers to use any training procedure and the leader to be agnostic of the specific algorithm, which aligns with various real-world scenarios. We further consider the setting when the leader can influence the training of followers and propose an accelerated algorithm. We empirically demonstrate the performance of our algorithm for reward shaping and tax design.

Contextual Bilevel Reinforcement Learning for Incentive Alignment
Vinzenz Thoma" ETH AI Center
Barna Pasztor ETH Al Center
Andreas Krause ETH Zurich
vinzenz. thoma@ai. et.az.i.ethh.com
barna.pasztore ethz.
krausea@ethz..co
Giorgia Ramponi
Yifan Hu EPFL & ETH Zurich yifan. hu@epf1. ch
University of Zurich
ramponi
carippon@izi..... @uzh. ch
Abstract
The optimal policy in various real-world strategic decision-maie problems de- pends both on the environmental configuration and exogenous events. For these settings, we introduce Contextual Bilevel Reinforcement Learning (CB-RL), a stochastic bilevel decision decision-making model, where the lower level consists of solving a contextual Markov Decision Process (CMDP). CB-RL can be viewed as a Stack- elberg Game where the leader and random context beyond the leader's is control together decide the setup of many MDPs that potentially multiple followers best respond to. This framework extends beyond traditional bilevel optimization and finds relevance in diverse fields such as RLHF, tax design, reward shaping, contract theory and mechanism design. We propose stochastic Hyper Policy Gradient Descent (HPGD) algorithm to solve CB-RL, and demonstrate its convergence. No- tably, HPGD uses stochastic hypergradient estimates, based observations of the followers' trajectories. Therefore, allows followers to use any training procedure and the leader be agnostic of the specifie algorithm, which aligns with various real-world scenarios. We further consider the setting when the leader can influence the training of followers and propose accelerated algorithm. We empirically demonstrate the performance of our algorithm for reward shaping and tax design.
Introduction
In Reinforcement Learning (RL), Markov Decision Processes (MDPs) [53] provide versatile framework for capturing sequential pacision-making problems across various domains such as health care [76], energy systems [52], economics [14], and finance [33]. A considerable amount of work has been devoted to solving standard MDPs [2, 62, 67]. However, many applications, MDPs can be configured on purpose or affected by exogenous events, both of which can significantly impact the corresponding optimal policies. For example, in a simplified economic framework, the optimal decision of individual household depends both on public policies and economic uncertainties [19, 34]. The policy maker turn has to make decisions, anticipating the best response differently- minded individual agents to its policies and exogenous events outside the policy maker's control.
To study such problems, we introduce Contextual Bilevel Reinforcement Learning (CB-RL), hierarchical decision-making framework where followers solve contextual Markov decision
Equal Contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

processes (CMDP) [32], configured by the leader. CB-RL is formalized as:
min F(x) [x( m (leader, upper-level)
(I)
where T argmax (T) (follower, lower-level),
where x represents the model configuration of the CMDP chosen by the leader, & represents the context that followers encounter, and the function JA denotes the (entropy-regulaaiized reward of the CMDP for a policy æ, a given model parameters æ, a context ç. and a regularization parameter A.
In our framework, the leader chooses z to configure various aspects of the CMDP, such as state transitions, the initial state distribution, and the followers' reward functions. Modeling the problem as CMDP instead of a standard MDP is essential when modeling situations where the environment is influenced by side information or personal perferences. For example, the context & can capture a wide range of real-world scenarios such as: (1) there is one follower, who responds optimally not only to the leader's 's chosen x but also to a side information E. such as weather or season, (2) there are multiple followers, each aiming to maximize their own utility, in which case represents different possible follower preferences, and (3) there are multiple followers, each facing an uncertain contextual variable, i.c., (i, 7)) represents the i-th follower encountering specific context P..
The proposed framework extends the concept of contextual bilevel optimization [37], where the follower engages in static contextual stochastic optimization rather than sequential decision-making. also expands upon traditional MDP model design [78, 15] and configurable MDPs [50, 55], where typically only one follower attempts to solve MDP, as opposed to CMDPs. We defer a full discussion of the related works to Appendix A. Beyond these fields, our framework finds various applications in Principal-Agent problems [8], RLHF [13, 58), dynamic Stackelberg games 127, 65], Security Games [60, 46). dynamic mechanism design [18], contract theory [41, 69], and tax design [19, 82, 34]. See Appendix B for the concrete CB-RL formulations of these applications.
Despite its wide applicability, to the best of our knowledge, there are no algorithms specifically designed for CB-RL. The closest is an algorithm from model design for MDPs [15], which can be adapted to our setting after some modifications. However, [15] requires the follower to solve the MDP deterministically using soft value iteration. Moreover, the full hypergradient is computed in each iteration, as part of which the leader requires access to the lower-level computations. Both of these aspects significantly restrict how well the method can scale to larger settings.
Instead, in this work, we propose a stochastic Hyper Policy Gradient Descent (HPGD) algorithm for the leader that solely relies on trajectory data from followers. The followers can use variety of possibly stochastic learning algorithms to find an approximately optimal policy for the lower-level CMDPs. The leader in turn is agnostic of the exact algorithm used, as the hypergradient is estimated using only trajectory samples generated from the follower policy. The fact that both the lower-level and the hypergradient computation are stochastic makes HPGD salable to large problem settings.
We show non-asymptotic convergence of HPGD to a stationary point and validate these findings through experimental evidence. In scenarios where followers grant the leader full control over their training procedure, as posited in prior work [15], we present an accelerated HPGD algorithm, designed to minimize the number of lower-level iterations.
Our Contributions
We introduce Contextual Bilevel Reinforcement Learning (CB-RI.) that captures wide range of important applications (Sec. 2). It is the first bilevel reinforcement learning framework that through the context & allows multiple followers and side information. We summarize the key differences to the previous literature in Table 1.
We propose stochastic Hyper Policy Gradient Descent (HPGD) algorithm that performs stochastic gradient descent on the upper-level objective (Sec. 3.2). Importantly, we are the first to estimate the hypergradient from lower-level trajectory samples instead of computing it exactly, while further providing convergence guarantees. Furthermore, our approach agnostic of the learning dynamics of the agent, enabling followers to utilize wide range of algorithms to solve the lower-level CMDPs. We only assume the leader can sample lower-level trajectories from an inexact oracle. For several widely-used RL. algorithms, we explicitly show how to use them to build the inexact oracle needed by HPGD. Noteably, we are the first to consider stochastic lower-level learning algorithms, such as soft Q-learning.

---

Table 1: Summary of Related Works in Bilevel Reinforcement Learning.
Context
Agnostic
Deter
Upper
Lower
Ps
Px
Multi
Side Info
Control
Stoch
Iterations
Iterations
Method
[15]
Control
Deter
{ (log(6 1))
SoftVVI
[13]
Agnostic
Deter
O
(log(6 1))
PG
[58]
Agnostic
Deter
O(8
(log(68
PMG
[75]
Agnostic
Deter
O
(1oog()1))
PMG
O(log(6 ')) Soft-VI
HPGD
Agnostic
Stoch
O(8
O(log(8-1))
NPG
Ō(6--)
Soft-Q
HPGD
Control
Stoch
088
O(log(8-1)
RT-Q
Multi: Multiple followers. Side Info: Side information. Context: CMDP instead of MDP. P.. and denote the dependence of rewards, transitions, and initial state distribution æ. Agnostic vs. Control: Whether leader influence the training of the follower(s). Deter vs. Stoch: Requiring full knowledge of hypergradient estimating it from samples. Complexity is based on [[>)( I & instead of ||V F/>)( < 5. "[15] assumes convexity of F in and considers F(x) min F(x) < 6. VI: Value Itcration. PMG: Policy Mirror Gradient. Pl: Policy Iteration. NPG: Natural Policy Gradient. Q: Q-learning. RT-Q: Randomly Truncated Soft Q-learning.
We establish the non-asymptotic convergence rate of HPGD to a stationary point of the overall objective-depplee the nonconvex lower-level problem (Sec. 3.2). When assuming full hypergra- dient information, i.e., deterministic updates, the outer iteration complexity of HPGD reduces to ( recovering previous results. Moreover, we discuss how to estimate the hypergradient if the upper-level loss function admits specific form of cumulative costs (Sec. 3.3).
When the leader is allowed to control the follwers' learning dynamics (Sec 4), we propose stochastic accelerated algorithm denoted as HPGD RT-Q (Alg 8). It greatly reduces the number of lower-level soft Q-learning iterations from Ö 2) to (log(ō ( )), such that we recover the rate for deterministic lower-level updates. For this result we leverage several techniques, such as mini-batches, multilevel Monte Carlo [29, 37], and importance sampling.
We demonstrate the performance of HPGD for principal agent reward shaping and tax design (Sec. 5). In certain cases, the stochastic updates of HPGD are beneficial as they avoid local minima. Moreover, HPGD needs fewer outer iterations compared to benchmark algorithms.
2 Problem Formulation
We consider bilevel optimization problem, where the follower solves Contextual Markov Decision Process (CMPD) and the leader controls the configuration of the CMDP. In particular, the leader chooses a parameter x E X C Rd and nature chooses random context & according
distribution
Pg- Together (x, {) parameterizes an MDP Mz.e, which the follower aims to solve. .Mr.e is defined by tuple (S, A, Tx.ç, P.. Pe.g, Me.g, 7). where S denotes the state space, A denotes the action space, R is the reward function, (.. :) S x S x A + j0, 1] denotes the transition
T=.e(-.)) S x kernel, fr.g indicates the initial state distribution, and 7 is the discount factor. The subscript x, implies that rewards, transitions, and initial state distribution depend on the leader's decision x and the context &. Connecting to previous works, for fixed x, MM, is a contextual MDP [32] with respect to &. For fixed &, M2.s generalizes configurable MDP [50]. Given Mz.s, the follower maximizes an regulae-re objective by choosing policy nagg, where Tz (a; 8) denotes the probability of choosing action in state
A x
(2) where 8o ~ fr ai 7( (:; 8t+1 Pa.e( 8t, ax) and H(;;s) = - -,, <(;; log (1; s). We
max (). = Esg [V (5o) = Exg
Ex
Σ r' (Fa,e(St, 01) + (T; 1=0
call X > 0 the regularization parameter and V Viz the value function. As standard in RL literature,

---

we define the related Q and advantage functions as: (x,,,((,, a) (x, a) + -BBr Pac((aa)) [V A. (6')] (r,a) (8, a) - Vi (1) =
1 a.. e (8,
= ex
Σ क (aa: () (8,,)())))
(3)
The unique optimal policy for (2) is given by ((;(((;)) exp(OX (s, A)) i.e., the softmax of the optimal Q-function [51].² Given z, g S, the leader in turn incurs a loss f(z, g E) E R. which it wants minimize in expectation over Pg. To do so, it needs choose æ align the follower's policy T with the leader's s objective. CB-RL can thus be formulated as the following stochastic bilevel optimization problem:
min F(x) == [els(a, 5)] (leader, upper-level)
where - = argmax (T)). (follower, lower-level)
Equation (4) is well-defined due to entropy regularization ensuring the uniqueness of 2 It further ensures " is differentiable, stabilizes learning and appears in previous works [15]. Moreover, the difference between the regularized and unregularized problem generally vanishes À - 0 [15, 26].
CB-RL captures many important real-world problems, including RLHF, dynamic mechanism design, tax design, and general principal-agent problems. We discuss these in detail in Appendix B.
3 Hyper Policy Gradient Descent Algorithm for CB-RL
In this section, derive simple expression for the hypergradient of CB-RL. We present HPGD and prove non-asymptotic convergence. HPGD can be combined with a large class of lower-level MDP solvers satisfying mild inexact oracle assumption. We show this the case for several popular RL algorithms. Furthermore, we present results for two important special cases of our problem: (1) when the upper-level objective decomposes
discounted sum of rewards over the lower-level trajectories. and (2) when the leader can direct the lower-level algorithm. We defer all proofs to Appendix E. and make the following standard assumptions on how x and & influence the setup of the CMDP.
Assumption 3.1. We assume the following conditions:
f is Lippschtt continuous and Smoothh in and æ, uniformly for all &. i.e.
[| [(12, 22, {o < Ly (I|æn x22 x221ox + || T2 12ll )
| - 0,, m2, 1) S Sy ([|æ) -x2llo + ||| - n2 720)
| (1. - f 22, ll S Sy ([|=) -22lloc + +||T1 - 721120)
E (r,,ç(s, a)l R. ||0 log
< Kn, (s, K2.
3.1 Hypergradient derivation
The leader's 's loss f depends on x directly and indirectly through Th. Therefore, the derivative of f with respect to x is commonly referred to as the hypergradient to highlight this nested dependency. It is possible to obtain closed-form expression of the hypergradient, using the implicit function theorem [28]. However, this involves computing and inverting the Hessian of the follower's value function, which can be computationally expensive and unstable [24, 47]. Instead, we leverage the fact that _ a softmax function to explicitly compute its derivative with respect to x, which is
given by (T m (a; s)0, A X,== (ir5((s (s, a) [15], where A = (0r, A,..., ,0,, A). Applying the Dominated Convergence Theorem to switch derivative and expectation, we arrive at Theorem 1.
Theorem 1. Under Assumption 3.1, F differentiable and the hypergradient is given by
dF(x)= Taif(z, E) + Ea-narat dx =Eg
02f(I, ((
Or Th A
(5)
dx
Av(s))
θT (a;))
where v is any sampling distribution with full support on the state space S.
For brevity, notationally drop the dependence of Tx.ę X.

---

Algorithm Hyper Policy Gradient Descent (HPGD)
Input: Iterations T, Learning rate a, Regularization X, Trajectory oracle Initial point 2o for to T 1 do
8~ Pe, s ~ V/ and T (::s)
A A (s, a) Graaiennsstimator((.....
o) (Algorithm
JF ae 5)
+ 1 0ef
O2 A,2, (x, (s.0)
Wiis
dx
8z
Au(e) Ox(a,))
dF
1t++ f-
de
end for
Output: ïT ~
The first term captures the direct influence of on f. and the second the indirect influence through Tz. For now we assume the leader knows f. and fz, g). It remains to compute An (s, a), i.e. the partial derivative with respect to z evaluated for a given policy. For this, cf. (3), we need O, Qxini (s,a), a). We derive an expression for the latter in Theorem 2. The proof adapts the analysis of the policy gradient theorem to account for the dependence of Pa,,, Marg and r'r, on Theorem 2. For given n, N. &, holds that:
dr ( + r d'log Pa.g((1411 Se, at) Vi ((1+1))
0, 0z ao) = E s,a
dæ
dx
Note, Theorems 1 and generalize existing results in model design for MDPs to CMDPs [15, 78).
3.2 HPGD Algorithm and Convergence Analysis
Computing the exact hypergradient computationally expensive and thus infcasible in larger settings. Instead, to minimize Fxx). one would ideally sample unbiased estimates of the hypergradient in Equation (5) and run stochastic gradient descent (SGD). However, the leader does not have access to TH.g and generally
control over the training procedure of the lower level. Instead, assume the follower adapts any preferred algorithm to solve the MDP up certain precision 8 and the leader can observe trajectories from the follower's policy. Such a setting is well-motivated by economic applications.
Assumption 3.2. For any Mes the leader has access to an oracle o, which returns trajectories
sampled from policy ~ such that Vx, VC E, [| T2 1
8².
We will show that Assumption 3.2 is relatively mild and holds for a variety of RL algorithms. Given access to trajectories generated by #rg.- the leader can construct estimator of AT. by rolling out = for T steps, where T ~ Geo - 7). We defer the construction (Algorithm 2) and proof of unbiasedness (Proposition 3) to the Appendix. Using this estimator, introduce HPGD in Algorithm 1. As F is generally nonconvex due to the bilevel structure [28], we demonstrate non-asymptotic convergence
stationary point of F, which matches the lower bound for solving stochastic smooth nonconvex optimization [1].
Theorem Using HPGD, under Assumptions 3.1 and for a S 11((2S)), we have the following:
dF()r)
E
0 aT + +8+a)
(6)
dr
For a a - and O(1VTT). HPGD converges to a stationary point at rate (11/VT)
Proof sketch. Using the smoothness of F and the fact that &n uniformly sampled from all iterates, we upper bound the left side of (6) by the sum of three terms. The first is [((r)) - min, F(x))/(aTT) The second depends on the bias of our gradient estimate, which we show is linear in 8. The last term depends on times the variance of our estimator, which is bounded.
D
5

---

To the best of our knowledge, Theorem is the first result that shows convergence when using stochastic estimates for the hypergradient. When the hypergradient can be computed exactly, the last ((a) term vanishes and we recover the deterministic convergence rates of previous works [15, 13, 58).
Another major advantage of HPGDD is that the follower can use any (possibly stochastic) algorithm satisfying Assumption 3.2 to solve the lower-level MDP, while the leader only needs access to generated trajectories. While Assumption 3.2 certainly holds if the follower solves the MDP exactly, for example with an LP-solver, we are interested in verifying it for common RL algorithms, which can scale to larger state and action spaces. In Appendix E.8, we prove non -oymmmytiooiic convergence to T2,5 for Soft Value Iteration, which converges at rate (log 1/6) (Proposition 5); Q-learning, which converges rate of (log(1/6)) (1)))/52) (Proposition 6) and Natural Policy Gradient, which converges at rate of Olog 1/8) (Proposition 8). Additionaly, we show Vanilla Policy Gradient converges asymptotically in Proposition 7. All these Algorithms thus satisfy Assumption 3.2, which makes HPGD scalable and widely applicable to settings where followers might use a variety of model-free or model-based algorithms.
3.3 Upper-Level Discounted Reward Objective
So far we assumed the leader knows O, f(,, æ, and (xr, In this subsection, instead, we assume f can be written as the negative expected sum of discounted rewards over the lower-level trajectories and show how to estimate the hypergradient from trajectory samples without explicit knowledge of 0 f T, {) and or dynamic mechanism design (cf. Appendix B), the loss I satisfies:
E) In many practical applications, such as reward shaping,
f(x, - Σ. E."
(7)
Here 'z, represents the reward of the leader, which is generally distinct from the follower's 's reward. The expectation is taken over trajectories induced by the lower-level " In this case, the leader does not know the partial derivatives of f but can still estimate the hypergradient from trajectory samples. The following proposition follows from similar anlysis as the policy gradient theorem.
Proposition 1. If f decomposes as in Equation (7), then dF(x) can be expressed as follows: da
dx Eg dr
Ene Ex an) Qx,
t=
(8)
di dTzze(8e,(a)) + Og log (2.g( dx
where for compactness, we slightly abuse notation to express ps.g(so) as Pa. 8-1.
Here Va,g, Φn.s are the (unregularized) value and state action value functions with respect to Tz.g- Comparing to Theorem 1, note that the expectation is over trajectories with starting states distributed according to the actual initial distribution fa,,g instead of some v. We discuss how to construct estimators for (8) in Algorithm 5 (Appendix D) and prove unbiasedness in Proposition (Appendix E.7). A special case of Equation (8) appeared in [15], where they consider model design for MDPs, that does not take into account contextual uncertainty or the possibility of multiple followers, i. when the support of & is singleton.
Accelerated HPGD with Full Lower-Level Access
Previously, assumed that the leader does not know the solver used in the lower level and queries trajectories from an oracle. However, in certain settings, such as model design [15], and dynamic mechanism design [18], the leader can additionally influence how the followers solve the CMDP. In this section, we focus on the case when the followers use a stochastic tranining procedure, which usually require a polynomial number of steps in terms of 8 8-1 to lear the optimal lower-level policy. We argue that if the leader has influence on the followers' training procedure, we can greatly reduce the number of lower-level iterations.
Let us assume that the lower level solved using vanilla soft Q-learning (Algorithm 4 in Appendix D). According Proposition 6 (Appendix E.7), the follower needs run T O(K2*) iterations

---

Table Bias, variance and lower-level iteration complexity of hypergradient estimators when using vanilla soft Q-learning and RT-Q.
Vanilla
RT-Q
Bias
((2-k/2)
((2-K/2) O(K)
Variance
((1)
Complexity
O(K2K)
O(K2)
to ensure that E6
2, T Ilo
2 and thus
E
dF(w) da
J.P.
O (22), where n²
da
denotes the learned policy after running T-thh Q-learning iterations and dFr denotes the corresponding hypergradient estimator.
To reduce the lower-level iteration complexity, we propose randomized early stopping scheme over the lower-level soft Q-learning iterations, denoted as randomly-truncatt soft Q-learning (RT-Q). The pseudocode is given in Algorithm 8 (Appendix E.5). We illustrate the high-level idea below.
Without loss of generality, consider a subsequence t == O(k2*) such that tx == T. Let da denote the hypergradient estimator, based on the T-th policy iterate TT. It holds that:
Fr
K
d Pta) dr
Fiv+1
Fex
FT Pix
Fr.
+ P
dx Fr, + Enape
dn
dx dr
dr
da
Pk.
k=1
where Pk denotes truncated geometric distribution, such that Pk ~ The above shows that d
d du Fr, + Pk d Fr estimator, the follower does not need to run O(22K) soft Q-learning iterations but in expectation only 1K11 pkle= O(K2) iterations. This implies that if the leader direct how the followers learn and observe behaviors sampled from their learned policies, we can generate hypergradient estimator with the same bias as da Fr but a much smaller lower-level iteration complexity. We formalize results in the following Theorem.
Fta with k ~ is an unbiased estimator of d da Fr. Using this
du
Theorem 4 (Improved iteration complexity using RT-Q). Using Randomly Truncated soft Q-learning (KT-Q) instead of vanilla soft Q Q-learning to estimate the hypergradient, we achieve the bias, variance, and lower-level iteration complexity results summarized in Table 2.
The idea has been previously studied for contextual bilevel optimization under the name randomly truncated multilevel Monte-Carlo [29, 36, 37J. The reduction in the iteration complexity generally comes at the expense of an increased variance of the hypergradient estimator. In [37], this increase logarithmic the lower-level problem is static optimization problem and samples generated to estimate the hypergradient are independent from the lower-level decision variable. This structure is crucial for controlling the increased variance of the hypergradient estimator. However, for CB-RL, rollouts generated from T² are used to estimate the hypergradient. These trajectory samples thus depend on the lower-level decision and is not possible to control the variance as in [37]. To address this issue, we notice that the major source of randomness in our hypergradient estimators stems
from the estimator O, A (s, a) computed by MnddientEstimmtoor (Algorithm 2). We control this randomness by sampling multiple trajectories with a random length, which is expectation O(1).
We further sample an action a once from z and then use it to compute both 0 A- (s, a) and On 4*
t (s, a), using importance sampling. Combining all these tricks with multi-level Monte Carlo, RT-Q achieves a variance of O(K), where K (log(8-1)
5 Numerical Experiments
We illustrate the performance of HPGD in the Four-Rooms environment and on the Tax Design for Macroeconomie Model problem [34, 15] that we extend to multiple households with diverse preferences. We use Adaptive Model Design (AMD) [15] and zeroth-order gradient approximation algorithm for comparison. Details on the zeroth-order algorithm are deferred to Appendix F.1.2. We note that AMD is not directly applicable to CB-RL as it was designed for solving an MDP without
7

---

1.0-
Upper-levd objective: F
0.8
0.4
HPGD
AMD
ZERO-ORDER
2000
4000
6000
8000
10000
Outer iterations: T
(a) Four Room State Space
(b) Upper-level objective values, over the number of outer iterations
Figure I: Four-Rooms State Space and Performance. Left: S denotes the start state while G and G denote goal states that are considered separate tasks. +-1 denotes the target cell to which the upper-level aims steer the lower-level MDP. Right: HPGD escapes local optima achieving higher performance than comparison algorithms.
context. We apply it with modifications described in Appendix F.1.1. To our knowledge, such zeroth-order gradient method is also the first of its kind for CB-RL. The main distinction between the algorithms the zeroth-order algorithm requires two oracle queries for each gradient calculation while HPGD and AMD require only one. However, the zeroth-order method only needs to observe the function value of the upper level while the latter two require first-order information about the lower-level contextual MDP. In particular, AMD assumes complete access to the MDP to calculate exact hypergradient while HPGD relies only on trajectory samples. Technical details about the implementation are deferred to Appendix (F.2).
5.1 Four-Room Hoor-Rooms Environment
Figure (Ia) depicts the lower-level CMDP for the Four-Rooms environment. S denotes the initial position while GD and G are goal states. We consider the two goal states as separate tasks and define in Equation (4) to be the uniform distribution
the of tasks, i.e., & ~ Uniform( 2)). We denote the goal state in each task by G The state space S is defined by the cells of the grid world while the actions are the movements in the four directions. In each step t, with probability 2/3, the agent moves to S1+1 following the chosen direction o, while it takes random movement with probability 1/3. The reward is always zero except when 8; G where r(st, az) 1, and the episode resets. To incentivize taking the shortest path, we set the discount factor as 7 = 0.99.
For the upper level, we let æ parameterize an additive penalty function P. S x A + [-0.2, 0.0] such that the follower receives reward of + Fz, as in the Principal-Agen problem [8]. The goal of the leader is to steer the followers through the cell marked with +1 in Figure la, denoted by s +1 while keeping the penalties allocated to states to their minimum. We define Equation (7) as
Fa,ç 01) 1 [..=+t)) 31 Σ
s.a Fl.aa.
where 1 is the indicator function and the second term defines the cost associated with implementing the penalties for the lower level. Note that there trade-off between the terms in depending on the context variable Ç. If 2, the desired change in the follower's policy can be achieved with small interventions since the shortest path from S G2 already going through the bottom-left room. When & 1, the leader must completely block the shortest path from S to G to divert the follower through the desired state. An efficient algorithm for this CB-RL problem therefore must avoid the local optimum of setting 0 and find the balance between the follower visiting state ++1 and implementing too large penalties in the CMDP.
Figure (1b) depicts the upper-level's objective function over the learning iterations with hyperpa- rameters 0.001 and / 1.0. HPGD outperforms both AMD and the Zero Prro-Order algorithms
We implemented our experiments end-to-end in JAX [10] its runtime benefits and ease of experimentation. code available https:/ //githubb com/ http//lagroupp//P/ 'The parametrization of this function is described in Appendix F.2.

---

HPGD AMD
ZERO-ORDER
-0
-10-
+1
10-1
Figure 2: Reward penalties given to the lower-level agent in each state of the Four-Rooms problem optimized by the HPGD, AMD, and Zero- (edorr respectively. HPGD efficiently steers the lower-level MDP when the task is to reach G while others are only successful in the case of G?.
Table 3: Performance over hyperparameters and À for the Four Rooms Problem averaged over 10 random seeds with standard errors. Algorithms perform on-par for most hyperparameters while HPGD outperforms others in few. AMD enjoys low variance due to the non non-stochastic gradient updates while Aero-Order suffers from the most variation.
Parameters
Algorithms AMD
B
HPGD
Zero-Order
0.001
1
0.91 0.088
0.58 + 0.000
0.59 + 0.059
0.001
3
0.51 0.006
0.51 + 0.000
0.50 0.005
0.001
5
0.46 + 0.006
0.46 + 0.003
0.46 + 0.007
0.003
0.95 = 0.002
0.000
0.91 0.048
0.003
3
+.73
0.39 0.000
0.40 0.028
0.003
0.29 = 0.003
0.000
0.32 0.002
0.005
1
#
1.28
1.15 + 0.026
0.005
1.01 + 0.002
1.13 0.004
1.02 0.027
0.005
5
0.87 + 0.003
0.97 + 0.009
0.79 + 0.027
in this instance in terms overall performance. The major difference in their performances that HPGD successfully escapes the local optimum of F = 0 after about 5000 steps and assigns all the additive penalty budget to states in the gridworld. On the contrary. AMD and Zero-Order converge to the local optimum of minimizing the implementation penalty term in F. They only utilize 38% and 26% the available budget -0.2 to divert the follower when g = 2 but neglect the goal state G
Figure shows the value of additive penalties F in the state space with the highest probability paths for the goal states. HPGD successfully blocks the follower when from S to G along the other rooms, while AMD and Zero-Order fail to assign sufficient penalty the upper corridor to cause the same effect. All algorithms are successful in ensuring that the shortest path through the bottom- room is going through the marked state.
and diverts its shortest path
The parameters À and were chosen for demonstration purposes highlight the capability of HPGD to escape local minima, as has been observed for SGD [72]. However, we emphasize that in the majority of the cases, the three algorithms perform equally shown in Table We provide the figures for the remaining hyperparameters in Appendix F.2.3. The slightly higher performance of AMD and low standard error among initializations is expected since this algorithm calculates the gradient of f deterministically while HPGD and Zero- rely on stochastic estimates yielding more variations. especially for the Zero-Order approach.
Tax Design for Macrocconomic Models
test HPGD on bilevel macroeconomic model evaluating taxation schemes based on [34, 15). The economic model consists of finite set of consumption goods i E (1,..., MM each with price p;. We choose M with unit prices. On the lower-level, each time step I, 8, denotes the accumulated assets of houschold which in turn chooses the number of hours worked ne

---

0.5
50-
HPGD
Upper level objectivs
HPCD 31
HPGD 32
Tax rates
HPGD
0.44
ZERO-ORDER
10-
ZEHO-ORDER
ZERO-ORDER, 1:
HPGD
ZERO ORDER
0.24
ZERO-ORDER
200
M00
Glil
800
1000
Outer iterations:
T
Outer Iterations:
(a) Performance on the Tax Design problem.
(b) Tax rates over the outer iterations. HPGD increases income tax HPGD quickly learn optimal tax policies quickly and distinguishes VAT rates according to preferences. while Zero-Order takes more iterations.
and consumption Ci.t- The environment updates the accumulated assets of the household as 8 = s1+(l=z)wn, Di=1 Ci, where is sampled from normal distribution with mean 0 and standard deviation ç. We clip the accumulated assets to the range [-100, 100] for numerical stability. The utility of a household is given by = ass;) 0nž + +I== (Ci,:/p(11 + +3))) where the product-of- consumption term corresponds to the Cobb-Douglas function [57] and ar.) ) the value of accumulated assets. We define P& as the distribution of households representing different socio-economic groups in the economy. In particular, we define two equal-sized groups with a (0.6, 0.3, 0.1) and (0.1, 0.7, 0.2) that model their different preferences over the goods in the economy and optimize their consumption behavior using regularized deep Q-Jearning [26] with X = 0.2. On the upper-level, tax designer is optimizing the discounted sum of social welfare by setting the income tax æ E [0, 3] and aalue-added tax y/ E [0,3] 3] for (I....,M) In each time step t. the social welfare is defined as U, = (st) + E=
==1 Ct,// (1 y.) + & Iog(E C,,8 (1 + vi) + wan,) where w(.) is the utility
of accumulated assets and Φ a positive hyperparameter.
Figure 3a demonstrates that HPGD can successfully optimize the hyperparameters even continuous complex problems. Benefiting from first-order information, HPGD converges faster than the Zero- Order algorithm and increases the secial-welfare by about 25%. Additionally, HPGD shows better qualitative results for the optimised tax rates in Figure 3b. HPGD swiftly increases the income tax to improve its objective by increasing tax revenues while sets value-added tax rates according to the preferences of the houschold groups. Houscholds on average prefer the second good the most, therefore, is set low to increase consumption and therefore maximize the second term in er while the third good is the least preferred for which the tax rate is increased since consumption is already low. While Zero-Ore Order shows equivalent performance on Figure 3a to HPGD it fails to distinguish goods when setting value-added rates. We defer further details on the implementation, hyperparameter choices, and additional results to Appendix F.
Conclusion
We introduce CB-RL, class of stochastic bilevel optimization problems with lower-level contextual MDPs that capture a wide range important applications, where a leader aims to design environments and incentive structures that align the followers' policies with the leader's upper-level objective. We propose HPGD, an pracle-based algorithmic framework, and analyze its convergence. Importantly, HPGD works with any existing algorithm that solves the lower-level CMDP to near-optimality, making it suitable in various regimes when the leader can only observe trajectories of followers. Moreover, HPGD is the first provably convergent algorithm in this area, which uses stochastic estimates of the hypergradient. We further propose RT-Q, a more efficient algorithm and study its bias, variance, and cost when the leader fully control the followers' training. Numerical results further validate the expressiveness of the proposed model and the performance of our algorithm. Future directions include I) applying HPGD in various real- world applications, 2) studying the setting when the lower-level problem is a game, and 3) studying single-loop algorithms for bilevel reinforcement learning with when the lower-level is just MDP.
5 '22 1.9 after 1000 iterations. The figure is cropped for better readability.
10

---

Acknowledgements
The authors acknowledge constructive suggestions from Niao He and Sven Seuken. V. Thoma and B. Pasztor are supported by an ETH AI Center Doctoral Fellowship. V. Thoma acknowledges funding from the Swiss National Science Foundation (SNSF) Project Funding No. 200021-207343. This work was supported as part of NCCR Automation, a National Centre of Competence (or Excellence) in Research, funded by the SNSF (grant number 51NF40 225155).
References
[1] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 195(1)4165-214, 2023, (Cited on page 5.)
[2] Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep reinforcement learning: A brief survey. IEEE Signal Processing Magazine, 34(6):26-38, 2017. (Cited on page 1.)
[3] Kavosh Asadi and Michael L. Littman. An alternative softmax operator for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, ICML'17, page 243-252, Sydney, NSW, Australia, 201 7. JMLR.org. (Cited on page 49.)
[4] Jan Balaguer, Raphael Koster, Christopher Summerfield, and Andrea Tacchetti. The good shepherd: An oracle agent for mechanism design. In ICLR 2022 Workshop on Gamification and Multiagent Solutions, 2022. (Cited on page 19.)
[5] Jonathan F Bard. Practical bilevel optimization: algorithms and applications, volume 30.
Springer Science & Business Media, 2013. (Cited page 19.)
[6] Tobias Baumann, Thore Graepel, and John SaylorT Adaptive mechanism design: Learn- ing to promote cooperation. 2020 International Joint Conference on Neural Networks (IJCNN) pages 1-7. IEEE, 2020. (Cited on page 19.)
[7] Jacob Beck, Risto Vuorio, Evan Zheran Liu, Zheng Xiong, Luisa Zintgraf, Chelsea Finn, and Shimon Whiteson. survey of meta-reinforcemennt learning. arXiv preprint urXiv:2301.0802 2023. (Cited on page 21.)
[8] Omer Ben-Porat, Yishay Mansour, Michal Moshkovitz, and Boaz Taitler. Principal- agent reward shaping in mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 9500-950,, 2024. (Cited pages 2, 8, 20, and 21.)
[9] Mathicu Blondel and Vincent Roulet. The elements of differentiable programming, 2024. (Cited on page 46.)
[10] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPPy programs, 2018. (Cited on page 8.)
[11] Seth Brown, Saumya Sinha, and Andrew J. Schaefer. Markov decision process design: A framework for integrating strategic and operational decisions. Operations Research Letters, 54:107090, May 2024. (Cited on page 19.)
[12] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563- 2578, July 2022. (Cited page 52.)
[13] Souradip Chakraborty, Amrit Bedi, Alec Koppel. Huazheng Wang, Dinesh Manocha. Mengdi Wang, and Furong Huang. PARL: A unified framework for policy alignment reinforce- ment learning from human feedback. In The Twelfth International Conference on Learning Representations, 2024. (Cited on pages 2, 3, 6, 19, and 20.)
[14) Arthur Charpentier, Romuald Elie, and Carl Remlinger. Reinforcement learning economics and finance. Computational Economics, pages 1-38, 2021. (Cited on page 1.)

---

[15] Siyu Chen, Donglin Yang. Jiayang Li, Senmiao Wang, Zhuoran Yang, and Zhaoran Wang. Adaptive model design for markov decision process. International Conference on Machine Learning, pages 3679-3700 PMIR, 2022. (Cited pages 2, 3, 4, 5, 6, 7, 9, 17, 19, 20, 21, 46, and 52.)
[16] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34:25294425555 25307, 2021. (Cited on page 19.)
[17] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In I. Guyon, U. Von Luxburg, S. Ben- gio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. (Cited on page 20.)
[18] Michael Curry, Vinzenz Thoma, Darshan Chakrabarti, Stephen McAleer, Christian Kroer, Tuomas Sandholm, Niao He, and Sven Seuken. Automated design of affine maximizer mech- anisms in dynamic settings. Proceedings of the AAAI Conference Artificial Intelligence. 38(9):926--633, March 2024. (Cited on pages 2, 6, 19, and 21.)
[19] Michael Curry, Alexander Trott, Soham Phade, Yu Bai, and Stephan Zheng. Learning solutions in large economic networks using deep multi-agent reinforcement learning. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '23, page 2760-2762, Richland, SC, 2023. International Foundation for Autonomous Agents and Multiagent Systems. (Cited on pages 2. and 19.)
[20] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. SBEED: Convergent reinforcement learning with nonlinear function approximation. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1125- 1134. PMLR,
10-15 Jul 2018. (Cited pages 19 and 48.)
[21] Stephan Dempe. Foundations of bilevel programming. Springer Science & Business Media, 2002. (Cited on page 19.)
[22] Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. (Cited on page 19.)
[23] Manfred Diaz, Charlie Gauthier, Glen Berseth, and Liam Paull. Generalization games for reinforcement learning. In ICLR Workshop on Agent Learning in Open-Endedness,, 2022. (Cited
on page 19.)
[24] Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3133-3144. PMLR, 13-18 Jul 2020. (Cited on pages 4 and 19.)
[25] Jakob Foerster, Richard Y. Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbecl, and Igor Mordatch. Learning with opponent-lcarinng awareness. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '18, page 122-130. Richland, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems. (Cited page 19.)
[26] Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized markov decision processes. In International Conference on Machine Learning, pages 2160-2169. PMLR, 2019.
(Cited on pages 4, 10, and 19.)
[27] Matthias Gerstgrasser and David C. Parkes. Oracles & followers: Stackelberg equilibria in deep multi-agent reinforcement learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the
12

---

40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 11213-11236. PMLR, 23-29 Jul 2023. (Cited on pages and 19.)
[28] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv: 1802.022400 2018. (Cited pages 4, 5, 19, and 34.)
[29] Michael B. Giles. Multilevel monte carlo methods. Acta Numerica, 24:259-328, 2015. (Cited on pages 3 and 7.)
[30] Tuomas Haarooja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In Proceedings of the 34th International Conference Machine Learning Volume 70, ICML'17, page 1352-1361, Sydney, NSW, Australia, 2017.
Jog.. (Cited on page 49.)
[31] Dylan Hadfield- Menell, Smitha Milli, Pieter Abbeel, Stuart Russell, and Anca D. Dragan. In- verse reward design. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 6768-6777, Red Hook, NY, USA, 2017. Curran Associates Inc. (Cited on page 19.)
[32] Assaf Hallak, Dotan Di Castro, and Shie Mannor. Contextual markov decision processes. arXiv preprint arXiv: 1502. 02259, 2015, (Cited on pages and 3.)
[33] Ben Hambly, Renyuan Xu, and Huining Yang. Recent advances in reinforcement learning in finance. Mathematical Finance, 33(3):437-503, 2023. (Cited on page 1.)
[34] Edward Hill, Marco Bardoscia, and Arthur Turrell. Solving heterogeneous general equilibrium economic models with deep reinforcement learning. arXiv preprint arXiv:2103.16977 2021. (Cited pages 1, 2, 7, 9, and 20.)
[35] Yifan Hu, Xin Chen, and Niao He. Sample complexity of sample average approximation for conditional stochastic optimization. SIAM Journal on Optimization, 3033):2003-2133,22222 2020. (Cited page 34.)
[36] Yifan Hu, Xin Chen, and Niao He. On the bias-variance-cost tradeoff of stochastic optimization. In Advances in Neural Information Processing Systems, volume 34, pages 12119-22131, 2021. (Cited on page 7.)
[37] Yifan Hu, Jie Wang. Yao Xie, Andreas Krause, and Daniel Kuhn. Contextual stochastic bilevel optimization. Advances in Neural Information Processing Systems, 36, 2024. (Cited on pages 2, 7, 19, and 27.)
[38] Yifan Hu, Siqi Zhang, Xin Chen, and Niao He. Biased stochastic first-order methods for conditional stochastic optimization and applications in meta learning. Advances in Neural Information Processing Systems, 33:2759-2770, 2020. (Cited on page 34.)
[39] Yujing Hu, Weixun Wang, Hangtian Jia, Yixiang Wang, Yingfeng Chen, Jianye Hao, Feng Wu, and Changjie Fan. Learning utilize shaping rewards: A new approach of reward shaping. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19931-1941. Curran Associates, Inc., 2020. (Cited on page 19.)
[40] Jiawei Huang, Vinzenz Thoma, Zebang Shen, Heinrich H. Nax, and Niao He. Learning to steer markovian agents under model uncertainty, 2024. (Cited page 19.)
[41] Dima Ivanov, Paul Dütting, Inbal Talgam- Tonghan Wang, and David Parkes. Principal- agent reinforcement learning, 2024. (Cited on pages 2, 20, and 21.)
[42] Sham Kakade. A natural policy gradient. In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, NIPS'01, page 1531-1538. Cambridge, MA, USA, 2001. MIT Press. (Cited on page 52.)
[43] Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. near-optimal algorithm for stochastic bilevel optimization via double-momentum. Advances in neural information processing systems, 34:30271-302888 2021. (Cited on page 19.)
13

---

[44] Jeongyeol Kwon, Dohyun Kwon, and Hanbaek Lyu. On the complexity of first-order methods in stochastic bilevel optimization. arXiv preprint arXivv2402.07101, 2024, (Cited on page 19.)
[45] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning. pages 18083-18113, PMLR, 2023. (Cited on page 19.)
[46] Joshua Letchford and Yevgeniy Vorobeychik. Optimal interdiction of attack plans. In AAMAS, pages 199-206. Citeseer, 2013. (Cited on page 2.)
[47] Boyi Liu, Jiayang Li, Zhuoran Yang, Hoi-To Wai, Mingyi Hong, Yu Nie, and Zhaoran Wang. Inducing equilibria via incentives: Simultaneous design-and-play ensures global convergence. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 29001-29000 -29013. Curran Associates, Inc., 2022. (Cited on pages 4 and 19.)
[48] Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A value-function-basee interior-point method for non-convex bi-level optimization. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6882-6892. PMLR, 18-24 Jul 2021. (Cited on page 19.)
[49] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global conver- gence rates of softmax policy gradient methods. In Hal Daumé IIII and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Pro- ceedings of Machine Learning Research, pages 6820 6829. PMLR, 13 13-18 Jul 2020. (Cited on pages 19, 43, 48, 51, and 52.)
[50] Alberto Maria Metelli, Mirco Mutti, and Marcello Restelli. Configurable markov decision processes. In International Conference on Machine Learning, pages 3491-3500. PMLR, 2018. (Cited on pages 2, 3, and 19.)
[51] Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 2772-2782, Red Hook, NY, USA, 2017. Curran Associates Inc. (Cited on pages 4, 48, and 50.)
[52] ATD Perera and Parameswaran Kamalaruban. Applications of reinforcement learning in energy systems. Renewable and Sustainable Energy Reviews, 137:11061 2021. (Cited on page 1.)
[53] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. (Cited on page 1.)
[54] Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approx- imation and g-learning. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3185-3205. PMLR, 09-12 Jul 2020. (Cited on pages 49 and 50.)
[55] Giorgia Ramponi, Alberto Maria Metelli, Alessandro Concetti, and Marcello Restelli. Learning in cooperooee configurable markov decision processes. Advances in Neural Information Processing Systems, 14-22808-228222 2021. (Cited pages and 19.)
[56] R. Tyrrell Rockafellar and Roger J. B. Wets. Variational Analysis. Springer Berlin Heidelberg, 1998. (Cited on page 46.)
[57] Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu. Watch and learn: Optimizing from revealed preferences feedback. In Proceedings of the figty- annual ACM symposium on Theory of Computing, pages 949-962, 2016. (Cited on page 10.)
[58] Han Shen, Zhuoran Yang, and Tianyi Chen. Principled -enslty-based methods for bilevel reinforcement learning and rlhf. arXiv preprint arXiv:2402. 06886, 2024. (Cited on pages 2, 3, 19, and 20.)
14

---

[59] Laixi Shi, Eric Mazumdar, Yuejie Chi, and Adam Wierman. Sample-efficient robust multi- agent reinforeement learning in the face of environmental uncertainty. arXiv preprint arXiv:2404. 18909, 2024. (Cited on page 19.)
[60] Arunesh Sinha, Fei Fang, Bo An, Christopher Kiekintveld, and Milind Tambe. Stackelberg security games: looking beyond a decade of success. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 5494-5501, 2018. (Cited on page 2.)
[61] Heinrich von Stackelberg. Marktform und Gleichgewicht. Klassiker der Nationalökonomie. Verlag Wirtschaft und Finanzen, Düsseldorf 1934. (Cited page 19.)
[62] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. (Cited on page 1.)
[63] Matteo Turchetta, Andrey Kolobov, Shital Shah, Andreas Krause, and Alekh Agarwal. Safe reinforcement learning via curriculum induction. Advances in Neural Information Processing Systems, 33:12151-12162, 2020. (Cited page 19.)
[64] Nino Vieillard, Tadashi Kozuno, Bruno Scherrer, Olivier Pietquin, Rémi Munos, and Matthieu Geist. Leverage the average: an analysis of kl regularization in reinforcement learning. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20 Red Hook, NY, USA, 2020, Curran Associates Inc. (Cited on page 21.)
[65] Jing Wang. Meichen Song, Feng Gao, Boyi Liu, Zhaoran Wang, and Yi Wu. Differentiable arbitrating in zero-sum markov games. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '23, page 1034-1043, Richland, SC, 2023. International Foundation for Autonomous Agents and Multiagent Systems. (Cited on pages and 19.)
[66] Kai Wang, Lily Xu, Andrew Perrault, Michael K. Reiter, and Milind Tambe. Coordinating followers to reach better equilibria: End-to-end gradient descent for stackelberg games. Pro- ceedings of the AAAI Conference on Artificial Intelligence, 36(5):5219-522 5227, Jun. 2022. (Cited on page 19.)
[67] Xu Wang, Sen Wang, Xingxing Liang, Dawei Zhao, Jincai Huang, Xin Xu, Bin Dai, and Qiguang Miao. Deep reinforcement learning: A survey, IEEE Transactions on Neural Networks and Learning Systems, 2022. (Cited on page 1.)
[68] Ronald J Williams. Simple statistical followig algorithms for connectionist reinforce- ment learning. Machine learning, 8:229 2229-256.12 1992. (Cited on page 51.)
[69] Jibang Wu, Siyu Chen, Mengdi Wang, Huazheng Wang. and Haifeng Xu. Contractual reinforce- ment learning: Pulling arms with invisible hands, 2024. (Cited on pages 2, 20, and 21.)
[70] Shuo Wu, Haoxiang Ma, Jie Fu, and Shuo Han. Robust reward design for markov decision processes, 2024. (Cited on page 19.)
[71] Li Xia, Luyao Zhang, and Peter W. Glynn. Risk-sensitive markov decision processes with long-run evar criterion. Production and Operations Management, 32(12):404944067 December 2023. (Cited on page 19.)
[72] Zeke Xie, Issei Sato, and Masashi Sugiyama. A diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. In International Conference on Learning Representations, 2021. (Cited on page 9.)
[73] Chang Yang. Yuiyu Wang, Xinrun Wang, and Zhen Wang. A game- theorrhc perspective of generalization in reinforcement learning. In Deep Reinforcement Learning Workshop NeurlPS 2022, 2022. (Cited on page 19.)
[74] Jiachen Yang, Ang Li, Mehrdad Farajtabar, Peter Sunehag, Edward Hughes, and Hongyuan Zha. Learning to incentivize other learning agents. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15208-1522 Curran Associates, Inc., 2020. (Cited page 19.)
15

---

[75] Yan Yang, Bin Gao, and Ya xiang Yuan. Bilevel reinforcement learning via the development of hyper-gradien without lower-level convexity, 2024. (Cited on pages and 19.)
[76] Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: A survey, ACM Computing Surveys (CSUR), 55(1):1-36, 2021. (Cited page 1.)
[77] Guanghui Yu and Chien-Ju Ho. Environment design for biased decision makers. In Lud De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 592-598. International Joint Conferences on Artificial Intelligence Organization, 2022. Main Track. (Cited on page 20.)
[78] Haifeng Zhang, Jun Wang, Zhiming Zhou, Weinan Zhang, Ying Wen, Yong Yu, and Wenxin Li. Learning to design games: strategic environments in reinforcement learning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI' 18, page
AAAI Press, 2018. (Cited on pages 2, 5, and 19.)
[79] Haoqi Zhang and David Parkes. Value- based policy teaching with active indirect elicitation. In Proceedings of the 23rd National Conference Artificial Intelligence Volume 1, AAAI 08, page 208-214. AAAI Press, 2008. (Cited on page 20.)
[80] Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Başar. Global convergence policy gradient methods to (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58(6))3586-366 January 2020. (Cited on page 46.)
[81] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, pages 321-384, 2021. (Cited on page 19.)
[82] Stephan Zheng, Alexander Trott, Sunil Srinivasa, David C. Parkes, and Richard Socher. The economist: Taxation policy design via two-level deep multiagent reinforcement learning. Science Advances, 8( 2600 2022. (Cited on pages 2, 19, and 20.)
16

---

Contents
Introduction
2 Problem Formulation
3 Hyper Policy Gradient Descent Algorithm for CB-RL
3.1 Hypergradient derivation
3.2 HPGD Algorithm and Convergence Analysis
3.3
Upper-Level Discounted Reward Objective
Accelerated HPGD with Full Lower-Level Access
5
Numerical Experiments
5.1
Four-Rooms Environment
5.2 Tax Design for Macroeconomic Models
6
Conclusion
10
Related Work
19
Applications: RLHE, Tax Design, Reward Shaping, Contract Design, and Dynamic Mechanism Design
19
Frequently-Used Notation
22
Algorithms
22
Proofs
24
E.1
Overview
24
E.2 Proof of Theorem
24
E.3 Proof of Theorem
25
E,4 Proof of Theorem 3
27
E.5
Proof of Theorem 4
33
E,6 Proof of Proposition
44
E.7 Auxiliary Results
46
E.8
Convergence Results for Popular RL Algorithms
48
F
Implementation Details
52
E.I
Baseline Algorithms
52
E.1.1
Adaptive Model Design [15]
52
F.1.2
Zero-Order Algorithm
52
F22
Four Rooms
53
E.2.1
Implementation Details
53
17

---

F.2.2
Hyperparameters
53
F.2.3
Additional Figures
................................
54
F3
Tax Design for Macroeconomie Models
59
F.3.1
Implementation Details..
59
F.3.2
Effects of lower-level regulariztiono
59
F.4
Computational Costs
59
18

---

A Related Work
Stochastic bilevel optimization has been extensively explored in the literature [21, 5]. In recent years, there is a pivotal shift to non-asymptotic analysis of stochastic gradient methods [28, 16, 43, 45, 44, 48J. [37] propose contextual stochastic bilevel optimization where the lower level solves a static contextual optimization. Our work generalizes to the lower level solving contextual MDP. This poses unique challenges in terms of hypergradient estimation and sample generation. Comparing to bilevel optimization, leveraging the special structure of CB-RL, we avoid Hessian and Jacobian estimation of the lower-level MDP when computing the hyper policy gradient, which is crucial for scalability.
Configurable MDP [50] is an extension of traditional MDP allowing external parameters or settings to be adjusted by the decision- makerr, often referred to as the configurator. Only recently some works studied the case where the configurator has a different objective than the agent [55]. However, that work assumes access a finite number of parameters that the configurator can control, while our model goes beyond this assumption. In addition, our model captures the variability and uncertainty that the agent could face in the same configuration environment.
Stackelberg games are a game theoretic framework, where a leader takes actions to which one or multiple followers choose the best response [61]. Several existing lines of work have studied solving variants of Stackelberg games. Examples include Stackelberg equilibrium solvers [24, 27], opponent shaping [25, 74], mathematical programs with equilibrium constraints [47, 65, 66), inducing cooperation [6, 4]. steering economic simulations [19, 82]. These works are either too general with limited implications for our problem or consider entirely distinct settings.
Multi-agent RL (MARL) studies multiple agents interacting a joint environment, i.e., their actions together determine the next state [81, 59). In CB-RL the lower level CMDPs can be seen as a special instance of MARL where the interactions the followers are restricted to jointly influencing the decision of the leader.
Bilevel RL studies how design additional rewards or change the underlying MDP achieve desir- able learning outcomes. Many applications are formulated as bilevel RL, such as environment design for generalization [22, 23, 73], reward shaping [31, 39, 40, 70]. safe reinforcement learning [63], optmizing conditional value at risk[71], and model design [15, 78, 11]. Previous work on bilevel RL considers a special case of our setting when there only one lower-level MDP [15, 13, 58, 75J. In particular, [15] focus on the case when the leader has control on the follower's training procedure. (58) further extend from one single lower-level MDP to lower-level min-max game. [13] and the concurrent work of [75] focus on the case when the leader only influence the reward of the MDP.
The introduction of the context makes CB-RL harder to solve as there can be many followers, each with its own preferences, and their best response policies change even for the same leader decision x when facing different contextual uncertainties. Multiple followers and additional side information are very common, which highlights the practical relevance of our work. In addition, the algorithms in the aforementioned works focus on deterministic updates on the upper and lower level decisions, i.e.. assuming access to the full hypergradient and performing exact policy gradient/value iteration, which both computationally hard and not feasible for large-scale practical applications. To the best of our knowledge, we are the first to provide convergence analysis for the stochastic case, when the hypergradient is estimated from samples and the lower level uses a stochastic update rule.
B Applications: RLHE, Tax Design, Reward Shaping, Contract Design, and Dynamic Mechanism Design
We list several applications of CB-RL below. For a clearer exposition, we omit the entropy regular- ization term at the lower level. However, we stress that some of the referenced works explicit use
entropy regularization [18, 15] or make overlapping assumptions such as unique optimal policies [13]. Additionally, for problems without explicit entropy regularization refer to [15, 49, 20. 26] who have shown that -reuuayere RL approximates the unregularized problem as + 0 both in the upper and lower level.
Reinforcement Learning from human feedback (RLHF) considers the setting where an agent tries to learn task from human feedback. The difficulty stems from the fact that the human feedback is
19

---

given preferences over two possible trajectories and not directly as a reward [17]. The feedback is of the form {To, TI.1} where To. Ti are two trajectories and I 0, 1 indicates whether To is preferred over 71 or vice versa. It has been shown that this problem can be framed as CB-RI,, where the upper- level tries to learn rewards that minimize the cross-entropy loss, between the actual and predicted labels, using the Bradley-Terr Model and the lower level finds the optimal policy with respect to that reward function [13, 58).
max D [(1 - log (To > -1(12) + llg P (T1 > To r=]]
N Σ
s.t. (T) argmax E
(5t,
1=
Here H is the time horizon. is the sampling distribution of trajectories using "2,c and
exp Ei=o ('ra
P T1/rx)
exp Σ o ( (s),aa) aQ) exp Ei
Note in the case of standard RLHF the context becomes trivial.
Tax Design for Macroeconomic Modeling considers a public entity setting tax rates and represen- tative households responding optimally by balancing their short-term utility of consumption and long-term wealth accumulation [34, 15, 82]. potential formulation of this problem as CB-RL is
max Bg 2.3
s.L. T. argmaxx E
Σ y 1=0
( W (8)) (s) +(
where x and y denote the income and value-added tax rates, respectively, and Φ defines the social welfare objective of the leader. The state 5t defines the wealth of a household while their actions decide their working hours and consumption each time step. The reward function r and rC define the households' utility functions for wealth and consumption, respectively. The value-added tax rate affects the consumption utility function C y. while the income tax changes the transition kernel modeling wealth accumulation, i.e., $t+1 Pa.e(*: St, az). represents the preferences of the households over several consumption goods and their productivity in this problem formulation.
Population Prineipal-Agent Reward Shaping considers a principal aiming to craft a non-negative bonus reward function r parameterized by x. motivate an agent [8, 77, 79]. Commonly, principal faces multiple agents that form distribution. Each agent has its own individual reward function rę. This scenario, termed population principal-agent reward shaping captured by our CB-RI. framework.
max T.
Σ (((((1,m2e(s)))
s.t. (-) argmax E
?2 (re(s, ((+)) + r (s x (s1)))
Here Eg denotes the expectation over the distribution of agents and the trajectories. The policy TT (+) the optimal response of the E-th agent to the composite reward function Tig + r The principal's reward is F(st, uz) when the agent visits the state action pair az).
Dynamic Contract Design studied by [41, 69] similar to the above reward shaping. Generalizing it to contextual setting, the problem consists of an agent of type & that incurs a cost eg (s a) for taking action a in state s. The principal in turn gets a reward r(s, s') for transitioning from state to s'. but cannot observe the agent's s action. It can however offer contracts 2(,, s') that get paid if the MDP transitions from state s to s'. These contracts are positive payments by the principal and are thus added to the lover-level objective and substracted from the leper-level objective.
o0 r' (r(se: st+1) x(55 (4.)))))
maxE 2
1=0
Σ r" (2(5)) cs {
S.l. (.)e() = argmax E,
20

---

Dynamic Mechanism Design considers the problem of a mechanism designer controlling an MDP for group of n bidders, who get a reward based on the observed trajectories [18]. The con- text & parameterizes the bidders' reward functions fi,g, which they report to the mechanism de- signer. The latter wants to learn a policy for the MDP and charge payments the bidders, to ensure eliciting truthful reward reports and also maximizize an objective L. e.g. the total sum of payments. In this setting, [18] propose to search for such a mechanism within the class of affine maximizers, as they guarantee truthful reports by all bidders. In these mechanisms, set of agent-dependent weights Zw,ú and state-action dependent boosts Ih is chosen by the mechanism designer, then policy is learned to maximize the corresponding affinely transformed social welfare Bec.a E (Ex-1 T,, ax)) + [b(s), as) and bidders are charged for the learned policy depending on their reported reward functions. Searching for the optimal mechanism parameters Tw.i and 2% to maximize L in expectation over &, subject to the constraint that the mechanism's s policy maximizes affine social welfare can be formulated as CB-RL. In this case Iw, and 24 are the decision variable, the context parameterizes the bidders' preferences and the affinely transformed social welfare at each time step the reward function of the lower-level MDP, as shown below:
min Eg[C (TÉ Twi [b)]
Tm + so(enna) Σ
s.t. TT Eo arg max E
Σ
Note, that all previous works in these application areas have either focused on the setting with single representative follower [8, 15, 41, 69] or presented a problem-specific algorithm that cannot capture our CB-RL framework in its full generality [8, 18].
The CB-RL framework is also related Meta reinforcement learning (Meta RL), that aims to leverage the similarity of several RL tasks to learn common knowledge and use it on new unseen tasks [7]. One way to formulate Meta RL problems is to find common regularization policy म for multiple tasks.
Σ /reest _ s.t. (+) arginax
1'ress Σ 1=
A KL(T(s))|((ss))
max EE
where & represents the distribution of multiple RL tasks and is the reward for the task indexed by Although the upper-level regularizer is different from intropy-reeularizzan
still results in
unique softmax policy of the form t5. (s, a) exp (0..= + log(# (s..)) [64]. Moreover, in
Meta RL the leader does not change the transitions or rewards, but the target policy म, that goes into the KL regularization term of the followers.
21

---

C Frequently-Used Notation
Table 4: Table of notation used in the paper.
Notation
Description
æ
Upper-level decision variable/leader's decision
{
Contextual variable
Ma.g
MDP parameterized by x and ç
S
State Space
A
Action Space
Tz.8
Reward function
Pa.e
Transition kernel
Initial state distribution
y
Discount factor Trajectories of MDP
Follower policy for Ma,e
(x)
cntropy-regularieen lower-level objective function Initial state
((::))
Entropy of policy state
V Wi (s)
Value function
e (s,
Q-function
A A
Advantage function
THE
Optimal policy maximizing xx,,,{(T)) (dependence on is droped)
Oracle policy with distance 5 from "2,g
"ns
Follower policy after performing ty learning steps Upper-level loss for specific context g Upper-level loss function Regularization parameter Lipschitz continuity parameter of f
F())
A
L5
Sj
Smoothness parameter of f
R
Upper bound absolute value of reward function
K1,
||0, log (s.e(8/: 8, a)ll < K1, 1100r,,((* (8, < K2.
a)
|2
8
Oracle inaccuracy, such that Va, vg E. T x2
5 82
RT-Q
Randomnly-Truncatee Soft Q-learning Contextual Bilevel Reinforcement Learning
CB-RL
HPGD
Hyper Policy Gradient Descent
Used to define variance and complexity of RT-Qneu Sampling distribution to estimate hypergradient m == min, v())
v
m
test
0,A (s,a)
Estimate of Advantage derivative, obtained from Algorithm
0 a))
Estimate of Q derivative, obtained from Algorithm 2.
O²Q
Smoothed Q derivative setimate, 0²Q²'* + Di O₂Q=*' (7)
F
Upper-Level reward function for special loss function (cf. Section 3.3) Unregularized upper-level value and Q functions for F Geometric distribution with parameter 7 Soft Bellman optimality operator
V.Q
Geo(1 -)) T
D Algorithms
We give the pscudocode certain algrrttmsstottissppooclusss mentioned in the main text.
22

---

Algorithm 2 Gradi Ett.eeentttttmt...........
Input: Ç. state action trajectory oracle
TQ, Tv ~ Geo(1 7), Geo(1 70.6)
Qo t SampleTrajectorr(00 start (s, a). length = Tq + TQ +1)
t SampleTrrajectory(...ta start 8, length = Tv + Tv +1)
+ Ei di rs
72
)
Ta E Iottot1 T-y log P( To P
Lt=lo+1 -(t-To- (r(s; 2e ,0)) + AH (T((:::)))
OTa
(s) Er Oar(s
a
r log P( 18 ~Ty+Ty+1 / (r(s)) ,.T + (H(
Tt=Tv+1
Output: 0gA(s,a) + (xQ(s,a) - 0zV(s)
Algorithm Soft Value Iteration
Input: Number of iterations T
2: Result: Approximation Va = policy TΛ = "ं
3: Initialize V/1 -=
4: for (. = 0 to 7 do
5: for 8 do
6: for a E do
7: Qx(s,a) a) = r(s, a) + 7Bslas [Va(s')
8: end for
Vnew, Alog (Eee exp (2(s.0))
9:
10: end for
set VA View,A
12:
end for
(x.((x(e.o)AA)
T Σ, (x.(()(sa)/A))
14: return V,, and Nx
Algorithm 4 SoftQlearning(T; TB. {auhe20)
1: Input: Number of iterations T, Behavioural Policy nn, Stepsizes (ar)220
2: Result: Approximation Qx s Q policy πa RV π
3: Initialize QA 0
4: Initialise
5: for = 0 to 7 do
6: Sample (
7: Observe next reward r(st, a) and state s441 P(-1st,
8: Qx(st, Qx(s), ar (r(st, a) >Alog Ewee exp (Qleerraa))
9: end for
TQ(a;) s) + Enr (x.e)A(
exp(Qx(els)/A)
11: return Q3 and oz
23

---

Algorithm 5 Becommppableerrrcdenteeeeee
Input: Ç, x, initial distribution Mu.c- oracle o
T, ~ Geo(1 - 7), T" ~ Geo - -0065)
(80: 00:000
00, ..000..:........................ 8T+T" aT++' SampleTraaecctor((..ttaa start Mr,g, length T + T)
A 2. aTT, (5 07,
A.
dF
EL= ((t, ai) + x(1-7)
1 Oz A.
(ST. ar) Ev=r av)
da
+ Og log P(ST, 11 -1=T
T+I
1t' -T) ( av)
dF Output: de
Algorithm 6 Vanilla Policy Gradient Algorithm
Data: Initial parameter lo. initial state s
Result: Approximate policy 1Tg
for = 0 to L do
Sample T ~ Geo(1 - 7)
Sample trajectory (So, au $1
11, ar) using policy To.
Sample T ~ Geo(1 7²)
Set 8g 8T and āg aT
Sample trajectory (oo; un, 81, ... -1, 8T Fr arr)) using policy wa Determine step-size a.
(.. - log (ar|st) ) 2N=0 7t/ /2 Fr
8 = 8: - (B).
end for
E
Proofs
E.1
Overview
In this section, we provide proofs for the presented theorems and propositions. We provide the proof of Theorem 1, deriving the hypergradient of function F(zz;; the proof of Theorem deriving the derivative of the action-value function with respect to .;; the proof of our main result, Theorem 3, which shows convergence of HPGD to a stationary point of F(z).
For the propositions, we show how to estimate the upper-level gradient if f is decomposable in the proof of Proposition 1; In Proposition we show how to compute the gradient of the optimal policy with respect to x; the proof Proposition 3, which shows we can achieve unbiased estimates of the advantage hypergradient; and the proof of Proposition 4, which shows the same for the special case when f decomposes.
We state and proof Propositions to 8 which show convergence in La to the optimal policy of soft value iteration, soft Q-learning Vanilla Policy Gradient and Natural Policy Gradient respectively.
Lastly, we prove Theorem 4, regarding the reduced iteration complexity of RT-Q claimed in Section 4.
E.2
Proof of Theorem 1
Proof. The proof relies on on three main ideas.
Show that Dominated Convergence applies, i.e. all derivatives are uniformly bounded by integrable function. Thus we can exchange derivative and expectation and compute the derivative of f instead of F.
2. Use Proposition to get an expression for the derivative of the optimal policy with respect
to
24

---

3. Use importance sampling with some distribution v to get an expression of the hypergradient that we can cheaply sample, instead of having to multiply two matrices with size [S] |A].
By Proposition 2, it follows that
@m dr
2 -
Oz 0x (s.
X
2 K2 KKKKI
A1 7 (1 - 7)
As the partial derivatives of f are bounded by J (cf. Assumption 3.1), we can apply the Dominated Convergence Theorem to get
0, [f(x, T x {)] E [. (2, E)
0 f1f(z, π e
02 02f(2, m2 Ox' dm
dx i (1x E.
θTZ Ix
025(2, m) 0 (a; 8)
dx
On (a;8)
dx
8,0
S1r TH + dr
025(s, (T)
E
dn (a;s) x T (0),
(9)
Or O2f(2, Th R
E
Es 2.g
Og Og A (s,
Ōx
Av(s) (a; 8)
where we use Proposition 2 for eq. (9) and importance sampling with any distribution v in the last equality, as long as v has full support on S. Further, we note that (
E |sti, (R)
0n
and dm P5
E Mat (i Hence, we just explicitely write out the matrix multiplication for the second equality. The second equality follows from the multivariate chain rule and the first equality from the Dominated Convergence Theorem.
E.3 Proof of Theorem 2
Proof. Theorem 2 is important as 0g.45..r. (s, a) and thus 0,QT, (s, a) allow us to compute da do (ef. Proposition 2). We will prove the theorem using an induction proof, which follows the analysis of the policy gradient theorem. However, instead of at each timestep (u);;:)) depending on a policy parameter 0, it will be the transition Pa.g(Se+1) 8t, (x) and reward ra,g (8t, az) depending on æ. Also note that we only consider the partial derivative with respect to evaluated at some policy which in the case of T
In the following, will show by induction that
dQK,ne(ssa)
ΣΣTpas PP.es((8, s', (dras(ss,d) dx t=
d.P. dP dr
Vr
dx
where (r,g(8, a - 8', a'; is the probability that the Markov Chain induced by æ, starting from reaches 8', after t steps. Note, the formulation is equivalent to the one stated in Theorem 2.
The proof follows the analysis of the standard policy gradient theorem. We drop here the dependence on & and & to simplify the notation. Assuming that Q (s, induction that for all N holds that
a) is differentiable for all s, a, we show by
dQx a) dx
dr(s'sa') a')
dP a²) V ((())))
p'p(s + +d,dttt.))
Σ
dr
dr
1=0 s'
(10)
p(s, 3, + L, (3,
+ ++1
dr
25

---

The claim then follows as n - oc.
Base case (n = 0)
It is easy to check that
dQT(,,a) a)
d
r(s,a) + Σ P(6:),0)V5(6))))
dx
dr
d
r(s a) + E(4 P(s Pl dx
d
vi(6))
dx
dx
r(s,a) a) + Σ [ (
d dr
Σ T(a'; ss) d
+ p(s':s, a)
dr
dx
dr(('saa) dx
dP(s" a') Vx V% (6"))
Σ
1'p(s, a d';,,
r Σ
dx
t= s'
8²
(3. dæ
+
Σ 8.0
p(s,a
We use the definition of QT a) in the first equality. The second follows by the product rule. The third equality follows by the definition of the value function. The last equality comes from rearranging terms.
Induction step (n = n n+
Assuming eq. (10) holds for n we show it holds for n + 1:
dQT a)
dr((',a') dx
dP(s"; s a²) V/ (s")
7'ss,, + s',d'tt,
+
dx
dx
s',''
(3,
+ 1 n+1
p(s.a + 8, 1,
dx
dr((',a') dx
dP(s"; 8 (s(("))
7 ppss a + s'ditt)
+
(s")
dx
1=0
8"
+ t a+1
p(s.u - +, 1,
r(5,0)) +7 Σ
de
dr((',a') dr
dP(s"; S a')
pppss s(dit,))
V (s")
dr
t'O'''a'
Σ d
+ + a+1
3,
T(, + +
(3)
de
dx
3,
+ P(':; ④)
n ((,'33' 3') d
dr Qx(3,aa)
á
R+1
dr((''a') dx
dP dP(s"; ;",,'') a')
Σ
psss a 8 ,d;;,,
+ Σ
V (s"))
dr
(3)
+ 22 +2
p(s, a + +,,0;++222
dx
3,
The first equality is simply the base case. The second equality follows from the definition of the f-function. The third equality follows from the multivariate chain rule and the definition of the value function and the last equality is again rearranging terms.
D
26

---

E.4
Proof of Theorem 3
Proof.
By the smoothness f. we use the following bound from [Lmmaa 1 I
1/
dF()T) dr
2
2(F(z)) min, F(x))
T
dF()))
(f,)))
E
S
L
E
(11)
of
da
dr
(1)
(2)
dF(at))
(x))
+ E
dr
dr
The term naturally decomposes into initial enror divided by T (1), bias term (2), and variance term (3), which decreases with the stepsize a.
For (1) we do not need to simplify any further.
To prove our claim, we need show that (3) is O(1), and that (2) ( The latter is the main challenge of this proof.
Let us begin by bounding the bias term (2). The goal is to show that it can be upper bounded by sum of terms, which are all linear in -2 22
dF dF(x))
(Fs))))
IF
dx
dx
00
(x.)
@if(Er, T =
1 O2f(ar, (2 θT(S,a)
d A (s. a)
E
Eg,0
+ Ey Elanrene
E
dx
dx
Av(s)
dx
[i for E
Ö1f(I T E E) dx
E
dx
(A)
Ø2f(z, +) (a; 8)
02f(2, T x) Or A T
Σ
(a; Os
A (x (aa))))))
(s,(()
(u(s)
OT (a;8))
where the first equality is by definition and the first inequality follows from the trinalge inequality and d we further use the fact that de Ax,rg is an unbiased estimator of de A shown in Proposition 3.
(A) is relatively easy to bound. Indeed by the smoothness of f Assumption 3.1), it immediately follows that
(A) S Ex, of Sy || T = Nee.slaa) s Syø.
To bound (B) again use the triangle inequality to decompose:
(B)
1
Σ
T2,g(a;
02f(x, 5)
A This O
Xine X (8, - (a;();))
02f(2,
02f(E, I 22. 0,1 A
As((s)
Omo (a;
O2f(e, 52 O
< 2
Σ
TH.e (a: Th Fr-gla;s)l
O. the (
\u(s)
(n)
1 + 21.0
1
Σ
(a)
02f(1, π 5) On (a; 8)
O₂ Tone Te
A
(s,
02f(2, TO 2:
O2 0g - A (o)
Au(s)
OTy 2 (a;8)
27

---

aa) is relatively easy to bound. We have
02 v x 5)
BS." 2x
AA66
P Ae (s,a)
{v((8)
@m 81)8)
B5, 1x
Av(s) |A|ōL,
Oz A
X,055 (s,
< B Av(s)
|
02 020%i
(s, (xx0))(((
where the assumption the oracle in the first inequality, that is Lipschitz continuous in the second inequality, and that OO, V. (0)
< 5 Te. (8, a) aoc in the third inequality. Note that:
(R + Alog [Al)
(s)
1-7
since the entropy of any policy is bound by log |A| (which follows from Jensen's inequality). Using the definition that
80
dr dr ax)
+ r+1 dloog (s St, at)
o2 0 (8,0) = B
V
Vx (86-1)
dx
dx
thus holds that
K2
Kí Ki Alog 141)
$ 1 1-7
+
(12)
71-
Letting m min, vs)), we thus have
(1
K2
K2 llog (Al) ) (1-
S
|A|LL
+
Am
1-7
For (b) we further simplify using the triangle inequallity:
Ō2f(1, -T g: 5)
S2f(1, No 5:
(b)
E Am 21.0
A (s,
A,A A
rn (158)
OT O (a)8)
021 n ()
02f(I, 2o E1
E
00. F
Xm $2.00
ÔT UT (a;
Om OT (a;
02f To E: Om (a)
+
EE
| Te (s, dz A (s,
Am
(i)
Similar to (a), we can bound (i) using the smoothness of f (Assumption 3.1):
St Am
( K₂
KR Alog (A))
ii
+
1
(1 71
is the tricky part of this proof. We first need to show two intermediate results. First, we bound the difference entropy between two policies and the difference in the regularized value functions of two policies. Once we have
Bounding (ii) and in particular
A, [ T2 (.: ()) Oz A fi (s, a)
28

---

that, we can tackle |aa4 "i x, (s, - 0,4 0, (s, a) u
For the entropy, we denote by 4 == ain T (a; s) the minimum probability of playing an action in any state under the optimal policy. Recall that $, |s,,((,a)] < R and that 0 I H(; I log |A| (by Jensen's inequality). Thus we have
R
R Alog |A| s &i (8, S
1 1-7
1-7
Because (s:a) x ex (s)aas/aaa) /A), it follows that
exp( X(1->)
-H
4 2
> 0.
AA| exp(
R+A log (d1) X(1-7)
We assume now that 5 is sufficiently small, i... 8 S /2, such that 11/2 I min (a s). We need to have such a lower bound on the policies, touse the fact that the log function is Lipschitz continuous with parameter 1 on an interval (a, oc) for any a > O. Hence we have
[ (s) H (
Σ
Tze g log lo
Σ m (a; 8) log (
20
Σ _ T2.1lon |10g + |llog Th. - log 1 1
$ |A|| log 4 1/6 + 2.. 6.
4
We use this to bound the difference in the value functions of t and 22.5.
(s) V TimE (s)
The (a; 8) s) ti (s,a) 2 (0
+ + +>|||((*t,50)) - -H
Σ
(T 8) )) ie (s, - (a; 8) 22. (s, (s.
+ 1o (141ll0811+
2 - T
<
Σ T sa;
(s)
(s,a)= 2x*x((,,0)
(5 (s. |100 + to [AAlllog11 + 7
+ Σ
| (a;s)
(a;s)
bo 20
[Allllog 41| + T, 8| 1-7
R
||| V (s) Vn (s)
<Ao
+
X8
(IAIl log 41
+
2
8|
+
(1 11-7) 7)2
(13)
The first inequality follows from the definition of the regularized value function and the triangle
inequality. The second inequality follows from our derived bound the difference of entropies. The third inequality is agian using the triangle inequality and the fourth inequality is bounding the Q-function using that the rewards are upper bounded by and that (s, a) = rz,g(s, a) +
Pa.sssa..)):s..) VT,,g(s)) The last inequality then follows by iteratively plugging in the inequality for the term y (s) V (s) which gives geometric sum. We employ similar technique to bound (ii) using the above results:
29

---

02 (2 To
E Am
(od
21.0
I/f E Am
Oz A Nari (8; 0) 0r
0 (8,
L 2 Am
1 Ti A.n (8. 2 a0)laa)/__
+ LAl
K2 I-7
K1 + A Aogg (Al)
|| marelloo)
(1 -1-78 7)²
Here the first inequality follows from the Lipschitz continuity of f. For second inequality we use the definition of the advantage function, the triangle inequality and the following inequality:
Og V A.
(s) Ox A,rrE (8)
Σ T T (a; 8) 1r Fo Q..:
Σ (a)) Q2e
Σ maa T e s)) On Q (s, Σ TTn (a; (0) (o. 0 8.
A| K1 R + Alog (A))
(1 -)- || | Tl + 100 d 0, (x22
(14)
where the last inequality follows from the trianlge inequality and Equation (12).
We bound the difference in Q Q-function derivatives as follows:
O₂ Q ( 0,Q (
dra.(s',a') dx
dPx, ( a²)
r' P a','',,,
+ E
dx
(ra.e(d',a")
d. ( ,a)
Y Pe,g(s,a + + s','';t, )
+ E
dx
dx
1=0 s',
8/1
dr ((,,)(),a)
+7 Σ
dP dP a)
(s)
dx
dr
2' Pe,e(8, d';''',, T
dress(s,a)
+, E
de2,
V (x))((""))
dx
dx
1=1 s'
8/1
dr (s,,)(
dP dPa.e(s'is, a) dr
dx
dra.e(s'aa)
d.P. (
Pa, ( s',''' (
+ )
V
(5"))
dx
dx
1=1 s',"'
dP ( ;8,0)
Taie (8))
T Vx(e(((")) (5')
dr
+
Σ
P(s'; 8, a) (a',
I' Pr.e (s' (s',aa - d"
8'."
t= o'
dr drz,s(s",,nn a")
d.P d. a")
V Vi (8"))
dx.
dx
A
Σ p()
(a's
Σ
P ,",a";t,
t=0 a'
30

---

drzg(s",a") ad)
d dPo.(s" ,a")
Vi (5")
+
dx
dæ
dP n. ( ;0,08800)
ViTee Vi (8')
dx
+ 7
Σ
,00) Ox ())
8'a0
P(s
dP a (8' 8,00 u)
5 Σ
F V
Aor (s')
dx
+
0 2
Σ P(s';s,a) 8'
(
Tans (a' 8'1l
+ Σ a) 1 s'aa'
On 0xig
where the dots indicate multiplication the linebreak. The first equality follows from plugging in the result from Theorem 2. The second equality follows by taking out all terms with t t= 0. The first inequality uses the triangle inequality. The second inequality plugs back in the definition from Theorem 2. The last inequality follows from the triangle inequality again.
Taking the expectation, we thus get: BS
1 (s, (i a) [1m]
[ogl 1-7
log 41|
K₂
KG + Alog [Al)
)
S1
+ 1-
+
(1 - 7)3
(1 7)
(ia. ,d)) - Oz -2 (8', aa) [|]]
+ +BB
A8 [IAll 4
7
8|A||
+ K₂ + KG Alog (Al)
1
1-7
(1-7)²
-)²
> (IAI) log// 4 + 1-?
87 - 1-7
A (1 - 7)
1-7 + Ki + A log (Al)
K₂
+
(1 71-
where the intermediate result from before to bound the difference between the value functions, the upper bound on the Q-function derivative shown in Equation (12) and the assumption on the oracle get the first inequality. The second inequality follows from the the resulting geometric sum and the last equality is just rearranging terms to show the linearity in
Using this result, we can now bound (ii):
(lAI) log 4/ +
2L,00 (ii) Am
A
K₂ }(11+)
(
Ki + A Alog (Al) (1 7
|
+
-))
1 1-7
- 7)2
Kg
K1 Alog (Al)
+ |Al
?
(1-7)7
With that we are done decomposing (2). Combining everything, we have the following bound:
dF(x.))
dF(x))
(2)
E
dx
dr
31

---

+
(b)
+ +a)++
SSy6 + 2
K2
K K1(R+ + Alog (AB))a))
251
K2
KiRR+ Alog (A))
LAJLL
1-7 +
Am
7-
(1 (1-7)²
dm
(1-7)2
(1All log /11
2L,
A
+ (
K₂
KI + -lllog (Al) )
[S]Ki
+ Xm(1 -7)
+
1 1-7
(1 - ?)²
-17
(1 71-
K2 +
K1 K1 + KI Alog (Al)
|AA
71-
-0(
With that we have tackled terms (1) and (2) in Equation (11). It remains to bound the variance, i.e.
term (3). can show that (3) (1) then the last term in Equation (11) is O(a) as claimed and we are done. Indeed, bounding (3) is relatively easy, as all important terms are bounded by Assumption 3.1. We have:
(F dr
dF (xa)
dF
dF dF( dr
dF dF(#))
dF((),))
<2
E
+ 2B
E
dx
dr
dx
dx
dF
(
$20( + 2E
dr
dx
dF (x))
dF (x.)
<0(6²) +2 E
dr
dx
dx))
50(69) +
dx
where the third inequality follows directly, the second inequality the definition of the variance and the first inequality uses that
la + b112 = ||a|12 + 2a T
||b||2 & ||a||2 - 2 |||||| |b6|| + |ab|i = 2 [||||] + 2|bb
By the above, it suffices to bound the second moment:
dF())
O To
5.
1 O2, :2.g:))) A, A
E
+
dr
Or
Au(s)
OT(
Ls
L,
A
T Fu (s,
Am
32

---

To proceed, we upper bound I
(s,
by
E
Og
A
Fel 2
8,
To
<4E
Σ
d
rst
di
dx
To+To+1
7 d
+ 1 - dx
log
P(oTe TQ
-1: "T uTa
Σ
10-TT--1//2 (r(s7 ,0,9) (
(=Tx+1
<4B
Take
Y 1-7 Ki
R + A log |A
0.5
(15)
where Tę is the random variable defined Algorithm 2. The first inequality uses the definition of the advantage estimate (cf. Algorithm 2), the i.i.d. property of Tq and Tv, as well as of T22 and TV. and Equation (16). The second inequality follows from Assumption 3.1.
Plugging in the above, we thus get:
2
dF (xt)
(x)))
=
Ly + Am
1g0,A Ax
dr
Tof
2
S
2 2
+
(mm)
O₂
(5,
2E
| 113
+8
E
TaK2
+
7
Ki
R + A log |A
Am
1-7
1 70.
L Am
2
K1 R + > log |A|
s 21E
||,
16
12
16E
0.5
OL),
where repeatedly apply Equation (16) and the fact that the second moment of geometric random variable is finite.
Now plug all our bounds back into Equation (11) get the result of Theorem 3.
dF
(F
E
(1) (2) (3)
dr
0 + 0 + 25aa (0(6² + 1)) NT
< 00 27 )000)
E.5 Proof of Theorem 4
Vanilla soft Q-learning
We give a brief overview of how HPGD is combined with vanilla soft Q-learning (Algorithm 4) to get bias of (22-K/2) in Algorithm 7. In the algorithm refer to tx O(K2K) as the
number of iterations soft Q-learning needs achieve X - 11 s =E|l - -211 < 2-K
(cf. Proposition 6). Note we slightly abuse notation, when pass policy instead of an oracle
33

---

to Algorithm 2. However, the policy can be equivalently used to sample trajectories. Note that the idea of HPGD with soft Q-learning a double-loop methods that aims to find an d-oracle. Similar 5-oracle idea also appears in conditional stochastic optimization [38, 35], in bilevel optimization [28].
Algorithm 7 HPGD with vanilla soft Q-learning
Input: Iterations T, Precision param. K, Learning rate a, Regularization A, Initial point zo. behavioural policy Ta. Q-learning rates {0 for = to T do
{ ~ Pg
7 +- SoftQlearning,, (tx, TB, fach2o) (Algorithm 4)
8 ~ / and a ~ n (:s)
0 A k (s,a) + GradientEstimatorre Tz, a, T'K) (Algorithm 2)
dF a.f(z.m g)
a. 5 02 A (s,a)
dv
dn
Au(s)
(m,a)
dF
Fe+1
f- It
a
de
end for
Output: är ~ (0
Randonly-Trunccttd Truncated soft Q-learning (RT-Q)
Let us now turn to RT-Q, for which we provide the pseudocode in Algorithm 8. As above, we denote by t (k:2%) the number of iterations soft Q-learning needs to achieve XE|[ x II I E|IQ*= Qi < 2-
k We slightly abuse notation in the Pseudocode, such that we do not just return the last soft Q-learning iteration but also the second last and the first. Moreover denote
by Pa = _ and we generally use to denote estimates from single sample and denote averaged estimates from multiple samples.
Algorithm 8 HPGD with RT-Q
Input: Iterations T, Precision param. K, Learning rate a, Regularization X, Initial point behavioural policy тB, Q-learning rates (0n)120 for = to T do
{ ~ Pe
k ~ Pk
m/* ttt n + SoftQlearning, (1&+1, TB, (at)22)) (Algorithm 4)
8 v. a n fell (+:s) and a' x"(())
0 A
a)) 2 -==1 GradientEEstimmoor((,.... a, th (Algorithm
"allott 2)
A 1k+ (8,a) - 1 E
Gradienffstimmttor((...... T((+1)
Ar (s,0') Gradienntsstimmtorr,,......dd 7
dF de
f .0)
00f(2./(+11 .1) 00 A (s
dv
Tu(3)
(x(a,0)
dr t++1 de
+ ('s())))
(2f(x,=*k 0,A (s,
Ox
(a;4) Au(s) On(a,a)
dF.,
01f(2,0110)) Oz Au(e) On(s,a')
def(z,,(11
0, 1 (s
de
Kg
dF
di
dx
AFRT
Fe+-1 f- Ee
O2
di
end for
Output: i. ~
34

---

Proof. First let us specify that "bias" refers to the bias of the hypergradient estimator, i.c.
dF())))
dF()))
E
dæ
dr
Equivalently for "variance" we mean the variance of the estimator i.c.
dF (a()))
dF((x))
dx
dæ
Moreover, the "iteration complexity" is the number of soft Q-learning iterations needed to solve the lower level.
For Vanilla soft Q-learning, we can just combine previous results to compute the iteration complexity and variance to achieve bias of 2- K/2 For RT-Q. we formalize the intuition of Section show we can achieve the same bias with only (K3)) iterations because we rarely perform many soft Q-learning iterations but assign relatively higher magnitude to these few accurate hypergradient estimates. This necessarily increases variance and most of the proof will be spent on how to bound it. Here we "divide and conquer" the variance until we have easy terms that depend linearly on
T2.6 |
or related terms we can easily bound. To decompose the variance, our main tool will be the following identity
||e + b1| = ||a| + 2 ||a]| |b|| + |bb| < 2 ||a|| 2 [|6]
(16)
which have already derived and used in the proof of Theorem and also follows from the Parallelogram Law.
Vanilla soft Q-learning
We start with the analysis of using HPGD with vanilla soft Q-learning to estimate dF(x) In Theorem we showed that
dF dF((r))
O5),
dr
dx
where
| - T 1 E,
$ 5².
In Proposition 6, show that after tx O(K2K) soft Q-learning iterations, it holds that TH. |
E
1x 2
O(2-k),
where o denotes the 1x-th iterate of the soft Q-learning algorithm. The results for complexity and bias follow directly. It remains to bound the variance. However, have already shown in Theorem that
dF
d.Ftx
dx.))) dx
E
E
<
= -(1).
dr
dr
Randomly- Frnncatyy-Truccated soft Q-learning (RT-Q)
We first show that de following estimators have the same mean:
SF&T
has the same bias as its vanilla counterpart
dF dr
For this, observe that the
d
dFF
d.F.
4k E
E
tz
E
dr
dr
dr
35

---

The first equality holds because of importance sampling and the second inequality holds by the linearity of expectation. Plugging in these identities, we get
EK
E
dæ
d.Ft
K
d
dF
-E
Pk
E
dæ
dr
dx
d.F
K
d'Fiat1
d.
Pk
E
- E
dæ
Pk
dx
dx
d.FtR
-E
dx
It follows directly that the hypergradient estimators obtained by RT-Q and vanilla soft Q-learning must have the same bias.
For sampled & E fl...., K), soft Q-learning has an iteration complexity c of Okk2k) to build following hypergradient estimator:
dF dF de
d.F.
d.F..
IK
de
dr
dx
Pk
As sample any i with probability Pk
1-2-K K. the expected iteration complexity is then given by
2-
C&PP
A=1
K
2- k
Ck
2-k
k=
k
2
0
2
1- 2- K
km
K
50 50(K)
Σ
0
1
2-K
k=1
-O(3))
which proves our claim. The attentive reader will note that RT-Q runs GradientEstimatorr 2 times instead of once and thus samples 2 trajectories to estimate the advantage derivative instead of one like vanilla soft Q-learning. Nonetheless, RT-Q has the better sample complexity as both methods need to sample (A:2k) state action pairs for given I to soft Q-learning and then estimate the advantage derivative. The same analysis as for the iteration complexity thus shows that the sample complexity of vanilla soft Q-learning is O ((k2*) and ( for RT-Q
remains to show that the variance is of order O(K). This is the most challenging part of the proof. As outlined previously, we will iteratively decompose the variance until we can bound all terms by OKK).
For better readability we introduce the following notation for given pair s, a:
(1(1) 01f(2,7** "²,,()
36

---

aes(a, {))
Oz Art (8,
if =1
Hx(2)
Av(s) (TT(a.))
Ar (8,0)
if
Xu(s) Bal(a,))
(";(s;s)
02 x2'
(2) Au(() ml+ (158)
Og A (s,a)
(8(8,))
01 (2
(1) =
dx
(2) 1 (2
(u(s)
(T,
Then for a given ç, a (which are sampled at the beginning of RT-Q) we have that
d
FR (1( H2 H1+1(1) + Hk+1(2) HA (1)
H (2)
dx
Ps
Now let us decompose the variance of the RT-Q hypergradient estimator using the newly introduced notation:
d
E
F
RT
E
F
RT fx
dx
dx
d
2
<E
RRT
F(x)
dx
1K
dx
d FIT Itr
2
d
<2E
H, H1) (2)
+ 2
H1(1) + H2
F(x)
dr
dr
Hk+I (1) (1(1) 2
(2) H Hh++ (2)
<4E
+4E
+2E
H1 +1)1+ H2
F(x)
Pk
Pk
dr
(I)
We proceed to bound the individual terms.
Note that (3) is indepedent of k. Using Equation (15) in the analysis of Theorem 3, we can bound it as
(3) < ((1 K₂ + Ki (R Alog (A1) (1
(11) -
R+ Alog |A|
K2
K1
(1 7)-
1-7
0.5
= 0(1).
(1) is also relatively easy to bound, shown below:
K
(1) =
E
H (1) (1)1
Pk:
k=1
0 fxr x(+11
0, 0zf x) !
E
Pk
dr
k=1
K
SPE
co+z - [100
k=1
K
1
$72
E
|| - T
+E || - T2.5112
pk
K
1
1
$72
+
Pk
2k+1
2
1=1
37

---

K
3 2k
2t
k=1
=35KK
O(K)
In the first equality we simply use that & is sampled with probability Pk = I-2-xx In the second equality we plug in the definitions of I1) and (1),). In the first inequality use the smoothness of f. The second inequality uses Equation (16). The third inequality follows from The remaining
2-
the fact that 4++1 is chosen to guarantee expected distance of at most 20-1 The
equalities follow from plugging in ps: and rearranging terms.
Now want to repeat the same analysis again for (2). As for (1) get over & with the factor 1 which we need to compensate by bounding IE
|| H2)++ H (2)1l by ((2-*). However, bounding the latter is more invovled than our analysis for (1). In the following pages, we will iteratively apply Equation (16) until the terms get easy enough, such that following two facts about RT-Q:
PE"
one of the
1. ts = (k:2h)) is chosen sucht that A|El - 7 111 5 =EIQ - 1212 S
2. 0_A='++1 (s,a) a) and related terms are an average estimate over 2* trajectory samples, such that their variance (with respect to these random rollouts) is O y1
We briefly note that in the analysis below we will sometimes write ((s a) or A(s, a) inside the infinity norm for case of exposition. When we do so, the infinity norm is still interpreted as the maximum over all possible s, and not as the absolute value of the Q-function or advantage for specific s, a.
Let us start decomposing the numerator of (2):
Hy+ (2) _ [2)
E
1 O25 nh (E)) O (s,a)
at (a)s) 02,(5, 0rA (s,
=E
(x) (T(
Au(s) T'+ (1;8)
OT(s,a)
T' ()) Og AT (s, a)
x (a: 8)
x')(a;s) s)
<2F
(s(s)
aT(
Tle+1 (a:
Ttit1 (a;
Tty (a) T (a;
02 x(++,,))
1 02f(2, n"x ,(),
2
+ 2E
θz An'ht1 (s,
A (s,
Av(s)
ÖT((,0)
Au(s)
ŪT(S,
1 1,,
<2
Or Ar' (s,n)
|| (a; (a;
(v(s)
(T((sa))
Nl++ (a;
t (a; 1 (a; 8)
2
1 (2, x(01, A (s,a) Au(s) Ōn(s, a)
02f(2, ("
+ 2
Ar'r (s,
(s)s) (7(s,a)
The first equality is just plugging in definitions. The first inequality follows from Equation (16) and the second inequality comes from the Cauchy-Schwarz inequality.
Let us begin with bounding (i). First we want to tackle the fractions of the policies. For this, recall
that Vz, S, a |rz,ç(s, a)) < R and that 0 < H H(T; s) < log |A| (by Jensen's 's inequality). Thus we have that:
R
R + log LA|
1-ク < Qx( <
38

---

The above bounds extend to any soft Q-learning estimate, which can be obtained by Algorithm 4, since by Assumption 3.1 the algorithm cannot observe rewards with greater magnitude than R. As Algorithm 4 returns softmax policy, i.c.
exp(Q 8)/))
A (a; 8) E.' (//))))))
holds that:
expl R- Alo LA1 x(1-2)
exp( x(1ー9)
Vtg, Vs, Va:
2 π (a; z
(17)
|A| expl ^P إ((ー
| exp( 2(1-7)
R+ log (اl)
Therefore we have:
1
1WE < 00, V4A Vt,
S M1
x b (a; 8)
7 (a;
M22 < 00, Vlx
S M2.
x (a:
Using this we can bound (i). Let = min, (s),, then:
Mj
K₂
+ 7 R + Alog |A]
1-7 K1 - 70.5
E 11 - (a; s)
Am
y
<
2E
| (a; 8) - - (a: (a;
+ 2E
|| (a;)) - T (a; 8) s1]1[s]]
0
2k
The first inequality uses Equation (15). The second inequality uses Equation (16) and the last equality uses the convergence of soft Q-learning.
Now we turn to bound (ii):
M2
O2f x)),,, (T( a)
OrAt'rt (s,a) 0ef(x,='+,E))
2 0gAn't (s)
(ii)
E
Am
ÜT(S,a)
M2 E Am
A (s,a) 02f D A
(s,a)
0T(3,
ÖT(8,a)
02f m(tt1,
T" An' (s:0)
2
(n(saa)
(T(),))
<4 M2 Am
E
Oo (2f (I nttt1, ,()
||
O 10 (8, -O,A*' (s,
(T((,0)
02 O, [))
n" 12
+
0 (s)
θT(,,))
(T(
M2
O2 82f(x, (2, ,+++1gg))
O2f t {)) @T(s,a)
<4
E
Ax (s.a)
Am
θT((,
(A)
1.3 E
A
(s) Or A'' (s,
(B)
The first inequality uses M2 to bound the policy fraction the definition of m min, v(s) and Cauchy-Schwarz. The second inequality uses Equation (16) and Cauchy-Schwarz. For the final inequality, rearrange and use the Lipschitz continuity of ff (cf. Assumption 3.1).
39

---

(A) is relatively easy to bound as follows:
K2
Ki R + A log [A (111)
))
2
(A)
2
SyB || [| - xzx (a: s })
7
1 1-7
70.5
0
2E
||
(a;s)
- (a,)(ai))))
+ 2E
(a;+( (a; 8) (=])
2
In the first inequality Equation (16) and in the final inequality the convergence of soft Q-learning.
the smoothness of f and Equation (15). In the second inequality
Now, we turn our attention towards bounding (B). First, notice that both advantage derivatives are evaluated for the same state-action pair. This because Algorithm we sample a once according to nf*+1 and reuse the same a for A (s, a) by doing importance sampling. Without this trick, would be hopeless to bound (B).
When bounding (B), we need to consider two sources randomness. First, there the randomness in the soft Q-learning iterations. Second, we have to account for the randomness over the trajectory rollouts of GradientEstimator estimate Az GradienEst first separately estimates
0, V and 0₂ V** from trajectory and then returns 0_A=' -000*' 0_V='', We therefore denote by
2
1
0g V'*
0g n (m).
2
the average over the 2 value function derivatives estimated part of the 2 GradientEstimator procedures performed in RT-Q. Note because of the unbiasedness of GradienEstimaton (cf. Propo-
sition 3), it holds that 0g yT = E, 0 V
Using the above notation, we get the following bound by repeatedly applying Equation (16):
(B) <2E
2 2.QT" (8,a) - 0zQ00h11 (8, a)
2
O₂ Va'N (s) - O2 V 1611
<4B
O, 0,0T* (s, - 0,Q² (s,a)
+ 4E
0 2 12 (s - 0200 (s,
+ 4F
O, V (s) V (s)
4E
O. V+
- 0.v=' (s)
<8E
0 Q (8) O, QT
" (s,
8E
0 0 " (8 0,Q² (8.0)
+ 8E
0, Q 1k (8, - On 0,Q Q *+ 2
a)
+ 88E O h+4 (8, 0,Q²' (5,a)
+ 8E
O2 V (s) - O2 v' (s)
1
+ +E
a. 2 (s) 0²v² (s) 2
02 V+ (s) O2 V (s)
2 V (s) - 0z (s)
+ 8E
8E
Here Q denotes the optimal Q-function, i.c. for the policy 2 In the equations above we have two flavours of terms. The first are the differences between the derivative estimator and its expectation for a given policy and the second are the differences between the expected derivative under the learned and optimal policy. We start by bounding the first kind of terms. Recall that
2*
2*
0²Q0%
Σ a.Q
TM
(TT),
0.V
1
O2 V (T)
2*
2
1=1
1=1
40

---

As the second moment of 02Q (n) and 0₂ V** (ni) is bounded, we have that:
E, since we use 2h sampled trajectories. The same analysis of course also holds for tk+1 and thus plugging this in, we get
/ 02 - 0(2 E
02V='e Og Vo = 0(2
(18)
(B) 0
1 +
SE
O2Q
0 (s.a) - -2Q" (s.0)
+ +8B
| 2 tti (8, - -0000 -0,00
0.
2
(s) 02 (s) + +8E 8E 0g 12 (s) - 02 (s) ?
+
8E
Og V
O 1a (s, a) - 0₂0" (8, (s, 1| + 1 u+1 (3, - 0,0" (s, 2
<0 2
+ 24E
(Ki(R+Alog ) (BIIT** 111 +B E - x )
K ( + log
+ 16
(1-
1 0 2 + 24E
1000 (8, - 0000 (s,0)] + +4E 1 (s, - -2Q" (s, (3.
In the first inequality, we simply plug in Equation (18). In the third inequality we use the convergence of soft Q-learning and in the second inequality, we use the following identity (cf. Equation (14)):
2₂ V Th.s (s) O2p x. (s) 1|c
Σ (aa s)d 2
F (8, a)
Fen (s, Σ 5xx
Σ ((: (a; O TE.
Σ T T (0.0 0z OoQ (exte)(ss
K1 KI(R Alog (A))
|| - Th.ell +2 f (s O -2,0
(1 71-
where we use Equation (16) for the last inequality.
To bound (B), it only remains to upper bound E 1 (s, -0000 (s, (s.
and
(0.Q=*++1 as,a) a, (s,a) a)
Below we will derive an upper bound for the former term. The same analysis yields equivalent bound for the latter term. We denote by VX the optimal regu- larized value function. Note, the analysis is similar to the one performed in the proof of Theorem 3,
1. 1 (s, a) - 02Q2(s,0)
ddan((s'.a)
dP d a') yotk v (s"))
7 Pe.ess a- d''tt,))'
+
dr
dx
5¹
+ Σ drac(st.a) a')
dP d s a²) Vs()"))
Σ Σ
P' ,''t',
dx
dx
s'
dr drz,g(s,a) dr
dP dPp,c(s':8,0 y (s')
dx
Y' Pe.ee (8, + a'a',t, dran((s'ad)
+ E
dP
dPo.c("":s', v (80)
dx
dr
1=1 s',0'
dr (3,,g(s,a)
dP ds' ss a) V2'5
7
dx
dr
41

---

7 ( +1, (
dP
( a')
+ +7 E
Vi(("))
dx
dx
d (8' 8, a)
VT -8)
dr
Σ ((
Po ,a' + s", aliit
6'.a'
1=0 s"
dra,el"",a" )
dP e a")
V2(("))
da
dx
P(stss
Σ
Σ
Y P d' + s a";","
s'aa
s"
dra.s(s", aa)
dP= dP"
yark (5"))
+7
dx
dx
5M1
dP ( a)
|Itt (()))-V('')) 12(60)/1
dr
+ 7
Σ P(s 2ld s'
Σ (), (d'
s'aa
dP (8'38
yark (8') V3((5')
dr
+7 +7110.0065.
Σ P(s'is,a)
| T'* 11
Σ s, s, a) (aos)))0000000 (200((5' - 0x00" -600="(6',))
+
s'a0'
dP d a)
| (8') (8) 13(00111
8
dx
+7 +010000(ss a aL. T 10
+7 100 ,a) - 0202* (5', (d.
S>/81K,
|= (5') -V2(3))
1-7 + (R + Alog A)
K₂
+7
TT - 7th 100
71-
15' ,a)- - -0, (5', (s'.a))
+-
S|Ki |/TM((5 (s') - (i')'s)
<
7 Kg + KI A Alog A)
+ 1-7 ア 1-7 (1 11-71 7)2
|| 1l
The first equality follows from plugging in the result from Theorem 2. The second equality follows by taking out all terms with 1. = O. The first inequality used the triangle inequality. The second inequality plugs back in the definition from Theorem 2. The third inequality uses Cauchy-Schwarz.
42

---

The fourth inequality follows from simplifying. The fifth inequality uses Equation (12). The sixth inequality uses the geometric sum.
To simplify the bound above we want to expres | (s) - (x')
using 0 - 22 and
|| 11 (as we know the latter two converge for soft Q-learning). We have previously seen in Equation (13) that
1 (5)) - ( s -000- + +||="=- - I'
R (1-m-
+ logll /21 2,,
Here we use l2 to denote the minimum possible value that any policy output by soft Q-learning can achieve. Note L2 O, which follows from Equation (17).
Plugging this result back in, we get
1 (s, 0, (x)
s 7 7 |S|Ki (1e0Te - -0x" || - - 101oo ( R
logglll/ 11Alll 2 2,2 1/2 )
1-7
+ - ( K2 + K1 (1 Alog A)
|| - 1/
(1- 7)2
From [49][Lemma> 24] we know
||T - 11 S 1 = - -2
With that result we can simplify to
100Q (s, - -2,
7 SK| (1105 - 22
R
/21 11))) )
+ 10th -2ilo (I-7
+ logll
7 ( K2 + Ki(R Allog A)
1 11Qtt Qillo
+ 1- 1
(1 - 7)2
<
1 Qx
2 SS|
1+
1
+ |All log b2] +
2
+
7
K₂
K1(R + 2 log A)
2)
Al
1-7
1-
(1 7)2
Therefore it follows that
E |0 (s,a) 0 -s. (2,
=0
2k
00
where we use the convergence of soft Q-learning.
Using the above analysis, we can bound:
(B) < ( 2k
+ 24E
0000 (s.a) 0²0
-= (s.a) + 24E
0. n4t (s,a) 02 (s,
1
O
2
This allows us to finish bounding (ii) as follows:
M2
iii
4 Am
(A) + L²(())
0 2k
43

---

Plugging this result into (2), we thus have:
K
2
(2)
-
(0+ + (i))
Pk
k=1
K
1 (0l
+ 0 1
Σ
2h
2
2x
O(K).
Coming back to the start, we get for the variance our desired result as follows:
d
d F
E
p
dx
1x
dr
4(1) + 4(2) 2(3)
+ +(KK)++ +O(K)+0(1)
O(K).
E.6 Proof of Proposition
Proof. In this proof we will derive an expression for
(xr x)
dx
Applying the Dominated Convergence Theorem then directly gives the expression for the derivative of Fxx). As we focus on / we can drop any dependence on helow to make the proof more readable and concise.
Let
p(14 - s,t, ..) denote the probability given the leader's choise x of reaching state s after steps starting at y and following policy æ
p(p + s, a, t, v. .) denote the probability under choice æ reaching state s after steps and then taking action starting and following policy
p(14 > 8, a, s, ..): denote the probability under choice æ of reaching state s' after steps having previously been in state and having taken action starting at l and following policy æ
Assuming V(s) is differentiable for all s, we show the following statement by induction.
(f E) dx
d th v(s) + dx
n+1 ΣΣΣΣ p(ux +s,a, A dlog Pa s, V(s') dx
Σ (s)
(orAAi Th Q(x, a) +
di ds a)
+
pluz + 8, 8, x
dx
+ n+1 Σ pluz
m, 2 (.V())))
(19)
Note that taking then directly proves claim.
44

---

Base case 72 = 0
We prove the statement for = 0
df (x, 5)
d
Σ m(s)
Σ n (a {){
dx
dx
(s)
V(s) + [e((s) E (ais(ass)
1 -
dx
{ Hondftz (s) V(s) + "'EExh px(s) Σ (ais)
1
dF,(s,a)
da
+ Σ Pa($'is,a) d doog (s a)
V(s') Ps P,((5i8,,))0
dx
Σ
Uz (s)
dlogMe Mr dx
V(8) + ΣΣΣΣ 2 Tplus - +, o',,, ,,, Tm x)
dlog Pa(s'is,a) a) V(s')
dx
1=1
Fo.ARb- Q(s,)(((s)))))))) + di dr,(s,
+
pf1 + 8, a, n x) x)
dx
t=
a
p(u0 - 8, , 0),, + 7 Σ
where we use the definition of f in the first equality. The second equality follows fromProposition and the product rule. Rearranging terms gives the third equality.
Induction step n = n ++1
Assuming Equation (19) holds for n. we prove for n 1.
dlog Mr V(s)=
Y y'plu= -s, t xx dlog (a(s'; s, a) V(5')
Σ (s)))
ΣΣΣΣ
dr
dx
1=1
ΣΣ piu + +, Tx x)
HoLANt001 a)) +
1
di (8, a)
+
dx
t=0
Σ p(us s,,, T 2)0)
+
Σ (s) dlog Us V(s) + n+1 ΣΣΣΣ d'plzz + -s,a,s'tt Tx, x)
dlog Pa(s'; ;0;;8,,0 V(5')
dx
dx
HoLARi-0 dra(s, a)
+
pluz + 8, s,a, ((,1
dx
Ti. s,,, x)) Σ Thi Ao ".. dF,(s,
+ Σ plu s,t,
dx
+ 7 Σ Pa(ssis,)) dlog as V(s') + Pa(s'is, av(o)) dr
de
Σ (s)
dlog Ms
v(s) + ΣΣΣΣ tpluu - +s,a, n,, x)
n42
dlog Po(s': s, V(5')
dx
dx
a+1
H a(s + (8,
ΣΣ p(ux - 8, L, ,, Tx,x, x)
dr
Σ pluz + 8, t,
n,, n, x 0(V(sss)
which proves our claim. In the first equality we use the definition of V and the product rule. The second inequality follows from collecting terms.
D
45

---

E.7
0-Q305(aa) Auxiliary Results
Proposition 2 (Gradient of Best response Policy). holds that
dx x (8,
1 T (a;
( a).
nie (8)a).
dx
X
Proof. For a given 5, this result was previoysly shown by [15]. We give short proof below. dr a. (8, a) dx E. (s,
d exp(Q),,,(s,,)))))
dr
Eaar 1 En exp((X..
cxp(Qx,,((s.a)/)) exp ex. (s.))/) Os ((raa))
explOx (),
O, ( T( Eo exp((Xx.. 8. Pimaloon'
=;
E exweeeeX...x....... (8))11)
1 "a; (0,,)) 1 x (a; Σ 2 (d'; () (5s
X
sa; (0 [0 (s, -e 10. [s)
X
= x" (a; (0, 2x a) -2 (x)
X
1
(a; s)0,A
X
The second equality follows from the quotient rule.
The third and fourth equality follows from the definition of ", (8,a). a). The remaining equalities leverage the definition of the advantage function.
Note, we can replace the total with the partial derivative of Q* (z) max Q(T, I). due Rockafel- lar's thoerem because Q is continuously differentiable in for all æ and IT is compact and convex [9, 56].
The Proposition 3 (Unbiased advantage derivative estimator). The output O2 (8,5)(8,))) a) of Algorithm is an unbiased estimate of Or A A.
(8, a), ie
E
O A The
N (5)
Proof. We drop any dependence on x; E, 2. for notational clarity. We further emphasize that the trick of truncating a rollout after a geomtrically sampled time to obtain unbiased gradients commonly used in the RL literature for obtaining unbiased estimates of the standard policy gradient [80].
We show that the estimator 0, (x, a) given by
To+To+1 +1 7(t
? d log (1 8T (Ta) (st, ac) + - dx
Σ
(t-To (r(s), + (H(((;;)))
1=To+1
unbiased. The same argument then holds for de First of all, we have:
Va(s) and implies that 1 Ax a) unbiased.
de
Taa (0/2 (r(s;, + {H(({(;s)))
E
46

---

T2
EIg E
10/2 (r(s),
(H(((())))) (
ETg
7 (0)/2 (r(s), ax) + (=(((;;))))
1
= -
BTd LiSTy/ (r(s))(((ss ar) + {H(+(:))))
(20)
=B;
7 (r(s), ar) + (H(T(:)))))
=s)(s),
(21)
where we use Fubini'ss theorem for eq. (20) and the Dominated Convergence Theorem and the fact that T22 Geo(1 705) in eq. (21). Because Tę and T/2 are sampled independently, it immediately follows that
To d T dx
ET
rst,
0z)
1=0
To+T
7
log P(sT++1: STo aTa)
Σ
(t- 1)/2 (r(s), ar) (H((T((s)))
y dx
t=yt
To d
y d dlog P (1: @Ta
E Erg
r(st,
az)
+ 1 1-7
V (sra)
5.a
dr
dr
1=0
We seperately show that the two summands are unbaised estimates. Then by linearity of expectation the result follows. For (1) using Fubini's theorem and Dominated Convergence Theorem it holds that
To d
o
Erg ET
r(st, at)
= B
Σ
(1
7) A
Σ (=0
r(s dx
dx
t=
k==0
00
00
(1 7)
r(t.
dr
k=
d r(se, ac)
(1
E s,a
dx
ge d dr
r(se, an)
E s.a
Similarly for (2), we have using Fubini and Dominated Convergence Theorem that
d P(sra+1; 0Te V (STT))
ETg E
dx
dlog P(s Se, ar)
Ex Era
T=
V (8x)
1
dr
1=0
1-1 dl log P( St, az) VT
=B
dx
1=0
47

---

Plugging these results back in, we have
To d
d dlog P( oTa) VT (ST2)
Brg
B
(e)
dr
1 1-7
dx
y' dr r(s,, ar) + t d log P(s at) Vx (s:)
=E
dr
t=0
=0,
which proves the proposition.
Proposition 4 (Unbiased gradient estimator for F), The gradient estimator described in Algorithm unbiased for the given policy "
Proof. We need to show that:
d
T+T
E
a()
+ 1(1 (1-1)
deA The A
( ar) Σ
(1-T)/2 ((-T)/ ((sy 0v)
dx
1=0
T
(1)
(2)
T-T
1
O₂ log P(ST, -1- 8T
11' -T- (sy
( 0r)
1
(oossiielen (ss,
Egg
Σ ,x' 1=
T(s,, az) + O2 log (2, a1-1: 8(-1)V
dx
We can show the claim seperately for (1), (2) and (3). Note for (1) and (3) the claim directly follows from the proof of Proposition 3. And the proof for (2) works almost identical to the one for (3), relying on the fact that truncation via geometric distribution is identical to infinite trajectory with discount factor.
E.8 Convergence Results Popular RL Algorithms
For the next Proposition, consider the following soft Bellmann optimality operator, which has been shown to contraction [20, 51].
(r(s, a))
1l VV2 (6)6))
VA) (8) = Alog
Σ cxp NaEA
(22)
A
Using Equation (22), can define standard soft value iteration algorithm (see Algorithm 3 in Appendix D). We show soft value iteration satisfies Assumption 3.2.
Proposition 5. Algorithm 3 converges, such that |
2 82 after T iterations, where
T Ollog 1/8).
Proof. From [Lmmmaa 24] we have
TT" T''
- -|=-~--11 - 1 1 - Qillac
Moreover
1 -x
S 2 | x
S
VT - Vx
S X(1 (1-7) (R+ Alog [Al),
where we use the contraction property shown in [20, 51] and the fact that instantiate V/ with 0. such that no value iterate can ever be larger than higher than R + Alog [A)). The claim follows from 8 < T)
48

---

As soft value iteration assumes knowledge of the transition function and scales badly when the state and action space are large, in practice stochastic methods such as soft Q-learning are used instead. For this method, consider the soft Bellman state-action optimality operator [3, 30]:
(Q((,ad) (2xler))
))
(Tx (T.))) := a) + +. A log
Σ exp
(23)
Ao'EA
We can use Equation (23) to run soft Q-learning, as described in Algorithm 4 in Appendix D. Equivalently to soft value iteration, we can show soft Q-learning satisfies Assumption 3.2.
Proposition 6. Let Th be sufficiently exploratory. such that the induced Markov chain is ergodic.
Then soft Q-learning converges, such that E, mhiee T 1
S 8 after T iterations, where
= ( (log(1/))) 82
We use the following Theorem from [54] to prove our claim:
Theorem [54] Let E gd and F; IR + gd be an operator. We use F; to denote the i 'th entry of F. We consider the following stochastic approximation scheme that keeps updating x(t) E Rd starting from z0) being the all zero vector,
xy (1 + = zz(1) + as (Fi(a())) (1) w())) xt [ z,(t)
for :ori-n its for $ in
where in E {I.....d} is a stochastic process adapted to a filtratioon Fr, and w(t) is some noise. Assume the following:
Assumption (Contraction) (a) Operator F is Y contraction in |1-1 iee for any z, Rd.
[1)(x) F(y)llo Sk vlloor (b) There exists some constant C > s.t. [F(x)) S ||=1l000 C, Vx E IR.
Assumption (Martingale Difference Sequence) w(t) Fi+1 measurable and satisfies Ew(t) Fr 0. Further, [w)))] S ti almost surely for some constant w.
Assumption 3 (Sufficient Exploration) There exists E (0,1) and positive integer, т, such that, for any E N and t 2 T, P (ie = Ft-r) G.
Suppose Assumptions 1,2 and 3 hold. Further, assume there exists constant I 2 || s.f.
Vt, [[)(() < Σ almost surely. Let the step size be at Ttto -( Then, with probability at least 8,
h with to 2 max(4h, T), and
2(r 2(r+1)72
[T) - x² x011 S 1 1-
12c
/
1)h
log
max
16Ele
25 (r + tol
σ
T + to
T + to
where 2F + C w.
Proof. Our algorithm can be seen as stochastic approximation scheme where we update Q asyn- chronously just like above in the following way
Quaa + 1) = Q (t) + ar (Feci (Q(1)) - Qar.o (1) + we) Qe 1) Qs,a(t)
for 8, + St, at.
where
(((saa))
Fs (Q) = r(8, (8 a) +7BosP((lad
Alog
Σ
exp
A
Wa'ed
and the errors:
Q2((442,aa)
-1(,, (e) + +dllog
Σ l'Ed
exp
A
Qu(((+1,a))
r(ss,, at) +.
log Σ
exp
A
49

---

We now show that F satisfies the assumptions of the Theorem from [54] and use the result to prove our own claim.
In the following we let Ft be the o-algebra generated by the random variables (8o, Ao, ... St, at)
First we restate the following identity from [51]
(Q(,aa))
(s.)) r(s, a) + +
Alog Σ exp
n'EA
rr(s, a) + P((aaa) max 8'), + (H( 8/)
We use it to show that T is a contraction. Indeed we have:
( Tx (2
as, + +ymax Σ
P(s';s, ((Q((,)))) AH(TTsss
r((s,)) a) - max
((Q2;,,))(Q2(,,,))) + AH;
59 max
P(s'is,a ())()))))))
<> || Q211oo
Moreover, holds that
F(Q) R +++ + Allo (A].
So
set C = C |A|
Next we note that wi 1ii--mmane measurabee (it depends on 8141) 1) and that
Bi [Fe] =
Moreover wt) is bounded by w (T+ LAI) 1->
Further we have assumed that the behavioural policy лy sufficiently exploratory. Let ju be
corresponding stationary distribution, umia infs,a ju(s, a) and tmix the mixing time. Then [54] show that for Mmin and [log2( 2
(0))((m) [tmiz it holds that
Vs E S.E.AAEA2... P(st, = s.
(24)
Moreover, we note that Q(() and Q are bound by I R+AloRIAl
1-7
Using the Theorem from [54] we thus have the following result:
h Let a₂ E+l with to 2 max (4h, [ogg Pamin tmixx and h
2
Mmnin (1-73- Then, with probability at
least 1 - p.
IIQ(T) @i S
2
logg
Iiaia +1 T2|S|AA1
[oog
Imix 1 h log
< 60(R + Alog (A))
2
Auain
71-
Amin
T + to
4(R + Alog (Al)
160h
loga
2
tmix
(1OES.
2 7 tmix + to) )
Puai
(1 11-79 7)2
Pmin
Mmnn
T to
50

---

We denote the bound above by (A). Let us choose p = 82.0 With probability IIQ(T) Q is
not bounded by (A), However, it is always upper bounded by
2( log+Alog((A
1-7
Setting = O lox(1/4)
we get
2 log 82
(A) -0
T
T
log (7)
T
1// 82
log
T=
(1/
log(1/8] 6
8
log
log(1/6) 8th
log (1/8)
log (8)
log (log (1/6))
8
log (1/0)
3 log (6)
log (log (1/6))
=0
8
+
log (8)
log (1/6)
Since 8 1, log(1/)))) > 0 and for it holds that log(ar) 1/e, such that we get:
(A)50 8
=0 (6).
Using [49][Le 24], arrive at:
E2 || 11
<4E,
| 22113-
12(R+ A Alog((A41)
)
<4
(1 - (A) +
1 -
=0(8)).
popular class of RL algorithms are policy gradient methods such REINFORCE [68]. For the entropy-regularised problem, it generally makes sense to choose softmax parametrization for the policy, know (s; a) x exp(Qi.z.c (i........ (s, a)/A) [49]. We defer the details Algorithm 6 in Appendix D and present the following convergence result, which shows using vanilla policy gradient for the lower level also fulfills Assumption 3.2-at at least asymptotically.
Proposition Vanilla policy grudient with sofimax parameterization converges, such that T2. TT, < 82, where of, the computed policy after iterations.
VO, 3T, Vt T:
NNoe that d represents the distance between softmax policies under the supremum norm.
51

---

Proof. As in most proofs we drop the subscripts for The proof is an adaptation of the one presented in [49][Lemma 16]. We denote by मe the iterates of the policies of the algorithm and by (X"(() the corresponding value function with starting distribution It can be shown that VX is s-smooth for some 8 [49]. Choosing stepsize of 1/8, we have that the value functions increase monotonically, i.e.
VE: VX M (1) 2 (H).
(1).
At the same time, it holds that:
(p) S R Alog
1-7
By monotone convergence thus follows that VT (x),), where (x( is the maximum possible value.
Si and ((A)) is compact it follows that {me} has a convergent subsequence (To, Denote by nT the limit this subsequence. has to hold that VT (m) = Vi (u) and thus
Since N. E ((A)|S)
n² is the optimal policy.
Now assume that { e does not converge x². In that case
Je, Vt, 3/' 2 t: || - wyll >
Note that due to entropy regularization V is the unique maximum. This means that
Ex max V π x 10 +x<+
It follows then that
v1, 3/ 26:
V V K
which implies V (u) does not converge to V*-a contradiction our conclusion above. It therefore has to hold that ग. + π².
The asymptotic guarantee of Vanilla Policy Gradient can be improved to non-asymptotic by using Natural Policy Gradient, as introduced by [42]. We restate the following result from [12].
Proposition 8 (Linear convergence of exact catroop-regularizer NPG, [12]). For any learning rate 0 < 17 S (1 TT, the entropy-regularized NPG updates (18) satisfy
0 10--Q((11) Q((+1)
( m/)²
log क. log n (1+1)
2 - 1/A)1,
for all t O, where
- - + 1 (1-17A 17d )
G 4=:1108 -
||og log (0)
1 7)
F
Implementation Details
F1 Baseline Algorithms
F.1.1 Adaptive Model Design [15]
As noted in Section 5, the Adaptive Model Design (AMD) algorithm [15] was proposed for the Regu- larized Markov Design (RMD) problem which a special case of Contextual Bilevel Reinforcement Learning. In particular, when P& is Dirichlet distribution CB-RL reduces to the RMD problem. To account for this difference, we modify the AMD algorithm (Algorithm in Algorithm 9, We denote the upper-level reward and value functions with the superscript in the algorithm.
[15]) as described
F.1.2 Zero-Order Algorithm
Algorithm 10 defines the zero-order gradient estimation algorithm described in Section 5. We parametrize the perturbation constant to decrease with the number of iterations such as ut = where C' is positive constant.
52

---

Algorithm 9 (Modified) Adaptive Model Design
Input: Iterations T. Inner iterations: K, Learning rate a, Regularization X, gradient of the pre-leamed model V, log P, gradient of the reward function Vzr Initialize z0. Qo. V Vo and Qo
for t = to T 1 do
Ç Pg for k = to K do
Te.& +- exp(AQx(s.))) ))
Calculate Vi, Va, Vis VU Vz, Ag, Ab, V
Qu+1 f (V&)
V Zz, Qk+1 = Tan (Z Vk + v. log P)
U++1 = Trunnu (V+)
Q++1 f Tv r"+AAp As (V/s + V log P)
end for Set dF de
Vk
dF E++1 + 2 + de
Reinitialize Qo Qk. V.Qo VvQ.. and @o QK
end for
Output: Optimised parameter vT
Algorithm 10 Zero-Order Algorithm
Input: Iterations T, Learning a, Regularization À Initialize zo
for 0 T do
E~
Sample NO,,
TH + OraclePolicy(mn.f)
To t +- OraclePolicy((z + 244, E)
Set dr f(ttuns (2 dz
Me
Et++1 f- + dF
end for
Output: îT ~ U((20...,ET11))) IT-1l)
F22
Four Rooms
F2.1
Implementation Details
We parametrize the penalty function F the softmax transformation of [Rd.+1 where the i-th entry of æ corresponds to the i-th cell the state space and the additional dimension d, + 1 is used to allocate the penalties not effective and also excluded from the penalty term received by the leader at the end of each episode. In particular,
F(s, a) 0.2 softmax(s;:x).
where softmax(s; æ) denotes the value of the softmax transformation of at the entry corresponding to the state 8. Note that this parametrization explicitly restricts the maximum available budget for penalties to -.22.
F.2.2 Hyperparameters
For the upper-level optimization problem, we use gradient norm clipping of 1.0. The learning rate for each algorithm has been chosen as best performing one from [1.0, 0.5, 0.1, 0.05, 0.01] individually. Additionally, we tune the parameter C' for the Zero-order algorithm on the values [0.1, 0.5, 1.0, 2.0, 5.0). For Hyper Policy Gradient Descent, we sample 10, 000 environment steps for each gradient calculation.
53

---

F2.3 Additional Figures
0.8
Upper-level objective: F
0.6
0.4
0.2
HPGD
AMD
ZERO-ORDER
2000
1000
6000
8000
10000
Outer iterations: T
Figure 4: Upper-level objective values, over the number of outer iterations for hyperparameters 0.001 and / = 3.0
Upper-leved level objective: F
0.6
0.4
0.2-
HPGD
AMD
ZERO-ORDER
2000
1000
6000
8000
10000
Outer iterations: T
Figure 5: Upper-level objective values, over the number of outer iterations for hyperparameters = 0.001 and 3 = 5.0
54

---

1.0
Upper-level objective: F
0.8
0.6
0.14
0.2-
HPGD
AMD
ZERO-ORDER
0
2000
4000
6000
8000
10000
Outer iterations: T
Figure 6: Upper-level objective values, F, over the number outer iterations for hyperparameters
0.003 and | 1.0
0.8
Upper-level objective: F
0.6
0.4
0.2
HPGD
AMD
ZERO-ORDER
0
2000
4000
6000
8000
10000
Outer iterations: T
Figure 7: Upper-level objective values, F, over the number of outer iterations for hyperparameters 0.003 and | 3.0
0.6
Upper-leeel objective: F
0.4-
0.2-
0.0
0..
-0.4
HPGD
AMD
ZERO-ORDER
2000
4000
6000
8000
10000
Outer iterations: T
Figure 8: Upper-level objective values, over the number of outer iterations for hyperparameters = 0.003 and 3 = 5.0
55

---

1.4
Upper-leve objective: F
1.2
1.0
0.8
0.6
0.4
HPGD
AMD
ZERO-ORDER
0
2000
1000
6000
8000
10000
Outer iterations: T
Figure 9: Upper-level objective values, F, over the number of outer iterations for hyperparameters
0.005 and | 1.0
1.4
Upper-leve objective: F
1.2
1.0
0.8
0.6
0.4
0.2
HPGD
AMD
ZERO-ORDER
2000
4000
6000
8000
10000
Outer iterations: T
Figure 10: Upper-level objeecttvv values, F, over the number of outer iterations for hyperparameters = 0.005 and 3 = 3.0
1.2
1.0-
Upper-lewe level objective: F
0.8-
0.6
0.4
0.2-
-0.0
0.2
HPGD
AMD
ZERO-ORDER
-0.4-
2000
4000
6000
8000
10000
Outer iterations: T
Figure 11: objjetivv values, over the number of outer iterations for hyperparameters 0.005 and 3 = 5.0
56

---

HPGD
AMD
ZERO-ORDER
+
--10 10
Figure 12: Reward penalties given to the lower-level agent in each state of the Four-Rooms problem optimized by the HPGD, AMD, and Zero-Order, respectively, for hyperparameters 0.001 and 3.0
HPGD
AMD
ZERO-ORDER
G
+
100
-100
Figure 13: Reward penalties given to the lower-level agent in each state of the Four-Rooms problem optimized by the HPGD, AMD, and Zero-Order, respectively, for hyperparameters 0.001 and 9= 5.0
HPGD
AMD
ZERO-ORDER
-10
-
Figure 14: Reward penalties given to the lower-level agent in each state of the Four-Rooms problem optimized by the HPGD, AMD, and Zero-Order, respectively, for hyperparameters 0.003 and 1-0 1.0
57

---

HPGD
AMD
ZERO-ORDER
10
Figure 15: Reward penalties given to the lower-level agent in each state of the Four-Rooms problem optimized by the HPGD, AMD, and Zero-Order, respectively, for hyperparameters 0.003 and 3.0
HPGD
AMD
ZERO-ORDER
+
+
-00
--001
Figure 16: Reward penalties given to the lower-level agent in each state of the Four-Rooms problem optimized by the HPGD, AMD, and Zero-Order, respectively, for hyperparameters 0.003 and 9= 5.0
HPGD AMD
ZERO-ORDAE
S
10
Figure 17: Reward penalties given to the lower-level agent in each state of the Four-Rooms problem optimized by the HPGD, AMD, and Zero-Order, respectively, for hyperparameters 0.005 and 3 1.0 1.0
58

---

HPGD
AMD
ZERO-ORDER
10
--001
Figure 18: Reward penalties given to the lower-level agent in each state of the Four-Rooms problem optimized by the HPGD, AMD, and Zero-Order, respectively, for hyperparameters 0.005 and 3.0
HPGD
AMD
ZERO-ORDER
-10
-10
Figure 19: Reward penalties given the lower-level agent in each state of the Four-Roome problem optimized by the HPGD, AMD, and Zero-Order, respectively, for hyperparameters À 0.005 and 8 5.0
F.3
Tax Design for Macroeconomic Models
E3.1
Implementation Details
(s)) max(0. (0, 1og(s/20 1)) and wss) min(s, 0) and select the hyperparameters as 8 = 0.1, Φ = 5.0, = 5.0, w = 1.0 and À = 0.3. We use products in the simulated economy with unit prices and assume two equal-sized socio-cconomic groups with preferences (0.6, 0.3, 0.1) and (0.1, 0.7, 0.2). Assets initialized so N(, v2) and each episode is truncated after 200 steps. Both chosen consumption levels and hours worked are discretized with ranges [0, 5] and [0, 8] and cardinality 5 and 10, respectively. All tax rates initialized 0.3 and optimized over the continuous domain [0.0, 2.0].
In experiments,
E.3.2 Effects of lower-level regularization
Figure 20 and Figure 21 shows the results for X 0.3 and À 0.1, respectively. Changing the regularization has small effects on the final results and only marginally change the speed of convergence, especially for the Zero-Ordes algorithm.
F44 Computational Costs
We ran our experiments on shared cluster equipped with various NVIDIA GPUs and AMD EPYC CPUs. Our default configuration for all experiments was single GPU with 24 GB of memory, 16 CPU cores, and GB of RAM per CPU core. For all parameter configurations reported in Table 3, the total runtime of the experiments for HPGD, AMD, and Zero respectively, totaling 59 hours. Our total computational costs including the intermediate experiments estimated be 2-3 times more.
Zero-Order Order were 17, 40, and 2 hours,
59

---

HPGD
Uppes level objective
31
0.04
HPGD g5
Tax rates
HPGD
ZERO-ORDER
10-
ZERO-ORDER y1
ZERO-ORDER 3
0.2-
35
200
800
1000
200
3.0
9.0
1000
Outer iterations:
Outer
(a) Performance on the Tax Design problem
(b) Tax rates the outer iterations.
Figure 20: Results with À 0.3
Upper level exive. F
HPGD
HPGD 3:
0.04
HPCD
45
Tax rates
HPGD
ZERO-ORDER
10-
ZEHO-ORDER 51
ZEHO-ORDER 3:
HPGD
0.24
3b
35
200
800
1000
200
3.0
0.0
1000
Outer iterations:
Outer iteraiion:
(a) Performance on the Tax Design problem
(b) Tax rates the outer iterations.
Figure 21: Results with À 0.1
60

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our Abstract gives a short overview of our main contributions. Moreover in the Introduction (Section 1), state the contributions clearly with bullet points and point to the relevant sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: For all proofs we clearly state the assumptions (see Assumption 3.1 and Assumption 3.2) we need to make and write the main limitations multiple times in the text. For the experiments we clearly point the sensitivity of the regularization parameters.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
61

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:[Yes)
Justification: Our Appendix E contains all proofs to all our statements. For our main theorem (Theorem 3) we further give a proof sketch in the main paper to help with intuition. Our Assumptions are clearly stated.
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We describe the main experimental setting in Section while provide details explanation in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
62

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide all code related the research in this paper at https://githhnn com/ hamm/aggroop/HHG..
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
Saaides/CooeSubiiin
conPolicy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips wttpccccppccccccttcccccccccccttt wew.uddee/oeeeuubeeeeeeeeeeeeeee ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All experimental details including hyperparameter selection is described in Appendix F.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report the average over 10 random seeds and the corresponding standard errors for the experimental results reported in Table 3 and on Figure 1b.
Guidelines:
The answer NA means that the paper does not include experiments.
63

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report our used resources in Appendix F.4.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics attps://neurs http://wwwrrppssccpppiiiiee wttee/hthhsueeelenmeeeeeem ines?
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and conducted the research following the guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work has theoretical focus without immediate impact society.
64

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
To our best knowledge there do not exist such risks for our work.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cite all codes and models used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
65

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ comdaatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We neither have crowdsourcing experiments nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We neither have crowdsourcing experiments nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
66

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
67


Reviews:
[{"review_id": "HFlg5gHAqG", "reviewer": "Reviewer_UZX1", "summary": "The paper introduces BO-CMDPs, a form of two-level optimization problems in which the inner optimization is a contextual MDP and the outer optimization problem selects the injected context based on some objective. The authors connect this formulation to a range of interesting domains (meta-RL, economics & reward shaping), before proposing a gradient-based algorithm for solving these problems. Depending on the level of insight the outer optimiser has into the workings of the inner different convergence guarantees are established before the algorithm is assessed on a toy example. An ablation into the role of several hyperparameters is also provided.", "questions": "A minor point: Would it make sense to rename the problem setting to Bi-cMDP? \"BO\" is quite overloaded with Bayesian Optimisation and might be slightly confusing for some readers.", "limitations": "The authors assumptions are stated were necessary.\nThe algorithms limitations and room for future work are briefly outlined in the final section of the paper.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Overall the work is well-presented and easy to follow.\n\nThe introduced problem setting is well-motivated and connected to existing work. The example applications are of high interest to the community and lend further importance to the proposed formulation.\n\nTechnical contributions and theoretical analysis appears sound and the empirical examination supports the authors claims.", "weaknesses": "Arguably, the main limitation of the paper is the simple nature of the toy example.\n\nWhile the provided results appear promising and the examinations of the learned incentive maps illustrate the viability of the algorithm, they leave questions regarding the computation complexity and scalability of the proposed method.\nI think such questions could be answered by returning to one of the motivating examples (e.g. Meta-RL or Reward Shaping tasks) and applying HPGD to some moderate-to-large-scale settings. This would also lend further credibility to the papers motivating settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful evaluation and valuable comments.\n\n**Experiments.** Thank you for the nice suggestions. The current experiment already covers an important economic application of Principal-Agent reward shaping, as initially motivated. We will clarify this connection in the final version of the paper. In addition, we would like to emphasize that the primary contribution of our paper is the novel problem setting, algorithmic design, and the convergence for HPGD, providing the first upper bound on the complexity of bilevel RL in a stochastic setting. For comparison to prior works and their complexities, we add a summary table in the attached PDF. It illustrates that our setting is more general and our randomized algorithm more practical. \n\nIncluding more experiments would definitely be interesting. While Meta-RL, Reinforcement Learning with Human Feedback, and Dynamic Mechanism Design are significant applications of BO-CMDP, these are very active research areas and are worth more thorough investigation, which we plan to address in future work.\n\n**Naming.** We really appreciate your suggestion to rename the problem setting. We agree that both \"BO\" and \"CMDP\" are overloaded terminology with “Bayesian Optimisation” and “Constrained-MDP”, respectively. We will consider renaming the problem setting.\n\nWe sincerely hope that our responses have answered your questions and concerns, in which case, we would appreciate if you could raise your scores appropriately. If you have additional questions, please reach out to us during the discussion period and we will be happy to clarify.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qMly9Wzebo", "reviewer": "Reviewer_Y6ix", "summary": "This paper considers the bilevel reinforcement learning problem with lower-level contextual MDPs. As compared to existing works, the problem considered is more general. The paper proposes a hyper-gradient based method. The hyper-gradient can be directly evaluated by leveraging the close form optimal policy in terms of optimal value function, enabled by the entropy regularization in the lower level. Furthermore, the paper establishes non-asymptotic convergence for the proposed method.", "questions": "How does the complexity of the proposed algorithm compare to the existing methods? A table of result comparison might be beneficial for putting this work in context.", "limitations": "no potential social impact", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strength of this work can be summarized as:\n1) The paper is well-written and easy to follow.\n2) Compared to previous works where the lower level problem does not include context, the lower-level contextual mdp considered in this work is more general and includes more applications.\n3) The close form hyper-gradient facilitates practical implementation.", "weaknesses": "Though the paper offers experiments showing the effectiveness of their method, the experiments might be a bit boyish. I believe the work could benefit more from including more scaled up experiments like meta RL listed in the application section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to evaluate our work and appreciate their comments.\n\n**Experiments.** Thank you for the nice suggestions. The current experiment already covers an important economic application of Principal-Agent reward shaping, as initially motivated. We will clarify this connection in the final version of the paper. In addition, we would like to emphasize that the primary contribution of our paper is the novel problem setting, algorithmic design, and the convergence for HPGD, providing the first upper bound on the complexity of bilevel RL in a stochastic setting.\n\nIncluding more experiments would definitely be interesting. While Meta-RL, Reinforcement Learning with Human Feedback, and Dynamic Mechanism Design are significant applications of BO-CMDP, these are very active research areas and are worth more thorough investigation, which we plan to address in future work.\n\n\n**Complexity comparison.**\nWe followed your suggestion of providing a Table of comparison with prior works to highlight our contribution. It can be found in the attached PDF and will be included in the final version. \nThe related works, which we compare to are listed below. Note that two of them were published only recently and were thus not yet included in our submission.\n\n-  **[Chakraborty et al., 2024]** Chakraborty, S., Bedi, A., Koppel, A., Wang, H.,\nManocha, D., Wang, M., and Huang, F. (2024). PARL: A unified framework\nfor policy alignment in reinforcement learning from human feedback. In The\nTwelfth International Conference on Learning Representations.\n\n- **[Shen et al., 2024]** Shen, H., Yang, Z., and Chen, T. (2024). Principled penalty-\nbased methods for bilevel reinforcement learning and rlhf. arXiv preprint\narXiv:2402.06886.\n \n- **[Chen et al., 2022]** Chen, S., Yang, D., Li, J., Wang, S., Yang, Z., and Wang, Z.\n(2022). Adaptive model design for markov decision process. In International\nConference on Machine Learning, pages 3679–3700. PMLR.\n\nThe table emphasizes that in our work we consider stochasticity in the hypergradient estimates, at the upper level (via the context), and at the lower level when using Q-learning. None of the three factors has been considered in previous work. Note that these three points are essential to design a scalable and practically relevant algorithm. Furthermore, we emphasize that if we do not have a stochastic hypergradient estimate, i.e. the variance of our estimator is zero, the last term $\\alpha$ vanishes in our Theorem 3. This improves the convergence rate of HPGD to $\\mathcal{O}(1/T)$, which translates to $\\mathcal{O}(\\varepsilon^{-2})$ complexity in the upper level in Table 1 and our analysis thus exactly recovers the deterministic rates of previous works. Theorem 3 therefore both subsumes and significantly extends the previous results in the literature. \n\nWe hope that our additional comparison table provides valuable insights for the reviewer, in which case, we would appreciate if you could consider raising the scores appropriately.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ckTQfaTvNc", "reviewer": "Reviewer_miD3", "summary": "This paper introduces the framework of bilevel optimization with lower-level contextual MDPs (BO-CMDP), which covers a wide range of practical decision-making applications. The authors of this paper propose the Hyper Policy Gradient Descent (HPGD) algorithm for solving BO-CMDP. They prove the convergence of HPGD theoretically and demonstrate the practical efficiency of HPGD in experiments.", "questions": "- In line 551, the authors said they used the results from [30]. It seems like they used Lemma 1 in [30] which requires stepsize $\\alpha\\leq 1/(2S_f)$, but the authors did not mention this requirement for stepsize $\\alpha$ in either the main text or the appendix of this paper. Moreover, the coefficient before $S_f$ in [30] is 1, whereas in this paper, the coefficient is 2. Could the authors explain the reasons for this discrepancy?\n\n- Assumption 3.1 requires further clarification. In line 551, the authors used the infinity norm, but in Assumption 3.1, the specific norms used for $\\nabla f$ were not specified. \n\n- Typos:\n\nIn line 551, should $L$ be $L_f$?\n\nIn line 188, the $(s,a)$ on the left side of the equation should have subscripts about $t$.\n\nIn line 599 and subsequent lines, $d\\log P_x(s’;s,a)$ missed $/dx$.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper introduces an interesting framework of BO-CMDP and shows that many practical applications can be formulated as BO-CMDP problems. The authors propose HPGD and prove its convergence. The authors also verify the practical efficiency of HPGD by experiments.", "weaknesses": "There are several typos in the statements and the proofs of the main results of this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to evaluate our work and appreciate their comments.\n\nFor Assumption 3.1, we will clarify that the statement is with respect to the infinity norm. We will also add the assumption on the stepsize from [30] and fix the typo in line 551, where the extra 2 is not needed, as well as all other typos pointed out. Note that the results remain unchanged. We greatly appreciate your help to present the paper in its best possible form. In the attached one-page PDF, we add a summary table comparing the differences between our work and prior works that only consider deterministic updates without context information.\n\nIf you have additional questions, please reach out to us during the discussion period and we will be happy to clarify. If you have no further concerns, we would appreciate it if you could consider raising the score as you see appropriate.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2WhDF8HVMq", "reviewer": "Reviewer_Gnk4", "summary": "This paper proposes a general approach for bilevel optimization where the lower-level component is modeled as a Markov Decision Process (MDP). Traditional solvers for bilevel optimization often involve the computation of the Hessian term, which can be complex and computationally intensive. The main strategy employed here leverages the properties of entropy-based reinforcement learning (RL), which offers a closed-form solution. Consequently, the lower-level problem is simplified to a best response function, streamlining the training process. The authors also explore additional scenarios, including one where the upper-level objective is a discounted reward and another where the leader can further influence the follower.\n\nExperiments conducted in a four-room environment demonstrate the effectiveness of the proposed method.", "questions": "Please answer my question mentioned above.", "limitations": "Please refer to the weaknesses section.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The problem setting of bilevel optimization in reinforcement learning (RL) is crucial for the community. \n\nThe authors provide a detailed theoretical analysis of their proposed methods.", "weaknesses": "1) The methods proposed might only be used when the lower-level components have a closed form, as the algorithm relies on the closed form provided by entropy-based reinforcement learning (RL). What happens in cases where entropy RL is not used in the lower-level MDP, such as in meta RL?\n\n2) The authors propose various scenarios, including meta RL and macroeconomic modeling, but only test the method in the Four-Rooms environment. Could the authors also conduct experiments on meta RL or economic models, and compare relevant baselines?\n\n3) Proposition 9 follows the established work closely, which limits its theoretical contributions.\n\n4) The authors propose having full access to the lower-level components, but this does not seem to be utilized in the experiments. It would be beneficial to include experiments that make use of this access.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments.\n\n**Q1: Entropy**\nEntropy regularization allows us to compute the hypergradient explicitly without resorting to implicit differentiation. Without the entropy term, the lower level admits multiple solutions. The problem thus becomes ill-posed as one needs to decide which optimal policy to use in the upper-level objective and our method is not directly applicable. \n\nHowever, with regularization, our problem is still harder than classical stochastic bilevel optimization with a strongly convex lower level. Moreover, important RL applications use regularization. For example, recent work has framed RL with human feedback (RLHF) as a BO-CMDP with lower-level entropy regularization [Chakraborty et al., 2024]. We will include this example in the next version. Additionally, prior work on bilevel RL also considered lower-level regularization. In fact, [12, 39] have shown that entropy-regularized RL approximates the unregularized problem as $\\lambda \\rightarrow 0$ by bounding the gap between the regularized and unregularized problems in both the upper and lower-level objectives.\n\nConcerning meta-RL; in Sec. 2.2 we present a formulation with KL divergence instead of entropy regularization. The optimal policy in this case is also a softmax of the form $\\pi^*_{x,\\xi}(s;a)\\propto \\exp(Q^*_{\\lambda,x,\\xi}(s,a)/\\lambda+\\log(\\tilde{\\pi}(s,a)))$, with $\\tilde{\\pi}$ being the target policy [Vieillard et al., 2020]. Therefore, our analysis can extend to this setting. We will clarify this in the next version.\n\n**Q2: Experiments**\nThank you for the nice suggestions. The current experiment already covers the important economic application of Principal-Agent reward shaping, as motivated in Sec 2. We will clarify this connection in the final version. We would like to emphasize that the primary contribution of our paper is the novel problem setting, algorithmic design, and the convergence of HPGD, providing the first upper bound on the complexity of stochastic bilevel RL. For comparison to prior works and their complexities, see Table 1 in the attached PDF. It illustrates that our setting is more general and the randomized algorithm more practical. \n\nIncluding more experiments would definitely be interesting. While Meta-RL, RLHF, and Dynamic Mechanism Design are significant applications of BO-CMDP, these are very active research areas and are worth a more thorough investigation, which we plan to address in future work.\n\n**Q3: Prop. 9**\nOn a high level, the proof of Prop. 9 works similar to [30], as both papers use multi-level Monte Carlo (MLMC). However, on a more detailed level, there are several unique challenges in BO-CMDP, not covered in [30].\n\nThe first challenge (cf. Sec. 3.4) is that in [30] samples generated to estimate the hypergradient are independent from the lower-level decision variable. This is crucial to control the variance. When calculating their respective estimates $\\frac{d}{dx}F_{t_{k+1}}$ and $\\frac{d}{dx}F_{t_k}$, they can sample once and use the same data for both hypergradient estimates, such that the variance of $\\frac{d}{dx}F_{t_1}+p_{{k}}^{-1}\\left[\\frac{d}{dx}F_{t_{{k}+1}}-\\frac{d}{dx}F_{t_{{k}}}\\right]$ is easy to bound. \nIn our case (cf. Alg. 1), the hypergradient estimate depends on an action $a$ and a trajectory following $a$, both generated by the lower-level policy. Thus, the data used to estimate hypergradient depends on the lower-level decision and one cannot use one trajectory to estimate both $\\frac{d}{dx}F_{t_{{k}}}$ and $\\frac{d}{dx}F_{t_{{k}+1}}$. On the other hand, sampling different trajectories, according to $\\pi_{t_k}$ and $\\pi_{t_{k+1}}$ would significantly increases variance.\n\nThe second challenge is that the estimator of the advantage derivative $\\widehat{ \\partial_x A^{\\pi^{t_k}}}(s,a)$, computed in Alg. 2 has itself a high variance. This issue does not arise in [30], as they do not consider RL in the lower level. \n\nTo address the first challenge, we can use importance sampling, i.e. sampling the action $a$ from $\\pi_{t_{k+1}}$ for both estimators with an additional factor $\\frac{\\pi^{t_k}(a;s)}{\\pi^{t_{k+1}}(a;s)}$ for the second one. \n\nTo address the second challenge, we can compute $\\widehat{ \\partial_x A^{\\pi^{t_k}}}(s,a)$ by averaging over $2^k$ trajectories to control the noise.\n\nBy addressing these two challenges as described, we obtain a desired variance bound of $\\mathcal{O}(K)$, which further strengthens Proposition 9. In the final version, we will clarify the challenges and the technical contributions we make in overcoming them.\n\nTo conclude, while the high-level proof ideas of Prop. 9 follows [30], extending their results to the class of BO-CMDP is important and non-trivial, as the latter poses unique challenges not addressed in previous works.\n\n**Q4: Lower-level Access**\nTo clarify, BO-CMDP is a broad class of problems where the upper level can influence some (but necessarily all) of the lower-level MDP's rewards, transitions and initial distribution. Contrary to previous works, we do not allow full access/control over how the lower-level problem is solved. The only exception is Sec. 3.4, where we discuss how to leverage full access to accelerate HPGD. \n\nOur experiments study reward shaping, which is an important instance of BO-CMDP. While conducting experiments in other settings is interesting, we leave them for future investigation (see our answer to Q2). We hope this answers the question. Otherwise, please clarify what is meant by \"access to lower-level components\".\n\n**Final Remarks**\nWe hope our clarifications and proposed changes address the reviewer's questions, in which case, we greatly appreciate it if you could consider raising the score appropriately.\n\n**New References**\n\nChakraborty et al., 2024. PARL: A unified framework for policy alignment in reinforcement learning from human feedback.\n\nVieillard et al., 2020. Leverage the average: an analysis of kl regularization in reinforcement learning.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their efforts and helpful comments. We appreciate that all reviewers recognized our contributions and efforts. Specifically, they highlighted:
- Our "well-motivated" *(UZX1)* problem formulation (BO-CMDP) and “interesting framework” *(miD3)* that is "crucial for the community" *(Gnk4)* with "example applications [...] of high interest to the community and [that] lend further importance to the proposed formulation" *(UZX1)*
- The “detailed technical analysis” *(Gnk4)* that establishes non-asymptotic convergence guarantees.
- The style and writing of the work. In particular, we were happy to reviewers found the paper "well-presented" *(UZX1)*, "well-written" and "easy to follow" *(Y6ix)*.

Reviewer Y6ix asked us to include a Table, summarizing our work to other results on bilevel RL, which we were more than happy to do. The resulting comparison can be found in the PDF. The table emphasizes that our work is the first to consider contextual lower-level MDPs, stochasticity in the hypergradient estimates, and randomized algorithms to solve the lower level problem (when using Q-learning). None of these three factors was ever considered in previous work. We note, when the hypergradient estimator becomes deterministic, we recover exactly the same upper-level convergence rates as previous works. Moreover, when using stochastic updates, our *randonmly-truncated Q-learning* (RT-Q) algorithm significantly reduces the number of lower-level iterations needed.

Meta-review: **Summary:**
The paper addresses bilevel reinforcement learning with lower-level contextual MDPs, introducing a gradient-based method called Hyper Policy Gradient Descent (HPGD). It establishes non-asymptotic convergence for HPGD and demonstrates its effectiveness through experiments.

**Strengths:**
- The framework of bilevel contextual MDPs (BO-CMDPs) is a significant and novel contribution with broad practical applications.
- The proposed HPGD algorithm is theoretically sound, with proven convergence and practical efficiency.
- The paper is well-written and clearly presented, making complex concepts accessible.

**Weaknesses:**
- The experiments are limited to a simple toy example; more diverse and large-scale applications are suggested.
- The paper’s theoretical analysis and results are somewhat constrained by reliance on closed-form solutions provided by entropy-based RL.
Decision: Accept (poster)