Meta-Reinforcement Learning with Universal Policy Adaptation: Provable Near-Optimality under All-task Optimum Comparator
Authors: Siyuan Xu
Minghui Zhu
Venue: NeurIPS 2024 poster (2024)
Keywords: Meta-learning
reinforcement learning
Primary area: reinforcement_learning

Abstract: Meta-reinforcement learning (Meta-RL) has attracted attention due to its capability to enhance reinforcement learning (RL) algorithms, in terms of data efficiency and generalizability. In this paper, we develop a bilevel optimization framework for meta-RL (BO-MRL) to learn the meta-prior for task-specific policy adaptation, which implements multiple-step policy optimization on one-time data collection. Beyond existing meta-RL analyses, we provide upper bounds of the expected optimality gap over the task distribution. This metric measures the distance of the policy adaptation from the learned meta-prior to the task-specific optimum, and quantifies the model's generalizability to the task distribution. We empirically validate the correctness of the derived upper bounds and demonstrate the superior effectiveness of the proposed algorithm over benchmarks.

Meta-Reinforcemeee Learning with Universal Policy Adaptation: Provable Near-Optimality under All-task Optimum Comparator
Siyuan Xu & Minghui Zhu School of Electrical Engincering and Computer Science
The Pennsylvania State University University Park, PA 16801 (spx5032, muz16) ) @ @psu.edu
Abstract
Meta-reinforcement learning (Meta-RL) has attracted attention due to its capability to enhance reinforcement learning (RL) algorithms, terms of data efficiency and generalizability. In this paper, we develop a bilevel optimization framework for meta-RL (BO-MRL) to learn the meta-prior for sask-specific policy adaptation, which implements multiple-step policy optimization on one-time data collection. Beyond existing meta-RL analyses, we provide upper bounds the expected optimality gap over the task distribution. This metric measures the distance of the policy adaptation from the learned meta-prior to the task-specific optimum, and quantifies the model's generalizability to the task distribution. We empirically validate the correctness of the derived upper bounds and demonstrate the superior effectiveness of the proposed algorithm over benchmarks.
Introduction
Meta-lcarning [58] 15 25) aims to extract the shared prior knowledge, known as meta-prior, from
the similarities and interdependencies of multiple existing learning tasks, in order to accelerate the learning process, increase the efficiency of data usage, and improve the overall learning performance in new tasks. Meta-learning has been extended to solve RL problems, known meta-RL [15] []],
and shows its promise to overcome the challenges of traditional RL algorithms, including scarce real-world data
65 limited computing resources, and slow learning speed [54] 63)
Meta-learning methods be generally categorized into aptimization-basel model-based (black box methods), and metric-hased methods [2 The optimization-ban based meta-learning approach [25) is compatible with any model trained by an optimization algorithm, such as gradient descent, and thus is applicable to a vast range of learning problems, including RL problems. Specifically, it formulates meta-learning as bilevel optimization problem. At the lower-level optimization, the task-speeific model is adapted from shared meta- mneaa-paraeeter by an optimization algorithm. At the upper-level optimization, the meta-pas patammeereetrr to maximize the meta-objective, i.e., the performance of the model adapted from the meta-paramen parameter over training tasks. The existing methods, including MAML and variants [15 38 [2] take a one-step gradient ascent as the lower-level policy optimization algorithm, which limits its data inefficiency and leads to sub-optimality.
During the meta-test, MAMI conducts one-time data collection, i.e., collecting data using one policy (the meta-policy), and adapts the policy by one step of policy gradient to the new task. However, the collected data is only used in one policy gradient step. which may sufficiently leverage the data and potentially fail to achieve a good performance. To mitigate the issue, a typical practice is to implement the data collection and the policy gradient alternately multiple times [3]]. However, the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Solved theoretical challenges of meta-RL
Convergence of meta-objective
Optimality of meta- meta-objective
Near- eear-optimality
under aas- optimum
12
57
x V When assuming convergence
x
60
X
x
V Under optimal
4
expert policy supervision
This paper
Immediate result from 60
environment exploration is usually costly and time-consuming during the meta-test in applications of meta-RL [44] 6 36). As a result, the low data efficiency limits the optimality of task-specific policies. collect data by meta-policy for one time and utilize multiple policy optimization steps to improve the data efficiency.
In contrast, in this paper,
The optimality analysis of MAML is studied in 12 60 with a metric of optimality on the meta- objective, where the error of the meta-objective defined by the expectation of the optimality gap between the task-specific policy adapted from the learned meta-parameter and the policy adapted from the best meta-parameter [60] 14 26). However, the best mnta-parametee is shared for all tasks. Even if the meta-objective error is close to zero, i.e., the learned meta-parameter is close to the best one, the model adapted from the learned meta- parrmmeter might be far from task-specific optimum for some tasks. In contrast, aim to design meta-RL algorithm that can fit stronger optimality metric, called near-optimality under all-task optimum, where the comparator, i.c., the policy adapted from the best meta-pane parameter, is replaced by the task-specific optimal policy for each task. This metric offers a more strict comparator for the model adapted from the learned meta veta-paramettr, i.e., when the metric achieves zero, the policy adaptation produces the optimal policy for every task. A similar metric is studied by [42.. It assumes that the task-specific optimal expert policy for each task is accessible and serves the supervision for policy adaptation during meta-training, which alleviates the analysis difficulty caused by the optimal policy comparator. However, the expert policy supervision is not accessible
standard meta-RL problem. The metric under all-task optimum is also studied by [9 10 655 in the context of supervised meta-learning.
Main contribution. We develop a bilevel optimization framework for meta-RL, which implements multiple-step policy optimization on one-time data collection during task iesk-specific policy adaptation. The overall contributions summarized as follows. (i) We develop universal policy optimization algorithm, which performs multiple optimization steps to maximize a surrogate of the accumulated reward function. The surrogate is developed only using one- one-time data collection. It includes various widely used policy optimization algorithms, including the policy gradient, the natural policy gradient (NPG) (30), and the proximal policy optimization (PPO) [52) as the special cases. Then, learn the mete-prior, we formulate the meta-RL, problem as a bilevel optimization problem, where the lower-level optimization the universal policy optimization algorithm from the meta-policy and the upper-level optimization is to maximize the meta-objectiy function, i.c., the total reward of the models adapted from the meta-policy. (ii) We derive the implicit differentiation for both unconstrained and constrained lower-level optimization problems to compute the hypergradient, i.e., the gradient of the meta-objective, and propose the meta-training algorithm. In contrast to [60. we do not require to know the closed-form solution of the lower-level optimization. (iii) We derive upper bounds that quantify (a) the optimality gap between the adapted policy and the optimal task-specific policy for any task, and (b) the expected optimality gap over the task distribution. Since the proposed framework incorporates several existing meta-RL. methods, such as MAML, as a special case, the analysis also provides the theoretical motivation for them. (iv) We conduct experiments to validate the theoretical bounds and verify the efficacy of the proposed algorithm on meta-RL RL benchmarks.
Table I compares the solved theoretical challenges of meta-RL between this paper and previous works
60 42 Specificallyy paper [60] derives the optimality on the meta-objective under the assumption of bounded hypergradient. Papers 12 57 consider the convergence of the meta-objective. The near optimallty under all-task optimum is considered in [42]. However, assumes the optimal expert policies of the training tasks are available in meta-traine meta-training, such that it can learn to approach the expert policies, while the other methods do not require the expert policies and learn from the explorations of the environments. In this paper, we show the convergence and optimality guarantee on the meta-objective, and, more importantly, the optimality guarantee under the all-task optimum comparator. It is noted that the optimality on the meta-objective is an immediate result from (60).

---

2 Related works.
Categorization of meta-RL. Meta-RL methods can be generally categorized into (i) optimization- based meta-RL, (ii) black-box (also called context-based) meta-RL. Optimization-based meta-RL approaches, such as MAML [5] and its variants [55] 38) usually include a policy adaptation algorithm and a meta-algorithm. During the meta- metai-rainingg the meta-algorithm aims to learn a meta-policy, such that the policy adaptation algorithm can achieve good performance starting from the meta-policy. The learned meta-policy parameter is adapted to the new task using the policy adaptation algorithm during the meta-test. Black-box meta-RI. [11 [9 49 68) aims to learn an end-to-end neural network model. The model has fixed parameters for the policy adaptation during the meta-test, and generates the task-specific policy using the trajectories of the new task takes. In optimization- baasd meta-RL, the task-specific policy is adapted from a shared meta-poligg over the task distribution. The learned meta- weeta-nnowledg is not specialized for each task, and its meta-test performance on task depends that task. In contrast, the end-to-end model in black- meta-RL. RL typically includes specialized knowledge for any task within the task distribution, and uses the new data merely an indicator to identify the task within the distribution. As a result, the optimality of optimization-be based methods is usually worse than black-box methods, especially when the task distribution is heterogeneous and the data scale for adaptation is extremely small. On the other hand, the policy adaptation algorithms in the meta-test of pptimizatiion-baed methods can generally improve the policy starting from any initial policy, not only the learned meta-policy. Therefore, it is robust to sub-optimal meta-policy and can deal with tasks that are out of the training task distribution [16] 62). In contrast, due the specialization of the learned model, black-box methods cannot be generalized outside of the training task distribution. In this paper, we focus on the category of optimization- based meta-R -L and compare the proposed algorithm with the existing optimization-ban based meta-RL. approaches in terms of both experimental results and theory.
general policy optimization algorithm applied to new data from
Bilevel optimization in meta-RI. Bilevel optimization has been widely studied empirically 45 18
21
17
53
29 and theoretically (20
22 29) It has been applied to many machine learning problems,
including meta-learning 35 [88. hyperparameter optimization 45 17 18]. RL
[24 34 and inverse
33 40 41. Since the overall objective function in bilevel optimization is generally non-convex, theoretical analyses of bilevel optimization mainly focus on the algorithm convergence [20] 29] 64], rarely on the optimality. This paper formulates meta-RL as bilevel optimization problem. The key theoretical contribution of this paper is to derive upper bounds on the near-optimality under all-task optimum, i.e., the expected optimality of the solutions of the lower-level optimization compared with that of the task- spec-specific optimal policies. The pear-optimality under all-task optimum is unique to meta-learning and has not been studied in the literature on bilevel optimization.
RL
3 Problem statement
MDP. A Markov decision process (MDP) M A (S,A, T.p, P,r) is defined by the bounded state space S, the discrete or bounded continuous action space A, the discount factor 7, the initial state distribution P over S, the transition probability P(s'|s, a) S Ax S + [0, 1]. and the reward function : S x A X S + [0, T'az].
Policy and value function. A stochastic policy π : S + P(A) is a map from states to probability distributions over actions, and T raass) denotes the probability of selecting action a in state s. For
a policy n, the value function defined as V*(()) _ 1E 7'r (sx, de, 81+ 1) |so = 8, m]. The 20 7'r (St, ae, 82+1) 1) 180 = 8, ag = a, T.. The E -
action-value function is defined as Q" (s. a) - E
advantage function is defined as A AT a) (*((xa)= - V*(s), The accumulated reward func- tion is (TT) e Eepp [s)] Define the discounted state visitation distribution of a policy as ox (s) A [1 - ?) EP (s+ = s/z)]. In this paper, we consider parametric policy me. parameterized by 0. The optimal parameter 0* can maximize the accumulated reward function, i.e., gr argmax, JmTo). If 8" is not unique, denote the set of the optimal solutions by e
Meta-reinforcemmnn learning. Meta-RL aims to solve multiple RL tasks. Consider space of RL tasks H, where each task E I is modeled by MDP M A AS, Pr, Pr.r.). Correspondingly, the notations V.2. Q7, AE, UF, 0z, O and J, are defined for task т. The RL tasks follow probability distribution P(T). Meta-RA RL aims to leam peta-policy To parameterized by meta parameter é.
3

---

such that it can adapt to an unseen task Tnew ~ P(T) with a few iterations and small number of new environment explorations. In specific, during the meta-training. several tasks can be i.i.d. sampled from IP(T), i.e., (T;)}= P(T)), and the tasks' MDPs (Mr, 1ز=1 can be explored. The meta-learner applies a meta-algorithm to update the meta parameter & by using the data collected from the sampled tasks. During the meta-test, new task nnw is given, one time of within-task algorithm Alg with data collected from Thew is applied, the meta-parameter @ is adapted to the task-specific parameter 0' ''.... and the task-specific policy W8tma. is tested on the task Trew.
Optimality Metric. Consider a meta-RL algorithm that produces meta- parameter o and the take-specific parameter Te; is adapted from the meta-paraman parammeer 6 on task т. denoted as næ; Alg r). We define the task-expected optimality gap (TEOG) as the metric to evaluate the algorithm, i.e., [r- T. First, the TEOG considers the expected error over the task distribution P(T). reflecting the generalizability of the produced veta--arameter. Second, the TEOG adopts the comparator of the optimal task specifcc policy To; for any task T (all-task optimum comparator), and evaluates the optimality gap J. ( (Alg(TT, 7)). In contrast, [60] I4 (6) adopts the comparator of the policy adapted from the optimal meta-pate peta-paraetter T and evaluates the optimality gap (= .))
- Jr (Alg(TT, +))], where 0 is the optimal parameter for task
Jr (Alg(TTT T)). The latter only considers the optimality on the meta-objective, i.e., how well the trained meta-objective can approach the optimal meta-objective. However, even if the error of the meta-objective is approaching zero, i.e., the learned meta-policy is close to the best candidate, the performance of the model adapted from the optimal meta-policy might still be lacking. This is because policy optimization usually requires thousands of value/policy iterations to converge; when tasks are heterogeneous, even if it starts from the best meta-policy, one time of Alg with one time of value estimate may not be sufficient. In contrast, if our metric is zero, the policy adapted from the meta-parameter to any task is optimal for the task.
Policy distance and task variance. To find the solution for a new task within a few iterations of policy optimization. is crucial that the meta-policy To can benefit from learning on correlated tasks. Similar to 4 9 31, we measure the correlation of tasks in the task distribution P(T) by its variance, defined by the minimal mean square of the distances among the optimal task-specific policies, i.e.,
(TT(P(T)) ming ming; E,-P(T) [D? (ma, To;)l. Here, D=(TO, To;) is the distance metric between Ty and Te; on the task T and is defined by (TT ) - V [dP no (-1s))],
where d((Ta(1s)), To ( (-Is) is the distance of the policies Te and TT. on the state s.
Note that the distance metrics D+(:-) and d(. .(....)) can be custom-defined, leading to multiple policy update algorithms, as shown in Section Here, we introduce several examples of d( d(.,., s)
and -.(-,), which are commonly used as the distance metrics in RL literature [51] 30 371 For
policies Ty and Te. we apply (i) the KL-divergence of the action probability distribution, i.c.. (TTO s) s) & (To(T(() || To (-1s)). which is similar to the definition in (3I]: (ii) The KL- divergence with the other order, i.e., (B(TO, To., 5) A D [I distance of the parameters, i.c., dB(TT. (8) & 110 - 0'112. Correspondingly, for i = 1,2, and 3, we define (To, ) A V VE (TO; no,, , s)]- Note that the distance metrics (i) are not symmetric, i.e., (TTrr TTr) ) F (TTr,, T. ). and (iii) is symmetric.
(iii) the Euclidean
In the subsequent sections, we present algorithms based on the generalized distance definitions of :-(::) and ( Moreover, conduct analyses for the introduced distance metrics, from Dr,1 to Dr,3, to provide comprehensive insights into their respective performances.
4 Meta-Reiiforcemmntt Learning Framework
In this section, we develop meta-RL algorithm by bilevel optimization, where the lower-level optimization is the -ith algorithm that adapts the parameter from the meta- meram-ar and the upper-level optimization is the meta-algorithm that obtains the meta peeta-parameter.. The proposed algorithm has two distinctions compared with existing algorithms. First, it uses one time of a universal policy optimization algorithm as the lower-level within-task algorithm. Second, we derive the hypergradient by the implicit differentiation, where the closed-form solution of the lower-level optimization is not required.

---

Within-task algorithm. Consider the policy optimization from the meta policy as the within- algorithm Alg. Specifically, given the meta-parameter @ and a task T, the task-specific policy To; = Alg( To. X, r) is defined by 0z = PrggmaxP..... .a-ma(-1ss) [Q (s.a).
XD ( (T To)-
When the action space is discretized and the policy tabular, i.e., the probabilities of actions are independent between different states, the above problem can be solved by Taz (-18)
Alg(TT (T A, (-(s)) argmax
Enea (o (s, a) Ad >d ( (-ss) (-(sss)
*a(-|=)
for all states S. When the policy is parameterized by approximation function, in both continuous and discrete action space A, To; = Alg((To X, T) is computed by 8
(a(a))) (a(a)s)
argmaXg snuys a (-16)
Q7 (s.aa >Dz (TT) me).
(2)
In (1) and (2). A O is a tuning hyperparameter and the distance metric D, can be arbitrarily chosen. Considering the explorations for the task are limited, Alg only needs to evaluate the Q? by Monte-Carlo sampling on single policy TH, where the data sampling complexity exactly the same as the one-step gradient descent in MAML [15. Therefore, we denote Alg, i.e., collecting data
on the meta- meta-policy and solving the optimal solution of I and 22 as the one-time policy adaptation. More details about the data sample complexity and the computational complexity of (T) and (2) are clarified in Appendix F On the other hand, one gradient step is usually not sufficient to identify a good policy. Therefore, Alg is to solve the optimal solution of (L) (2) As shown in Section (..4
the objective function of (T) or (2 is an approximation of the true objective function Jr (x))
Note that the objective function in (I) and 2 can reduce to that of multiple widely used policy optimization approaches: (i) PPO in 52 when D, = Dr.2; (ii) a variant of the PPO (60 [7] when D. = D (iii) the proximally regularized policy update, i.e., the policy optimization regularized by Euclidean distance of the policy parameter [5T), when D, = Dr.3- Moreover, (iv) we approximate the expectation in (2) by its first-order approximation and also select D, D,,3, the within-tass algorithm (2) also can be reduced to one-step policy gradient, as shown in Appendix HH (v) if use the first-order approximation of the expectation in (2). the second-order approximation of the term (T ). and select D, = Dr.2, the within-tash algorithm 2 is reduced to the natural policy gradient (NPG).
Meta-algorithm.
The performance of the meta-paramess Φ evaluated by the meta-objective function, which is defined as the expected accumulated reward after the parameter is adapted by the within-task algorithm, i.e., [- X, r))] In the meta-algorithm, we maximize the meta-objective to obtain the optimal meta-parameter o² i.e.
argmax EJ (Alg(To T)]]
(3)
As I and 2 provide multiple choices of the within-task algorithms when selecting different D,, the meta-algorithm 3 provides the algorithms learn the corresponding meta-priors. For example, (3) takes on the role of the meta-PPO algorithm when D, = Dr.1 or Dr.2, i.e., (3) learns the mntta-iitialiiztionn for PPO. It is a meta-NPG algorithm with the corresponding approximation and Dr. Moreover, when Alg A, r) in (2) reduces to the one-step policy gradient shown in (iv) of the last paragraph, (3) represents a precise formulation of MAML in [1]. More details about the formulation and its relations with MAMI. are shown in Appendix G and
64 the meta-algorithm in (3) aims to solve bilevel optimization problem. In previous works (60), they apply the policy optimizations that have known closed-form solutions as the lower-level within-task algorithms. As a result, the bilevel optimization problem is reduced to a single-level problem. In contrast, in this paper, as we consider a universal pol- icy optimization, its closed-form solution cannot be obtained. To address the challenge, we compute V Alg((T. X, r) and the hypergradient by deriving the implicit differentiation on Alg(To, A, r). As shown Section the optimization problem Alg (T. X, r) is unconstrained in (2). but is constrained in T due to Eae <[als) = 1. Therefore, we derive the implicit differentiation for both uncon- stramed and constrained optimization problems. The following proposition shows the hypergradient computation for the tabular policy. Its proof is shown in Appendix J.1
Hypergradient computation. Simlar to 29
Proposition 1 (Hypergradient for the tabular policy). For the tabular policy in the discrete state-action space, consider any meta-paramend
and the within-task algorithm ( Let
5

---

TØ; Alg(To. (.T). If ((s) A aar 711s (To()1)) (-1ss) is non-singular for each E
S. we have Vody = - SNut 7o EDEE VOTT: (als)] Q- nM (s, ai). where V Te; (-|s) =
(M(s)-2 M(e) 1 [M(6)="
@ (s, Aa V
(--as) (-o (1)( To;
M
The computation of V Q (s.-) -) is shown in Appendix C A sufficient condition of (s) being non-singular is that d is locally strongly-convex
me; shown in Appendix I.I Moreover,
when d d1 or d d2 (correspondingly, D, Dr,1 D, Dr.2 in ( the matrix M(s) XV ((1as) d ( (-1 s), r(-ss)) is always non-singular for any Φ and M(s) is always diagonal, and thus is easy to compute M M-1(s). The hypergradient computation Vo)+(()))) for D, = Dr,1 and D,,2
shown in Appendix K. and L.1
The following proposition shows the hypergradient computation for the policy with function approxi- mation. Its proof is shown in Appendix J.2
Proposition 2 (Hypergradient for the policy with function approximation). When a policy is represented by function approximation, in both the discrete and continuous action spaces, for any meta-pet meta-parameter & and the within-task algorithm in Let Tø. Alg( X, T).
Ve met (als) net (s. 0)]. and
If V (To)( exists, VoJ+(TOL) - V
Top (als) QT
anono (-1a) ( (ano(" Vidl (TO Te(- - (amolals) AFo((al)
Brave
THt
V 0- = -E Bnu
Q (s,
E sNN aa
& [V J V Ved ( (e(-s)) Vanalale) Aro(ols)
V Q7 a))1==8;
sufficient condition of V (To)(T);) being existent the objective function of (2 is locally strongly
concave at 9 = 8,, as proven in Appendix J.2 The computation of V VoQT (s,-) is shown in Appendix
C Note that we need compute the inverse of the Hessian when computing the hypergradient in
Proposition
2 Similar to several widely used RI. algorithms, such as TRPO [51] and CPO []]
we apply the conjugate gradient algorithm 23 to compute the inverse of the Hessian, which has demonstrated high efficiency across wide range of applications of RL and meta-learning [51] 29 15]
More clarifications about the computation efficiency of the Hessian inverse are shown in Appendix
Algorithm 1 Meta-Training for BO-MRL
Require: Regularization weight À >> O; Initial meta meta-paraaannn parameter dui learning rate
1: for t= 0,.... T do
Sample task F P(T) with MDP M, i.i.d.
3: Evaluate g for current meta-policy Ta, by Monte-Card sampling
Adapt the task-specific policy ne; from the meta-policy Te. by solving Te; Alg(A, se, defined
(1) or 2).
5:
Evaluate Q- (..-) for adapted policy Toy Monte-Carlo sampling
6: Compute the hypergradient VaJr(ma;) ) Proposition 2 by conjugate gradient method
7: Update meta-pane paraaaarreeeer d1+1 di + aV (Toe)
8: end for
Return ØT
With the hypergradient computations Proposition and Proposition 2 we apply the stochastic gradient ascent (SGD) solve the optimization problem in (3). The meta-training of the bilevel optimization framework for meta-RI. (BO-MRI)) is formally stated in Algorithm [ The state-action value function in lines and 5 can be estimated by many approaches, including Monte-Carlo sampling used in MAML [15] and vine in [51]. We also propose practical algorithm of Algorithm[] as shown in Algorithm 2 in Appendix D. which includes more implementation details of the algorithm and several mechanisms to improve Algorithm[]
Theoretical Results
In this section, we quantify the performance of Algorithm distance metrics introduced in Section 3 are adopted. For convenience, denote Alg Alg in and (2) when D,- Dr.1, and denote (l and (lg in analogous way. In Section 5.1
[ where the softmax policies and several

---

introduce the softmax policy and necessary assumptions. In the following three sections, we consider two cases of Algorithm including (i) Algorithm I with the within-task algorithm Alg and Alg for the tabular softmax policy; and (ii) Algorithm with the within-task algorithm Alg for the softmax policy with function approximation. For the algorithms in (i) and (ii), we study the existence of hypergradient Section [522] derive the convergence guarantees in Section [3.3] and derive the near-optimality under the all- optimum, i.e., derive the upper bounds of TEOG, Section 5.4
5.1 Softmax policy and assumptions
We apply the softmax policies, which are commonly applied assumptions on the task r.
66
37
60
and use the following
Softmax policies. Consider the softmax policies ftg parameterized by 0 for (i) the tabular policy and (ii) the policy with function approximation. In particular, the tabular policy in a discrete state-action space is defined by f-{()s) x exp(f(s. :)), where 0 E RIS [A] a tabular map. The policy with function approximation is defined by ft(-(s) x exp(fo(s,)) )), where fo is function approximation model& S x A -> IR with the parameter 0 E IR". Assumption 1 (Upper bound of advantage function). For any task T E I and any softmax policy ft.. (A5 a)l < Amax for any a E A and any E S.
Since the reward r, S Tmaa is bounded, it is easy show that (A, S Emux and Assumption 1-y
1 always holds. But still keep Assumption I here, since there usually exist Amar such that maz Tmoz We also have the following assumption and show its remark.
Assumption 2 (Sufficient state visit). For any task T E T, there exists a constant > 0, such that for all bounded parameters 6, Vr (x)(s) 2 for all E S.
Remark 1. Here are two sufficient conditions for Assumption 2 (i) For any task T E I, the MDP M, is ergodic [43 56]; or (ii) the initial state distribution Pr has pr (8) > 0.ror any any E S.
The proof of Remark is shown in Appendix O Note that (i) of Remark 1 is mild condition and is assumed in recent studies on RL algorithm analysis [6 [6).
For the policy with function approximation, we require the following additional assumptions on the approximate function Jo. which are standard or weaker than those the analysis of meta-learning
and meta-RI. problems (9, 12 13 [1].
Assumption 3 (Property of the approximate function). For any state-action pair (s, E S A. (i) the approximate function fo(s,a) are cubic differentiable. (ii) fols, a) is Li-Liscchitz iee. [o, (s, a) - So, (8,a)) a)ll < Lı |0; 02rl any 0,,02 E R.. (iii) Vala(s, a) is Lz-Lipschitz, i.e. VoJo, (s, a) VaJo (8, a)ll < L2|00 02l for any 0,, 02 E RR, (iv) VjJa(s a) is Lz-Lipschitz. Le., V85o, () Vifo, (s, (s,a)] & L - 02l for any 0₁ 02 E TR..
5.2 Existence of hypergradient.
An essential prerequisite for using Algorithm 1 is that the hypergradients in Propositions [ and 2 exist. As shown in Section 4 for the tabular policy, when i = 1 or 2, the hypergradient VoJ, (Alg()) >, 7)) exists for any 6. For the policy with function approximation, we derive the following sufficient condition of the hypergradient being existent. Its proof is shown in Appendix M Proposition (Existence of hypergradient for the policy with function approximation). In both discrete and continuous action space, consider the softmax policy with function approximation shown in Section 5.1 Suppose that Assumptions and hold. If X > (6L + 2L2) A (alg(Al) (T X,T)) always for any d.
5.3 Convergence guarantee
We begin with the convergence guarantee of Algorithm | for the tabular policy. The following
notations are used in the theorem: B,, C., Gi, K1, M, (i 1 and 2), where K; A 2(B, )r
(1-7)*
M, A (B.+20)) for i = 1 and 2. B, A 16rmus
+ 1- + 1. G - - and G₁ 2 44 4Ames
(1-7)"
A[1-7F
(1-7)²
B2 A(1-))3
16rmez + [I-ンパ C2 A 4 . and G2 A 2Amas (1-7)²-
18

---

Theorem 1 (Convergence guarantee for tabular softmax policy). Consider the tabular softmax policy in the discrete action space. Suppose that Assumptions I and 2 hold.
Let (dr)t= be the sequence of mela-parameiers generated by Algorithm 1 with X
2 -1 (1-7)²
2Amaz and the step size a - -min [mar [1-3p
G.VT Then, the bound:
+E MI (#o. A, A.
K.
Mr holds for or VT
The first expectation comes from the random sampling in line 2 of Algorithm Theorem are shown in Appendices K. and
! The proofs of
The following theorem shows the convergence guarantee for the policy with function approxima-
tion. The notations are used in the theorem: B3. C3. G3, K3, M3. where K3 & 2[B max
(1-7)*
A (Ba+22))Garmar G3 A Am (A+ (A+, 1- L.AAmo))
21+ 27 19.mos)
M3
C3 A
[1~ (62) +2lg) and
(1-7))
[1->](A-(ain))) +2az)
11602]+66L/ Lo 22, LiAmaz)² (1-
B3
Theorem 2 (Convergence guarantee for softmax policy with function approximation). In both dis- crete and continuous action space, consider the softmax policy with function approximation. Suppose that Assumptions
and hold. Let {Øt) be the sequence of meta-paranie preta-parameters generated by Algo-
{
rithm l with À > (612 + Amaz and the step size a min
(1-))
Ymas Bg
2nrman
(1-7))
GaVT
Then, the bound + + E (A (fr X, T)1))111
Kg
holds. vT
The first expectation arises from the random sampling in line 2 of Algorithm ! The proof of Theorem 2 is shown in Appendix M Theorems T and 2 show that the convergence rate of Algorithm | is and the constants in the notation O are only related to the discount factor the reward bound Tmaz: the bound of the advantage function Amaz, and the Lipschitz constants of fo-
5.4 Near-optimality under all-task optimum
Before the derivation of the optimality analysis, we first introduce two intermediate Lemmas.
Lemma 1. Suppose that Assumptions 7 2 hold. For any task T, any bounded parameters and 6', and = or 2, we have (f - J, (fte) 2 Esnuz and (-1a)
(x.().))
27Amaz D2
D2 ).
1-7
(1-7)²e
Lemma 2. Consider the softmax policy with function approximation shown in Section 5.1 Suppose that Assumptions 7 2 and and Wolld For any task t, and any softmax policies parameterized by bounded
0 and 0', have J, ( J, (ite) 2 E. snut aa (-1a)
A_5
(s.0)
4nAmaaLi (fte, (1-7)²
The proof's of Lemmas 1 and are shown in Appendix N.1 Given Lemma when A 27Amaz the
(1-7)e
within-tase task algorithm (1 T) in is actually designed to maximize the right-hand side of the inequality, where #' is the decision variable. Similarly, Given Lemma 2 when = 47 12
(1-7)e
Alg (3) (fa; 7, 2 maximizes the right-hand side of the inequality, where कe. the decision variable. In other words, for each = 1,2, and 3, the within-tast algorithm Alg is to maximize a lower bound of Jr (fte. denoted as J, (ft)) This idea, referred to as the
(MM) (28). is widely used in [51 33) The design of Alg enables us to connect the accumulated reward of the policy after the policy adaptation with that of the optimal policy केद for task t, i.e.,
(Alg (T,, X, T)) 2 J= (fre)) which is a key intermediate result for the optimality analysis.
The final preparatory step is that borrow the analysis of the veta-training error from [60]. In particular, its theoretical result encapsulated in the following assumption.
Assumption 4. (Bounding error of meta-objective using gradient) Let (() A (Alg)))))))))))))))))))))))))))) T))] For both the tabular policy and the policy with functional approxi- mation, there exists concave positive non-decreasing function h; : [0, +00) - [0, +00), such that maxy FOt) (o') FF) & (.F
8

---

Assumption 4 assumes the optimality gap of 7e on the meta-objective is upper bounded by an increasing function of its gradient. A sufficient condition of Assumption is provided by [60]. Combine the Assumption and the convergence analysis in Theorems I and 2 we can bound the error of the meta-objective, i.c., max (o) }+0 (Φt). This result is referred to as the optimality of the meta-objective shown in Table [ Finally, we derive the upper bounds of the TEOG for both
the tabular policy and the policy with function approximation.
Theorem (Optimality guarantee for softmax tabular policy). Consider the tabular soft- max policy for the discrete state-action space. Suppose that Assumptions [72 and E
hold. Let { be the sequence of parameterssssrs generated by Algorithm 7 with Then, the following holds for
2Amaz and the step size a shown in Theorem (1-7)e
[
i 1 or 2: E Br ( Jr (Alg (f S h1 (4+ -
2(1+7) Var, (PP)))((T)) where fee; is the optimal softmax policy for task T and the constants K; and (1 (1-7))
Mj are shown in Theorem! 7
Theorem 4 (Optimality guarantee for softmax policy with function approximation). In both
discrete and continuous action space, consider the softmax policy with function approximation. Suppose that Assumptions 2 and 4 hold. Let {ot)t= be the sequence of meta- peea--arraeeters generated by Algorithm with
(GL7 (iL7+2L)AAman and the step size a shown in Theorem 2
(1-7)c
The following holds: 1. Et= Es (ET [Jr - (A >, S ha
K3 +
Ma
T
vT)
+22,)))mm2 (P(T), where #oo is the optimal softmax policy for task 7 and the constants (1-7)'²c K3 and M3 are the same as Theorem 2
The proofs of Theorems 3 and theorems, are shown in Appendix N.2 The theorems derive the upper bounds of the TEOGs between the parameter adapted by one- one-time policy adaptation from the produced meta- metaa-araameter o and the task-specific optimal parameter 8r. It is shown that, with at most T iterations, we can achieve the upper bounds in the order of (hhe( ( Var(P(T))) In other words, there exists
well as the selection of the hyperparameter À in these two
t S T with E,yp(rr) (Alg(( X,)) 2 E (+to))) O(h, (+7) Var((P(T))) As the number of iterations T increases, or the variance of the task distribution (ar(P(TT) reduces, the optimality of the meat-parameter & improves. The second term Var((P(T)) in the upper bounds of Theorems 3 and and corresponds the intuition of meta-learning, which is that, if the variance of task distribution is smaller, the meta-policy learned from the task distribution is more helpful for new tasks in the task distribution, then the performance is better. Moreover, this term shows that the learned meta-policy achieves a better performance than the meta-policy geenter defined by arg ming (,,,(r) DD*, 7,6 (To, (To) which is the center of all the task-specific optimal policies Te;
The order of our upper bounds comparable to O + Var(P(T)) that is shown in (31). On the other hand, compared with (31) in this paper, the constants in the notation O only consist of Tmaz, Amaz. and the Lipschitz constants of f. and do not rely on |A] and (S]. As a result, our upper bounds are tighter when handling high-dimensional problems or continuous spaces.
Monotonic improvement of the within-task algorithm. Another benefit from Lemmas and and the idea of MM used by the within-task algorithm is that, the policy update by the within-task
algorithm monotonically improves, i.e., J, (Algg (ftg. X, r)) 2 J, (ftg for i = 1, and and any and any task Therefore, multiple times of Alg always perform better than one-time Alg.
6 Experiments
6.1 Verification of theoretical results
We conduct an experiment to verify the optimality bounds of Algorithm shown in Theorems 3 and
We consider two scenarios of the Frozen Lake environment in Gym: two task distributions with a high task variance and a low task variance. More details of the setting and the hyperparameter selection are shown in Appendix A We consider the within-task algorithm Alg for all = 1, 2 and
3. where the results of = 2 and 3 are shown in Appendix A

---

High valerce (4gHt koll
14y uppled)
14gh vok abrowen (Ag appleed
Low taak varinnsn (ig appledd
Eiprctee Opemadty
100
Randon iiai coke
Rardan statiadi
0.1
MANE.
Number palcy scaplation stapa
Number polccy acpptationniicccoooc
1f
Figure I: Results of the meta-test on Frozen Lake, where Alg (2) is applicd. Left: Average accumulated reward across test tasks v.s. number of policy adaptation steps; Right: Comparing the expected optimality gap by the BO-MRL and baselines with the upper bound of the accumulated reward of one-time Alg
Hat-cheatah goot voloc
Hot-chosteh moniyg dreckon
Act. good valocit
Art. movingg drection
Acomuatte mexdd
MAMK-1000 M000
lovel 1150
kood T9PD
2910
Numbe adapiation
Sumbbr assptation
Namber adap
policy a'laptatiio stops
Figure 2: Average accumulated reward across all test tasks during the meta-test under the practical algorithm of BO-MRL on the locomotion tasks.
We compare our algorithm with MAML 15 and the random initialization. Figure D shows that, for Algorithm| 1 with the within-task algorithm Alg it outperforms the baseline methods. For all scenarios, the expected optimality gap of the one-time policy adaptation is smaller than the upper bounds shown in Theorems 3 and 4 which verify our theoretical analysis. Morcover, in Figure [ the expected optimality gap of the policy adaptation is better (smaller) but close to the upper bound, while that of the other policy adaptation approach, the policy gradient, is worse (larger) than the upper bound. It shows that the derived upper bound is tight.
6.2 High-dimensional Experiment
To evaluate the proposed practical algorithm, Algorithmßin Appendix D we conduct experiments on high-dimensional locomotion settings in the MuJoCo simulator, including Half-Cheetah with goal directions and goal velocities, Ant with goal directions and goal velocities. We compare the proposed algorithm with several optimization- bbaaed meta-RL algorithms, including MAML, E-MAML (55) and ProMP [50]. For the fairness of the comparison, all the methods share the same data requirement and task setting. More details of the task setting, the hyperparameter selection, and the supplemental results are shown in Appendix B
Figure 2 shows that the proposed algorithm with the within-task algorithms Alg outperforms the baseline methods in all four experimental settings. For example, we achieve about 25% of performance improvement in Half-cheetah direction and Ant direction experiments. Moreover, compared with the baseline methods, the proposed algorithm achieves more policy improvement when more policy optimization steps are given. For example, our approach achieves about 10% of performance improvement in the second policy optimization step, while those of bascline methods are almost 0%.
Conclusion
This paper develops bilevel optimization framework for meta-RL, which implements multiple-step policy optimization on one-time data collection during task-specific policy adaptation. Beyond existing meta-RL. analyses, we provide upper bounds of the expected optimality gap over the task distribution. Our experiments validate the bounds derived from our theoretical analysis and show the superior effectiveness of the proposed framework.
10

---

Acknowledgments and Disclosure of Funding
This work is partially supported by the National Science Foundation through grants ECCS 1846706 and ECCS 2140175. We would like to thank the reviewers for their constructive and insightful suggestions.
References
[1] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pages 22-31. PMLR, 2017.
[2] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. The Journal of Machine Learning Research, 22(():4431 14144311-66,,, 2021.
[3] Karol Arndt, Murtaza Hazara, Ali Ghadirzadeh, and Ville Kyrki. Meta reinforcement learning for sim-to-real domain adaptation. In 2020 IEEE International Conference on Robotics and Automation, pages 77225-7731 IEEE, 2020.
[4] Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- based mecaa-carning. In International Conference on Machine Learning, pages 424-433. PMLR, 2019.
[5] Jacob Beck, Risto Vuorio, Evan Zheran Liu, Zheng Xiong, Luisa Zintgraf, Chelsea Finn, and Shimon Whiteson. A survey of meta-reinforcement learning. arXiv preprint arXiv:2301.08028, 2023.
[6] Suneel Belkhale, Rachel Li, Gregory Kahn, Rowan McAllister, Roberto Calandra, and Sergey Levine. Model-based reta-reenforcemeent learning for flight with suspended payloads. IEEE Robotics and Automation Letters, 6(2):1471-1478, 2021.
[7] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint 1rXiv:1666.0:. 2016.
[8] Imre Csiszár and János Körner. Information theory: coding theorems for discrete memoryless systems. Cambridge University Press, 2011.
[9] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. Learning-to-lenn stochastic gradient descent with biased regularization. In International Conference on Machine Learning, pages 1566-1575. PMLR, 2019.
[10] Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil. Online-within-nile online meta-learning. Advances in Neural Information Processing Systems, 32, 2019.
[11] Yan Duan, John Schulman, Xi Chen, Peter L Bartlett, Ilya Sutskever, and Pieter Abbeel. RL?: Fast reinforcement learning via slow reinforcement learning. In International Conference Learning Representations, 2017.
[12] Alireza Fallah, Kristian Georgiev, Aryan Mokhtari, and Asuman Ozdaglar. On the conver- gence theory of debiased model-agnostic meta-reinforcemen learning. Advances in Neural Information Processing Systems, 34:3096-3107, 2021.
[13] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- based model-agnostic meta-learning algorithms. In International Conference on Artificial Intelligence and Statistics, pages 1082-1092. PMLR, 2020.
[14] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Generalization of model-agnostic meta- learning algorithms: Recurring and unseen tasks. Advances in Neural Information Processing Systems, 34:5469-5544 -5880 2021.
[15] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. International conference on machine learning, pages 1126-1 133.. PMLR, 2017.
11

---

[16] Chelsea Finn and Sergey Levine. Meta-learning and universality: Deep representations and gradient descent can approximate any learning algorithm. In International Conference on Learning Representations, 2018.
[17] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-basee hyperparameter optimization. In International Conference on Machine Learning, pages 1675-113. PMLR, 2017.
[18] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning, In International Conference on Machine Learning, pages 1568-1577. PMLR, 2018.
[19] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
[20] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming, arXiv preprint arXiv: 1802. 02246.2226622 2018.
[21] Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprini arXiv: 1607.055077 2016.
[22] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo, On the iteration complexity of hypergradient computation. In International Conference on Machine Learning. pages
PMLR, 2020.
[23] Magnus Hestenes and Eduard Stiefel. Methods of conjugate gradients for solving. Journal of research of the National Bureau of Standards, 49(6):409, 1952.
[24] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
[25] Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A survey. IEEE transactions on pattern analysis and machine intelligence, 44(9):5149-516 2021.
[26] Yu Huang, Yingbin Liang, and Longbo Huang. Provable generalization of overparameterizeed meta-learning trained with SGD. Advances in Neural Information Processing Systems, 36566- 16576, 2022.
[27] Mike Huisman, Jan N Van Rijn, and Aske Plaat. A survey of deep meta-learning. Artificial Intelligence Review, 54(6):4433-454 2021.
[28] David R Hunter and Kenneth Lange. A tutorial algorithms. The American Statistician, 58(1):30-37, 2004.
[29] Kaiyi Ji, Junjie Yang, and Yingbin Liang, Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892. PMLR, 2021.
[30] Sham M Kakade, natural policy gradient. Advances neural processnn 14, 2001.
processing systems,
[31] Vanshaj Khattar, Yuhao Ding, Javad Lavaci, and Ming Jin. CMDP-within-nlinee framework for meta-safe reinforcement learning. In International Conference on Learning Representations, 2023.
[32] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 112.v:1412.6980, 2014.
[33] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
12

---

[34] Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems, pages 1008-1014, 2000.
[35] Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10649-10657,, 2019.
[36] Thomas Lew, Apoorva Sharma, James Harrison, Andrew Bylard, and Marco Pavone. Safe active dynamics learning and control: A sequential exploration-exploiittion framework. IEEE Transactions on Robotics, 2022.
[37] Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimization attains globally optimal policy, Advances in neural information processing systems, 32, 2019.
[38] Hao Liu, Richard Socher, and Caiming Xiong. Taming MAML: Efficient unbiased meta- reinforcement learning. In International conference machine learning, pages 4061-4071. PMLR, 2019.
[39] Shicheng Liu and Minghui Zhu. Distributed inverse constrained reinforcement learning for multi-agent systems, Advances in Neural Information Processing Systems, 35:33444-33456, 2022.
[40] Shicheng Liu and Minghui Zhu. Learning multi-agent behaviors from distributed and streaming demonstrations. In seventh Conference Neural Information Processing Systems, 2023.
[41] Shicheng Liu and Minghui Zhu. Meta inverse constrained reinforcement learning: Convergence guarantee and generalization analysis. In The Twelfth International Conference on Learning Representations, 2023.
[42] Russell Mendonca, Abhishek Gupta, Rosen Kralev, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Guided meta-policy search. Advances in Neural Information Processing Systems, 32, 2019.
[43] Teodor Mihai Moldovan and Pieter Abbeel. Safe exploration in markov decision processes. In Proceedings of the 29th International Coference International Conference on Machine Learning, pages 1451-1458, 2012.
[44] Anusha Nagabandi, Ignasi Clavera, Simin Liu, Ronald S Fearing, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Learning to adapt in dynamic, real-world environments through meta- reinforcement learning. In International Conference on Learning Representations, 2018.
[45] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning, pages 737-746. PMLR, 2016.
[46] Shuang Qiu, Zhuoran Yang, Jieping Ye, and Zhaoran Wang. On finite-time convergence of actor-critic algorithm. IEEE Journal on Selected Areas in Information Theory, 2(2):652-66 664, 2021.
[47] Roberta Raileanu, Max Goldstein, Arthur Szlam, and Rob Fergus. Fast adaptation to new environments via policy-dynamics value functions. In Proceedings of International Conference on Machine Learning, pages 7920-7931, 2020.
[48] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances neural information processing systems, 32, 2019.
[49] Kate Rakelly, Aurick Zhou, Chelsea Fino, Sergey Levine, and Deirdre Quillen. Efficient off-policy meta-reinfforeement learning via probabilistic context variables. In International Conference Machine Learning, pages 5331-5340. PMLR, 2019.
[50] Jonas Rothfuss, Dennis Lee, Ignasi Clavera, Tamim Asfour, and Pieter Abbeel. Promp: Proximal meta-policy search. In International Conference on Learning Representationss 2019.
13

---

[51] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
[52] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint vrXiv:/707006344 2017.
[53] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
[54] Xingyou Song, Yuxiang Yang, Krzysztof Choromanski, Ken Caluwaerts, Wenbo Gao, Chelsea Finn, and Jie Tan. Rapidly adaptable legged robots via evolutionary meta-learning, 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3769-3776. IEEE, 2020.
[55] Bradly C Stadie, Ge Yang, Rein Houthooft, Xi Chen, Yan Duan, Yuhuai Wu, Pieter Abbeel, and Ilya Sutskever. Some considerations on learning to explore via metu-reinforeement learning. arXiv preprint 1iXiv:1803.000 2018
[56] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[57] Yunhao Tang. Biased gradient estimate with drastic variance reduction for meta reinforcement learning. In Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 21050-21075. PMLR, 17-23 Jul 2022.
[58] Sebastian Thrun and Lorien Pratt. Learning to learn. Springer Science & Business Media, 2012.
[59] Jane X Wang. Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning reinforcement learn. arXiv preprint arXiv: /6/ 1.05663, 2016.
[60] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. On the global optimality of model- agnostic meta-learning. In International conference on machine learning, pages 9837-9846. PMLR, 2020.
[61] Yue Frank Wu, Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33:17617- 17628, 2020.
[62] Zheng Xiong, Luisa M Zintgraf, Jacob Austin Beck, Risto Vuorio, and Shimon Whiteson. On the practical consistency of meta-reinforrement learning algorithms. In Fifth Workshop on Meta-Learning at the Conference on Neural Information Processing Systems, 2021.
[63] Siyuan Xu and Minghui Zhu. Meta value learning for fast policy-centric optimal motion planning. Roboties Science and Systems, 2022.
[64] Siyuan Xu and Minghui Zhu. Efficient gradient approximation method for constrained bilevel optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 32510) 12517, 2023.
[65] Siyuan Xu and Minghui Zhu. Online constrained meta-learning: Provable guarantees for generalization. In Thirty-seventh Conference on Neural Informaionn Processing Systems, 2023.
[66] Tengyu Xu, Yingbin Liang, and Guanghui Lan. Crpo: A new approach for safe reinforcement learning with convergence guarantee. In International Conference on Machine Learning, pages 14880-11491, PMLR, 2021.
[67] L. Zintgraf, K Shiarlis, M Igl, S Schulze, Y Gal, K Hofmann, and S Whiteson. Varibad: very good method for bayes-adaptive deep via meta-learning. Proceedings of ICLR 2020, 2020.
[68] Luisa Zintgraf, Kyriacos Shiarlis, Maximilian Igl, Sebastian Schulze, Yarin Gal, Katja Hofmann, and Shimon Whiteson. Varibad: very good method for bayes-adaptive deep via meta- learning. In International Conference on Learning Representations, 2019.
14

---

Appendix for "Mett-Reinforcement Learning with Universal Policy Adaptation: Provable Near-Optimality under All-task Optimum Comparator"
Experimental Supplements
All experiments are executed on computer with a 5.20 GHz Intel Core i12 CPU.
A Experimental Supplements of Verification of Theoretical Results.
Experimental settings. In Section 6 we use the Frozen Lake environment in Gym 7 and consider a task distribution P(TT) with high task variance and a task distribution IP(T) with low task variance. In each distribution, there are 20 tasks. The tasks characterized by the different settings of holes in the lake, where the holes are generated by random sampling. In the task distribution with high variance, the probability of the appearing hole in each grid is 0.3; in the task distribution with low variance, its probability is 0.1. We set Y 0.8, the reward is 1 when reaching the goal, and the reward - when reaching the holes. When deriving the upper bound in Theorems 3 and 4 approximately regard T be sufficiently large, and Oh,,( (Trr) )) be close to 0. The Lipschitz of the tabular policy is 1, i.e., L1 1; the Lipschitz of the derivative and the second-order derivative of the tabular policy are both 0, i.e., L2 = and Ly = 0.
Selection of hyper-parameeers. We consider the tabular softmax policy and use Monte Carlo sampling to evaluate the Q-value. For the task distribution with high task variance, we set À 0.5 for Alg (1) A 0.5 for Alg and = 0.04 for (lg For the task distribution with low task variance, we set À = 0.25 for Alg A = 0.25 for Alg and A = 0.02 for Alg There is clarification about the ppprr-prraeeter selection and the verified bound shown in Appendix N..
Supplemental results. Figures 3 and 4 show the results of the proposed algorithm with Alg and Alg (8), It shows that, for all scenarios, the expected optimality gap of the policy adaptation Alg or Alg is smaller than the upper bound shown in Theorems and 4 which verify our theoretical analysis.
CROETe Aoguraaaee resen
1. applns)
14gh spoloc)
applect)
05-UFLI
50-MTL Jumn)
MAA
NAYI
Opimal cotippecoopiconn
Optinall trab poi
of pokay antgration skips
Number palicy adactator stegs
Figure 3: Results of the meta-test of BO-MRL on Frozen Lake, where (lg is applied. Left: Average
accumulated reward across all test tasks v.s. number of policy adaptation steps; Right: Comparing the expected optimality gap by the BO-MRL and baselines with the upper bound of the accumulated reward of one-time (2)
High took vor anco LAg coptied)
Low tack voriance LAy apolledi
Expcated Cydiaaiyy
Expected Cytimaity
aradis Ag
Gratiz
Drenkaro
20
100
Ghaata Of
Figure 4: Results of BO-MRL on Frozen Lake, where (lg gap by the BO-MRL and baselines with the upper bound of the accumulated reward one-time (1)
(3) is applied. Comparing the expected optimality
15

---

B Experimental Supplements of Locomotion.
Experimental settings. We consider locomotion tasks HalfCheetah with goal directions and goal velocities, Ant with goal directions and goal velocities. We follow the problem setups of [67] [5 In the goal velocity experiments, the moving reward is the negative absolute value between the agent's current velocity and a goal velocity, which is chosen uniformly at random between 0.0 and 2.0 for the cheetah and between 0.0 and 3.0 for the ant. In the goal direction experiments, the moving reward is the magnitude of the velocity in either the forward or backward direction, chosen at random for each task in P. For the Half-cheetah, the total reward moving reward- ctrl cost. For the ant, the total reward = healthy reward + moving reward- ctrl cost contact cost. The horizon is H 200, with 20 rollouts per policy adaption step for all problems except the ant direction task, which used 40 rollouts per step.
Selection of hyper-parameters. We apply the proposed practical algorithm of Algorithm I Algo- rithm in Appendix D We consider the policy as Gaussian distribution, where the neural network produces the means and variances of the actions. The neural network policy has two hidden layers of size 64, with tanh nonlinearities. We use Monte Carlo sampling to evaluate the Q-value. At the lower-level task -ascifpe policy adaptation, the optimization number by Adam 50. The models are trained for up to 500 meta-iterations For the TRPO in meta petaa-er optimization, we use the KL-divergence constraint as Le
For the experiment of Calf-Cheetah with goal velocities, set À = 0.5 for Alg A = 0.4 for Alg For the experiment of Half- Cheethh with goal directions, we set À = 0.5 for Alg X 0.5 for Alg(z) For the experiment of Ant with goal velocities, we set À = 0.5 for Alg X = 0.5 for
Alg(2), For the experiment of Ant with goal directions, we set À = 0.5 for Alg (1) = 0.5 for Alg(2)
Comparison setting. We compare the proposed algorithm with several optimization- meta-RL algorithms. including MAML, E-MAML [53]. and ProMP [50]. The experiment results of E-MAML, ProMP, and MAML-TRPP TRPO come from 67 [5] We do not compare the proposed algorithm with black-box meta-RL. RI. algorithms, as they are based on the task context and even can achieve good performance without adaptation.
Supplemental results. T that the proposed algorithm with both within-task algorithms Alg ( outperform the baseline methods in four experimental settings. The accumulated rewards of proposed algorithms increase fast and stop at points with better performance than the baseline methods.
gool weisdry
gosl
gool
gas Dawan parpuoo
of
metiiniinng
meeo-intingg
Figure 5: Accumulated rewards during the meta-training under the practical algorithm of BO-MRL on the locomotion tasks.
Algorithm supplement
C Computation of V 27
In the computation of meta- shown in Propositions I and 2
we need to compute V & Q (
V Vo
7 1 7 ( (oo
In (a'ls') Q7 (s',a'))
(3.0) where the state-action visitation probability 07,00 initialized at (s,a) E S A is defined by
a (1.) T.me
(s',a') = (1 7)) Σ
PP (st s' = a'| 50 ~ P+(11s,
t=0
16

---

For the tabular softmax policy in discrete state- actton space shown in Section 5.1
V Veler.) (8,
7 (0.0) 1-7 r (3)) (s') (-00'1))) & A (s',))
(4)
where O is the element-wise product, Ø(s', is the vector which includes 66s', a') for all d' E A as the elements, and A, 4 (s, is the vector which includes A (s.a) a) for all a E A as the elements. Equivalently,
oas a Q (s, = ?
(s',d').
(5)
For the softmax policy with the function approximation.
Vana(a'b'))
Q7
(8,
7
E
2 of (s.d))
(a'ls))
?
E
(s'
(a.a)
Vofalsi,d (5'
(6)
Ri
7
E (o' (aia)
Vola (4,
Proof. As shown in 60
200 VA (11 (1 ())))r((ss))) +y. Bx [ (s')])
E (ows
V In (a (''ss') Q (s',a')
(s/ (oooon)
1
EE ( (s'','")vokh (ca)
Vo In (a' (a'ls')
A (s',
1
V VoTo (a'ls")
E (o' a')oaao (aa))
A (s', d')
To (d'ls')
By Lemma from 12
we can obtain
44; from (14). we can obtain
D Practical algorithm
In Sections []
we develop a theoretically guaranteed algorithm with Assumptions 1 and In this section, develop practical instantiation of Algorithm I and evaluate its performance in high-dimensional experiments Section 6
Algorithm 2 states the practical algorithm of Algorithm [ Compared with Algorithm Algorithm
considers and overcomes the following limitations of Algorithm T (a) evaluating the exact expectation in ① and ( is costly and the approximation етгоr could influence the task-specific policy adaptation the meta-RL. problem where the sampling data limited: (b) the optimization problems in (1) and (2) have no dlosed-fomm solution; (c) the computation of the gradients of the meta-objectives shown Propositions [ and 2 time-consuming: (d) the gradient- approach to optimize the meta-objective is not stable in RL problems.
using sampling, especially
In the beginning of Algorithm 2, we first sample a batch of tasks {T: IPT)). On each task 7,, we sample the trajectories of the meta-policy Td. as Br,, and evaluate the state-action value function Q (.,-) for each T; Next, since the number of the sampling state-action pairs in B,, is limited, if we directly use the sampling average to approximate the expectation (2). the approximation error will be very large when T (als) is small. Therefore, we solve the following optimization problem as the within-task algorithm instead of (2):
To(als) (a)s)))
no; Alg(A, the T) arg min
Σ (B,
(F, - (T? To),
B
where h(x))
2-= The function h avoids the term [a(ss) is optimized very large. We
Ra(a(s)
use Adam 32 to solve the problem in 77) Next, the computation of the gradients of the meta-
objectives shown in Proposition 2 time-consuming, since the computation complexity of the term
17

---

Algorithm 2 Practical Algorithm of BO-MRL
Require: Regularization weight 0; initial meta-parameste Φo: learning rate
1: for 1, 1.... , do
2: Sample batch of tasks {T, i P(T) with the MDP Mr. i.i.d.
3: On each task T;, sample the trajectories of the meta-policy Td, as Bri.
4: Evaluate the state-action value function Q (-,-) for cach Ti.
5: For each task T, compute the task-specific policy ne: by solving Alg(A, or, Ti) defined in
by Adam.
6: Compute VaJr, (FTr, ) in (8) by conjugate gradient method
7: Update meta- meta-paramann parameter by the TRPO with the gradient N Ei V Votn,(TTr (Tor.) and the sampling
trajectories 1Br,)
8: end for
9: Return ØT
Vona(als) (s, is very high. So, we omit the term, and compute V Vodr (Tee) as
Amglals)
Vor oz no; (als)
Qr Tut (8, (s,0a)
E
of am Tpt (11s)
Top (a|s)
(8)
where
(alo()
E an3a(1116)
Vidl (To(sss)))
\TT(als) Ot (s.
E
Vod ( (-o))))) no (-1)) 8=8;-
Amatl (
Finally, since the gradient-basse based approach is not stable in RL problems, we optimize meta-parameter by the TRPO with the gradient N 2, V Volr, (Tor,) and the sampling trajectories [B, similar to 15
E Discussion about computational complexity of hyper-gradient
In Algorithms D and we compute the inverse of the Hessian matrix when computing the hyper- gradient by Proposition and (8). The computation of the inverse of the Hessian matrix is not time-consuming and does not increase the processing time much. Here are the two reasons.
First, we apply the conjugate gradient algorithm to compute the inverse of the Hessian and its computation complexity not high. According our experiment of Half-cheetah, the computation time of the hyper-gre erper-gradient with the inverse of Hessian for three-layer neural network is about 0.3 second in each meta-parameter update, where we use only the CPU to compute the This approach has demonstrated high efficiency across wide range of applications, including several widely used RL algorithms, such as TRPO [5]] and CPO [. which compute the inverse of the Hessian in each policy update iteration. The detail is shown in Appendix C of (5T). They usually compute thousands times of the Hessian inverse for single RL task. In the simplest meta-RL. method, MAML [5]. the authors use the TRPO to update the parameter, as shown in Section 5.3 of [1], the inverse of the Hessian is also computed. Therefore, the computational complexity of the hyper-gradient in proposed method is comparable to many existing RL and meta-RL RL approaches, which are shown efficient.
Second, the biggest computational bottleneck in the meta-RL framework is not the gradietra computation. According to our experiment, the percentage of the computation time in the meta- parameter update, including the computation time of the syper-gradien computation, is less than 5%, where we use only the CPU to compute the hyper-gradient. The percentage of computation time in the data collection and the Q value computation by Monte-Carlo sampling is more than 70%, although the state-action data points are collected the MDP simulator Gym and the data collection is very fast. In real- world applications, the state-action data points are even harder to collect and
18

---

data collection consumes a longer time. Therefore, the computational time of the hyper-gradient computation has a relatively small impact on the mete-RL framework.
F
Data sampling complexity and computational complexity of one-time policy adaptation
The one-time policy adaptation in our algorithm is defined as solving the optimal solution of the optimization problem in ① or (2) by multiple optimization iterations. The definition of the one- meme policy adaptation follows many widely used RL algorithms, such as TRPO [5T] and CPO [. which evaluate the Q-values for the current policy and solve the optimal solution for an optimization problem to obtain the next policy each policy optimization iteration. For example, TRPO solves the optimization problem in (14) of [51] in each iteration.
In the one-time policy adaptation, we only need evaluate the Q-function for one policy T by Monte-Carlo sampling, which requires the agent to explore the MDP using one policy Tg. then solve the optimization problem in [T] or (2) by multiple optimization iterations with the fixed Q-function. The data sampling complexity is exactly the same as the one-step gradient descent in MAML, which uses Monte- Carlo sampling to evaluate the Q-function and compute the policy gradient based on the Q-function.
The multiple optimization steps in the one-time policy adaptation different from the multi-step policy gradient update in MAMI.. In our algorithm, the multiple optimization steps in a one-time policy adaptation only need evaluate the Q-function for one policy Tg. which requires the agent to explore the MDP using only Tg. In MAML, the Q-function for a new policy needs to be evaluated in each policy gradient update, and then multiple Q-functions are evaluated for multiple policies, which requires the agent to explore the MDP using multiple policies. Instead, the one-time policy adaptation in our algorithm corresponds to a one-step policy gradient update in MAML, as they use the same number of data points.
Moreover, we would like to claim that the computation complexity for the one-time policy adaptation in our algorithm and that of the one-step policy gradient update in MAMI. is comparable, although our algorithm requires multiple optimization iterations. As mentioned in Appendix [E] the computation time in the data collection and the Q value computation takes more than 70% of total computation time, which is much longer than other parts of the algorithm, including the multiple optimization iterations in police adaptation (15% of total computation time). This happens although the state-action data points are collected in the MDP simulator Gym and the data collection is very fast. In real-worke applications, the state-action data points are even harder to collect and the consuming time of data collection is much longer. Therefore, the computational time of the multiple optimization iterations has relatively small impact on the mete-RL. RL framework. Therefore, the computation time of our algorithm and that of MAML is comparable.
From the statement in the above paragraphs, both the data sampling complexity and computational complexity of the one-time policy adaptation in our algorithm and the one-step policy gradient update in MAML are similar. Thus, we define solving the optimal solution of the optimization problem in I or 2 as a single policy adaptation step.
G Algorithm details with the first-order approximation
As we mentioned in Section we can approximate the first term E E,,,, awas (+1a) [.(a|s)))))))))) Q7 (s, a)] in (2) by its first-order approximation as the within-task algorithm, similar to the implementations in TRPO (5T) and PPO (52). In particular, the within-task algorithm is reduced to the following formulation,
molale)
TB Alg(TT X, argmin To A [( DDTTTO++ me).
Here, we use the first-order approximation to replace the first term of In particular, G(Ø) Φ) is the first order approximation of E BNwe (11))))))) (a G( V&E VGEgany (-1s) [emefale) Q (s, a)]le=o = E BaNU," (-1))))))))
ma(a
(s, ()).)] where
(ana(a)s) Q (s, a)].
T (a(ass) Under the simplified within- task algorithm Alg, the hypergradient of the meta-objective function
19

---

(Tor(TT)) can be computed by
V 0r noz (als)
Vodi(TT;)) = -
20
Qr n0: (s.
n4
no; (als)
an (-10)
where
V
V = Vo. D2 Tp=)
V I. (s,a)+
TT(a(s)
Srully (113)
(10)
(alss)
(s, - V V (Ts mp.))
Ta (als)
The computation of VJ 0' derived in Section
J.3
H Connection between the proposed algorithm and MAML
As we claim in Section 4 when we approximate the first term EL s- aron (11s) m Q7 (s, a)] in (2) by its first-order approximation and also select D, D7.3, the within-task algorithm ?
[afals)
is reduced to the policy gradient ascent. In particular, the term _ awm, (11)) Q7 (8,a) approximated by (0 +6) TTT.EAA
(molale)
Vxalals)
Q (5, (s, then the within-task algorithm (a(aaa)
s~u7 (-)
Alg TT. A, r) becomes to
V VoTolalss) (a(a)s)
Q² Q7 (s.0)
84 Alg(TTs 7) a argmax 2110 281 AT
(11)
grapy a
Solve the optimization problem, we have
V (alss To (a|s)
Q7 (s.aa) o 1 1-7
V (0).
0- = Sou
(-18)
which is policy gradient ascent. Thus, when we select (T] the within-task algorithm, the meta- algorithm (3) is reduced to the algorithm that can learn the initialization parameter for the policy gradient ascent.
As shown in 15,, MAMI. also learns the initialization parameter & for the policy gradient ascent. However, MAML ignores that the sampled trajectories with policy Ty also depend on ø. Specifically, MAML first uses the sampled trajectories to approximate " a) by (Monte Carlo sampling the REINFORCE algorithm), then computes the policy gradient and does one step of gradient ascent for the task-specific adaptation. Next, it computes V (O,) to update the meta-parameter é. When it computes V&O', it treats Q (s, a) given data point that is independent with and then ignore the Q=Q.* a). In contrast, our reduced meta-algorithm takes it into account and provides precise formulation to learn the meta-initialization for the policy gradient algorithm.
Since the proposed meta-RL framework can include MAML as special case, our analysis in Section 5 also provides the theoretical motivation for MAMI.
Analysis and Proof
Auxiliary Results
Lemma 3 (Policy gradient [56] 2).. Let ma be the parameterized policy with the parameter 0.
holds that
1
VoJ+(TO)
E Fo (-1o)
[Vo In (n
1 -
1 Na am)o))))))
(V In To (cls) a)].
20

---

Lemma 4 (Policy gradient of the softmax policy). Consider the softmax policy fg parameterized by exp(O(s,a))
0. For a discrete state-action space and the tabular policy, tt(aas) Ewee exp(O(s,aa)) v(s,a)
S x A. It holds that
1 7 vio
V Vo(s.)Jr
- (s,),
(12)
where @ is the element-wise product, .(s,.) is the vector which includes ((s, a) for all a E A as the elements, A (s, .) the vector which includes A (s, a) for all E A as the elements. Equivalently,
V Ve
Vr (s)) (8,a).
(13)
For the softmax policy with function approximation, the policy To is defined by to(als) (xp(fo(s.a))
=
Ia exp(fols.a')daa" V(s a) ES x A. It holds that
VoJ+(
Vo
(14)
soa (
Proof. For the discrete state-action space and the tabular policy, 12 is shown in Lemma C.I of [
For the softmax policy with function approximation, from Lemma we have
J (ft)
1-7 amuff .anit((-1s))
[V In ( (s.
exp(fols,a))
smup s0 amtt((1)))
Voln
exp(folsss a)) a'))
Vofo(s,a) Vn ( exp(fols, a)) a'))da' A7 (s,
Here, V In (IA exp(So(8 (8, a')) d')"
is independent with a, then Vo))(
V - In ( exp((f(s, A3" (s,
envii amt)(1)))
E to (mstu((ss)
7 swv,
Vo In (/ exp(fo(s. ))da'
E
E (1))
Since Bawto(-1o) A5o (s, = Baniol 1n (s,) (s)aa) - V. = 0. Then,
VeJr
E ? sn a
(eff
J Proofs of the computation of hypergradient
J.1 Proofs of Propositions
Proofs of Propositions
7
Consider the within-task algorithm in discrete space:
Alg(To, = argmax E
Σ (alls)
LEEAA
Σ ((als)Q7 (TT((ss))
argmax E
LeE.A
Here, d can be selected from d, d3 defined in Section corresponding to the selection of D, from
Dr.1 to Dr,3.
21

---

The above optimization problem is formally defined by the following problem,
Alg( argmax E
Σ
(- (s, a) Ad (T
sma,
LOEA
(15)
subject Σ
T(aas)) =, for any 8.
With Assumption 2
the problem is equivalent to that, for any E S,
A, argmax *(|ls)
Σ ([
- Ad (1)(())),
aEA
(16)
subject
Σ T(aas)
1.
aEA
Consider 8 E S, the Lagrangian of the above maximization problem is
Σ xalls) (s, a) + (T(( + p (als)) 1), .E.A
cEAA
where j is the Lagrangian multiplier. The optimality condition of (-188 (8) is that,
QT (8, + AV (T)))))( (-18), 111, ... 1] = 0.
Here, Q=* denotes vector include Q (s, a) for each a A. and π (-|ss) denotes vector include T (a|s) for each a E A.
Then, have
(s,,) + AV ( ((1)) pl1,.... .1] -.
(17)
Note that the optimization problem (15) depends on Φ. and x Alg( A, r) is function of d, we have
Q To (s,
AV A ((3)) ((0) ,1]T = =0,
i.e., j is function of 6. Also, we have
m(O)( Σ Alg(TT,), aEA
0.
(18)
With 17 and 18 we can compute V VoAlg(Ta, T) where Alg(Ts, A, is continuously dif-
ferentiable as shown in (64). We do derivative of I7 and (18) with respect to Φ, we have (V Alg A, T), V
2 7 (11s) d (11(()
VJO +AV (F (-1ss) ]
1
0
where म = Alg(TT T)
Solve the equation, we have
Alg(To, X, 7)-1ss) = (M) M(s)-11 1 MM) (
1 11
(19)
VJ Aa V (-1s)
where M(s) = 2V
m (e) ( (1()) It is easy to show that V2 V2 (To(-(s) (-|ss) is
non-singular for any for any selected d d1, d = d2, or d d3.
22

---

From the policy gradient theorem in Lemma 3
V (Tor((TT;))
1
E not
V In To; (a|s)Ar o (s, a)]l =
7
B- lannn (1a)
1
V Vono, (als)
Ar not (s, (s,0) laoe -lg((
E
? smu, Lamay (1a)
Toz (als)
1 1 sma,
V no, (a Fol (8, Alotsoo()))
LaEA
where VoTTo (-1s) = V VoAlg(TT. A, () (-1s) is shown in 19
J.2
Proofs of Propositions
Proofs of Propositions
2
First, have
V V Vo: (Too)
From the policy gradient theorem in Lemma 3
(odr( = 1 1-7
Vol
Vo In ne; (als)Ar n0h (s, lo: A.
o amyy aamoo (165
We have
V Top (als)
V (TOr(
1 VaOg
E not ovpe aartor (116)
mot (8) lo;=Aig(Ta
Toz (als)
Next, we compute V Vabl where
f = Alg(T 7, argmax E
To(a|s)
(5)
(To: (T: mo).
smu, (-11))))))
TT(a|s)
0
The optimization problem is equivalent to
0r A argmax E smatly
T7(als)(7" (s, - (-) To (1(ss))
argmin smN
E
Tz (8, a)da (1))
0
argmin
Ut (8)
(o(als) (s, a)da + de (T (1s), no( mo(-)s))
#ES
Similar to the derivation from
15 to 16
with Assumption 2 we have that, when 0 = Alg(TT,
(-/A To(als) (s, (T(( 0.
Vo
Then, we have
V (s) (-]mo(als) a)da + Ad (Fo(-1)) 0.
To(a|s)
By using implicit differentiation, if the matrix E E. ( (s, + A To(-1s)) invertible, i.e., E EaNug To [- Sa no(als) (F (s, (s,a)da 0 0z we have
Ad (s)( [-()) mo is strongly convex at
[-/ Vire (s. (s. AV (()
mo(1s))
0
E Eanuço
I/A VoTo(als) (s, (s, +E + (T()) =((-ss) +
-E Baanyo Eo
FOpt (s) (-/1
To(als) (s, (s,a)da + Ad To((1))) lo-0z-
SES
23

---

This is equivalent to
Vo [Bonn (
[E
Vino(a)s)
Q7 T (8, + AV TO (0(11s))
To(als)
VaTT (a(s
E sno a)))))1)))
(s, +
To (1(ss) la-0;
J.3 Proofs of hypergradient of the algorithm Section
Deviation of 10
As 0' argmin t E Smwe a (1s)
Vana(ala) xa(a|s)
A (s, [ss,a]]= + D2 TO). by
the implicit differentiation theorem in bilevel optimization analysis,
V (aTa(a)s) Talals)
VJ0
V
0 E
+ DJ no)
V Tota())s) TT(a
VO
0
E
En (1))
Q7 (s, (T To) 10-08
Also, we have
V VoTo(a)s) V TT snu, (m))))1))) {a(s))
Q (s)) = 0,
and
V (ato(als) (a(s)
V VoVol
E s (-1))
Q (s,a))
VoTa(als)
a) + (a
E
(a|s)) Q (z,
(a(s)
Srwby (-1))
Then, get V 0r
K
Proofs of convergence when D, Dr,1
K.1
Gradients V J (TT;) when D, = Dr.1
From Proposition 1
Jodl (TO:)
E *ot
Tor (als)A (s.a)
?
gnule
LAEA
(20)
E go.
A, (s, V VISTTO (-18)
? gnuvt
where
VJ Te: (-1s) = [(s)--1_ M(s)-11 MT)())
1 1M (111111
QT" AV ch l=
where
(o(a)))) Tay (s11s)2
M(s) = XV (1 (P 8)8) 8)
m(-1s)
na Ca (8)
Tog (on 18)
Then,
Ngg (s]
[o(
M(s) X
(21)
Moz (s)
(o(ou]))

---

and
Tat (os [s)*
M(s)-111 '11'1'''' M(s) 1M)Ms 1 MMM -1
(ailss)) :
Met 10)
Ret (am]a)
Jof aa]
(a (8)
A Σ A *a(((s)
(a 1s)
(a
Also,
ma
V Jallasl ())
Nat (0] [8]
Fot (01
V (
(22)
(a ls) Jap (an (8)
V (a(a
Tap (0.
Then, plugging these equations into 20 we have
( (TT;)
1
Ar Tot Ar (s,
Toz (1|s)
Tot
27 (s, + (inol) Fog (a1 R)
(M(s)-1 M(s) -1 '11''11111 (MM))
A7 Tot (8,
1
1 1M) $1
QF (s, an) + Vina
Toy (am]8)
([[A4]"(s) (s, - (s (s)) Koy (a) ca(a (x)
Tog (an ))²( (A, 76 (s, (s))
E Jot 1 swv,
Jalan (s)
Q (1, + (aile))
may (s)
1 v Q as) + VJ Rap. (an(s)
where
(+(s) EeEA A7 (s, a)
Jot
Foz (als)²
[a(a)s)
(23)
Nog (u|a)²
EnEA
(als)
Then, we simplify the computation of V Jr (TTO ). we have V Jr (TT:)
1
Σ (A. th (s, a) cs)) no. (a|s)²
VJ (als)
(a(aas) ( V. (s,
(s.
7
Fet SNUV
Top (a|s)
LaEA
no (a|s)
V n (a)s))
Σ LaE
Toy (a (A, Tos (s,a) (s))
VJ QJQ= (s,a) +
swur
Tut
(Tp((
{a((())
When the tabular policy is the softmax policy, we have Ac(a)s) = En'ed exp(o((s,a)) then
exp(dls.a))
Vi*a(als)
no(als) = V (als) v a - Vo In Σ exp (xp(0ss.0))
(24)
a'EA
= =(s,a)) tss (-(s).
Here, 1(s', .') denote the column vector where the element is if = s' and a = a otherwise is 0, for each pair (8, a) E x A: (-18") is the column vector, where the element (alss')) if s 0 if * s', for each pair (s.a) E S x A.
25

---

So, we have
Σ net (Ar fot (s, cx))
(f(;:)
764
LREA
foz (a|s)
V (s,
(als
A
E f0t gwil
Σ LAEA
ne! (A, (8, cr(s)
1
(25)
To; (a|s)
V
R0 Q= + a) =
(al()
E TH
[14 (s.a)
(s.a) -c((s)
Bw
ammio
no. (a|s) (als
Vo 2= (s. + 1 (s, a) +o((15)7)
K.2
Convergence guarantee when D, = D
K.2.1 Auxiliary lemmas
Lemma 5. Suppose that Assumption 2 holds. Let noz Alg(Ts, (,T) where D, Dr for any s E S and a E A. we have
Tay (a|s)
S A - max, A (s,
A + maxs al AA (s, a)l
(a(a)s)
Proof. From 16). when D, = -D.,1, we have TØ
= Alg(TT X, and
Toz (118)
argmax
Σ
T(als) (s. - AdR T,
(-1s)
aEA
subject to acA
Σ (aass) 1.
For any s S. the Lagrangian of the above maximization problem is
Σ
x7 (s, a) + (To(ss)) + p(s) Σ (aass) 1),
REAA
aE.A
where y is the Lagrangian multiplier. The optimality condition of (-1ss) is that,
(s,-) (s,-)
AV ( (t1 n, 8) + p(s)[I, 11 0.
Solve the equation,
To(als) To. (a|s) + +p(s)) = O.
i (s)
Let (s) = -V." (()),, we have
To (a(s))
AA
THe (a|s) + 14 (s) =0.
(26)
Then,
To; (als)A7 (s, ATo(als) + To; (als) (s) 0.
We derive the summation of all a E A.
Σ
noz (als))FF((s,
x 0.
26

---

We have
(1(6)= = Σ
no (als) (8,0)+ (3.00))
aEA
From
26 we have
To (a(s)) Te; (a|s)
M1(() (s,a)
A
+ EWed Tos (4 (s,
A
So, we have
Toz (a|s)
A
(a(s)
A LaEd To; (a (.7 A, (s,
then
A
Tay (als)
S x - max,,a aa as) TT(a)))
À + maX,, aa AA, (
Lemma 6. Suppose that Assumption
2 holds. Let mo; = Alg( where D, D7,1, we have
2,
AA, Fot as)
max |A, Fa' (s) 7 + +2).
AA,
max
Vool(TT;) )l
1 7
max, |A, (s, 7
Proof. As shown in 25
6 (#0;
Σ LaEd
मेद (als) (8, et (x))
*0t
swv,
tेz (als)
2d (s, (1 (
(as()
ΣΣ SES aEA
VT *o/ (5) (als) R0/ - (c())
(als) V. Q² (s, a) + (s, a) - )-
(tts(als)
Since Eves VT #0/ (s) and Enes no: (a|s) = for all s E S. we have (ftt)());) ) s
1
max [I(,, oot (s, (s))( के. (a|s) {ap()
V O (s. +1 (s) (-(ss)
1-7 7 0,s
From 23 for any E S and a E A, we have
|A, #00 (s, -c+(s) & |A, #ot (s,a))-
|A,
Also, for any E S and E A,
[[s, a) - #-((|s)))l S 11+ [| 2.
From Lemma 5
के. (als)
A
X max,, A (s.
From the computation of V V (s, shown in ( of Appendix
V Voor Q² (s, 1- (30)) (s' J (a')s') A²" (s)
<
d 7.
(s.a) (5' ( |s)] max A t (s,a)
27

---

(sa) Also, since EvEAsEs r.o
( )=²= 1, we have
V (s,a)] (s, = 7 max A (s,a)}-
(27)
7 a.e
Therefore, we have
maX |A, + (s, max A Rot (3. 7 +
Voo- )ll
1-7
max,, ia |A,0 (s, 1-7
Lemma 7. Suppose that Assumption 2 holds. Let Roz Alg(ão, 2, where D, Dr,1, for any 8 E S we have
Σ
II va (a|s)]l
1
y maxx,s (s,a)
2(A max |A, (s, a) ())
max, (s))
1-7
8,
and
Σ aEA
mo (a|s)]
1
8r max
max, AA,0 (s.a) a.]
(1 - -3
À + max, .a AA," (s, a)l
(2 - 7) max as)
+
+ 2A + 2)).
X max, ,a A a)l
1 1-7
Proof.
From 19), for any E S
V Roy (+1s) = M(s)-1_ M(s)
AV AV )
M())='
In=
(s)
From the computations of M(s V V Vz(le) (ata)c((ttooo (fto it, ))(== and V V= in we have
(M(())
M(s))'11'M(S)) M()
M(s)
nor (als)
toz (a(s)
fog (a|s)
1 11
A
max
a. (a(a)s)
maxxa A (s. a)
and
| (s, S max |V V (s, a)) S 1-7 0,s
max AA (s,a)).
From
22 24
to *a(a(s) Rop (a|s)
|AV & V (a(ale) (ft R, x)(l ()(I(s,a) (-(ss)
|| || 2(A
max A (s,
8,s
The last inequality comes from Lemma
So, we have
नe. (als)
max .
2(A + max | (s.a))))) AA no (s,a)
|| to; (a|s)
X max,,a A (s, a)l
1 1-?
a,8
Therefore,
max |A (s,a)
Σ
V sno (a|s)ll
+ 2(A + max A no (8, ()).
maxx,a 1 1 (s,a)
1 1-7
aEA
Also, we have
V (a|s)] S no. (als)
(1 a)) + X1VV
max,.a A 18, (8,a)
From Lemma D.4 in 22 we have
8r 3rmax
5
(1 73
28

---

Moreover, we have
To {a(a
NIVVo((((s, a) - -
)
#0; (als)
À + max, s. A (s)
y ymaxa,, 1A,0 (s, + +2(A + max | (s. 1) +2)
À max,, ,a AA, (s,
1-9
a,8
A + max, AA," (s.
(2 - -7) maXa.
1A (s.a)
+2 + 2)
A max ( (8,a))
1 1-7
So,
1
8rmax
V no; (a|s)] 5 X max,, AA, a)l - (1-7)3
À + max,, A (s,a)l (2 - 7) max,, (s) + + +2).
X max,, A (s)
1-7
Lemma 8. Suppose that Assumptions annd hold. Let no; Alg(fto. X, where D, Dr,1, we have
Tmax B
27rmax C²
| J. 1. (1 71- (1-
(28)
where
C
A-amaz (21-0
2X 2Aman) and B
Samar
Amara (1-1)
Ammam
(2-2)Amox A-Amaz
2X + 2)). 1-
Proof. From Lemma 7 we have bounded EoEA |V Vann (a|s)] and EnEA
V2 (a|s)]l. Borrow
the result from Lemma D.2
K.2.2 Convergence guarantee
Theorem Consider the tabular softmax policy for the discrete state-action space shown in Section 5.1 and the within-task algorithm Alg in (.. Suppose that Assumptions) 2 hold. Let yf be the sequence generated by Algorithm 7 with D, = D,= X >> Amazz and the step size selected as
(
B
+ 27 C2
1
min
7)3
GVT
Then,
T
E, V V (, (
2r mar
B
4yr man C
2r max
Tmar B
2 mar C2 G
+
7)3
(1 7)4
1
1-7
7]2
(1 (1-7)3
VT
where
2Amar 1-7 γ
Amaz
7 + 2),
G
Amax
1 1-
Ammax
C
+ 22 + 2 2Amax))
Amaz
1-7
and
8rmax
A
Amaz
(2 7) Amar
+ 2A + 2)).
A - Amaz
Amaz
-
29

---

Proof. As the smoothness constant of J ( ), i.e.,, Jr (Alg(To A, is obtained in (8, the smooth- ness constant of (e (Algg(fs. A, r)] is the same, i.e.,
7)2 + 27T C v Pu ATIll 5
Brmar
(1 7)
Moreover, from Lemma
6 have
Amaz 1-7 A-
Amar
V & (Alg(Ais; 1)]1
Amaz + 2).
From the convergence theorem of SDG with smoothness and bounded gradient shown in [1)., let the step size
{ ( I'azzi B
2ymmar O2
min
(1I (1 (1-7)3
+
GVT
we have
Be [| V POEE A
2,
T
2r 2rmaz B
4yT C²
7)2 +
(1-
E, (rweec)ls-AAgg((Tpp A,) - Jr (Alg(Foo A, T,1
- T))] + Tman man C2
2E,
(1 7)2 (1 7)3
Since B,- (1- 7)) - (All {, I- we have
1
E.
2, mar
B
4yr mara C2
(1 - 7) )
2r max
Tmar B
2 marmas C2) G
(1 7/
+
+
1 1-
(1
7)2
(1 - 11- VT'
where
2Amar 1-7
Amaz
7 + 2),
Amax
1 7
Ammax
C X A Amax
+ 2X + 2Amaa))
and
1
8r max
t Amaz
(2 - 7)
B X Amaz
+ 2X + 2)).
(1 7/3
X Amaz
Corollary 1. Suppose all assumptions and conditions in Theorem hold, and we set X 2 2A
then
(B + y
man 25 max G
Σ
(1 7)
T
VT
where
16rmaz
24
C T and A 4Ames (1-7)s.
XI X1-9)
T-y
Proof. Since 2 2Amars have A-Amae A Amor
and Amao 1 4. Then, simplify the
inequality in Theorem 5
30

---

L
Proofs of convergence when D, = D7.2
L.1
Gradients of V ( when D, = D7,2
From Proposition
we have
VoJ+(fo;)
E Fot [ Votor(113 Ar (8.-)
(29)
1 swur
where
V T mot (-1s) = (M(s)- M(s)-117 M(s)
1M( 11
(30)
V 2o (s, -VV V Va(lle) de dz a. 1==
where
Hog (0:18) (8)
((s) = AA (3) f. A
Nec (0 8))
Then,
toz (ails)
M(5)-1= 1 7
(31)
#o (an (8)
Also,
V ((()s)) ( R.
(32)
V (onla))
{a(an|s)
Specially, Ar #ot (T. M(s) 111 M(a) 0, because we have
1
A, to0
((s) (
Σ
nेz (a|s) #ot (8, = 0.
aEA
Then.
V ()ta) = 1
t0t (s, V. (s(8a) =-(-1))T)
E
A+
*os
ame, am
Since EoEA the (a (r not (s, then EnEd #e: (als) (s) O. We have
A te (s,
(5.0 Q (s. a) + +1
(ftet) 1-7
E Rgl
(33)
e~vt
andd,
Here, 1(s', a') denote the column vector where the element is 1 if = and a', otherwise is 0. for each pair (8, a) E ESxA A.
L.2
Convergence guarantee when D, = Dr.2
L.2.1
Auxiliary lemmas
Lemma 9, Suppose that Assumption holds. Let foo = Alg( 7, where D, = Dr.2, we have
fel (s. a)l | WeJt max, AAth
max, a |A, Reg (s,
+ +1).
1-7
1-
31

---

Proof. As shown in 33
Ar not (s, (s, 1 v ot + 11 (s.a))
V (rto))
E
x
T gnit amilos
As shown in proof of Lemma 6 in 27
V (s,aa 1 1 7 a,e
7 max A (s,a)
we have that
max, s,al |A7 Fo's (s, (s, (s) max 1 Foz
(s, 1,, 7
(f 1l
+1).
1 1-7
X
1-7
Lemma 10. Suppose that Assumption 2 holds. Let næ; Alg(fip; 7, E S, we have
where D, = Dr for any
Σ aEA
V Re (a|s)]l s
27 A(1 - 7) a,
max |A, (s,a)]+
and
2y
16r mar
to ooz (als)] S 1(1 - 7)
max |A (s,a) 4)2 a.e
+ 2.
X(1 - 7)3
aEA
Proof. As shown in 30 have VJ Ao (-1s)
( M(s) ( M(+)-1)
( (s, - AA d( ()) k=m
1 1 1s
where the computations of M(s) and a R, 8) are shown in 31
32 and
24h. then
f0o (als) no: (als)
(() *-(sss)
no; (als)
Σ
के (d'ls) V V. (s, + 1(8,0() - (11)))
a'EA
Therefore,
V aato (a|s)ll S
b (alss) (s, 1(s,a) #0(11))
foo (als) +
Σ
#og VV (ss,a') #
a'EA
Then,
Σ
V tे: (a|s)] S Σ
o (a|s)( V + 1(s,a) - *
aEA
aEd
+ Σ
#o:: (als)
Σ
#o: (a'ls)( 0..F ( + (s, -
aEA1
d'EA
From
27 we have
V (= 5 7 max IA (s, (s,a) J.
1-7
32

---

Then.
V p (a|s)]I = Σe
Roy (a|s)
V QF (s, + ((s,a) - ap((15)
EEA
EEAA
Σ
no; (a|s)
Σ #o; (a'ls)(
A v VoQ= (s,a') + +s, - ()(sss)
a
I'EAA
cØg (als)(
1(1 -1) 7) max |A a) 22)
eEA
+
Σ Mog (als)
Σ maz (a'1s){
7
max IA (s. +2)
1(1 7)
a.e
aEA
a'EA
27
$ X(1 7)
max
|A, (8, +4,
a.s
And
27
V so: (a|s)]|
hØ; (als)(
max |A (s. +44
(34)
X(1 7)
a.s
Moreover, since
V Vato; (als) = no; (a|s) {
(s. + (s,
(1)(()
nΦę (a|s)
Σ
केo (a'ls) V (s,d) + (() - (1s))
d'EA
we have
V2 To (als) -V (als)(
-
+ noz (a|s)
+ - (1+))+
Ao. (als) Vo
Σ
tे (a ( V O= (s, + (s, - #c((1)) -((1)))(((((
a'EA
Then.
a2 (a|s)] 2 V क
(a|s)]|
v (s, + ((sa)
2 [a|s)]
V T (s [ota(-|s)]-
From 34
2x
|| V Ao (a|s)] S ने. (a|s)(
max a,
|A の (s, | + +4).
X(1 7)
From 27
1 v Vo (x, + 1s - #,(-1s)|1 s X(1 71
max 14.0 (s, | +2 a,
From Lemma D.4 in 2 we have
8rmar
- (1 7)33
then
8r maaa
2 Q (s,a) (s, - voto(-1s)|1 5
X(1 7)3 + 1.
Therefore,
a (a|s)]| < too (a|s)(
27
max A R (s,a) + 4)² + 2 (a|s) 0,s
Srmax + 1).
X(1 - 7)
X(1 7)3
So,
2y
16r max
V to: (a|s)]| S ( A(1 - 7)
max | (s,a) + ( 4)² + X(1 - -333
+
a,s
A
33

---

Lemma 11. Suppose that Assumptions we have
! and 2 hold. Let to; Alg(fio. 2,7) where D, = Dr.2
Tmax B
27T C2
V (tt;:)
(35)
7)2 (1 7)
where C =
27 X(1->) Amaz 4 and B =(xxt 24 Amar 4)2 + 16rmez + 2.
((11-)
x(17)3
Proof. Similar the proof of Lemma 8 by using Lemma 10
L.2.2 Convergence guarantee
Theorem 6. Consider the tabular softmax policy for the discrete state-action space shown in Section
5.1 and the within-task algorithm Alg 17. Suppose that Assumptions [and holld. Let {dr
be the sequence generated by Algorithm with D, DD,22 and the step size selected as
min {
[Tmaz B 2armar C2 C²)
1
(1 (1-7)3 7)3
GVT
Then,
T
[ {,
Es V B
1=1
21 20
B
4 4w C
2r mar
Tman B
+ 27r mas 02 G
max
+
73
(1 7)4
T
1 1-7
(1 7)2
(1 11-333
7)3 VT
where
2Amaz
Amaz
7 + 1),
G 1 1-7
1 1- y
27
C A(1 7)
Amar + +,,
and
27A Amar
16r 16rmaz + 2. X(1
B
+
X(1 7)
Proof. Similar to the proof of Theorem in Lemma I1
[]] by using the gradient bound in Lemma the smoothness
Corollary 2. Suppose all assumptions and conditions in Theorem 6 hold, and we set 2 2Amoz
then
Σ
T
E
V
(B + 2C 2
Mmaz 2mmax
G
T
(1 7)4
T
VT
1=1
where B
16r 16rmaz
18
C
A T-g. and G A (1-ngs):
7
Proof. Since À > 2Amaz. we have < 2Amas Then, simplify the inequality in Theorem 5
M Proofs of convergence when D, = =
Lemma 12. Suppose that Assumptions and hold. Let ftg = Algg( 2, where D, = Dy (3) (T X, T)) exists for any G. and If X > (6L2 + 2Lz) then V (Agg
L Amar (A + 24 1 Aman)
V Vodr )1l
(1 7)(2 (6L + 22))) Amaz)
34

---

Proof. From Proposition 2 we have
Vod+( - 1-7 V
o
V or no: (als)
Ar fot (s.0)
04 amttat (-1x)
tig (a]s)
Arally
where
Vato(als) (s. + + (o()sss)
To(a(s)
andite (-1+)
Vota(aals)
E anapy anoite
(s,a) (tg)s) l0-0;-
#t(aas)
When D = Dr,3, and the policy with function approximation defined by Ao(a)s) & exp(fo(s.0)) ((s ES x A, from Lemma 4 Ta exp(Jols,a')dde
(Ttr( = T
Vor fane (s (s.0))
Ret an (11x)
soaer
where V
0e nor (a|s) {a(as)
V Veg tog (als) Ao(a|s)
E
Q (8,
E
2 (s. a) AI (s,
sma,
amat (-1x)
11
U Vo tog (4 da XI
E
E
grilt
U Ve: to: (3 AI
E t swily
V no (s.))
E Ro
First, we have
| W
A J0t (s,a) ||.
7g4 am am (118)
and
Rot (s. || ()
Reb (s, ( S L Amer. max Vefa(s, a) max |A, a,
E
a,
Sway aniite (1)
For the term V Voll consider Vog nor (als) and V no (als), we have
Vato(als) = = (a(as)) SA V Vofo(s, a') exp (fo(s, a')
(36)
LA exp (oo(s,a)))al
Then,
JA Vefo (s, a') exp (Fo(s,a')dda
Vott(alss S / +o(((s)
Sa exp (fe(s, d')a
(37)
(
We also have (3lo(als)=
Vo + Vao(a|s) LA V fo a') exp (Fo(s,a') La exp (fo(s, a'))aa SA a') (Jo(s a')da' Vo/o))ddosVVooosoo,ooo a' V fo(s, a') exp (fols, d dda' exp (fo(s, d')
Volu(s,
+ #a(s))) SA Vofo(s, a') exp (fo(s, a') )o' fA T fols, exp (fo(s, a d'))
(A exp (fo(s, al (f)
35

---

Then.
(g 2ng(a [a + 25 #g(als) 2 25 6f)( ( 2
(38)
So,
Vog to (a (8, a)da ||
E sm-M
S (6L) + 2L2)
snu, t SA Vi. my to; (al () (s, a)da is diagonal matrix, the above shown its largest Ama) Then, the smallest eigenvalue of -Sa Vg 6; Roz (als) (s, a)da NI is larger than X - (6L} + 2Tz) A Therefore, > (6L) + 2L A
Since IE'
absolute eigenvalue is smaller than (6L)
E
[-/A
V 04 no. (als) (5, (s + +N|
I x (61} + 2L2) Amar
(39)
soaple
Moreover, if À (6L} (6L]-2L2) 2 Aaaz the objective function in the optimization problem Alg( 7,
strongly concave. Then, from 644, the solution is unique and Va.-(AAg(() (ft. X, r)) exists.
From
6
VoQT * (s) 7
Vofa (s'. ( (5,
E
(o',a') (
(am) 1io
1-7
Then,
V a)) 1 1-7 LIAmar.
Combine 37,.
we have
VA Vog Rez (a|s) (s, a) +1|
24
E anily
SA=
LP Amax.
t
1
So have
A + T- T.? 1.A.mu Amar
| 1V00 (1- - (6I.) 2T.2) Amaz)
(40)
Therefore, we have
L1 L1Amau (A + 27 L2Amasi
V V [foe)l
I-7
(1 7) (6L + 2L2) Amax)
Lemma 13. For softmax policy parameterized by d.
(6L + 2L2)2mmazz
(+x))) <
71
(1 7)3
87 872Lrrmax
76L2 + 2L2) ) (1 7)
(41)
(1 7)
Proof. From 37
f | ( S 2L1
From 38
/ | (att( 5TT, + 2
Borrow the result from Lemma D.2 in (2)
(6T. 2T mmaz
8r maz
V (++))l
(1 71
(1 7)
36

---

872 mmz S
76617 + 2L2)rmax
(1 - 7)3
(1 71-
Lemma 14. Suppose that Assumption holds. Let foz; Alg(ft A, 7) where Dr Dr,3, for any E S, we have
2L, + + ,-, Am
V to; (als)]lda
< (1 71- (6T.7 + +2112) )
and
1 (als)]lda (160L] + 561,22 + 4l3)(A 1 Amoz)) (1- (6L) +2Lz)
Proof.
First consider V s Ro; (als), we have
Voñu (als) = toz ol Vor Soz (8, - n0; (a|s)V 00, La Vo, Jo: (s, exp (for (',
Sa exp (So: (8, a²) d'))da'
(42)
Then,
Votto (a|s)] fto; (als) V Fot
SA Vo for d') cxp (foz (s, d') Sa exepp exp (Joz (s, d'))
कें (a|s) V 1
(43)
(A+ +
2" T- L Am/n)))) L1
2 (als) (1 7)(1 (6L) + Ammz)
Then,
2L, (A 1 27 L3A
1-7 V for (als)llda < (1-7)(> - (6I3 ALz)))
Next, we consider 2 fe; (als). From 42 we have
V T (als)
V 0 V for
Top (als) + केे (2 Vor Jor (8) V の fo: (s, V. VoO, LA Vo, for (s, a') exp (fo: (s, a²) ddd
+ * (als)
V nog (a|s)
exexp exp (So, (8, a²) a'))da'
VoL for (s, a') exp (Sor (s, d'))d'
no. (
oo; Vols
LA exp (So; (8, a'))da'
[A(V], foz for a2) exp (fo, (s, a') + Vo, fo: (s, a') a') foz (s, a') exp (foz a')
VJ0
LA exp (foz (s, dda'
+ #og (als)V vo0 (A (L for (s, a') exp (fo; (s, d') SA exp (Jo: (8, d')dd)
Therefore,
V te; (a|s) fe (tt (a|s)] + मे (a|s) V VlVV for (s,
+ मे. (als) +tc.c///4////./13...000//1/////1
(a|s)]
+ के: (als) |,660)/00|00000/0000001111111143 || fo; a)
+ no; (als)
(8, a)l
< 24 8 0 मे: (a|s) 2tg L1 | + 2 (als) + L7).
From 40
and 43
2L2 + 66 + 1 -32 Am
0 Ro: (a|s)]l < #Øz (a|s)
+ 2L, 22L1|V'30 13661
(1-7)2(2> - (6L? + 2222) Amaz))
37

---

Then.
2L2 + 6 + A=moAAmaz)
1 t0 o (als) da - (1 (1- 7)- (6L) + ) Amnrs)
+ 2L, V
Next, we consider V200 We have
[-/A /
= E
noz (o
30
IAA
E SMuV
Vi Roy
(a|s)
1 da
IA V 04 Noz (a|s)
ME
mo (a 1f (8, de M-1N
smult
where
M
sww e | A o noz (als)A² (s, (s + +11] and N
SA Vo, Rez (als) (als) Q (s, a) 21}
Also, we have M IN Va0
te 8Ni--
Similar to 33
38
can derive the upper bound of V foll then
I toz (a|s)] S nø; (als) + 16L, L2 + 2Lz).
So, from 38
40
we have
27 12 mar (6L2 + 21 + 27 12 (maz)
02
I-7
(1 - 7) - (612 + +2212) Amax)²
8- iirmar + 76613 + +2222)
(1 7)3
(1-
A (6L7 + +222) A
x 27 I2AAman
(40L + 161, + 2L3)(A + 27 L2 Ama )
1-9
1-7
(1 7)(1 - (6Ig + 2L2) Amau)
(1- (6L) + Amar)
2y
1 (6L3 ALaz)..
Simplify the inequality by < 1 and 1 O.
1 ( + 28L, L2 (A + I-9 L3Amns)
(1-7)3(2 (6L) + 2L2))mox)
Then,
(160L) + + 4L3)(A+ 27 Li Amaz)z
J V toe (als)]lda
I-7
(1-7) (6L) 2222) Amaz)
Lemma 15. Suppose that Assumptions and hold. Let āo; Alg( >, where D- Dr.3. we have
Fmax B
2Trmax C
V2 )1
(44)
(1- (1- (1 7)3
(1-7)(A- (627 +2b4) Aman) and B (160L (x- Amax)
2L1 27 Amaa)
Poy LiAmax)?
where
Proof. Similar to the proofs of Lemma and Lemma I| by using Lemma 14
Theorem 7. In both discrete and continuous action space, consider the softmax policy with func-
tion approximation shown Section 5.1 and the within-task algorithm Alg defined in (
with D. = Dr.3. Suppose that Assumptions I and hold. X (6L + 22) Amar. then
V (3) T)) exists for any 6.
38

---

Let {dilE= be the sequence generated by Algorithm 7 with X > (6L) + (2L2)Amaz and the step size
B + 27mmaz C2
1
== min
(1 7)3
GVT
Then, the following bound holds:
T
Ee
V B (U {;
T
1=1
25 max
B
4-r mar
C²
2r 2rmaz
Tman B
27 C2 G
<<
+
+
7)
(1 7)
T
1-
7)2
(1 7)3
VT
where
La Ai (A + 24 Li Amx)
G
1-n
7A - -66I3 + +2L22) Aman))
C= 2L 21 1-- 1-,,,AA -[]Amaz)
7) (6L} +2L2) Amar)
and
B (160L) + 56 + (L3)(A 2y Aman)
1-y
(1-7) - (6I) 212) Amax)
Proof. Similar to the proof of Theorem 5 by using the gradient bound in Lemma 12 and the smoothness in Lemma
N
Optimality of one-time policy adaptation
N.1 Important Lemmas
Lemma 16. Suppose that Assumptions 7 hold. For any task T, and any policies a and n', the following bound holds:
1
1 E 8 am (1|s)
E sovt
- [
S J,(7) - J+(m) 1
[A7(8,
C7(#))
amon (-13)
where
(T('' 47 Amar Drv (Fl| (Drv ( (1 - 7)²
|T(als) (als)) in a discrete action space Here, define (Tv( (-1s) & LaeA
or Drv(a((b6)(==((11) A 1 SacA (m(as) - <'(als)dda in a continuous action space, and Dipe (x|laa) A max Drv (x(-s)) (+(ss)
Proof. Let PF is a matrix where P. (i, EEow((1a:) Pr(sy (5, a) and ps is matrix where pF (i.j) = (r a). Let G = =11+=1++----- 7P7 + P7 +...) (1 - - and + (1 -1 Let p be a density vector on state
similarly G= (1+ 71+7p"t space and r, is reward function vector state space, thus r is scalar meaning the expected reward under density p. Note that J+(T) r, Gp,, and d='=') rf Gp Here, or is the initial state distribution for task r. Let px p.s.
Follow the proof in Appendix B in (11, we have
c-i- = (1~)P,) - (11-Ppa) = AA
Left multiply by Ô and right multiply by G,
ク=ンदAG G
(45)
39

---

Left multiply by G and right multiply by G,
G GAG + G.
(46)
Substituting the right-hand side in (45) into G in 446 then
d= G + +GGG GAGAG.
So have
J. - (G
+ +T
(47)
Note that r = of T, where v is the value function on the state space, We also have Gpr where v/ is the state visitation distribution vector. So,
--
G) - 7 A + 1 Uf AGAVT.
(()
Consider the first term
7 1- 1i AuF similar to Equation (50) in we have
Y07 AV 1/ (P= - P μリ
1 (8)
(als) {(als) (z)
(48)
Σ (s) Σ
- ( r(s) + Σ Pr
v(s)
Σ (s) Σ -
- [(cls))
Since have Ea [[als) (8, have
yo A Σ oz (8) Σ x (z) =
[A](s
a anda (-16)
Combine
47) and the above equation, we have the following for the second term:
AGD = J+('') (x)
E S'N
[A] a))
a>>((1ss)
Then need show
72 T AGA
17
$ (T
1-7"
First, by Hölder's inequality,
AGA S 1- T A
Similar to 48 each element in the vector No A is Er ([als)) a), then we have
Iro A
(aaas) ( A
(1] (8, S 2A Diper (m||²²).
From the Lemma of we have
2 ?
| 111 <
Rawyy (+()))
Therefore, have
4- 4-Amax Diver (Tllz')Bowr) (Drv(
AGA S (T
(1 - (1-
Then the bounds hold.
40

---

Lemma 17. Suppose that Assumptions 2 hold. For any task T, any bounded parameters and 6', and or the following bound holds for both and 2:
1
27Amaz D>? D² fto
J-(ftor) J+(ot) -
E to andite (-18)
(s, a)] + (1 (1-7)²c
sowey
and
27 D² ( #tr).
J+(#t() - J+(+t) 2
[A (s,
1
soupe am (-le)
(1 7)
Proof. The proof follows similar lines of Theorem in [5T] and Corollary 1 and 2 in M. For the sake of self-containedness,, we provide the complete proof.
We show the first inequality. The second inequality follows similar way. From Lemma 16
47Amoz DTV (tre ] smufo DDv (ftls (+s)))
J (
E ewpp Te a (-1s)
[A a)] - (1 71-
From Assumption Then, we have
2
)e for any s E A. Also, Drv (# (fo (+|s) 2 0 for any A.
eDTV (ãe ) S EE swuto [
From Jensen's 's inequality, we have
E
s [Drv (fr (-1s)) (11)))1 < E smojo [Div (1 (+ss)]
From the above three inequalities, we have
1
4yAmau E amoeo [Div (fo foo (-1s))]
- ((t)
E s-0,70 (-1s)
[s* 5 (1 (1-91 7)2
(49)
From
8
we have
1 D ( - ( (
2
and
1 < DKL > (+|s)|
(50(115)))
Therefore,
[A a)] + Ar D²
( - (+00) <
E
1-
(1 -1-91 722
amair( (-18)
and
(s) + 2yAmer D2 (fr)
J+( - (+(0)) S
E so
1
(1- 2)2
Lemma 18. Consider the softmax policy with function approximation shown in Section 5.1 Suppose that Assumptions 2 andBhoold For any task T, and any softmax policies parameterized by bounded O and O', the following bound holds:
(s, + 47Amaz L2 110 0'12
Jr(+to)) - Jr J+(+t)) - 1-7
E. swu
(1 7)
(-1o)(--1s)
and
47 Amaza T2 (1- 110 0'112.
Jr ( (fto)
E
[ (s,a))
exuio
antigr
41

---

Proof. From 36), for any 0 E IR",
= = Volla)) SA Vofo(s, a') exp (fo(s, d')
LA exp (fo a')
Then,
SA VoJo(s, a') exp (Jo(s, dd)a
Vato(lals)] S ( (o (
SA exp (fo(s, (,,8)a)))))))))) d'))
From the mean value theorem, we have
( a (als) - (a)((aaa))))))) 0'1.
where ((a) = 8(a)0 + (1 6())) and 0 - 8(a) - So,
1
Ao(aas) f (a|s) - Ln - 6'11.
2
aEA
From 49
we have
[A (s, [)) s 47 47 [i
J, (ft (fto)
E sway a-aig( (- ())
(1 (1-7) 7)2 110 011
We use the same way to show another inequality.
N.2 Proof of Theorems 3 and 4
Proof of Theorem
3 When the requirement of Theorem 1 X 2 2A 2Amaz is satisfied, From Assump-
tion 4 and Theorem for both 1 and 2,
T
E2 max (
(, (ft.. A, +)]]
T
Ex
(IVa A, }
(50)
T
Shi
T
E,
K;
M
<hi
where the constants K; and M; are shown in Theorem [ a concave function and Jensen's 's inequality.
The last inequality sign comes from that h;
Let to (Φ) (l (#t 7, for any meta-parameter & From the definition of the within-task algorithm, we have
E 80-7 amafar (1)))
[ff*(s,
XD2 A 7Øर (0))
E gn2y
[o.²
A R
antar (1|s)
This is equivalent to
E
A7 (5.
AD2 ( ĀØ: (0)) >
E
A (s, (s.a) -DD2 No:
a~1 and (9)(-e)
sonv.
(-1s)
42

---

when 2 27Amaz from the second inequality in Lemma 17 and the above inequality, (1-7)e
2yAmar D Ro; (6))
Jf (+)) - (Rto) 2
A (s.
o antiy (o)()1.)
(1 (1-7}E
E arupy
D² ( Rer (6))
1 7
anria (1)(-)
A [s,) - 1-7
A
D² (+ mt;))
smuue
amRaz (-15)
From the second inequality in Lemma
17
1 J= J. ( - 1-7 7 From the last two inequalities,
AA (s,a)) + AyAmar D² (fs fto:)
E
(1 (3E
snay
(nlt (11s)
Jr (fo; (0)) - (ttt)) 2 -((1 27 Amaz
A
73)E (-(0))))--- 1 1-7
+
) (ta to;
i.e.
J+(o)::) - (tt,,,) S 27 Amar
+ 1-
)D ( #o=))
72E
Then,
27 Ama
E (foot) - (Alg)) () 1))] S
11 7)26 (1 1
+
)E, PE DDr #o:)]
Let 6² = arg maxo (1 (Tg, we have
(AIg X, T)]] 2 max E,wrr) (A)
Therefore,
(x - (+(Agg A,tss,,,777 T))] < min E, ( J+ (#os, A))]
27Amaz 1
min) - 732E 1- B IV?, (ttos ht;:) )]
Since
min E, P())) D2 to; )1 = Var:
we have
27 Amam +
(= - Jr (1))
S (3(1111 7)2E + 1- (Pr.(P(T))
Note that in the above analysis, we need À 2 2Amaz and also x 2
2yAmaz So, we select we select T1-7]e
2Amaz to satisfy the requirement. When X 2Amaz we have (1-7)e-
(I-
2(1 + Amaa E E (fo:) Jr (fg, A,))
Var, (Pr((P(T)). (51)
(1 11-77 7)-E
From 50
and
51
we have
T
E,
E [ - J, (Alg (Tor X, T]]]]]
T
K;
Mi
2(1 +
x h
+
Var (PT)()
T
VT
(1 7
43

---

Proof of Theorem 4
Similar to the above proof of Theorem 3 The difference is using two inequalities Lemma 18instead of those Lemmal 17 and using Theorem for convergence instead of Theorem
1
The requirement of Theorem is À (6T.) Amaz and the requirement of Lemma 18
Andmaz 42, Therefore, we select À (6L)+2L))Amas Then, the bound is
(1-7]c
(1-3)e
E2
(U (-(Alg (f A, X.T))]]
1=1
Kg
M3
44,3 Ama
A
S/3
+
+
(arr((P(L)).
VT
(1 (1-7)22
1-71
K3
M3
(66 47) + +2L2) -mmz Vara (P()),
Shg
vT
(1 (1-7) (1)7)
N.3 Clarification of Amar
In all the proofs in Sections N.1 and N.1 we can replace as Amaz to A'mag. where A'mes defined by the maximum advantage function value of policy fty, where o' arg mins (r-r(r)(22 ( Raz ) It is easy see A' and convenience of the proofs, we keep Amaz in the proofs and Theorems 3 and 4 We actually make the bound in Theorems 3 and 4 |ighter by replacing Amer to A'mar In the verification of the theoretical results of Section 6 we select À based on A'aa and verify the tighter bounds by the experiments.
Amax- For simplification of the assumption statements, theorem statements,
O Proofs of Remarks
Proof of part (i) of Remark]] If the MDP M, is ergodic, there exists policy ग such that (s) 2 Eg. As Ø is bounded, the probability (or probability density) of each action of the softmax policy is larger than 0 and lower bounded by a 0. Therefore, the action probability of the policy f (a s) can be upper bounded by (a
/)/ for any a. Therefore, 1/ (s) 2 60/c1-
Proof of part (ii) of Remark - If the initial state distribution p- has p~(s) > 0 for any S. Since bounded, Pr (s) E2 for any s S. Then, v, (*'(s) 2 (1 - 7)22.
P Limitations
In this paper, we provide several theorems, where the hyper-parameter selection, e.g., X, is provided by the theorems. The theoretical analysis usually chooses conservative. In practice, tune them to improve the performance.
which are sometimes
44

---

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: The abstract and introduction, including the main contribution statement and related works, accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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.
is fine to include aspirational goals as motivation as long as 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:
We provide the limitations in the Appendix.
Guidelines:
The answer NA means that the paper has no 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 a separate "Limitations" section their paper.
The paper should point out 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 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged 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.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
45

---

Justification:
All proofs are provided in Appendix
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 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 to 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 of the paper to the extent that it 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 provide all details of the information needed to reproduce the main experimental results in the experiment section and in Appendix A and B.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer this question will not be 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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility 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, or other means that are appropriate to the research performed.
While NeurIPS 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
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.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-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to 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?
46

---

Answer: [Yes]
Justification: We provide open access to the data and code with sufficient instructions in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, 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. //nips.cc/ppl cc/public/guu wetgguddddeeoeeubbinnnnn htt.SSbbbiiiiooooiiiiiooooi 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, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
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 to understand the results?
Answer: [Yes]
Justification:
We provide all training details in Appendix A and B.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provide it in the section of the experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are 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).
47

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one 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 not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or 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 provide the information in the beginning of the Appendix.
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, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: It is followed.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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: This paper presents work whose goal is to advance the field of Machine Learning. There is no potential societal consequence.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or 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.
48

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
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 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. Lieenses 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: [NA]
Guidelines:
The answer NA means that the paper does 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 is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets 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.
49

---

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: [NA]
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was 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 to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 the NeurIPS Code of Ethies, 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: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
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 NeurlPS 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.
50


Reviews:
[{"review_id": "849wgZatDt", "reviewer": "Reviewer_Q7S4", "summary": "The paper proposes a bilevel optimization algorithm for Meta-RL, which unlike MAML, implements multiple-step policy optimization on one-time data collection. In addition, the paper provides an upper bound on the expected optimality gap over the task distribution, that quantifies the model’s generalizability to a new task from the task distribution. Experiments show the advantages of the proposed framework over existing meta-learning approaches.", "questions": "* Please address the aforementioned weaknesses.\n\n* In Line 178: does NPG mean Natural Policy Gradient? If yes, maybe state it explicitly. \n\n* Is it possible to formulate a similar bound for other meta-RL algorithms, such as RL2 [1] or VariBAD [2]? \n\n* Lines 32-33 explain that even if the learned meta-parameter $\\phi$ is close to the best one, the model adapted from the learned $\\phi$ might be far from the task-specific optimum for some tasks, since the best meta-parameter is shared for all tasks and learned from the prior distribution that can be with high variance. The proposed algorithm was designed to adapt a stronger optimality metric, where the model is adapted from the task-specific optimal policy for each task. Could you provide a real experiment (even a synthetic experiment) that demonstrates this phenomenon?\\\n\\\nThe existing experiments show that the proposed approach performs better than MAML, but it is still not entirely clear that this leads to the improved performance. A synthetic example can help fully explain this important failure case of existing meta-learning approaches. \n* Perhaps I missed the following point when reading the paper, but during task-specific policy adaptation, the algorithm performs multiple-step policy optimization on one-time data collection, which speeds up the learning process - should it decrease performance (theoretically) compared to one-step policy optimization on one-time data collection?\n\n[1] Yan Duan, John Schulman, Xi Chen, Peter L. Bartlett, Ilya Sutskever, and Pieter Abbeel. RL2: Fast reinforcement learning via slow reinforcement learning. arXiv:1611.02779, 2016.\n\n[2] Luisa Zintgraf, Sebastian Schulze, Cong Lu, Leo Feng, Maximilian Igl, Kyriacos Shiarlis, Yarin Gal, Katja Hofmann, and Shimon Whiteson. VariBAD: Variational Bayes-adaptive deep RL via meta-learning. Journal of Machine Learning Research, 22(289):1–39, 2021.", "limitations": "The authors addressed the limitations of the proposed algorithm in section P.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper proposes a practical algorithm, supported by a theoretical upper bound of the optimality of the proposed algorithm.\n* The paper is well-written and easy to follow and understand.   \n* The appendix is well-organized and contains all the proofs and discussions about complexity and its relation to MAML.\n* Experiments were performed to verify the theoretical results and show the advantage of the proposed algorithm over MAML.", "weaknesses": "* Comparison to state-of-the-art: the paper compares the proposed algorithm to MAML, EMAML, and ProMP, which were proposed 5 years ago. Since meta-RL is a very active research field, and even MAML has newer and more advanced variants, it is hard to be convinced that the paper compares the proposed algorithm to the most relevant approaches. In addition, the authors did not explain why they chose to compare to those specific baselines, and if the contribution of newer MAML variants can also be incorporated into their algorithm. \n\n* The related work section can be improved. Specifically, the section is a single short paragraph that covers only bilevel optimization algorithms for meta-RL. An extended related work section on meta-RL (even in the appendix) that covers the different types of meta-RL algorithms and places the paper with respect to the various approaches could help the reader understand the paper's contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your time and effort in reviewing our work. Thanks for your suggestions to make our manuscript better. \n\n>**Weakness 1. Comparison to state-of-the-art: the paper compares the proposed algorithm to MAML, EMAML, and ProMP, which were proposed 5 years ago. Since meta-RL is a very active research field, and even MAML has newer and more advanced variants, it is hard to be convinced that the paper compares the algorithm to the most relevant approaches. In addition, the authors did not explain why they chose to compare to those specific baselines, and if the contribution of newer MAML variants can also be incorporated into their algorithm.**\n\n**Answer:**  Thanks for the suggestive comments. In **the global rebuttal**, we introduce the categorization of meta-RL and compare the advantages/disadvantages of the categories. Based on it, we justify choosing MAML, EMAML, and ProMP as the baselines.\n\nIn this manuscript, we focus on the category of optimization-based meta-RL. It is typical in EMAML, ProMP, and [10, 1.a] that optimization-based methods are only compared with optimization-based methods (due to their worse optimality than black-box methods in the in-distribution meta-test setting). So, in the experiments, we compare the proposed algorithm with the existing optimization-based meta-RL approaches, including MAML, EMAML, and ProMP. The experimental results show that the proposed method can outperform the baselines significantly. Moreover, we also achieve the state-of-art theoretical result over all optimization-based meta-RL papers, as shown in Table 1 (line 35). \n\nRecent optimization-based meta-RL papers, including new variants of MAML [10, 1.a], aim to solve the meta-gradient estimation issues. They usually do not significantly outperform MAML, EMAML and ProMP. In **the attached PDF file of the global rebuttal**, we include a recent baseline from [10] (2022) and compare their performances. The results show that the proposed method can also outperform this baseline.\n\n[1.a] Tang, Yunhao. \"Biased gradient estimate with drastic variance reduction for meta-reinforcement learning\", 2022.\n\n>**Weakness 2. The related work section can be improved. Specifically, the section is a short paragraph that covers only bilevel optimization algorithms for meta-RL. An extended related work section on meta-RL that covers the different types of meta-RL algorithms and places the paper with respect to the various approaches could help the reader understand the paper's contribution.**\n\n**Answer:** Thanks for the suggestion. In **the global rebuttal** and **the answer to Weakness 1**, we discuss the categorization of existing meta-RL algorithms, compare the two categories, and the advantages of the method in the manuscript over the existing optimization-based meta-RL methods. These discussions make our contribution more clear. We will add them to the revised manuscript.\n\n>**Question 2. Is it possible to formulate a similar bound for other meta-RL algorithms, such as RL2 [1] or VariBAD [2]?**\n\n**Answer:** This manuscript focuses on the theoretical analysis of optimization-based meta-RL. To the best of our knowledge, almost all papers that work on the theoretical analysis of meta-RL algorithms [10, 38, 50, 52] focus on optimization-based meta-RL. From **the answer to Weakness 1**, we can see that the design of optimization-based methods is usually inspired by theoretical analysis, and the design of the black-box method is often more heuristic. As a result, it is challenging to derive optimality bounds for black-box meta-RL, such as RL2 and VariBAD.\n\n>**Question 3. Lines 32-33 explain that even if the learned meta-parameter is close to the best one, the model adapted from the learned might be far from the task-specific optimum for some tasks, since the best meta-parameter is shared for all tasks and learned from the prior distribution that can be with high variance. The proposed algorithm was designed to adapt a stronger optimality metric, where the model is adapted from the task-specific optimal policy for each task. Could you provide a real experiment (even a synthetic experiment) that demonstrates this phenomenon? The existing experiments show that the proposed approach performs better than MAML, but it is still not entirely clear that this leads to improved performance. A synthetic example can help fully explain this important failure case of existing meta-learning approaches.**\n\n**Answer:** We apologize for the confusion regarding the reason for the performance improvement of the proposed algorithm over MAML. The better performance of the proposed algorithm is not due to the use of a stronger optimality metric. The stronger optimality metric is only used to evaluate the proposed algorithm. It is not directly used in the design of the algorithm. Instead, the reason is that we design the policy adaptation problem (Problem (1), line 159) and solve it by multiple optimization steps.\n\nIn specific, MAML and its variants apply the policy gradient on the one-time data collection during the meta-test. Problem (1) (line 159) is to maximize a surrogate function, which is an approximate total reward function (as indicated in line 170) using one-time data collection. We solve the optimal solution of Problem (1) by multiple optimization steps. The objective function of Problem (1) is a better approximation for the total reward function than that of the policy gradient in MAML, and therefore can achieve a better performance than MAML.\n\nMoreover, since the objective of Problem (1) is a lower bound of the total reward function (stated in Lemmas 1 and 2, line 304), we can derive the optimality bound of the proposed algorithm under a stronger optimality metric. The theoretical analysis provides more insight into why the design of Problem (1) is good.\n\nTo improve clarity, we will swap the third paragraph and the fourth paragraph of the introduction, and add a necessary clarification to the modified manuscript.", "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": "wsi2jdCaE6", "reviewer": "Reviewer_DbXf", "summary": "This paper proposes an optimization framework to learn the meta-prior for task-specific policy adaptation.", "questions": "see the weaknesses", "limitations": "yes, the author has provided that", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method claims to be data-efficient in terms of data collection developed only using one-time data collection. Also, this paper aims to solve the RL problem as a bilevel optimization problem.\n2. The proposed method considers both unconstrained and constrained optimization problem cases.\n4. the upper bounds of the optimality between the adapted policy and the optimal task-specific policy are provided.", "weaknesses": "1. the proposed method heavily depends on the minimization problems of eq. 1 or eq. 2, which minimizes the distance between the policy and the predefined policy and finds the optimal policy for the additional task at the same time. My concern and question is that given the same problem that we want to adapt a pre-defined policy \\pi to a new task L while keep the original task J, what is the performance difference if i just train the \\pi to minimize L+J ? \n2. can you plot the algorithm deployment performance for the example in Fig. 2? since sometimes if you only do \\min_\\theta ||\\pi_\\theta - K(x)||, where K(x) is a predefined controller, the \\theta converges fast, but the achieved \\pi_\\theta does not work well in some examples.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your time and effort in reviewing our work. Thanks for your suggestions to make our manuscript better. We address your concerns as follows.\n\n>**Weakness 1. The proposed method heavily depends on the minimization problems of eq. 1 or eq. 2, which minimizes the distance between the policy and the predefined policy and finds the optimal policy for the additional task at the same time. My concern and question is that given the same problem that we want to adapt a pre-defined policy $\\pi$ to a new task $L$ while keep the original task $J$, what is the performance difference if I just train the $\\pi$ to minimize $L+J$?**\n\n**Answer:** The goal of the policy adaptation problem, i.e., Eq. 1 or Eq. 2 (lines 159 and 161), is **not** adapting a pre-defined policy $\\pi$ to a new task $L$ while keeping the original tasks $J$. \n\nMinimizing $L + J$ is essentially multi-task learning. The motivation for multi-task learning is that there exists a common solution for the multiple tasks and training on them together could benefit the training for each task. For example, the feature extraction layers for multiple image classification tasks are shared, and training these layers together could help extract better features for each task.\n\nIn the problem of this manuscript, we consider meta-learning, where we aim to learn knowledge for a task distribution. The tasks in the task distribution have different goals and there is no shared component that can applied to all tasks. For example, the task of driving a robot north and the task of driving a robot south are related and follow a task distribution. However, the optimal policies for them have no shared component. If we minimize $L + J$ of two tasks, the solution performs badly for any of the two tasks. Therefore, minimizing $L + J$ is not applicable to our problem. \n\nThis manuscript studies meta-learning, which is different from multi-task learning. Meta-learning aims to learn a meta-policy, such that the meta-policy can be adapted to tasks in a task distribution with a small amount of data. It trains a meta-policy during the meta-training. During the meta-test, the meta-policy is adapted to new tasks by the policy adaptation, Eq. 1 or Eq. 2 (lines 159 and 161).\n\nTherefore, the goal of Eq. 1 or Eq. 2 is adapting the meta policy to the new task $L$ in the meta-test, i.e., the adapted policy can minimize the loss of $L$ or is close to its minimum.\nDuring the meta-test, the original multiple tasks about $J$ are not used anymore, and the learned meta-policy $\\pi_\\phi$ serves as the prior knowledge to learn the task-specific policy for new tasks. \n\nNext, we would like to discuss why we cannot directly minimize $L$ without learning meta-policy $\\pi_\\phi$ and why the learned meta-policy $\\pi_\\phi$ is necessary. As we know, a fundamental difference between RL and supervised learning is that RL can not be solved on one-time collected data, i.e., the loss of $L$ cannot be minimized using the data collected on one policy. The RL algorithm minimizes $L$ by iterative data sampling and policy optimization. However, during the meta-test of meta-RL, we can only collect data on one policy (one-time data collection) on the new task of $L$ and it is impossible to minimize $L$. Therefore, we use the problem in Eq. 1 or Eq. 2 to approximate the minimization of $L$.\nMeta-RL is to learn how to better approximate the minimization of $L$, and the meta-policy $\\pi_\\phi$ in Eq. 1 or Eq. 2 is the knowledge that is learned by meta-RL to reduce the approximation error.\n\n>**Weakness 2. Can you plot the algorithm deployment performance for the example in Fig. 2? Since sometimes if you only do $\\min_\\theta ||\\pi_\\theta - K(x)||$, where $K(x)$ is a predefined controller, the $\\theta$ converges fast, but the achieved $\\pi_\\theta$ does not work well in some examples.**\n\n**Answer:** In Fig. 2 (line 359), we show the performance of adapted policies on the meta-test tasks. The x-axis is the adaptation iteration number that the meta-policy is adapted to the new tasks, and the y-axis is the average accumulated reward of the adapted policies. The meta-test occurs after the new tasks are given, i.e., it represents the deployment of the learned meta-policy to new tasks. Therefore, Fig. 2 can reflect the performance of $\\pi_\\theta$ beyond the convergence. Figure 5 in Appendix B (line 600) shows the convergence of meta-training.", "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": "oIrMkbGtT2", "reviewer": "Reviewer_8Th6", "summary": "This paper presents a bilevel optimization framework for meta-reinforcement learning (Meta-RL) named BO-MRL, which aims to enhance policy adaptation through a universal policy optimization algorithm. The framework is designed to improve data efficiency by implementing multiple policy optimization steps on a single data collection during task-specific adaptation. The authors provide theoretical guarantees, including upper bounds on the expected optimality gap over a task distribution, which measure the distance between the adapted policy and the task-specific optimal policy. Empirical validation is conducted on several benchmarks, demonstrating the superior effectiveness of the proposed algorithm compared to existing methods.", "questions": "### Q1. Hyperparameter Sensitivity\n\nHow sensitive is the proposed method to the choice of hyperparameters? \n\n### Q2. Scalability\n\nCan the authors provide more insights into the scalability of the proposed method? How does the computational complexity scale with the number of tasks and the size of the state-action space?\n\n### Q3. Practical Deployment\n\nWhat are the practical considerations for deploying the proposed method in real-world scenarios? Are there any specific challenges or requirements that practitioners should be aware of?", "limitations": "The authors have adequately addressed the theoretical limitations and the assumptions underlying their framework. However, a more detailed discussion on the potential negative societal impacts and how to mitigate them would be beneficial.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### S1. Theoretical Contributions\n\nThe paper provides a solid theoretical foundation for the proposed bilevel optimization framework, including convergence guarantees and upper bounds on the expected optimality gap. This strengthens the understanding of the method's performance and its theoretical underpinnings.\n\n### S2. Empirical Validation\n\nThe empirical results presented in the paper are comprehensive and robust, showing significant improvements over state-of-the-art methods on various benchmarks. This demonstrates the practical applicability and effectiveness of the proposed framwork.\n\n### S3. Novel approach\n\nThe introduction of a universal policy optimization algorithm within a bilevel optimization framework is a novel and effective approach to tackling the challenges in Meta-RL. This method addresses both the optimality and data-inefficiency issues commonly faced by existing methods.", "weaknesses": "### W1. Complexity of Implementation\n\nThe proposed framework, while theoretically sound and empirically validated, may be complex to implement in practice. The bi-level optimization and the need for hypergradient computation require careful tuning and expertise, which might limit its accessibility to a broader audience.\n\n### W2. Limited discussion on practical implications\n\nThe paper could benefit from a more detailed discussion on the practical implications and potential limitations of the proposed method in real-world applications. This includes considerations such as computational resources, scalability to large-scale environments, and adaptability to varying task complexities.\n\n### W3. Comparison with Broader Range of Methods\n\nWhile the paper compares the proposed method with several state-of-the-art Meta-RL algorithms, it would be beneficial to include a broader range of methods, especially those outside the immediate Meta-RL context, to provide a more comprehensive evaluation of its performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks very much for your time and effort in reviewing our work. Thanks for your suggestions to make our manuscript better. We address your concerns as follows.\n\n>**Weakness 1. Complexity of Implementation The proposed framework, while theoretically sound and empirically validated, may be complex to implement in practice. The bi-level optimization and the need for hypergradient computation require careful tuning and expertise, which might limit its accessibility to a broader audience.**\n\n**Answer:** We propose a practical algorithm (Algorithm 2, lines 628) to simplify the hypergradient computation in Propositions 1 and 2 (lines 199 and 212). In the simplified hypergradient computation, the inverse Hessian matrix is computed by the conjugate gradient, which can be implemented in many standard Python libraries, such as Scipy. The remaining parts of the gradient computation can be handled by the Autograd function in PyTorch.\n\nThe experiments in our paper adopt the conjugate gradient. The experiment results validate the computational efficiency of our algorithm. In the experiment of Half-cheetah, the computation time of the hyper-gradient with the inverse of Hessian for a three-layer neural network is about $0.3$ second in each meta-parameter update, where we use only the CPU to compute the hyper-gradient.\nThis approach has demonstrated high efficiency across a wide range of applications, including several widely used RL algorithms, such as TRPO [44] and CPO [1]. The details are shown in Appendix C of [44]. In the simplest meta-RL method, MAML [13], the authors use the TRPO to update the meta-parameter, as shown in Section 5.3 of [13], the inverse of the Hessian is computed in a similar way to ours. Therefore, the computational complexity of the hyper-gradient in our proposed method is comparable to many existing RL and meta-RL approaches, which are shown efficient. \n\n>**Weakness 2. Limited discussion on practical implications. The paper could benefit from a more detailed discussion on the practical implications and potential limitations of the proposed method in real-world applications. This includes considerations such as computational resources, scalability to large-scale environments, and adaptability to varying task complexities.**\n\n**Answer:** In the experiment of the proposed algorithm, we only use the CPU to do meta-training and meta-tests. After the meta-model is trained, the policy adaptation only takes a few seconds (2 seconds). Therefore, the requirement of the computational resources for the proposed algorithm is low.\n\nIn the experiment section (Section 6, line 362), we conduct the experiments on relatively simple grid-world environments (lines 362, the results are shown in Figure 1,), and also on the complex high-dimensional locomotion tasks (lines 373, the results are shown in Figure 2). The experimental results demonstrate the superior performance of the proposed algorithm, highlighting its good adaptability to varying task complexities.\n\nThe proposed algorithm holds the scalability to large-scale environments and tasks. Please refer to **the answer to Question 2** for more details.\n\nA potential limitation in the practice is that the design of the reward functions for multiple tasks could be challenging, and requires lots of efforts of experts.\n\n>**Weakness 3. Comparison with Broader Range of Methods. It would be beneficial to include a broader range of methods, especially those outside the immediate Meta-RL context, to provide a more comprehensive evaluation of its performance.**\n\n**Answer:** The manuscript focuses on meta-RL and compares it with the existing meta-RL algorithms [13,43,48]. It is typical for the meta-RL papers to compare within the context of meta-RL. \n\n>**Question 1. Hyperparameter Sensitivity. How sensitive is the proposed method to the choice of hyperparameters?**\n\n**Answer:** As the performance of RL algorithms can be sensitive to the choice of hyperparameters, as shown in [3.a], the proposed method could hold a similar property. However, the tuning of the hyperparameters is easy. In particular, in the proposed method, the hyperparameters that are required to be tuned often appear in existing widely used meta-RL and RL algorithms, such as TRPO. We can follow the previous standard choice of them. \n\n[3.a] Eimer, Theresa, et al. \"Hyperparameters in reinforcement learning and how to tune them.\" International Conference on Machine Learning, 2023.\n\n>**Question 2. Scalability. Can the authors provide more insights into the scalability of the proposed method? How does the computational complexity scale with the number of tasks and the size of the state-action space?**\n\n**Answer:** Overall, the computational complexity of the proposed method is comparable to many existing meta-RL algorithms, including MAML [13]. More details about the computational complexity analysis are shown in Appendix E and F (lines 633-694).\n\nIn terms of the scalability to a large number of tasks, the applied stochastic optimization algorithm, Adam, has shown good performance on a huge amount of data, e.g., millions of data points.\nIn terms of the scalability to large state-action space, we apply the neural network as the approximation function of the action policy, which can deal with large-scale problems.\nIn the experiment, the dimension of the continuous state-action of the Ant environment is 35, which is sufficiently large for most RL problems. \n\n>**Question 3. Practical Deployment. \nWhat are the practical considerations for deploying the proposed method in real-world scenarios? Are there any specific challenges or requirements that practitioners should be aware of?**\n\n**Answer:** Meta-RL algorithms have been widely applied to many real-world scenarios, such as robotics [6, 40]. In terms of real-world practice, our algorithm is similar to these meta-RL algorithms and has no extra requirement for practitioners.", "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 are grateful and indebted for the time and effort invested to evaluate our manuscript by all reviewers, and for all the suggestions and reference recommendations to make our manuscript a better and stronger contribution. Please find below our detailed replies to all the reviewers' comments.

In this global rebuttal, we would like to discuss the categorization of existing meta-RL algorithms and compare the advantages and disadvantages of these categories.

>**Categorization of existing meta-RL.** As mentioned in the second paragraph of the introduction (line 19), meta-RL methods can be generally categorized into (i) optimization-based meta-RL, (ii) black-box (also called model-based or context-based) meta-RL. Optimization-based meta-RL approaches, such as MAML and its variants, usually include a policy adaptation algorithm and a meta-algorithm. During the meta-training, the meta-algorithm aims to learn a meta-policy, such that the policy adaptation algorithm can achieve good performance starting from the meta-policy. The learned meta-policy parameter is adapted to the new task using the policy adaptation algorithm during the meta-test.
Black-box meta-RL, such as RL2 and VariBAD, aims to learn an end-to-end neural network model. The model has fixed parameters for the policy adaptation during the meta-test, and generates the task-specific policy using the trajectories of the new task takes. The meta-RL algorithm in the manuscript is an optimization-based method. 
>
>
>Optimization-based meta-RL methods are typically less specialized to the training tasks and hold worse performance than black-box methods. However, it is more robust to sub-optimal meta-policies and can handle tasks outside the training distribution, compared with black-box methods.
In optimization-based meta-RL, the task-specific policy is adapted from a shared meta-policy over the task distribution. The learned meta-knowledge is not specialized for any task, and its meta-test performance on a task depends on a general policy optimization algorithm applied to new data from that task. 
In contrast, the end-to-end model in black-box meta-RL typically includes specialized knowledge for any task within the task distribution, and uses the new data merely as an indicator to identify the task within the distribution.
As a result, the optimality of optimization-based methods is usually worse than black-box methods, especially when the task distribution is heterogeneous and the data scale for adaptation is extremely small. 
On the other hand, the policy adaptation algorithms in the meta-test of optimization-based methods can generally improve the policy and show the convergence starting from any initial policy, not only the learned meta-policy. Therefore, it is robust to sub-optimal meta-policy and can deal with tasks that are out of the training task distribution. In contrast, due to the specialization of the learned model, black-box methods cannot be generalized outside of the training task distribution.

Meta-review: The paper proposes a bilevel optimization algorithm for Meta-RL. Different from the popular approach of MAML, the proposed algorithm performs multiple-step policy optimization on one-time data collection. The paper provides an upper bound on the expected optimality gap over the task distribution, that quantifies the model’s generalizability to a new task from the task distribution. The superior performance of the proposed algorithm over the existing meta-RL method has been shown via simulation experiments on standard benchmarks. 

We received three expert reviews, with the scores, 5, 6, 7, and the average score is 6.00. Reviewers are happy about the novelty of the proposed approach, the theoretical guarantees provided. The reviewers are also generally happy about the quality of the presentation. 

Reviewer DbXf has a question about the difference between the proposed method and multi-task learning, and the authors have clearly addressed this question in their rebuttal. Reviewer 8Th6 has expressed concerns about the implementation complexity and the comparison with more benchmarks. The authors have agreed to include more details about this in their revision, and the reviewer has accepted that. 

I have read the paper, the reviews, and the rebuttal. I believe that the paper proposes an interesting algorithmic approach for meta-RL. While mainly an algorithmic paper, it also provides some theoretical guarantees for the proposed approach. The simulation experiments are convincing. 

Please revise your paper based on the reviewers’ comments for the final submission.
Decision: Accept (poster)