Meta-Reinforcement Learning with Universal Policy Adaptation: Provable Near-Optimality under All-task Optimum Comparator

Authors: siyuan  xu
minghui  zhu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 21:17:41

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.

Main paper: 
 introduction: 
 Meta-learning [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 as meta-RL [15, 5] , and shows its promise to overcome the challenges of traditional RL algorithms, including scarce real-world data [3, 44, 65] , limited computing resources, and slow learning speed [54, 63] .Meta-learning methods can be generally categorized into optimization-based, model-based (black box methods), and metric-based methods [27, 5] . The optimization-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 a bilevel optimization problem. At the lower-level optimization, the task-specific model is adapted from a shared meta-parameter by an optimization algorithm. At the upper-level optimization, the meta-parameter is to maximize the meta-objective, i.e., the performance of the model adapted from the meta-parameter over training tasks. The existing methods, including MAML and its variants [15, 38, 12] , 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, MAML 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 not 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 [15] . However, the 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.In contrast, in this paper, we collect data by meta-policy for one time and utilize multiple policy optimization steps to improve the data efficiency.The optimality analysis of MAML is studied in [12, 60] with a metric of optimality on the metaobjective, where the error of the meta-objective is 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 meta-parameter 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-parameter might be far from task-specific optimum for some tasks. In contrast, we aim to design a meta-RL algorithm that can fit a stronger optimality metric, called near-optimality under all-task optimum, where the comparator, i.e., the policy adapted from the best meta-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-parameter, 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 in a standard meta-RL problem. The metric under all-task optimum is also studied by [9, 10, 65] 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-specific policy adaptation.The overall contributions are summarized as follows. (i) We develop a 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-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, to learn the mete-prior, we formulate the meta-RL problem as a bilevel optimization problem, where the lower-level optimization is the universal policy optimization algorithm from the meta-policy and the upper-level optimization is to maximize the meta-objective function, i.e., 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 benchmarks.Table 1 compares the solved theoretical challenges of meta-RL between this paper and previous works [12, 57, 60, 42] . Specifically, 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-optimality under all-task optimum is considered in [42] . However, it assumes the optimal expert policies of the training tasks are available in 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] .∞ t=0 γ t r (s t , a t , s t+1 ) |s 0 = s, π]. The action-value function is defined as Q π (s, a) ≜ E [ ∞ t=0 γ t r (s t , a t , s t+1 ) |s 0 = s, a 0 = a, π]. The advantage function is defined as A π (s, a) ≜ Q π (s, a) -V π (s). The accumulated reward function is J(π) ≜ E s∼ρ [V π (s)]. Define the discounted state visitation distribution of a policy π as ν π (s) ≜ E s0∼ρ [(1 -γ) ∞ t=0 γ t P (s t = s|π)]. In this paper, we consider parametric policy π θ , parameterized by θ. The optimal parameter θ * can maximize the accumulated reward function, i.e., θ * ≜ argmax θ J(π θ ). If θ * is not unique, denote the set of the optimal solutions by Θ * .Meta-reinforcement learning. Meta-RL aims to solve multiple RL tasks. Consider a space of RL tasks Γ, where each task τ ∈ Γ is modeled by a MDP M τ ≜ {S, A, γ, ρ τ , P τ , r τ }. Correspondingly, the notations V π τ , Q π τ , A π τ , ν π τ , θ * τ , Θ * τ and J τ are defined for task τ . The RL tasks follow a probability distribution P(Γ). Meta-RL aims to learn a meta-policy π ϕ parameterized by a meta parameter ϕ, such that it can adapt to an unseen task τ new ∼ P(Γ) with a few iterations and a small number of new environment explorations. In specific, during the meta-training, several tasks can be i.i.d. sampled from P(Γ), i.e., {τ j } T j=1 ∼ P(Γ), and the tasks' MDPs {M τj } T j=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, a new task τ new is given, one time of a within-task algorithm Alg with data collected from τ new is applied, the meta-parameter ϕ is adapted to the task-specific parameter θ ′ τnew and the task-specific policy π θ ′ τnew is tested on the task τ new . Optimality Metric. Consider a meta-RL algorithm that produces a meta-parameter ϕ, and the take-specific parameter π θ ′ τ is adapted from the meta-parameter ϕ on a task τ , denoted as π θ ′ τ = Alg(π ϕ , τ ). We define the task-expected optimality gap (TEOG) as the metric to evaluate the algorithm, i.e., E τ ∼P(Γ) [J τ (π θ * τ ) -J τ (Alg(π ϕ , τ ))], where θ * τ is the optimal parameter for task τ . First, the TEOG considers the expected error over the task distribution P(Γ), reflecting the generalizability of the produced meta-parameter. Second, the TEOG adopts the comparator of the optimal task-specific policy π θ * τ for any task τ (all-task optimum comparator), and evaluates the optimality gap J τ (π θ * τ )-J τ (Alg(π ϕ , τ )). In contrast, [60, 14, 26] adopts the comparator of the policy adapted from the optimal meta-parameter π ϕ * , and evaluates the optimality gap J τ (Alg(π ϕ * , τ )) -J τ (Alg(π ϕ , τ )). 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, it is crucial that the meta-policy π ϕ can benefit from learning on correlated tasks. Similar to [4, 9, 31] , we measure the correlation of tasks in the task distribution P(Γ) by its variance, defined by the minimal mean square of the distances among the optimal task-specific policies, i.e.,Var(P(Γ)) ≜ min θ min θ * τ ∈Θ * τ E τ ∼P(Γ) [D 2 τ (π θ , π θ * τ )].Here, D τ (π θ , π θ * τ ) is the distance metric between π θ and π θ * τ on the task τ and is defined byD τ (π θ , π θ ′ ) ≜ E s∼ν π θ τ [d 2 (π θ (•|s), π θ ′ (•|s))], where d(π θ (•|s), π θ ′ (•|s))is the distance of the policies π θ and π θ ′ on the state s.Note that the distance metrics D τ (•, •) and d(•, •, s) can be custom-defined, leading to multiple policy update algorithms, as shown in Section 4. Here, we introduce several examples of d(•, •, s) and D τ (•, •), which are commonly used as the distance metrics in RL literature [51, 30, 37] . For policies π θ and π θ ′ , we apply (i) the KL-divergence of the action probability distribution, i.e.,d 2 1 (π θ , π θ ′ , s) ≜ D KL (π θ (•|s)∥π θ ′ (•|s)), which is similar to the definition in [31] ; (ii) The KLdivergence with the other order, i.e.,d 2 2 (π θ , π θ ′ , s) ≜ D KL (π θ ′ (•|s)∥π θ (•|s)); (iii) the Euclidean distance of the parameters, i.e., d 2 3 (π θ , π θ ′ , s) ≜ ∥θ -θ ′ ∥ 2 .Correspondingly, for i = 1, 2, and 3,we define D τ,i (π θ , π θ ′ ) ≜ E s∼ν π θ τ [d 2 i (π θ , π θ ′ , s)]. Note that the distance metrics (i)(ii) are not symmetric, i.e., D τ (π θ ′ , π θ ′′ ) ̸ = D τ (π θ ′′ , π θ ′ ), and (iii) is symmetric.In the subsequent sections, we present algorithms based on the generalized distance definitions of D τ (•, •) and d(•, •, s). Moreover, we conduct analyses for the introduced distance metrics, from D τ,1 to D τ,3 , to provide comprehensive insights into their respective performances. 
meta-reinforcement learning framework: 
 In this section, we develop a meta-RL algorithm by bilevel optimization, where the lower-level optimization is the within-task algorithm that adapts the parameter from the meta-parameter and the upper-level optimization is the meta-algorithm that obtains the meta-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-task algorithm Alg. Specifically, given the meta-parameter ϕ and a task τ , the task-specific policyπ θ ′ τ = Alg(π ϕ , λ, τ ) is defined by θ ′ τ = argmax θ E s∼ν π ϕ τ ,a∼π θ (•|s) Q π ϕ τ (s, a) -λD 2 τ (π ϕ , π θ ).When the action space A is discretized and the policy is tabular, i.e., the probabilities of actions are independent between different states, the above problem can be solved byEQUATIONfor all states s ∈ S. When the policy is parameterized by an approximation function, in both continuous and discrete action space A,EQUATIONIn ( 1) and ( 2), λ > 0 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 a single policy π ϕ , where the data sampling complexity is exactly the same as the one-step gradient descent in MAML [15] . Therefore, we denote Alg, i.e., collecting data on the meta-policy and solving the optimal solution of ( 1) and (2) as the one-time policy adaptation. More details about the data sample complexity and the computational complexity of ( 1) 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 (1) or (2) . As shown in Section 5.4, the objective function of (1) or ( 2) is an approximation of the true objective function J τ (π).Note that the objective function in ( 1) and ( 2) can reduce to that of multiple widely used policy optimization approaches: (i) PPO in [51, 52] when D τ = D τ,2 ; (ii) a variant of the PPO [60, 37] , when D τ = D τ,1 ; (iii) the proximally regularized policy update, i.e., the policy optimization regularized by Euclidean distance of the policy parameter [51] , when D τ = D τ,3 . Moreover, (iv) if we approximate the expectation in (2) by its first-order approximation and also select D τ = D τ,3 , the within-task algorithm (2) also can be reduced to one-step policy gradient, as shown in Appendix H; (v) if we use the first-order approximation of the expectation in (2), the second-order approximation of the term D 2 τ (π ϕ , π θ ), and select D τ = D τ,2 , the within-task algorithm (2) is reduced to the natural policy gradient (NPG).Meta-algorithm. The performance of the meta-parameter ϕ is 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., E τ ∼P(Γ) [J τ (Alg(π ϕ , λ, τ ))]. In the meta-algorithm, we maximize the meta-objective to obtain the optimal meta-parameter ϕ * , i.e.,EQUATIONAs ( 1) and ( 2) provide multiple choices of the within-task algorithms when selecting different D τ , the meta-algorithm (3) provides the algorithms to learn the corresponding meta-priors. For example, (3) takes on the role of the meta-PPO algorithm when D τ = D τ,1 or D τ,2 , i.e., (3) learns the meta-initialization for PPO. It is a meta-NPG algorithm with the corresponding approximation and D τ . Moreover, when Alg(π ϕ , λ, τ ) in ( 2) reduces to the one-step policy gradient shown in (iv) of the last paragraph, (3) represents a precise formulation of MAML in [15] . More details about the formulation and its relations with MAML are shown in Appendix G and H.Hypergradient computation. Simlar to [29, 64] , the meta-algorithm in (3) aims to solve a 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 policy optimization, its closed-form solution cannot be obtained. To address the challenge, we compute ∇ ϕ Alg(π ϕ , λ, τ ) and the hypergradient by deriving the implicit differentiation on Alg(π ϕ , λ, τ ). As shown in Section 4, the optimization problem Alg(π ϕ , λ, τ ) is unconstrained in (2), but is constrained in (1) due to a∈A π(a|s) = 1. Therefore, we derive the implicit differentiation for both unconstrained and constrained optimization problems. The following proposition shows the hypergradient computation for the tabular policy. Its proof is shown in Appendix J.1. Proposition 1 (Hypergradient for the tabular policy). For the tabular policy in the discrete state-action space, consider any meta-parameter ϕ and the within-task algorithm (1) . Letπ θ ′ τ = Alg(π ϕ , λ, τ ). If M (s) ≜ λ∇ 2 π(•|s) d 2 (π ϕ (•|s), π(•|s)) is non-singular for each s ∈ S, we have ∇ ϕ J τ (π θ ′ τ ) = 1 1-γ E s∼ν π θ ′ τ τ a∈A ∇ ϕ π θ ′ τ (a|s)Q π θ ′ τ τ (s, a) , where ∇ ⊤ ϕ π θ ′ τ (•|s) = M (s) -1 -M (s) -1 1 1 ⊤ M (s) -1 1 ⊤ M (s) -1 1 ∇ ⊤ ϕ Q π ϕ τ (s, •) -λ∇ ⊤ ϕ ∇ π(•|s) d 2 (π ϕ (•|s), π(•|s)) | π=π θ ′ τ . The computation of ∇ ϕ Q π ϕ τ (s, •) is shown in Appendix C. A sufficient condition of M (s) being non-singular is that d is locally strongly-convex at π = π θ ′ τ , shown in Appendix J.1. Moreover, when d = d 1 or d = d 2 (correspondingly, D τ = D τ,1 or D τ = D τ,2 in (1)), the matrix M (s) = λ∇ 2 π(•|s) d 2 (π ϕ (•|s), π(•|s)) is always non-singular for any ϕ and M (s) is always diagonal, and thus it is easy to compute M -1 (s). The hypergradient computation ∇ ϕ J τ (π θ ′ τ ) for D τ = D τ,1 and D τ,2 is shown in Appendix K.1 and L.1.The following proposition shows the hypergradient computation for the policy with function approximation. Its proof is shown in Appendix J.2. Proposition 2 (Hypergradient for the policy with function approximation). When a policy is represented by a function approximation, in both the discrete and continuous action spaces, for any meta-parameter ϕ and the within-task algorithm in (2) . Letπ θ ′ τ = Alg(π ϕ , λ, τ ). If ∇ ϕ J τ (π θ ′ τ ) exists, ∇ ϕ J τ (π θ ′ τ ) = 1 1-γ ∇ ϕ θ ′ τ E s∼ν π θ ′ τ τ ,a∼π θ ′ τ (•|s) ∇ θ ′ τ π θ ′ τ (a|s) π θ ′ τ (a|s) Q π θ ′ τ τ (s, a) , and∇ ⊤ ϕ θ ′ τ = -E s∼ν π ϕ τ ,a∼π ϕ (•|s) [∇ 2 θ d 2 (π ϕ (•|s), π θ (•|s)) - ∇ 2 θ π θ (a|s) λπ ϕ (a|s) Q π ϕ τ (s, a)] -1 E s∼ν π ϕ τ ,a∼π ϕ (•|s) [∇ ⊤ ϕ ∇ θ d 2 (π ϕ (•|s), π θ (•|s)) -∇ θ π θ (a|s) λπ ϕ (a|s) ∇ ⊤ ϕ Q π ϕ τ (s, a)]| θ=θ ′ τ .A sufficient condition of ∇ ϕ J τ (π θ ′ τ ) being existent is the objective function of ( 2) is locally strongly concave at θ = θ ′ τ , as proven in Appendix J.2. The computation of∇ ϕ Q π ϕ τ (s, •) is shown in Appendix C.Note that we need to compute the inverse of the Hessian when computing the hypergradient in Proposition 2. Similar to several widely used RL algorithms, such as TRPO [51] and CPO [1] , we apply the conjugate gradient algorithm [23] to compute the inverse of the Hessian, which has demonstrated high efficiency across a 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 E. With the hypergradient computations in Proposition 1 and Proposition 2, we apply the stochastic gradient ascent (SGD) to solve the optimization problem in (3) . The meta-training of the bilevel optimization framework for meta-RL (BO-MRL) is formally stated in Algorithm 1. The state-action value function in lines 3 and 5 can be estimated by many approaches, including Monte-Carlo sampling used in MAML [15] and vine in [51] . We also propose a practical algorithm of Algorithm 1, as shown in Algorithm 2 in Appendix D, which includes more implementation details of the algorithm and several mechanisms to improve Algorithm 1. 
theoretical results: 
 In this section, we quantify the performance of Algorithm 1, where the softmax policies and several distance metrics introduced in Section 3 are adopted. For convenience, we denote Alg (1) as Alg in (1) and (2) when D τ = D τ,1 , and denote Alg (2) and Alg (3) in an analogous way. In Section 5.1, we introduce the softmax policy and necessary assumptions. In the following three sections, we consider two cases of Algorithm 1, including (i) Algorithm 1 with the within-task algorithm Alg (1) and Alg (2) for the tabular softmax policy; and (ii) Algorithm 1 with the within-task algorithm Alg (3) for the softmax policy with function approximation. For the algorithms in (i) and (ii), we study the existence of hypergradient in Section 5.2, derive the convergence guarantees in Section 5.3, and derive the near-optimality under the all-task optimum, i.e., derive the upper bounds of TEOG, in Section 5.4.We apply the softmax policies, which are commonly applied in [66, 37, 60] , and use the following assumptions on the task τ .Softmax policies. Consider the softmax policies πθ parameterized by θ 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 πθ (•|s) ∝ exp(θ(s, •)), where θ ∈ R |S|×|A| is a tabular map. The policy with function approximation is defined by πθ (•|s) ∝ exp(f θ (s, •)), where f θ is a function approximation model S × A → R with the parameter θ ∈ R n . Assumption 1 (Upper bound of advantage function). For any task τ ∈ Γ and any softmax policy πθ , |A πθ τ (s, a)| ≤ A max for any a ∈ A and any s ∈ S.Since the reward r τ ≤ r max is bounded, it is easy to show that |A πθ τ (s, a)| ≤ rmax 1-γ and Assumption 1 always holds. But we still keep Assumption 1 here, since there usually exist A max such that A max ≪ rmax 1-γ . We also have the following assumption and show its remark. Assumption 2 (Sufficient state visit). For any task τ ∈ Γ, there exists a constant ϵ > 0, such that for all bounded parameters ϕ, ν πϕ τ (s) ≥ ϵ for all s ∈ S. Remark 1. Here are two sufficient conditions for Assumption 2: (i) For any task τ ∈ Γ, the MDP M τ is ergodic [43, 56] ; or (ii) the initial state distribution ρ τ has ρ τ (s) > 0 for any s ∈ S.The proof of Remark 1 is shown in Appendix O. Note that (i) of Remark 1 is a mild condition and is assumed in recent studies on RL algorithm analysis [61, 46] .For the policy with function approximation, we require the following additional assumptions on the approximate function f θ , which are standard or weaker than those in the analysis of meta-learning and meta-RL problems [9, 12, 13, 14] . Assumption 3 (Property of the approximate function). For any state-action pair (s, a) ∈ S × A, (i) the approximate functionf θ (s, a) are cubic differentiable. (ii) f θ (s, a) is L 1 -Lipschitz, i.e., ∥f θ1 (s, a) -f θ2 (s, a)∥ ≤ L 1 ∥θ 1 -θ 2 ∥ for any θ 1 , θ 2 ∈ R n . (iii) ∇ θ f θ (s, a) is L 2 -Lipschitz, i.e., ∥∇ θ f θ1 (s, a) -∇ θ f θ2 (s, a)∥ ≤ L 2 ∥θ 1 -θ 2 ∥ for any θ 1 , θ 2 ∈ R n , (iv) ∇ 2 θ f θ (s, a) is L 3 -Lipschitz, i.e., ∇ 2 θ f θ1 (s, a) -∇ 2 θ f θ2 (s, a) ≤ L 3 ∥θ 1 -θ 2 ∥ for any θ 1 , θ 2 ∈ R n .An essential prerequisite for using Algorithm 1 is that the hypergradients in Propositions 1 and 2 exist. As shown in Section 4, for the tabular policy, when i = 1 or 2, the hypergradient ∇ ϕ J τ (Alg (i) (π ϕ , λ, τ )) exists for any ϕ. 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 3 (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 1 and 3 hold. If λ > (6L 2 1 + 2L 2 )A max , ∇ ϕ J τ (Alg (3) (π ϕ , λ, τ )) always for any ϕ.We begin with the convergence guarantee of Algorithm 1 for the tabular policy. The following notations are used in the theorem:B i , C i , G i , K i , M i (i = 1 and 2), where K i ≜ 2(Bi+2C 2 i )r 2 max (1-γ) 4 , M i ≜ (Bi+2C 2 i )Girmax (1-γ) 4 for i = 1 and 2. B 1 ≜ 16rmax λ(1-γ) 3 + 24 1-γ + 12 λ , C 1 ≜ 6 1-γ , and G 1 ≜ 4Amax (1-γ) 2 . B 2 ≜ 16rmax λ(1-γ) 3 + 18 (1-γ) 2 , C 2 ≜ 4 1-γ , and G 2 ≜ 2Amax (1-γ) 2 .Theorem 1 (Convergence guarantee for tabular softmax policy). Consider the tabular softmax policy in the discrete action space. Suppose that Assumptions 1 and 2 hold. Let {ϕ t } T t=1 be the sequence of meta-parameters generated by Algorithm 1 with λ ≥ 2A max and the step size α = minrmaxBi (1-γ) 2 + 2γrmaxC 2 i (1-γ) 3 -1 , 1 Gi √ T. Then, the bound:1 T T t=1 E[∥∇ ϕ E τ ∼P(Γ) [J τ (Alg (i) (π ϕt , λ, τ ))]∥ 2 ] ≤ Ki T + Mi √ T . holds for i = 1 or 2.The first expectation comes from the random sampling in line 2 of Algorithm 1. The proofs of Theorem 1 are shown in Appendices K.2 and L.2.The following theorem shows the convergence guarantee for the policy with function approximation. The notations are used in the theorem:B 3 , C 3 , G 3 , K 3 , M 3 , where K 3 ≜ 2(B3+2C 2 3 )r 2 max (1-γ) 4 , M 3 ≜ (B3+2C 2 3 )G3rmax (1-γ) 4 , G 3 ≜ L1Amax(λ+ 2γ 1-γ L 2 1 Amax) (1-γ)(λ-(6L 2 1 +2L2)Amax) , C 3 ≜ 2L1(λ+ 2γ 1-γ L 2 1 Amax) (1-γ)(λ-(6L 2 1 +2L2)Amax) , and B 3 ≜ (160L 3 1 +56L1L2+4L3)(λ+ 2γ 1-γ L 2 1 Amax) 2 (1-γ) 3 (λ-(6L 2 1 +2L2)Amax) 2.Theorem 2 (Convergence guarantee for softmax policy with function approximation). In both discrete and continuous action space, consider the softmax policy with function approximation. Suppose that Assumptions 1, 2, and 3 hold. Let {ϕ t } T t=1 be the sequence of meta-parameters generated by Algorithm 1 with λ > (6L 2 1 +2L 2 )A max and the step size α = minrmaxB3 (1-γ) 2 + 2γrmaxC 2 3 (1-γ) 3 -1 , 1 G3 √ T . Then, the bound 1 T T t=1 E ∥∇ ϕ E τ ∼P(Γ) [J τ (Alg (3) (π ϕt , λ, τ ))]∥ 2 ≤ K3 T + M3 √ T . holds.The first expectation arises from the random sampling in line 2 of Algorithm 1. The proof of Theorem 2 is shown in Appendix M. Theorems 1 and 2 show that the convergence rate of Algorithm 1 is O( 1 √ T ) and the constants in the notation O are only related to the discount factor γ, the reward bound r max , the bound of the advantage function A max , and the Lipschitz constants of f θ .Before the derivation of the optimality analysis, we first introduce two intermediate Lemmas.Lemma 1. Suppose that Assumptions 1, 2 hold. For any task τ , any bounded parameters θ and θ ′ , and i = 1 or 2, we haveJ τ (π θ ′ ) -J τ (π θ ) ≥ E s∼ν π τ ,a∼π ′ (•|s) A πθ τ (s,a) 1-γ -2γAmax (1-γ) 2 ϵ D 2 τ,i (π θ , πθ ′ ). Lemma 2.Consider the softmax policy with function approximation shown in Section 5.1. Suppose that Assumptions 1, 2, and 3 hold. For any task τ , and any softmax policies parameterized by bounded θ and θ ′ , we haveJ τ (π θ ′ ) -J τ (π θ ) ≥ E s∼ν πθ τ ,a∼π θ ′ (•|s) A πθ τ (s,a) 1-γ - 4γAmaxL 2 1 (1-γ) 2 ϵ D 2 τ.3 (π θ , πθ ′ ).The proofs of Lemmas 1 and 2 are shown in Appendix N.1. Given Lemma 1, when λ = 2γAmax (1-γ)ϵ , the within-task algorithm Alg (1,2) (π, λ, τ ) in ( 1) is actually designed to maximize the right-hand side of the inequality, where π′ is the decision variable. Similarly, Given Lemma 2, when λ = 2) maximizes the right-hand side of the inequality, where πθ ′ is the decision variable. In other words, for each i = 1, 2, and 3, the within-task algorithm Alg (i) is to maximize a lower bound of J τ (π θ ), denoted as Jτ (π θ ). This idea, referred to as the minorization-maximization (MM) [28] , is widely used in [51, 33] . The design of Alg (i) enables us to connect the accumulated reward of the policy after the policy adaptation with that of the optimal policy πθ * τ for task τ , i.e., Jτ (Alg4γAmaxL 2 1 (1-γ)ϵ , Alg (3) (π θ , λ, τ ) in ((i) (π ϕ , λ, τ )) ≥ Jτ (π θ * τ ), which is a key intermediate result for the optimality analysis. The final preparatory step is that we borrow the analysis of the meta-training error from [60] . In particular, its theoretical result is encapsulated in the following assumption. Assumption 4. (Bounding error of meta-objective using gradient) LetF (i) (ϕ) ≜ E τ ∼P(Γ) [J τ (Alg (i) (π ϕ , λ, τ ))].For both the tabular policy and the policy with functional approximation, there exists a concave positive non-decreasing functionh i : [0, +∞) → [0, +∞), such that max ϕ ′ F (i) (ϕ ′ ) -F (i) (ϕ) ≤ h i (∥∇ ϕ F (i) (ϕ)∥ 2 ).Assumption 4 assumes the optimality gap of πϕ on the meta-objective is upper bounded by an increasing function of its gradient. A sufficient condition of Assumption 4 is provided by [60] . Combine the Assumption 4 and the convergence analysis in Theorems 1 and 2, we can bound the error of the meta-objective, i.e., max ϕ F (i) (ϕ) -F (i) (ϕ t ). This result is referred to as the optimality of the meta-objective shown in Table 1 . Finally, we derive the upper bounds of the TEOG for both the tabular policy and the policy with function approximation.Theorem 3 (Optimality guarantee for softmax tabular policy). Consider the tabular softmax policy for the discrete state-action space.Suppose that Assumptions 1,2 and 4 hold. Let {ϕ t } T t=1 be the sequence of meta-parameters generated by Algorithm 1 with λ = 2Amax(1-γ)ϵ and the step size α shown in Theorem 1. Then, the following holds for i = 1 or 2:1 T T t=1 E t E τ ∼P(Γ) [J τ (π θ * τ ) -J τ (Alg (i) (π ϕt , λ, τ ))] ≤ h i Ki T + Mi √ T + 2(1+γ)Amax (1-γ) 2 ϵ Var i (P(Γ)), where πθ * τ is the optimal softmax policy for task τ and the constants K i and M i are shown in Theorem 1.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 1,2, 3 and 4 hold. Let {ϕ t } T t=1 be the sequence of meta-parameters generated by Algorithm 1 with λ =(6L 2 1 +2L2)Amax (1-γ)ϵand the step size α shown in Theorem 2.The following holds:1 T T t=1 E t E τ ∼P(Γ) [J τ (π θ * τ ) -J τ (Alg (3) (π ϕt , λ, τ ))] ≤ h 3 K3 T + M3 √ T + ((6+4γ)L 2 1 +2L2)Amax (1-γ) 2 ϵVar 3 (P(Γ)), where πθ * τ is the optimal softmax policy for task τ and the constants K 3 and M 3 are the same as Theorem 2.The proofs of Theorems 3 and 4, as well as the selection of the hyperparameter λ in these two theorems, are shown in Appendix N.2. The theorems derive the upper bounds of the TEOGs between the parameter adapted by one-time policy adaptation from the produced meta-parameter ϕ t and the task-specific optimal parameter θ * τ . It is shown that, with at most T iterations, we can achieve the upper bounds in the order of O(h i ( 1 √ T ) + Var(P(Γ))). In other words, there exists at ≤ T with E τ ∼P(Γ) [J τ (Alg(π ϕt , λ, τ ))] ≥ E τ ∼P(Γ) [J τ (π θ * τ )] -O(h i ( 1 √ T ) + Var(P(Γ))).As the number of iterations T increases, or the variance of the task distribution Var(P(Γ)) reduces, the optimality of the meat-parameter ϕ t improves. The second term Var(P(Γ)) in the upper bounds of Theorems 3 and 4 corresponds the intuition of meta-learning, which is that, if the variance of a 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 ϕ center defined byarg min ϕ E τ ∼P(Γ) [D 2 τ,i (π ϕ , π θ * τ )],which is the center of all the task-specific optimal policies π θ * τ . The order of our upper bounds are comparable to O(T -1 4 + Var(P(Γ)) that is shown in [31] . On the other hand, compared with [31] , in this paper, the constants in the notation O only consist of γ, r max , A max , 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 1 and 2 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 τ (Alg (i) (π θ , λ, τ )) ≥ J τ (π θ ) for i = 1, 2 and 3 and any θ and any task τ . Therefore, multiple times of Alg always perform better than one-time Alg. 
verification of theoretical results: 
 We conduct an experiment to verify the optimality bounds of Algorithm 1 shown in Theorems 3 and 4. 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 (i) for all i = 1, 2 and 3, where the results of i = 2 and 3 are shown in Appendix A. Upper bound for one-time  (1) High task variance ( (1) applied)One-time of  (1) One-step of policy gradient 0.00 0.05 0.10 0.15Upper bound for one-time  (1) Low task variance ( (1) applied)Figure 1 : Results of the meta-test on Frozen Lake, where Alg (1) 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 Alg (1) . BO-MRL with  (2) BO-MRL with (3) MAML-TRPO ProMP E-MAML 0 1 2 3Number of policy adaptation steps BO-MRL with  (2) BO-MRL with  (3) MAML-TRPO ProMP E-MAML We compare our algorithm with MAML [15] and the random initialization. Figure 1 shows that, for Algorithm 1 with the within-task algorithm Alg (1) , 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. Moreover, in Figure 1 , 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.To evaluate the proposed practical algorithm, Algorithm 2 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-based 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 (i) 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 baseline methods are almost 0%. 
conclusion: 
 This paper develops a 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.Appendix for "Meta-Reinforcement Learning with Universal Policy Adaptation: Provable Near-Optimality under All-task Optimum Comparator" 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: [NA] Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: All experiments are executed on a 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(Γ) with high task variance and a task distribution P(Γ) with low task variance.In each distribution, there are 20 tasks. The tasks are 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 γ = 0.8, the reward is 1 when reaching the goal, and the reward is -1 when reaching the holes. When deriving the upper bound in Theorems 3 and 4, we approximately regard T be sufficiently large, and O(h i ( 1 √ T )) be close to 0. The Lipschitz of the tabular policy is 1, i.e., L 1 = 1; the Lipschitz of the derivative and the second-order derivative of the tabular policy are both 0, i.e., L 2 = 0 and L 3 = 0.Selection of hyper-parameters. 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) , λ = 0.5 for Alg (2) , and λ = 0.04 for Alg (3) . For the task distribution with low task variance, we set λ = 0.25 for Alg (1) , λ = 0.25 for Alg (2) , and λ = 0.02 for Alg (3) . There is a clarification about the hyper-parameter selection and the verified bound shown in Appendix N.3. Supplemental results. Figures 3 and 4 show the results of the proposed algorithm with Alg (2) and Alg (3) . It shows that, for all scenarios, the expected optimality gap of the policy adaptation Alg (2) or Alg (3) is smaller than the upper bound shown in Theorems 3 and 4, which verify our theoretical analysis. Upper bound for one-time  (2) High task variance ( (2) Upper bound for one-time  (2) Low task variance ( (2) applied)Figure 3 : Results of the meta-test of BO-MRL on Frozen Lake, where Alg (2) 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 Alg (2) .One-time of  (3) One-step of policy gradient 0.0 0.5 1.0 1.5Upper bound for one-time  (3) High task variance ( (3) applied)One-time of  (3) One-step of policy gradient 0.0 0.2 0.4 0.6Upper bound for one-time  (3) Low task variance ( (3) applied)Figure 4 : Results of BO-MRL on Frozen Lake, where Alg (3) is applied. Comparing the expected optimality gap by the BO-MRL and baselines with the upper bound of the accumulated reward of one-time Alg (3) .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, 15] . 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 1, Algorithm 2 in Appendix D. We consider the policy as a 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-specific policy adaptation, the optimization number by Adam is 50. The models are trained for up to 500 meta-iterations. For the TRPO in meta-parameter optimization, we use the KL-divergence constraint as δ = 1e -3.For the experiment of Half-Cheetah with goal velocities, we set λ = 0.5 for Alg (1) , λ = 0.4 for Alg (2) . For the experiment of Half-Cheetah with goal directions, we set λ = 0.5 for Alg (1) , λ = 0.5 for Alg (2) . For the experiment of Ant with goal velocities, we set λ = 0.5 for Alg (1) , λ = 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-based meta-RL algorithms, including MAML, E-MAML [55] , and ProMP [50] . The experiment results of E-MAML, ProMP, and MAML-TRPO come from [67, 15] . We do not compare the proposed algorithm with black-box meta-RL algorithms, as they are based on the task context and even can achieve good performance without adaptation. Supplemental results. Figure 5 shows that the proposed algorithm with both within-task algorithms Alg (i) 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. BO-MRL with  (2) BO-MRL with  (3) MAML-TRPO Algorithm supplementC Computation of ∇ ϕ Q π ϕ τ (s, a)In the computation of meta-objective shown in Propositions 1 and 2, we need to compute∇ ϕ Q π ϕ τ (s, a) ∇ ϕ Q π ϕ τ (s, a) = γ 1 -γ • E (s ′ ,a ′ )∼σ (s,a) τ,π ϕ ∇ ϕ ln π ϕ (a ′ |s ′ ) Q π ϕ τ (s ′ , a ′ ) .where the state-action visitation probability σ (s,a)τ,π θ initialized at (s, a) ∈ S × A is defined byσ (s,a) τ,π ϕ (s ′ , a ′ ) = (1 -γ) ∞ t=0 γ t P (s t = s ′ , a t = a ′ |π ϕ , s 0 ∼ P τ (•|s, a)) .For the tabular softmax policy in discrete state-action space shown in Section 5.1,EQUATIONwhere ⊙ is the element-wise product, ϕ(s ′ , •) is the vector which includes ϕ(s ′ , a ′ ) for all a ′ ∈ A as the elements, and A πϕ τ (s, •) is the vector which includes A πϕ τ (s, a) for all a ∈ A as the elements. Equivalently,EQUATIONFor the softmax policy with the function approximation,EQUATIONProof. As shown in [60] ,∇ ϕ Q π ϕ τ (s, a) = ∇ ϕ (1 -γ) • r τ (s, a) + γ • E s ′ ∼Pτ (•|s,a) V π ϕ τ (s ′ ) = γ 1 -γ • E (s ′ ,a ′ )∼σ (s,a) τ,π ϕ ∇ ϕ ln π ϕ (a ′ |s ′ ) • Q π ϕ τ (s ′ , a ′ ) = γ 1 -γ • E (s ′ ,a ′ )∼σ (s,a) τ,π ϕ ∇ ϕ ln π ϕ (a ′ |s ′ ) • A π ϕ τ (s ′ , a ′ ) . = γ 1 -γ • E (s ′ ,a ′ )∼σ (s,a) τ,π ϕ ∇ ϕ π ϕ (a ′ |s ′ ) π ϕ (a ′ |s ′ ) • A π ϕ τ (s ′ , a ′ ) .By Lemma 4, from (12) , we can obtain (4); from (14), we can obtain (6) .In Sections 4 and 5, we develop a theoretically guaranteed algorithm with Assumptions 1, 2, and 3.In this section, we develop a practical instantiation of Algorithm 1 and evaluate its performance in high-dimensional experiments in Section 6.Algorithm 2 states the practical algorithm of Algorithm 1. Compared with Algorithm 1, Algorithm 2 considers and overcomes the following limitations of Algorithm 1: (a) evaluating the exact expectation in (1) and ( 2) is costly and the approximation error could influence the task-specific policy adaptation if using sampling, especially in the meta-RL problem where the sampling data is limited; (b) the optimization problems in (1) and ( 2) have no closed-form solution; (c) the computation of the gradients of the meta-objectives shown in Propositions 1 and 2 is time-consuming; (d) the gradient-based approach to optimize the meta-objective is not stable in RL problems.In the beginning of Algorithm 2, we first sample a batch of tasks {τ i } N i=1 ∼ P(Γ). On each task τ i , we sample the trajectories of the meta-policy π ϕt as B τi , and evaluate the state-action value function Q π ϕ t τi (•, •) for each τ i . Next, since the number of the sampling state-action pairs in B τi is limited, if we directly use the sampling average to approximate the expectation in (2), the approximation error will be very large when π ϕ (a|s) is small. Therefore, we solve the following optimization problem as the within-task algorithm instead of (2):EQUATIONwhere h(x) = 2 1+e -2(x-1) . The function h avoids the term π θ (a|s) π ϕ (a|s) is optimized to very large. We use Adam [32] to solve the problem in (7) . Next, the computation of the gradients of the metaobjectives shown in Proposition 2 is time-consuming, since the computation complexity of the term Algorithm 2 Practical Algorithm of BO-MRL Require: Regularization weight λ > 0; initial meta-parameter ϕ 0 ; learning rate α.1:for t = 1, • • • , T do 2:Sample a batch of tasks {τ i } N i=1 ∼ P(Γ) with the MDP M τi i.i.d.On each task τ i , sample the trajectories of the meta-policy π ϕt as B τi .4:Evaluate the state-action value function Qπ ϕ t τi (•, •) for each τ i . 5:For each task τ i , compute the task-specific policy π θ ′ τ i by solving Alg(λ, ϕ t , τ i ) defined in ( 7) by Adam.6: Compute ∇ ϕ J τi (π θ ′ τ i) in ( 8) by conjugate gradient method 7:Update meta-parameter by the TRPO with the gradient1 N i ∇ ϕ J τi (π θ ′ τ i) and the sampling trajectories {B τi } N i=1 . 8: end for9: Return ϕ T -∇ θ π θ (a|s) λπ ϕ (a|s) ∇ ⊤ ϕ Q π ϕ τ (s, a) is very high. So, we omit the term, and computeEQUATIONwhere∇ ⊤ ϕ θ ′ τ ≈ -E s∼ν π ϕ τ a∼π ϕ (•|s) ∇ 2 θ d 2 (π ϕ (•|s), π θ (•|s)) - ∇ 2 θ π θ (a|s) λπ ϕ (a|s) Q π ϕ τ (s, a) -1 E s∼ν π ϕ τ a∼π ϕ (•|s) ∇ ⊤ ϕ ∇ θ d 2 (π ϕ (•|s), π θ (•|s)) | θ=θ ′ τ .Finally, since the gradient-based approach is not stable in RL problems, we optimize meta-parameter by the TRPO with the gradient1 N i ∇ ϕ J τi (π θ ′ τ i) and the sampling trajectories {B τi } N i=1 , similar to [15] .In Algorithms 1 and 2, we compute the inverse of the Hessian matrix when computing the hypergradient by Proposition 2 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 is not high. According to our 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. This approach has demonstrated high efficiency across a wide range of applications, including several widely used RL algorithms, such as TRPO [51] and CPO [1] , which compute the inverse of the Hessian in each policy update iteration. The detail is shown in Appendix C of [51] . They usually compute thousands times of the Hessian inverse for a single RL task. In the simplest meta-RL method, MAML [15] , the authors use the TRPO to update the meta-parameter, as shown in Section 5.3 of [15] , the inverse of the Hessian is also computed. 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.Second, the biggest computational bottleneck in the meta-RL framework is not the hyper-gradient computation. According to our experiment, the percentage of the computation time in the metaparameter update, including the computation time of the hyper-gradient 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 in 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 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.The one-time policy adaptation in our algorithm is defined as solving the optimal solution of the optimization problem in (1) or ( 2) by multiple optimization iterations. The definition of the one-time policy adaptation follows many widely used RL algorithms, such as TRPO [51] and CPO [1] , which evaluate the Q-values for the current policy and solve the optimal solution for an optimization problem to obtain the next policy in 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 to evaluate the Q-function for one policy π ϕ by Monte-Carlo sampling, which requires the agent to explore the MDP using one policy π ϕ , then solve the optimization problem in (1) 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 are different from the multi-step policy gradient update in MAML. In our algorithm, the multiple optimization steps in a one-time policy adaptation only need to evaluate the Q-function for one policy π ϕ , which requires the agent to explore the MDP using only π ϕ . 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 MAML 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-world 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 a relatively small impact on the mete-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 (1) or (2) as a single policy adaptation step.As we mentioned in Section 4, we can approximate the first term 2) by its first-order approximation as the within-task algorithm, similar to the implementations in TRPO [51] and PPO [52] . In particular, the within-task algorithm is reduced to the following formulation,E s∼ν π ϕ τ ,a∼π ϕ (•|s) [ π θ (a|s) π ϕ (a|s) Q π ϕ τ (s, a)] in (EQUATIONHere, we use the first-order approximation to replace the first term of (2). In particular,G(ϕ) ⊤ (θ -ϕ) is the first order approximation of E s∼ν π ϕ τ ,a∼π ϕ (•|s) [ π θ (a|s) π ϕ (a|s) Q π ϕ τ (s, a)],whereG(ϕ) = ∇ θ E s∼ν π ϕ τ ,a∼π ϕ (•|s) [ ∇ θ π θ (a|s) π ϕ (a|s) Q π ϕ τ (s, a)]| θ=ϕ = E s∼ν π ϕ τ ,a∼π ϕ (•|s) [ ∇ ϕ π ϕ (a|s) π ϕ (a|s) Q π ϕ τ (s, a)].Under the simplified within-task algorithm Alg, the hypergradient of the meta-objective function∇ ϕ J τ (π θ ′ τ ) can be computed by ∇ ϕ J τ (π θ ′ τ ) = 1 1 -γ ∇ ϕ θ ′ τ • E s∼ν π θ ′ τ τ a∼π θ ′ τ (•|s) ∇ θ ′ τ π θ ′ τ (a|s) π θ ′ τ (a|s) Q π θ ′ τ τ (s, a) ,whereEQUATIONThe computation of ∇ ⊤ ϕ θ ′ τ is derived in Section J.3.As we claim in Section 4, when we approximate the first term 2) by its first-order approximation and also select D τ = D τ,3 , the within-task algorithm ( 2) is reduced to the policy gradient ascent. In particular, the termE s∼ν π ϕ τ ,a∼π ϕ (•|s) [ π θ (a|s) π ϕ (a|s) Q π ϕ τ (s, a)] in (E s∼ν π ϕ τ ,a∼π ϕ (•|s) [ π θ (a|s) π ϕ (a|s) Q π ϕ τ (s, a)] is approximated by (θ -ϕ) ⊤ E s∼ν π ϕ τ ,a∼π ϕ (•|s) [ ∇π ϕ (a|s) π ϕ (a|s) Q π ϕτ (s, a)], then the within-task algorithm Alg(π ϕ , λ, τ ) becomes toEQUATIONSolve the optimization problem, we haveθ ′ τ = ϕ + 1 λ E s∼ν π ϕ τ a∼π ϕ (•|s) ∇ ϕ π ϕ (a|s) π ϕ (a|s) Q π ϕ τ (s, a) = ϕ + 1 -γ λ ∇ ϕ J τ (ϕ),which is policy gradient ascent. Thus, when we select (11) as the within-task algorithm, the metaalgorithm (3) is reduced to the algorithm that can learn the initialization parameter for the policy gradient ascent.As shown in [15] , MAML also learns the initialization parameter ϕ for the policy gradient ascent. However, MAML ignores that the sampled trajectories with policy π ϕ also depend on ϕ. Specifically, MAML first uses the sampled trajectories to approximate Q π ϕ τ (s, a) by (Monte Carlo sampling on the REINFORCE algorithm), then computes the policy gradient and does one step of gradient ascent for the task-specific adaptation. Next, it computes ∇ ϕ J τ (θ ′ τ ) to update the meta-parameter ϕ. When it computes ∇ ϕ θ ′ τ , it treats Q π ϕ τ (s, a) as a given data point that is independent with ϕ, and then ignore the ∇ ϕ Q π ϕ τ (s, a). In contrast, our reduced meta-algorithm takes it into account and provides a precise formulation to learn the meta-initialization for the policy gradient algorithm.Since the proposed meta-RL framework can include MAML as a special case, our analysis in Section 5 also provides the theoretical motivation for MAML.Lemma 3 (Policy gradient [56, 2] ). Let π θ be the parameterized policy with the parameter θ. It holds that∇ θ J τ (π θ ) = 1 1 -γ E s∼ν π θ τ ,a∼π θ (•|s) [∇ θ ln π θ (a|s)Q π θ τ (s, a)] = 1 1 -γ E s∼ν π θ τ ,a∼π θ (•|s) [∇ θ ln π θ (a|s)A π θ τ (s, a)] .Lemma 4 (Policy gradient of the softmax policy). Consider the softmax policy πθ parameterized by θ. For a discrete state-action space and the tabular policy, πθ (a|s) = exp(θ(s,a))a ′ ∈A exp(θ(s,a ′ )) , ∀(s, a) ∈ S × A. It holds thatEQUATION)where ⊙ is the element-wise product, θ(s, •) is the vector which includes θ(s, a) for all a ∈ A as the elements, A πθ τ (s, •) is the vector which includes A πθ τ (s, a) for all a ∈ A as the elements. Equivalently,EQUATIONFor the softmax policy with function approximation, the policy π θ is defined by π θ (a|s) = exp(f θ (s,a))EQUATIONProof. For the discrete state-action space and the tabular policy, ( 12) is shown in Lemma C.1 of [2] .For the softmax policy with function approximation, from Lemma 3, we have∇ θ J τ (π θ ) = 1 1 -γ E s∼ν πθ τ ,a∼π θ (•|s) ∇ θ ln πθ (a|s)A πθ τ (s, a) = 1 1 -γ E s∼ν πθ τ ,a∼π θ (•|s) ∇ θ ln exp(f θ (s, a)) A exp(f θ (s, a ′ ))da ′ A πθ τ (s, a) = 1 1 -γ E s∼ν πθ τ ,a∼π θ (•|s) ∇ θ f θ (s, a) -∇ θ ln A exp(f θ (s, a ′ ))da ′ A πθ τ (s, a)Here,∇ θ ln A exp(f θ (s, a ′ ))da ′ is independent with a, then ∇ θ J τ (π θ ) = 1 1 -γ E s∼ν πθ τ ,a∼π θ (•|s) ∇ θ f θ (s, a) -∇ θ ln A exp(f θ (s, a ′ ))da ′ A πθ τ (s, a) = 1 1 -γ E s∼ν πθ τ ,a∼π θ (•|s) ∇ θ f θ (s, a)A πθ τ (s, a) - 1 1 -γ E s∼ν πθ τ ∇ θ ln A exp(f θ (s, a ′ ))da ′ E a∼π θ (•|s) A πθ τ (s, a) . Since E a∼π θ (•|s) A πθ τ (s, a) = E a∼π θ (•|s) [Q πθ τ (s, a)] -V πθ τ (s) = 0. Then, ∇ θ J τ (π θ ) = 1 1 -γ E s∼ν πθ τ ,a∼π θ (•|s) ∇ θ f θ (s, a)A πθ τ (s, a) .Proofs of Propositions 1. Consider the within-task algorithm in discrete space:Alg(π ϕ , λ, τ ) = argmax π E s∼ν π ϕ τ a∈A π(a|s)Q π ϕ τ (s, a) -λD 2 τ (π ϕ , π) = argmax π E s∼ν π ϕ τ a∈A π(a|s)Q π ϕ τ (s, a) -λd 2 (π ϕ (•|s), π(•|s)) .Here, d can be selected from d 1 to d 3 defined in Section 3, corresponding to the selection of D τ from D τ,1 to D τ,3 .The above optimization problem is formally defined by the following problem,EQUATIONWith Assumption 2, the problem is equivalent to that, for any s ∈ S,EQUATIONConsider a s ∈ S, the Lagrangian of the above maximization problem is- a∈A π(a|s)Q π ϕ τ (s, a) + λd 2 (π ϕ (•|s), π(•|s)) + µ( a∈A π(a|s) -1),where µ is the Lagrangian multiplier. The optimality condition of π(•|s) is that,-Q π ϕ τ (s, •) + λ∇ π(•|s) d 2 (π ϕ (•|s), π(•|s)) + µ[1, • • • , 1] ⊤ = 0.Here, Qπ ϕ τ (s, •) denotes a vector include Q π ϕ τ (s, a)for each a ∈ A, and π(•|s) denotes a vector include π(a|s) for each a ∈ A.Then, we haveEQUATIONNote that the optimization problem (15) depends on ϕ, and π = Alg(π ϕ , λ, τ ) is a function of ϕ, we have-Q π ϕ τ (s, •) + λ∇ π(•|s) d 2 (π ϕ (•|s), π(•|s))| π=Alg(π ϕ ,λ,τ ) + µ(ϕ)[1, • • • , 1] ⊤ = 0,i.e., µ is a function of ϕ.Also, we have µ(ϕ)( a∈A Alg(π ϕ , λ, τ )(a|s) -1) = 0.With ( 17) and ( 18), we can compute ∇ ϕ Alg(π ϕ , λ, τ ), where Alg(π ϕ , λ, τ ) is continuously differentiable as shown in [64] . We do derivative of ( 17) and ( 18) with respect to ϕ, we haveEQUATIONwhere π = Alg(π ϕ , λ, τ ).Solve the equation, we haveEQUATIONwhereM (s) = λ∇ 2 π(•|s) d 2 (π ϕ (•|s), π(•|s)). It is easy to show that ∇ 2 π(•|s) d 2 (π ϕ (•|s), π(•|s)) is non-singular for any ϕ for any selected d = d 1 , d = d 2 , or d = d 3 .From the policy gradient theorem in Lemma 3,∇ ϕ J τ (π θ ′ τ ) = 1 1 -γ E s∼ν π θ ′ τ τ ,a∼π θ ′ τ (•|s) [∇ ϕ ln π θ ′ τ (a|s)A π θ ′ τ τ (s, a)]| π θ ′ τ =Alg(π ϕ ,λ,τ ) = 1 1 -γ E s∼ν π θ ′ τ τ ,a∼π θ ′ τ (•|s) ∇ ϕ π θ ′ τ (a|s) π θ ′ τ (a|s) A π θ ′ τ τ (s, a) | π θ ′ τ =Alg(π ϕ ,λ,τ ) , = 1 1 -γ E s∼ν π θ ′ τ τ a∈A ∇ ϕ π θ ′ τ (a|s)A π θ ′ τ τ (s, a) | π θ ′ τ =Alg(π ϕ ,λ,τ ) .where∇ ϕ π θ ′ τ (•|s) = ∇ ϕ Alg(π ϕ , λ, τ )(•|s) is shown in (19).Proofs of Propositions 2. First, we have∇ ϕ J τ (π θ ′ τ ) = ∇ ϕ θ ′ τ ∇ θ ′ τ J τ (π θ ′ τ )From the policy gradient theorem in Lemma 3,∇ ϕ J τ (π θ ′ τ ) = 1 1 -γ ∇ ϕ θ ′ τ ⊤ E s∼ν π θ ′ τ τ ,a∼π θ ′ τ (•|s) ∇ θ ′ τ ln π θ ′ τ (a|s)A π θ ′ τ τ (s, a) | θ ′ τ =Alg(π ϕ ,λ,τ ) . We have ∇ ϕ J τ (π θ ′ τ ) = 1 1 -γ ∇ ϕ θ ′ τ ⊤ E s∼ν π θ ′ τ τ ,a∼π θ ′ τ (•|s) ∇ θ ′ τ π θ ′ τ (a|s) π θ ′ τ (a|s) A π θ ′ τ τ (s, a) | θ ′ τ =Alg(π ϕ ,λ,τ ) .Next, we compute ∇ ϕ θ ′ τ , whereθ ′ τ = Alg(π ϕ , λ, τ ) ≜ argmax θ E s∼ν π ϕ τ ,a∼π ϕ (•|s) π θ (a|s) π ϕ (a|s) Q π ϕ τ (s, a) -λD 2 τ (π ϕ , π θ ).The optimization problem is equivalent toθ ′ τ ≜ argmax θ E s∼ν π ϕ τ A π θ (a|s)Q π ϕ τ (s, a)da -λd 2 (π ϕ (•|s), π θ (•|s)) = argmin θ E s∼ν π ϕ τ - A π θ (a|s)Q π ϕ τ (s, a)da + λd 2 (π ϕ (•|s), π θ (•|s)) = argmin θ s∈S ν π ϕ τ (s) - A π θ (a|s)Q π ϕ τ (s, a)da + λd 2 (π ϕ (•|s), π θ (•|s)) .Similar to the derivation from ( 15) to ( 16) with Assumption 2, we have that, when θ = Alg(π ϕ , λ, τ ),∇ θ - A π θ (a|s)Q π ϕ τ (s, a)da + λd 2 (π ϕ (•|s), π θ (•|s)) = 0.Then, we haves∈S ∇ ϕ ν π ϕ τ (s)∇ θ - A π θ (a|s)Q π ϕ τ (s, a)da + λd 2 (π ϕ (•|s), π θ (•|s)) = 0.By using implicit differentiation, if the matrix E s∼νπ ϕ τ -A ∇ 2 θ π θ (a|s)Q π ϕ τ (s, a)da + λ∇ 2 θ d 2 (π ϕ (•|s), π θ (•|s)) is invertible, i.e., E s∼ν π ϕ τ -A π θ (a|s)Q π ϕ τ (s, a)da + λd 2 (π ϕ (•|s), π θ (•|s)) is strongly convex at θ = θ ′ τ , we have ∇ ⊤ ϕ θ ′ τ = -E s∼ν π ϕ τ - A ∇ 2 θ π θ (a|s)Q π ϕ τ (s, a)da + λ∇ 2 θ d 2 (π ϕ (•|s), π θ (•|s)) -1 -E s∼ν π ϕ τ A ∇ θ π θ (a|s)∇ ⊤ ϕ Q π ϕ τ (s, a)da + E s∼ν π ϕ τ λ∇ ⊤ ϕ ∇ θ d 2 (π ϕ (•|s), π θ (•|s)) + s∈S ∇ ϕ ν π ϕ τ (s)∇ θ - A π θ (a|s)Q π ϕ τ (s, a)da + λd 2 (π ϕ (•|s), π θ (•|s)) | θ=θ ′ τ ,This is equivalent to∇ ⊤ ϕ θ ′ τ = -E s∼ν π ϕ τ ,a∼π ϕ (•|s) - ∇ 2 θ π θ (a|s) π ϕ (a|s) Q π ϕ τ (s, a) + λ∇ 2 θ d 2 (π ϕ (•|s), π θ (•|s)) -1 E s∼ν π ϕ τ ,a∼π ϕ (•|s) - ∇ θ π θ (a|s) π ϕ (a|s) ∇ ⊤ ϕ Q π ϕ τ (s, a) + λ∇ ⊤ ϕ ∇ θ d 2 (π ϕ (•|s), π θ (•|s)) | θ=θ ′ τ .J.3 Proofs of hypergradient of the algorithm in Section G Deviation of (10) .As θ ′ τ = argmin θ -1 λ θ ⊤ E s∼ν π ϕ τ ,a∼π ϕ (•|s) [ ∇ ϕ π ϕ (a|s) π ϕ (a|s) A π ϕ τ (s, a)] + D 2 τ (π ϕ , π θ ), by the implicit differentiation theorem in bilevel optimization analysis,∇ ⊤ ϕ θ ′ τ = -∇ 2 θ - 1 λ θ ⊤ E s∼ν π ϕ τ ,a∼π ϕ (•|s) [ ∇ ϕ π ϕ (a|s) π ϕ (a|s) Q π ϕ τ (s, a)] + D 2 τ (π ϕ , π θ ) -1 ∇ ϕ ∇ θ - 1 λ θ ⊤ E s∼ν π ϕ τ ,a∼π ϕ (•|s) [ ∇ ϕ π ϕ (a|s) π ϕ (a|s) Q π ϕ τ (s, a)] + D 2 τ (π ϕ , π θ ) | θ=θ ′ τAlso, we haveEQUATION∇ ϕ ∇ θ ( 1 λ θ ⊤ E s∼ν π ϕ τ ,a∼π ϕ (•|s) [ ∇ ϕ π ϕ (a|s) π ϕ (a|s) Q π ϕ τ (s, a)]) = E s∼ν π ϕ τ a∼π ϕ (•|s) [ 1 λ ∇ ϕ π ϕ (a|s) π ϕ (a|s) ∇ ⊤ ϕ Q π ϕ τ (s, a) + 1 λ ∇ 2 ϕ π ϕ (a|s) π ϕ (a|s) Q π ϕ τ (s, a)].Then, we can get ∇ ⊤ ϕ θ ′ τ .EQUATIONwhereEQUATIONM (s) = λ∇ 2 π(•|s) d 2 1 (π ϕ , π, s) = λ      π ϕ (a1|s) π θ ′ τ (a1|s) 2 . . . π ϕ (an|s) π θ ′ τ (an|s) 2     .Then,EQUATIONandM (s) -1 1 1 ⊤ M (s) -1 1 ⊤ M (s) -1 1 = 1 λ a∈A π θ ′ τ (a|s) 2 π ϕ (a|s)      π θ ′ τ (a1|s) 2 π ϕ (a1|s) . . . π θ ′ τ (an|s) 2 π ϕ (an|s)      π θ ′ τ (a1|s) 2 π ϕ (a1|s) • • • π θ ′ τ (an|s) 2 π ϕ (an|s). Also,EQUATION. . .EQUATION. . .EQUATION)Then, plugging these equations into (20), we haveEQUATION. . .EQUATION. . .1 λ ∇ ⊤ ϕ Q π ϕ τ (s, a n ) + ∇ ⊤ ϕ π ϕ (an|s) π θ ′ τ (an|s)          , whereEQUATION)Then, we simplify the computation of∇ ⊤ ϕ J τ (π θ ′ τ ), we have ∇ ⊤ ϕ J τ (π θ ′ τ ) = 1 1 -γ E s∼ν π θ ′ τ τ a∈A (A π θ ′ τ τ (s, a) -c τ (s)) π θ ′ τ (a|s) 2 π ϕ (a|s) ( 1 λ ∇ ⊤ ϕ Q π ϕ τ (s, a) + ∇ ⊤ ϕ π ϕ (a|s) π θ ′ τ (a|s) ) = 1 1 -γ E s∼ν π θ ′ τ τ a∈A π θ ′ τ (a|s)(A π θ ′ τ τ (s, a) -c τ (s))( π θ ′ τ (a|s) λπ ϕ (a|s) ∇ ⊤ ϕ Q π ϕ τ (s, a) + ∇ ⊤ ϕ π ϕ (a|s) π ϕ (a|s) ) .When the tabular policy is the softmax policy, we have πϕ (a|s) = exp(ϕ(s,a))a ′ ∈A exp(ϕ(s,a ′ )) , thenEQUATIONHere, 1(s ′ , a ′ ) denote the column vector where the element is 1 if s = s ′ and a = a ′ , otherwise is 0, for each pair (s, a) ∈ S × A; πϕ (•|s ′ ) is the column vector, where the element is πϕ (a|s ′ ) if s = s ′ , 0 if s ̸ = s ′ , for each pair (s.a) ∈ S × A.So, we haveEQUATIONK.2 Convergence guarantee when D τ = D τ,1Lemma 5. Suppose that Assumption 2 holds. Let π θ ′ τ = Alg(π ϕ , λ, τ ) where D τ = D τ,1 , for any s ∈ S and a ∈ A, we have For any s ∈ S, the Lagrangian of the above maximization problem isλ λ + max s,a |A π ϕ τ (s, a)| ≤ π θ ′ τ (a|s) π ϕ (a|s) ≤ λ λ -max s,a |A- a∈A π(a|s)Q π ϕ τ (s, a) + λd 2 (π ϕ (•|s), π(•|s)) + µ(s)( a∈A π(a|s) -1),where µ is the Lagrangian multiplier. The optimality condition of π(•|s) is that,EQUATION)Then, -π θ ′ τ (a|s)A π ϕ τ (s, a) -λπ ϕ (a|s) + π θ ′ τ (a|s)µ 1 (s) = 0. We derive the summation of all a ∈ A,a∈A -π θ ′ τ (a|s)A π ϕ τ (s, a) -λ + µ 1 (s) = 0.We haveµ 1 (s) = a∈A π θ ′ τ (a|s)A π ϕ τ (s, a) + λ.From ( 26), we haveπ ϕ (a|s) π θ ′ τ (a|s) = µ 1 (s) -A π ϕ τ (s, a) λ = λ + a ′ ∈A π θ ′ τ (a ′ |s)A π ϕ τ (s, a ′ ) -A π ϕ τ (s, a) λ So, we have π θ ′ τ (a|s) π ϕ (a|s) = λ λ + a ′ ∈A π θ ′ τ (a ′ |s)A π ϕ τ (s, a ′ ) -A π ϕ τ (s, a),then λ λ + max s,a |A π ϕ τ (s, a)| ≤ π θ ′ τ (a|s) π ϕ (a|s) ≤ λ λ -max s,a |A π ϕ τ (s, a)| . Lemma 6. Suppose that Assumption 2 holds. Let π θ ′ τ = Alg(π ϕ , λ, τ ) where D τ = D τ,1 , we have ∥∇ ϕ J τ (π θ ′ τ )∥ ≤ max s,a |A π θ ′ τ τ (s, a)| 1 -γ ( max s,a |A π θ ′ τ τ (s, a)| λ -max s,a |A π ϕ τ (s, a)| γ 1 -γ + 2).Proof. As shown in (25) ,∇ ⊤ ϕ J τ (π θ ′ τ ) = 1 1 -γ E s∼ν πθ ′ τ τ a∈A πθ ′ τ (a|s)(A πθ ′ τ τ (s, a) -c τ (s)) ( πθ ′ τ (a|s) λπ ϕ (a|s) ∇ ⊤ ϕ Q πϕ τ (s, a) + 1 ⊤ (s, a) -πϕ (•|s) ⊤ ) = 1 1 -γ s∈S a∈A ν πθ ′ τ τ (s)π θ ′ τ (a|s)(A πθ ′ τ τ (s, a) -c τ (s)) ( πθ ′ τ (a|s) λπ ϕ (a|s) ∇ ⊤ ϕ Q πϕ τ (s, a) + 1 ⊤ (s, a) -πϕ (•|s) ⊤ ).Since s∈S ν πθ ′ τ τ (s) = 1 and a∈A πθ ′ τ (a|s) = 1 for all s ∈ S, we have∥∇ ϕ J τ (π θ ′ τ )∥ ≤ 1 1 -γ max a,s ∥(A πθ ′ τ τ (s, a) -c τ (s))( πθ ′ τ (a|s) λπ ϕ (a|s) ∇ ⊤ ϕ Q πϕ τ (s, a) + 1 ⊤ (s, a) -πϕ (•|s) ⊤ )∥.From ( 23), for any s ∈ S and a ∈ A, we have|A πθ ′ τ τ (s, a) -c τ (s)| ≤ max s,a |A πθ ′ τ τ (s, a)|.Also, for any s ∈ S and a ∈ A,∥1(s, a) -πϕ (•|s))∥ ≤ 1 + ∥π(•|s)∥ ≤ 2. From Lemma 5, πθ ′ τ (a|s) λπ ϕ (a|s) ≤ 1 λ -max s,a |A πϕ τ (s, a)| . From the computation of ∇ ϕ Q πϕ τ (s, a) shown in (5) of Appendix C, |∇ ϕ(s ′ ,a ′ ) Q πϕ τ (s, a)| = | γ 1 -γ • σ (s,a) τ,π ϕ (s ′ )π ϕ (a ′ |s ′ )A πϕ τ (s, a) | ≤ γ 1 -γ σ (s,a) τ,π ϕ (s ′ )π ϕ (a ′ |s ′ )| max a,s A πϕ τ (s, a) |.Also, since a∈A,s∈S σ (s,a)EQUATIONTherefore, we have∥∇ ϕ J τ (π θ ′ τ )∥ ≤ max s,a |A πθ ′ τ τ (s, a)| 1 -γ ( max s,a |A πθ ′ τ τ (s, a)| λ -max s,a |A πϕ τ (s, a)| γ 1 -γ + 2).Lemma 7. Suppose that Assumption 2 holds. Let πθ ′ τ = Alg(π ϕ , λ, τ ) where D τ = D τ,1 , for any s ∈ S we havea∈A ∥∇ ϕ πθ ′ τ (a|s)∥ ≤ 1 λ -max s,a |A πϕ τ (s, a)| ( γ max a,s |A πϕ τ (s, a) | 1 -γ + 2(λ + max a,s |A πϕ τ (s, a) |))anda∈A ∥∇ 2 ϕ πθ ′ τ (a|s)∥ ≤ 1 λ -max s,a |A πϕ τ (s, a)| ( 8r max (1 -γ) 3 + λ + max s,a |A πϕ τ (s, a)| λ -max s,a |A πϕ τ (s, a)| ( (2 -γ) max a,s |A πϕ τ (s, a) | 1 -γ + 2λ + 2)).Proof. From ( 19), for any s ∈ S, 21) (27) , we haveEQUATION∇ ϕ Q πϕ τ (s, •) in (EQUATION∥∇ ϕ Q πϕ τ (s, a)∥ ≤ max a ∥∇ ϕ Q πϕ τ (s, a)∥ ≤ γ 1 -γ max a,s |A πϕ τ (s, a) |.From (22)( 24)∥λ∇ ⊤ ϕ ∇ π(a|s) d 2 1 (π ϕ , π, s)∥ = ∥λ(1(s, a) -πϕ (•|s)) πϕ (a|s) πθ ′ τ (a|s) ∥ ≤ 2(λ + max a,s |A πϕ τ (s, a) |).The last inequality comes from Lemma 5. So, we have∥∇ ϕ πθ ′ τ (a|s)∥ ≤ πθ ′ τ (a|s) λ -max s,a |A πϕ τ (s, a)| ( γ max a,s |A πϕ τ (s, a) | 1 -γ + 2(λ + max a,s |A πϕ τ (s, a) |)).Therefore,a∈A ∥∇ ϕ πθ ′ τ (a|s)∥ ≤ 1 λ -max s,a |A πϕ τ (s, a)| ( γ max a,s |A πϕ τ (s, a) | 1 -γ + 2(λ + max a,s |A πϕ τ (s, a) |)).Also, we have∥∇ 2 ϕ πθ ′ τ (a|s)∥ ≤ πθ ′ τ (a|s) λ -max s,a |A πϕ τ (s, a)| (∥∇ 2 ϕ Q πϕ τ (s, a)∥ + λ∥∇ 2 ϕ ∇ π(a|s) d 2 1 (π ϕ , π, s)∥).From Lemma D.4 in [2] , we have∥∇ 2 ϕ Q πϕ τ (s, a)∥ ≤ 8r max (1 -γ) 3 .Moreover, we haveλ∥∇ 2 ϕ ∇ π(a|s) d 2 1 (π ϕ , π, s)∥ = λ∥∇ ϕ ((1(s, a) -πϕ (•|s)) πϕ (a|s) πθ ′ τ (a|s) )∥ ≤ λ + max s,a |A πϕ τ (s, a)| λ -max s,a |A πϕ τ (s, a)| ( γ max a,s |A πϕ τ (s, a) | 1 -γ + 2(λ + max a,s |A πϕ τ (s, a) |) + 2) = λ + max s,a |A πϕ τ (s, a)| λ -max s,a |A πϕ τ (s, a)| ( (2 -γ) max a,s |A πϕ τ (s, a) | 1 -γ + 2λ + 2) So, a∈A ∥∇ 2 ϕ πθ ′ τ (a|s)∥ ≤ 1 λ -max s,a |A πϕ τ (s, a)| ( 8r max (1 -γ) 3 + λ + max s,a |A πϕ τ (s, a)| λ -max s,a |A πϕ τ (s, a)| ( (2 -γ) max a,s |A πϕ τ (s, a) | 1 -γ + 2λ + 2)).Lemma 8. Suppose that Assumptions 1 and 2 hold. Let πθ ′ τ = Alg(π ϕ , λ, τ ) where D τ = D τ,1 , we haveEQUATIONwhereC = 1 λ-Amax ( γAmax 1-γ + 2λ + 2A max ) and B = 1 λ-Amax ( 8rmax (1-γ) 3 + λ+Amax λ-Amax ( (2-γ)Amax 1-γ + 2λ + 2)).Proof. From Lemma 7, we have bounded a∈A ∥∇ ϕ πθ ′ τ (a|s)∥ and a∈A ∥∇ 2 ϕ πθ ′ τ (a|s)∥. Borrow the result from Lemma D.2 in [2] .Theorem 5. Consider the tabular softmax policy for the discrete state-action space shown in Section 5.1, and the within-task algorithm Alg in (1) . Suppose that Assumptions 1 and 2 hold. Let {ϕ t } T t=1 be the sequence generated by Algorithm 1 with D τ = D τ,1 , λ > A max , and the step size selected asα = min r max B (1 -γ) 2 + 2γr max C 2 (1 -γ) 3 -1 , 1 G √ T .Then,1 T T t=1 E t ∥∇ ϕ E τ ∼P(Γ) [J τ (Alg(π ϕt , λ, τ ))]∥ 2 ≤ 2r 2 max B (1 -γ) 3 + 4γr 2 max C 2 (1 -γ) 4 1 T + 2r max 1 -γ + r max B (1 -γ) 2 + 2γr max C 2 (1 -γ) 3 G √ T ,whereEQUATIONB = 1 λ -A max ( 8r max (1 -γ) 3 + λ + A max λ -A max ( (2 -γ)A max 1 -γ + 2λ + 2)).Proof. As the smoothness constant of J τ (π θ ′ τ ), i.e., J τ (Alg(π ϕ , λ, τ ) is obtained in (8) , the smoothness constant of E τ ∼P(Γ) [J τ (Alg(π ϕ , λ, τ ))] is the same, i.e.,∥∇ 2 ϕ E τ ∼P(Γ) [J τ (Alg(π ϕ , λ, τ ))]∥ ≤ Br max (1 -γ) 2 + 2γr max C 2 (1 -γ) 3 .Moreover, from Lemma 6, we have∥∇ ϕ J τ (Alg(π ϕ , λ, τ ))∥ ≤ A max 1 -γ ( A max λ -A max γ 1 -γ + 2).From the convergence theorem of SDG with smoothness and bounded gradient shown in [19] , let the step sizeα = min r max B (1 -γ) 2 + 2γr max C 2 (1 -γ) 3 -1 , 1 G √ T ,we have1 T T t=1 E t ∥∇ ϕ E τ ∼P(Γ) [J τ (Alg(π ϕt , λ, τ ))]∥ 2 ≤ 2r max B (1 -γ) 2 + 4γr max C 2 (1 -γ) 3 E τ ∼P(Γ) [J τ (Alg(π ϕ T , λ, τ )) -J τ (Alg(π ϕ0 , λ, τ ))] 1 T + 2E τ ∼P(Γ) [J τ (Alg(π ϕ T , λ, τ )) -J τ (Alg(π ϕ0 , λ, τ ))] + r max B (1 -γ) 2 + 2γr max C 2 (1 -γ) 3 Since E τ ∼P(Γ) [J τ (Alg(π ϕ T , λ, τ )) -J τ (Alg(π ϕ0 , λ, τ ))] ≤ rmax 1-γ , we have 1 T T t=1 E t ∥∇ ϕ E τ ∼P(Γ) [J τ (Alg(π ϕt , λ, τ ))]∥ 2 ≤ 2r 2 max B (1 -γ) 3 + 4γr 2 max C 2 (1 -γ) 4 1 T + 2r max 1 -γ + r max B (1 -γ) 2 + 2γr max C 2 (1 -γ) 3 G √ T ,whereEQUATIONB = 1 λ -A max ( 8r max (1 -γ) 3 + λ + A max λ -A max ( (2 -γ)A max 1 -γ + 2λ + 2)).Corollary 1. Suppose all assumptions and conditions in Theorem 5 hold, and we set λ ≥ 2A max , then1 T T t=1 E t ∥∇ ϕ E τ ∼P(Γ) [J τ (Alg(π ϕt , λ, τ ))]∥ 2 ≤ (B + 2C 2 )r max (1 -γ) 4 ( 2r max T + G √ T ),whereB ≜ 16rmax λ(1-γ) 3 + 24 1-γ + 12 λ , C ≜ 6 1-γ , and G ≜ 4Amax (1-γ) 2 .Proof. Since λ ≥ 2A max , we have1 λ-Amax ≤ 1 Amax and 1 λ-Amax ≤ 2 λ .Then, simplify the inequality in Theorem 5.EQUATIONwhereEQUATIONwhereM (s) = λ∇ 2 π(•|s) d 2 2 (π ϕ , π, s) = λ     1 πθ ′ τ (a1|s). . .1 πθ ′ τ (an|s)     .Then,EQUATIONAlso,EQUATION. . .EQUATIONSpecially,A πθ ′ τ τ (s, •) ⊤ M (s) -1 1 1 ⊤ M (s) -1 1 ⊤ M -1 1= 0, because we haveA πθ ′ τ τ (s, •) ⊤ M (s) -1 1 = a∈A πθ ′ τ (a|s)A πθ ′ τ τ (s, a) = 0.Then,EQUATIONHere, 1(s ′ , a ′ ) denote the column vector where the element is 1 if s = s ′ and a = a ′ , otherwise is 0, for each pair (s, a) ∈ S × A. ∥∇ ϕ J τ (π θ ′ τ )∥ ≤ max s,a |A πθ ′ τ τ (s, a)| 1 -γ ( max s,a |A πθ ′ τ τ (s, a)| λ γ 1 -γ + 1).Proof. As shown in ( 33)∇ ⊤ ϕ J τ (π θ ′ τ ) = 1 1 -γ E s∼ν πθ ′ τ τ ,a∼π θ ′ τ A πθ ′ τ τ (s, a)( 1 λ ∇ ⊤ ϕ Q πϕ τ (s, a) + 1 ⊤ (s, a)) .As shown in proof of Lemma 6 in (27) ,∥∇ ϕ Q πϕ τ (s, a)∥ ≤ γ 1 -γ max a,s |A πϕ τ (s, a) |,we have that∥∇ J τ (π θ ′ τ )∥ ≤ max s,a |A πθ ′ τ τ (s, a)| 1 -γ ( max s,a |A πθ ′ τ τ (s, a)| λ γ 1 -γ + 1).Lemma 10. Suppose that Assumption 2 holds. Let πθ ′ τ = Alg(π ϕ , λ, τ ) where D τ = D τ,2 , for any s ∈ S, we havea∈A ∥∇ ϕ πθ ′ τ (a|s)∥ ≤ 2γ λ(1 -γ) max a,s |A πϕ τ (s, a) | + 4 and a∈A ∥∇ 2 ϕ πθ ′ τ (a|s)∥ ≤ ( 2γ λ(1 -γ) max a,s |A πϕ τ (s, a) | + 4) 2 + 16r max λ(1 -γ) 3 + 2.Proof. As shown in 30, we have∇ ⊤ ϕ πθ ′ τ (•|s) = M (s) -1 - M (s) -1 1 1 ⊤ M (s) -1 1 ⊤ M (s) -1 1 ∇ ⊤ ϕ Q πϕ τ (s, •) -λ∇ ⊤ ϕ ∇ π(•|s) d 2 2 (π ϕ , π, s) | π=π θ ′ τ ,where the computations of M (s) -1 and ∇ ⊤ ϕ ∇ π(•|s) d 2 2 (π ϕ , π, s) are shown in (31) (32) and ( 24), then∇ ϕ πθ ′ τ (a|s) = πθ ′ τ (a|s)( 1 λ ∇ ϕ Q πϕ τ (s, a) + 1(s, a) -πϕ (•|s)) -πθ ′ τ (a|s) a ′ ∈A πθ ′ τ (a ′ |s)( 1 λ ∇ ϕ Q πϕ τ (s, a ′ ) + 1(s, a ′ ) -πϕ (•|s)).Therefore,∥∇ ϕ πθ ′ τ (a|s)∥ ≤ πθ ′ τ (a|s)( 1 λ ∇ ϕ Q πϕ τ (s, a) + 1(s, a) -πϕ (•|s)) + πθ ′ τ (a|s) a ′ ∈A πθ ′ τ (a ′ |s)( 1 λ ∇ ϕ Q πϕ τ (s, a ′ ) + 1(s, a ′ ) -πϕ (•|s)) .Then,a∈A ∥∇ ϕ πθ ′ τ (a|s)∥ ≤ a∈A πθ ′ τ (a|s)( 1 λ ∇ ϕ Q πϕ τ (s, a) + 1(s, a) -πϕ (•|s)) + a∈A πθ ′ τ (a|s) a ′ ∈A πθ ′ τ (a ′ |s)( 1 λ ∇ ϕ Q πϕ τ (s, a ′ ) + 1(s, a ′ ) -πϕ (•|s)) .From ( 27), we have∥∇ ϕ Q πϕ τ (s, a)∥ ≤ γ 1 -γ max a,s |A πϕ τ (s, a) |.Then,EQUATIONMoreover, since∇ ϕ πθ ′ τ (a|s) = πθ ′ τ (a|s)( 1 λ ∇ ϕ Q πϕ τ (s, a) + 1(s, a) -πϕ (•|s)) -πθ ′ τ (a|s) a ′ ∈A πθ ′ τ (a ′ |s)( 1 λ ∇ ϕ Q πϕ τ (s, a ′ ) + 1(s, a ′ ) -πϕ (•|s)).we have∇ 2 ϕ πθ ′ τ (a|s) =∇ ϕ πθ ′ τ (a|s)( 1 λ ∇ ϕ Q πϕ τ (s, a) + 1(s, a) -πϕ (•|s)) + πθ ′ τ (a|s)( 1 λ ∇ 2 ϕ Q πϕ τ (s, a) + -∇ ϕ πϕ (•|s)) -∇ ϕ πθ ′ τ (a|s) a ′ ∈A πθ ′ τ (a ′ |s)( 1 λ ∇ ϕ Q πϕ τ (s, a ′ ) + 1(s, a ′ ) -πϕ (•|s)) .Then,∥∇ 2 ϕ πθ ′ τ (a|s)∥ ≤2∥∇ ϕ πθ ′ τ (a|s)∥∥ 1 λ ∇ ϕ Q πϕ τ (s, a) + 1(s, a) -πϕ (•|s)∥ + 2π θ ′ τ (a|s)∥ 1 λ ∇ 2 ϕ Q πϕ τ (s, a) -∇ ϕ πϕ (•|s)∥. From (34), ∥∇ ϕ πθ ′ τ (a|s)∥ ≤ πθ ′ τ (a|s)( 2γ λ(1 -γ) max a,s |A πϕ τ (s, a) | + 4).From ( 27)∥ 1 λ ∇ ϕ Q πϕ τ (s, a) + 1(s, a) -πϕ (•|s)∥ ≤ γ λ(1 -γ) max a,s |A πϕ τ (s, a) | + 2From Lemma D.4 in [2] , we have∥∇ 2 ϕ Q πϕ τ (s, a)∥ ≤ 8r max (1 -γ) 3 , then ∥ 1 λ ∇ 2 ϕ Q πϕ τ (s, a) -∇ ϕ πϕ (•|s)∥ ≤ 8r max λ(1 -γ) 3 + 1. Therefore, ∥∇ 2 ϕ πθ ′ τ (a|s)∥ ≤ πθ ′ τ (a|s)( 2γ λ(1 -γ) max a,s |A πϕ τ (s, a) | + 4) 2 + 2π θ ′ τ (a|s)( 8r max λ(1 -γ) 3 + 1). So, a∈A ∥∇ 2 ϕ πθ ′ τ (a|s)∥ ≤ ( 2γ λ(1 -γ) max a,s |A πϕ τ (s, a) | + 4) 2 + 16r max λ(1 -γ) 3 + 2.Lemma 11. Suppose that Assumptions 1 and 2 hold. Let πθ ′ τ = Alg(π ϕ , λ, τ ) where D τ = D τ,2 , we haveEQUATIONwhereC = 2γ λ(1-γ) A max + 4 and B = ( 2γ λ(1-γ) A max + 4) 2 + 16rmax λ(1-γ) 3 + 2.Proof. Similar to the proof of Lemma 8 by using Lemma 10.Theorem 6. Consider the tabular softmax policy for the discrete state-action space shown in Section 5.1, and the within-task algorithm Alg in (1) . Suppose that Assumptions 1 and 2 hold. Let {ϕ t } T t=1 be the sequence generated by Algorithm 1 with D τ = D τ,2 and the step size selected asα = min r max B (1 -γ) 2 + 2γr max C 2 (1 -γ) 3 -1 , 1 G √ T .Then,1 T T t=1 E t ∥∇ ϕ E τ ∼P(Γ) [J τ (Alg(π ϕt , λ, τ ))]∥ 2 ≤ 2r 2 max B (1 -γ) 3 + 4γr 2 max C 2 (1 -γ) 4 1 T + 2r max 1 -γ + r max B (1 -γ) 2 + 2γr max C 2 (1 -γ) 3 G √ T ,whereEQUATIONB = ( 2γA max λ(1 -γ) + 4) 2 + 16r max λ(1 -γ) 3 + 2.Proof. Similar to the proof of Theorem 5, by using the gradient bound in Lemma 9 and the smoothness in Lemma 11.Corollary 2. Suppose all assumptions and conditions in Theorem 6 hold, and we set λ ≥ 2A max , then1 T T t=1 E t ∥∇ ϕ E τ ∼P(Γ) [J τ (Alg(π ϕt , λ, τ ))]∥ 2 ≤ (B + 2C 2 )r max (1 -γ) 4 ( 2r max T + G √ T ),whereB ≜ 16rmax λ(1-γ) 3 + 18 (1-γ) 2 , C ≜ 4 1-γ , and G ≜ 2Amax (1-γ) 2 ).Proof. Since λ ≥ 2A max , we have 1 λ ≤ 1 2Amax . Then, simplify the inequality in Theorem 5.M Proofs of convergence when D τ = D τ,3Lemma 12. Suppose that Assumptions 1, 2, and 3 hold. Let πθ ′ τ = Alg(π ϕ , λ, τ ) where D τ = D τ,3 . If λ > (6L 2 1 + 2L 2 )A max , then ∇ ϕ J τ (Alg (3) (π ϕ , λ, τ )) exists for any ϕ, and∥∇ ϕ J τ (π θ ′ τ )∥ ≤ L 1 A max (λ + 2γ 1-γ L 2 1 A max ) (1 -γ)(λ -(6L 2 1 + 2L 2 )A max ).Proof. From Proposition 2, we have∇ ϕ J τ (π θ ′ τ ) = 1 1 -γ ∇ ϕ θ ′ τ • E s∼ν πθ ′ τ τ a∼π θ ′ τ (•|s) ∇ θ ′ τ πθ ′ τ (a|s) πθ ′ τ (a|s) A πθ ′ τ τ (s, a) ,where∇ ⊤ ϕ θ ′ τ = -E s∼ν πϕ τ a∼π ϕ (•|s) - ∇ 2 θ πθ (a|s) πϕ (a|s) Q πϕ τ (s, a) + λ∇ 2 θ d 2 (π ϕ (•|s), πθ (•|s)) -1 E s∼ν πϕ τ a∼π ϕ (•|s) - ∇ θ πθ (a|s) πϕ (a|s) ∇ ⊤ ϕ Q πϕ τ (s, a) + λ∇ ⊤ ϕ ∇ θ d 2 (π ϕ (•|s), πθ (•|s)) | θ=θ ′ τ .When D τ = D τ,3 , and the policy with function approximation is defined by πθ (a|s) ≜ exp(f θ (s,a))A exp(f θ (s,a ′ ))da ′ , ∀(s, a) ∈ S × A, from Lemma 4, ∇ ϕ J τ (π θ ′ τ ) = 1 1 -γ ∇ ϕ θ ′ τ • E s∼ν πθ ′ τ τ a∼π θ ′ τ (•|s) ∇ θ ′ τ f πθ ′ τ (s, a)A πθ ′ τ τ (s, a) ,where∇ ⊤ ϕ θ ′ τ = E s∼ν πϕ τ a∼π ϕ (•|s) - ∇ 2 θ ′ τ πθ ′ τ (a|s) πϕ (a|s) Q πϕ τ (s, a) + λI -1 E s∼ν πϕ τ a∼π ϕ (•|s) ∇ θ ′ τ πθ ′ τ (a|s) πϕ (a|s) ∇ ⊤ ϕ Q πϕ τ (s, a) + λI = E s∼ν πϕ τ - A ∇ 2 θ ′ τ πθ ′ τ (a|s)Q πϕ τ (s, a)da + λI -1 E s∼ν πϕ τ A ∇ θ ′ τ πθ ′ τ (a|s)∇ ⊤ ϕ Q πϕ τ (s, a)da + λI = E s∼ν πϕ τ - A ∇ 2 θ ′ τ πθ ′ τ (a|s)A πϕ τ (s, a)da + λI -1 E s∼ν πϕ τ A ∇ θ ′ τ πθ ′ τ (a|s)∇ ⊤ ϕ Q πϕ τ (s, a)da + λIFirst, we have∥∇ ϕ J τ (π θ ′ τ )∥ = 1 1 -γ ∥∇ ϕ θ ′ τ ∥∥ E s∼ν πθ ′ τ τ a∼π θ ′ τ (•|s) ∇ θ f θ (s, a)A πθ ′ τ τ (s, a) ∥,and∥ E s∼ν πθ ′ τ τ a∼π θ ′ τ (•|s) ∇ θ f θ (s, a)A πθ ′ τ τ (s, a) ∥ ≤ ∥ max a,s ∇ θ f θ (s, a)∥ max a,s |A πθ ′ τ τ (s, a)| ≤ L 1 A max .For the term ∇ ϕ θ ′ τ , consider ∇ θ ′ τ πθ ′ τ (a|s) and ∇ 2 θ ′ τ πθ ′ τ (a|s), we haveEQUATION)Then,∥∇ θ πθ (a|s)∥ ≤ πθ (a|s)∥∇ θ f θ (s, a)∥ + πθ (a|s) A ∇ θ f θ (s, a ′ ) exp (f θ (s, a ′ ))da ′ A exp (f θ (s, a ′ ))da ′ ≤ 2π θ (a|s)L 1 (37)We also have ∇ 2 θ πθ (a|s) =∇ θ πθ (a|s)∇ ⊤ θ f θ (s, a) + πθ (a|s)∇ 2 θ f θ (s, a) -∇π θ (a|s) A ∇ ⊤ θ f θ (s, a ′ ) exp (f θ (s, a ′ ))da ′ A exp (f θ (s, a ′ ))da ′ -πθ (a|s) A ∇ 2 θ f θ (s, a ′ ) exp (f θ (s, a ′ ))da ′ + ∇ θ f θ (s, a ′ )∇ ⊤ θ f θ (s, a ′ ) exp (f θ (s, a ′ ))da ′ A exp (f θ (s, a ′ ))da ′ + πθ (a|s) A ∇ θ f θ (s, a ′ ) exp (f θ (s, a ′ ))da ′ A ∇ ⊤ θ f θ (s, a ′ ) exp (f θ (s, a ′ ))da ′ ( A exp (f θ (s, a ′ ))da ′ ) 2 .Then,EQUATIONSo,E s∼ν πϕ τ A ∇ 2 θ ′ τ πθ ′ τ (a|s)A πϕ τ (s, a)da ≤ (6L 2 1 + 2L 2 )A max . Since E s∼ν πϕ τ A ∇ 2 θ ′τ πθ ′ τ (a|s)A πϕ τ (s, a)da is a diagonal matrix, the above shown its largest absolute eigenvalue is smaller than (6L 2 1 + 2L 2 )A max . Then, the smallest eigenvalue of EEQUATIONMoreover, if λ > (6L 2 1 +2L 2 )A max , the objective function in the optimization problem Alg(π ϕ , λ, τ ) is strongly concave. Then, from [64] , the solution is unique and ∇ ϕ J τ (Alg (3) (π ϕ , λ, τ )) exists.From (6) ,∇ ϕ Q πϕ τ (s, a) = γ 1 -γ • E (s ′ ,a ′ )∼σ (s,a) τ,π ϕ ∇ ϕ f ϕ (s ′ , a ′ ) A πϕ τ (s ′ , a ′ ) .Then,∥∇ ϕ Q πϕ τ (s, a)∥ ≤ γ 1 -γ L 1 A max .Combine (37), we haveE s∼ν πϕ τ A ∇ θ ′ τ πθ ′ τ (a|s)∇ ⊤ ϕ Q πϕ τ (s, a)da + λI ≤ λ + 2γ 1 -γ L 2 1 A max .So we haveEQUATIONTherefore, we have∥∇ ϕ J τ (π θ ′ τ )∥ ≤ L 1 A max (λ + 2γ 1-γ L 2 1 A max ) (1 -γ)(λ -(6L 2 1 + 2L 2 )A max ).Lemma 13. For a softmax policy parameterized by ϕ,EQUATION)Proof. From 37, A ∥∇ ϕ πϕ (a|s)∥da ≤ 2L 1 .A ∥∇ ϕ πϕ (a|s)∥da ≤ 6L 2 1 + 2L 2 .Borrow the result from Lemma D.2 in [2] ,∥∇ 2 ϕ J τ (π ϕ )∥ ≤ (6L 2 1 + 2L 2 )r max (1 -γ) 2 + 8γL 2 1 r max (1 -γ) 3 ∥∇ 2 ϕ Q πϕ τ (s, a)∥ ≤ 8γ 2 L 2 1 r max (1 -γ) 3 + γ(6L 2 1 + 2L 2 )r max (1 -γ) 2 .Lemma 14. Suppose that Assumption 2 holds. Let πθ ′ τ = Alg(π ϕ , λ, τ ) where D τ = D τ,3 , for any s ∈ S, we haveA ∥∇ ϕ πθ ′ τ (a|s)∥da ≤ 2L 1 (λ + 2γ 1-γ L 2 1 A max ) (1 -γ)(λ -(6L 2 1 + 2L 2 )A max ) and A ∥∇ 2 ϕ πθ ′ τ (a|s)∥da ≤ (160L 3 1 + 56L 1 L 2 + 4L 3 )(λ + 2γ 1-γ L 2 1 A max ) 2 (1 -γ) 3 (λ -(6L 2 1 + 2L 2 )A max ) 2 .Proof. First consider ∇ ϕ πθ ′ τ (a|s), we haveEQUATIONEQUATIONThen,A ∥∇ ϕ πθ ′ τ (a|s)∥da ≤ 2L 1 (λ + 2γ 1-γ L 2 1 A max ) (1 -γ)(λ -(6L 2 1 + 2L 2 )A max ).Next, we consider ∇ 2 ϕ πθ ′ τ (a|s). From (42), we have∇ 2 ϕ πθ ′ τ (a|s) = ∇ ϕ θ ′ τ ∇ θ ′ τ f θ ′ τ (s, a)∇ ⊤ ϕ πθ ′ τ (a|s) + πθ ′ τ (a|s)∇ 2 ϕ θ ′ τ ∇ θ ′ τ f θ ′ τ (s, a) + πθ ′ τ (a|s)∇ ϕ θ ′ τ ∇ 2 θ ′ τ f θ ′ τ (s, a)∇ ⊤ ϕ θ ′ τ -∇ ϕ θ ′ τ A ∇ θ ′ τ f θ ′ τ (s, a ′ ) exp (f θ ′ τ (s, a ′ ))da ′ A exp (f θ ′ τ (s, a ′ ))da ′ ∇ ⊤ ϕ πθ ′ τ (a|s) -πθ ′ τ (a|s)∇ 2 ϕ θ ′ τ A ∇ θ ′ τ f θ ′ τ (s, a ′ ) exp (f θ ′ τ (s, a ′ ))da ′ A exp (f θ ′ τ (s, a ′ ))da ′ -πθ ′ τ (a|s)∇ ϕ θ ′ τ A (∇ 2 θ ′ τ f θ ′ τ (s, a ′ ) exp (f θ ′ τ (s, a ′ )) + ∇ θ ′ τ f θ ′ τ (s, a ′ )∇ ⊤ θ ′ τ f θ ′ τ (s, a ′ ) exp (f θ ′ τ (s, a ′ )))da ′ A exp (f θ ′ τ (s, a ′ ))da ′ ∇ ⊤ ϕ θ ′ τ + πθ ′ τ (a|s)∇ ϕ θ ′ τ A ∇ θ ′ τ f θ ′ τ (s, a ′ ) exp (f θ ′ τ (s, a ′ ))da ′ A exp (f θ ′ τ (s, a ′ ))da ′ 2 ∇ ⊤ ϕ θ ′ τ .Therefore,∥∇ 2 ϕ πθ ′ τ (a|s)∥ ≤ ∥∇ ϕ θ ′ τ ∥∥∇ θ ′ τ f θ ′ τ (s, a)∥∥∇ ϕ πθ ′ τ (a|s)∥ + πθ ′ τ (a|s)∥∇ 2 ϕ θ ′ τ ∥∥∇ θ ′ τ f θ ′ τ (s, a)∥ + πθ ′ τ (a|s)∥∇ ϕ θ ′ τ ∥ 2 ∥∇ 2 θ ′ τ f θ ′ τ (s, a)∥ + ∥∇ ϕ θ ′ τ ∥∥∇ θ ′ τ f θ ′ τ (s, a)∥∥∇ ϕ πθ ′ τ (a|s)∥ + πθ ′ τ (a|s)∥∇ 2 ϕ θ ′ τ ∥∥∇ θ ′ τ f θ ′ τ (s, a)∥ + πθ ′ τ (a|s)∥∇ ϕ θ ′ τ ∥ 2 (∥∇ 2 θ ′ τ f θ ′ τ (s, a)∥ + ∥∇ θ ′ τ f θ ′ τ (s, a)∥ 2 ) + πθ ′ τ (a|s)∥∇ ϕ θ ′ τ ∥ 2 ∥∇ θ ′ τ f θ ′ τ (s, a)∥ 2 ≤ 2L 1 ∥∇ ϕ θ ′ τ ∥∥∇ ϕ πθ ′ τ (a|s)∥ + 2π θ ′ τ (a|s)L 1 ∥∇ 2 ϕ θ ′ τ ∥ + 2π θ ′ τ (a|s)∥∇ ϕ θ ′ τ ∥ 2 (L 2 + L 2 1). From ( 40) and ( 43)∥∇ 2 ϕ πθ ′ τ (a|s)∥ ≤ πθ ′ τ (a|s) 2L 2 + 6L 2 1 (λ + 2γ 1-γ L 2 1 A max ) 2 (1 -γ) 2 (λ -(6L 2 1 + 2L 2 )A max ) 2 + 2L 1 ∥∇ 2 ϕ θ ′ τ ∥ . Then, A ∥∇ 2 ϕ πθ ′ τ (a|s)∥da ≤ 2L 2 + 6L 2 1 (λ + 2γ 1-γ L 2 1 A max ) 2 (1 -γ) 2 (λ -(6L 2 1 + 2L 2 )A max ) 2 + 2L 1 ∥∇ 2 ϕ θ ′ τ ∥.Next, we consider ∇ 2 ϕ θ ′ τ . We have∇ 2 ϕ θ ′ τ = E s∼ν πϕ τ - A ∇ 2 θ ′ τ πθ ′ τ (a|s)Q πϕ τ (s, a)da + λI -1 E s∼ν πϕ τ A ∇ 2 θ ′ τ πθ ′ τ (a|s)∇ ⊤ ϕ θ ′ τ ∇ ⊤ ϕ Q πϕ τ (s, a) + ∇ θ ′ τ πθ ′ τ (a|s)∇ 2 ϕ Q πϕ τ (s, a) da - M E s∼ν πϕ τ - A ∇ 3 θ ′ τ πθ ′ τ (a|s)∇ ϕ θ ′ τ A πϕ τ (s, a) + ∇ 2 θ ′ τ πθ ′ τ (a|s)∇ ⊤ ϕ Q πϕ τ (s, a) da M -1 N where M = E s∼ν πϕ τ -A ∇ 2 θ ′ τ πθ ′ τ (a|s)A πϕ τ (s, a)da + λI and N = E s∼ν πϕ τ A ∇ θ ′ τ πθ ′ τ (a|s)∇ ⊤ ϕ Q πϕ τ (s, a)da + λI . Also, we have M -1 N = ∇ ϕ θ ′ τ .Similar to (37) (38) , we can derive the upper bound of ∥∇ 3 ϕ πϕ ∥, then∥∇ 3 θ ′ τ πθ ′ τ (a|s)∥ ≤ πθ ′ τ (a|s)(40L 3 1 + 16L 1 L 2 + 2L 3 ).So, from (38)(39)(40)(41), we have∥∇ 2 ϕ θ ′ τ ∥ ≤ 2γL 2 1 A max (6L 2 1 + 2L 2 )(λ + 2γ 1-γ L 2 1 A max ) (1 -γ) 2 (λ -(6L 2 1 + 2L 2 )A max ) 2 + 8γ 2 L 2 1 r max (1 -γ) 3 + γ(6L 2 1 + 2L 2 )r max (1 -γ) 2 1 λ -(6L 2 1 + 2L 2 )A max + λ + 2γ 1-γ L 2 1 A max (1 -γ)(λ -(6L 2 1 + 2L 2 )A max ) 2 ( (40L 3 1 + 16L 1 L 2 + 2L 3 )(λ + 2γ 1-γ L 2 1 A max )A max (1 -γ)(λ -(6L 2 1 + 2L 2 )A max ) + 2γ 1 -γ L 1 (6L 2 1 + 2L 2 )A max ).Simplify the inequality by γ < 1 and 1 -γ < 0,∥∇ 2 ϕ θ ′ τ ∥ ≤ (80L 3 1 + 28L 1 L 2 + 2L 3 )(λ + 2γ 1-γ L 2 1 A max ) 2 (1 -γ) 3 (λ -(6L 2 1 + 2L 2 )A max ) 2 Then, A ∥∇ 2 ϕ πθ ′ τ (a|s)∥da ≤ (160L 3 1 + 56L 1 L 2 + 4L 3 )(λ + 2γ 1-γ L 2 1 A max ) 2 (1 -γ) 3 (λ -(6L 2 1 + 2L 2 )A max ) 2 .Lemma 15. Suppose that Assumptions 1, 2, and 3 hold. Let πθ ′ τ = Alg(π ϕ , λ, τ ) where D τ = D τ,3 , we haveEQUATIONwhereC = 2L1(λ+ 2γ 1-γ L 2 1 Amax) (1-γ)(λ-(6L 2 1 +2L2)Amax) and B = (160L 3 1 +56L1L2+4L3)(λ+ 2γ 1-γ L 2 1 Amax) 2 (1-γ) 3 (λ-(6L 2 1 +2L2)Amax) 2 .Proof. Similar to the proofs of Lemma 8 and Lemma 11 by using Lemma 14.Theorem 7. In both discrete and continuous action space, consider the softmax policy with function approximation shown in Section 5.1, and the within-task algorithm Alg is defined in (2) with D τ = D τ,3 . Suppose that Assumptions 1, 2, and 3 hold. If λ > (6L 2 1 + 2L 2 )A max , then ∇ ϕ J τ (Alg (3) (π ϕ , λ, τ )) exists for any ϕ.Let {ϕ t } T t=1 be the sequence generated by Algorithm 1 with λ > (6L 2 1 + 2L 2 )A max and the step sizeα = min r max B (1 -γ) 2 + 2γr max C 2 (1 -γ) 3 -1 , 1 G √ T .Then, the following bound holds:1 T T t=1 E t ∥∇ ϕ E τ ∼P(Γ) [J τ (Alg(π ϕt , λ, τ ))]∥ 2 ≤ 2r 2 max B (1 -γ) 3 + 4γr 2 max C 2 (1 -γ) 4 1 T + 2r max 1 -γ + r max B (1 -γ) 2 + 2γr max C 2 (1 -γ) 3 G √ T ,whereEQUATIONB = (160L 3 1 + 56L 1 L 2 + 4L 3 )(λ + 2γ 1-γ L 2 1 A max ) 2 (1 -γ) 3 (λ -(6L 2 1 + 2L 2 )A max ) 2 .Proof. Similar to the proof of Theorem 5, by using the gradient bound in Lemma 12 and the smoothness in Lemma 15.N.1 Important Lemmas Lemma 16. Suppose that Assumptions 1, 2 hold. For any task τ , and any policies π and π ′ , the following bound holds:1 1 -γ E s∼ν π τ a∼π ′ (•|s) [A π τ (s, a)] -C π τ (π ′ ) ≤ J τ (π ′ ) -J τ (π) ≤ 1 1 -γ E s∼ν π τ a∼π ′ (•|s) [A π τ (s, a)] + C π τ (π ′ ) where C π τ (π ′ ) = 4γA max (1 -γ) 2 D max T V (π||π ′ )E s∼ν π τ [D T V (π(•|s)||π ′ (•|s))] .Here, we defineD T V (π(•|s)||π ′ (•|s)) ≜ 1 2 a∈A |π(a|s) -π ′ (a|s)| in a discrete action space or D T V (π(•|s)||π ′ (•|s)) ≜ 12 a∈A |π(a|s) -π ′ (a|s)|da in a continuous action space, andD max T V (π||π ′ ) ≜ max s∈S D T V (π(•|s)||π ′ (•|s)).Proof. Let P π τ is a matrix where P π τ (i, j) = E a∼π(•|si) P τ (s j |s i , a) and P π ′ τ is a matrix whereP π ′ τ (i, j) = E a∼π ′ (•|si) P τ (s j |s i , a). Let G = (1 + γP π τ + (γP π τ ) 2 + . . .) = (1 -γP π τ ) -1 , and similarly G = (1 + γP π ′ τ + (γP π ′ τ ) 2 + . . .) = (1 -γP π ′ τ ) -1 .Let ρ be a density vector on state space and r τ is a reward function vector on state space, thus r ⊤ τ ρ is a scalar meaning the expected reward under density ρ. Note that J τ (π) = r ⊤ τ Gρ τ , and J τ (π ′ ) = r ⊤ τ Gρ τ . Here, ρ τ is the initial state distribution for task τ . Let ∆ = P π ′ τ -P π τ . Follow the proof in Appendix B in [51] , we haveG -1 -G-1 = (1 -γP π ) -(1 -γP π ) = γ∆.Left multiply by G and right multiply by G,EQUATIONLeft multiply by G and right multiply by G, G = γG∆ G + G.Substituting the right-hand side in (45) into G in (46) , then G = G + γG∆G + γ 2 G∆ G∆G.So we haveEQUATION) Note that r ⊤ τ G = v π τ ⊤, where v is the value function on the state space. We also have Gρ τ = 1 1-γ ν π τ , where ν π τ is the state visitation distribution vector. So,J τ (π) -J τ (π) = r ⊤ τ ( G -G)ρ τ = γ 1 -γ v π τ ⊤ ∆ν π τ + γ 2 1 -γ v π τ ⊤ ∆ G∆ν π τ .Consider the first term γ 1-γ v π τ ⊤ ∆ν π τ , similar to Equation ( 50) in [51] , we haveEQUATIONSince we have a π(a|s)A π τ (s, a) = 0, we haveγv π τ ⊤ ∆ν π τ = s ν π τ (s) a π ′ (a|s)A π τ (s, a) = E s∼ν π τ a∼π ′ (•|s) [A π τ (s, a)] .Combine (47) and the above equation, we have the following for the second term:γ 2 1 -γ v π τ ⊤ ∆ G∆ν π τ = J τ (π ′ ) -J τ (π) - 1 1 -γ E s∼ν π τ a∼π ′ (•|s) [A π τ (s, a)] .Then we need to showγ 2 1 -γ v π τ ⊤ ∆ G∆ν π τ ≤ C π τ (π ′ ).First, by Hölder's inequality,γ 2 1 -γ v π τ ⊤ ∆ G∆ν π τ ≤ γ 1 -γ ∥γv π τ ⊤ ∆∥ ∞ ∥ G∆ν π τ ∥ 1 .Similar to (48) , each element in the vector γv π τ ⊤ ∆ is a (π ′ (a|s) -π(a|s))A π τ (s, a), then we have∥γv π τ ⊤ ∆∥ ∞ ≤ a |π ′ (a|s) -π(a|s)|A π τ (s, a) ≤ 2A max D max T V (π||π ′ ).From the Lemma 3 of [1], we have∥ G∆ν π τ ∥ 1 ≤ 2 1 -γ E s∼ν π τ [D T V (π(•|s)||π ′ (•|s))] .Therefore, we haveγ 2 1 -γ v π τ ⊤ ∆ G∆ν π τ ≤ C π τ (π ′ ) = 4γA max (1 -γ) 2 D max T V (π||π ′ )E s∼ν π τ [D T V (π(•|s)||π ′ (•|s))] .Then the bounds hold.Lemma 17. Suppose that Assumptions 1, 2 hold. For any task τ , any bounded parameters θ and θ ′ , and i = 1 or 2, the following bound holds for both i = 1 and 2:J τ (π θ ′ ) -J τ (π θ ) ≤ 1 1 -γ E s∼ν πθ τ a∼π θ ′ (•|s) A πθ τ (s, a) + 2γA max (1 -γ) 2 ϵ D 2 τ,i (π θ , πθ ′ ) and J τ (π θ ′ ) -J τ (π θ ) ≥ 1 1 -γ E s∼ν πθ τ a∼π θ ′ (•|s) A πθ τ (s, a) - 2γA max (1 -γ) 2 ϵ D 2 τ,i (π θ , πθ ′ ).Proof. The proof follows similar lines of Theorem 1 in [51] and Corollary 1 and 2 in [1] . For the sake of self-containedness, we provide the complete proof.We show the first inequality. The second inequality follows a similar way. From Lemma 16,J τ (π θ ′ )-J τ (π θ )- 1 1 -γ E s∼ν πθ τ a∼π θ ′ (•|s) A πθ τ (s, a) ≤ 4γA max (1 -γ) 2 D max T V (π θ ||π θ ′ )E s∼ν πθ τ [D T V (π θ (•|s)||π θ ′ (•|s))] .From Assumption 2, ν πθ (s) ≥ ϵ for any s ∈ A. Also,D T V (π θ (•|s)||π θ ′ (•|s)) ≥ 0 for any s ∈ A. Then, we have ϵD max T V (π θ ||π θ ′ ) ≤ E s∼ν πθ τ [D T V (π θ (•|s)||π θ ′ (•|s))] .From Jensen's inequality, we haveE s∼ν πθ τ [D T V (π θ (•|s)||π θ ′ (•|s))] 2 ≤ E s∼ν πθ τ D 2 T V (π θ (•|s)||π θ ′ (•|s)) .From the above three inequalities, we haveJ τ (π θ ′ ) -J τ (π θ ) - 1 1 -γ E s∼ν πθ τ a∼π θ ′ (•|s) A πθ τ (s, a) ≤ 4γA max (1 -γ) 2 ϵ E s∼ν πθ τ D 2 T V (π θ (•|s)||π θ ′ (•|s)) .(49) From [8] , we haveEQUATIOND 2 T V (π θ (•|s)||π θ ′ (•|s)) ≤ 1 2 D KL (π θ ′ (•|s)||π θ (•|s)).Therefore,EQUATIONJ τ (π θ ′ ) -J τ (π θ ) ≤ 1 1 -γ E s∼ν πθ τ a∼π θ ′ (•|s) A πθ τ (s, a) + 2γA max (1 -γ) 2 ϵ D 2 τ,2 (π θ , πθ ′ ).Lemma 18. Consider the softmax policy with function approximation shown in Section 5.1. Suppose that Assumptions 1, 2, and 3 hold. For any task τ , and any softmax policies parameterized by bounded θ and θ ′ , the following bound holds:J τ (π θ ′ ) -J τ (π θ ) ≤ 1 1 -γ E s∼ν πθ τ a∼π θ ′ (•|s) A πθ τ (s, a) + 4γA max L 2 1 (1 -γ) 2 ϵ ∥θ -θ ′ ∥ 2 and J τ (π θ ′ ) -J τ (π θ ) ≥ 1 1 -γ E s∼ν πθ τ a∼π θ ′ (•|s) A πθ τ (s, a) - 4γA max L 2 1 (1 -γ) 2 ϵ ∥θ -θ ′ ∥ 2 .Proof. From (36), for any θ ∈ R n ,∇ θ πθ (a|s) = πθ (a|s)∇ θ f θ (s, a) -πθ (a|s) A ∇ θ f θ (s, a ′ ) exp (f θ (s, a ′ ))da ′ A exp (f θ (s, a ′ ))da ′ . Then, ∥∇ θ πθ (a|s)∥ ≤ πθ (a|s)∥∇ θ f θ (s, a)∥ + πθ (a|s) A ∇ θ f θ (s, a ′ ) exp (f θ (s, a ′ ))da ′ A exp (f θ (s, a ′ ))da ′ ≤ 2π θ (a|s)L 1From the mean value theorem, we have|π θ (a|s) -πθ ′ (a|s)| ≤ 2π ϕ(a) (a|s)L 1 ∥θ -θ ′ ∥, where ϕ(a) = δ(a)θ + (1 -δ(a))θ ′ and 0 ≤ δ(a) ≤ 1. So, 1 2 a∈A |π θ (a|s) -πθ ′ (a|s)| ≤ L 1 ∥θ -θ ′ ∥.From (49), we haveJ τ (π θ ′ ) -J τ (π θ ) - 1 1 -γ E s∼ν πθ τ a∼π θ ′ (•|s) A πθ τ (s, a) ≤ 4γA max L 2 1 (1 -γ) 2 ϵ ∥θ -θ ′ ∥ 2 .We use the same way to show another inequality.Proof of Theorem 3. When the requirement of Theorem 1, λ ≥ 2A max , is satisfied, From Assumption 4 and Theorem 1, for both i = 1 and 2,EQUATIONwhere the constants K i and M i are shown in Theorem 1. The last inequality sign comes from that h i is a concave function and Jensen's inequality.Let πθ ′ τ (ϕ) = Alg (i) (π ϕ , λ, τ ) for any meta-parameter ϕ. From the definition of the within-task algorithm, we haveE s∼ν πϕ τ a∼π θ ′ τ (ϕ)(•|s) Q πϕ τ (s, a) -λD 2 τ,i (π ϕ , πθ ′ τ (ϕ)) ≥ E s∼ν πϕ τ a∼π θ * τ (•|s) Q πϕ τ (s, a) -λD 2 τ,i (π ϕ , πθ * τ ).This is equivalent toE s∼ν πϕ τ a∼π θ ′ τ (ϕ)(•|s) A πϕ τ (s, a) -λD 2 τ,i (π ϕ , πθ ′ τ (ϕ)) ≥ E s∼ν πϕ τ a∼π θ * τ (•|s) A πϕ τ (s, a) -λD 2 τ,i (π ϕ , πθ * τ ).when λ ≥ 2γAmax (1-γ)ϵ , from the second inequality in Lemma 17 and the above inequality,J τ (π θ ′ τ (ϕ)) -J τ (π ϕ ) ≥ 1 1 -γ E s∼ν πϕ τ a∼π θ ′ τ (ϕ)(•|s) A πϕ τ (s, a) - 2γA max (1 -γ) 2 ϵ D 2 τ,i (π ϕ , πθ ′ τ (ϕ)) ≥ 1 1 -γ E s∼ν πϕ τ a∼π θ ′ τ (ϕ)(•|s) A πϕ τ (s, a) - λ 1 -γ D 2 τ,i (π ϕ , πθ ′ τ (ϕ)) ≥ 1 1 -γ E s∼ν πϕ τ a∼π θ * τ (•|s) A πϕ τ (s, a) - λ 1 -γ D 2 τ,i (π ϕ , πθ * τ ).From the second inequality in Lemma 17,J τ (π θ * τ ) -J τ (π ϕ ) ≤ 1 1 -γ E s∼ν πϕ τ a∼π θ * τ (•|s) A πϕ τ (s, a) + 2γA max (1 -γ) 2 ϵ D 2 τ,i (π ϕ , πθ * τ ).From the last two inequalities,J τ (π θ ′ τ (ϕ)) -J τ (π θ * τ ) ≥ -( 2γA max (1 -γ) 2 ϵ + λ 1 -γ )D 2 τ,i (π ϕ , πθ * τ ), i.e., J τ (π θ * τ ) -J τ (Alg (i) (π ϕ , λ, τ )) ≤ ( 2γA max (1 -γ) 2 ϵ + λ 1 -γ )D 2 τ,i (π ϕ , πθ * τ ). Then, E τ ∼P(Γ) [J τ (π θ * τ ) -J τ (Alg (i) (π ϕ , λ, τ ))] ≤ ( 2γA max (1 -γ) 2 ϵ + λ 1 -γ )E τ ∼P(Γ) [D 2 τ,i (π ϕ , πθ * τ )].Let ϕ * = arg max ϕ E τ ∼P(Γ) [J τ (Alg (i) (π ϕ , λ, τ ))], we have E τ ∼P(Γ) [J τ (π θ * τ ) -J τ (Alg (i) (π ϕ * , λ, τ ))] ≤ ( 2γA max (1 -γ) 2 ϵ + λ 1 -γ)Var i (P(Γ)).Note that in the above analysis, we need λ ≥ 2A max and also λ ≥ 2γAmax (1-γ)ϵ . So, we select we select λ = 2Amax(1-γ)ϵ to satisfy the requirement. When λ = 2Amax (1-γ)ϵ , we haveEQUATIONFrom ( 50) and (51) we have1 T T t=1E t E τ ∼P(Γ) [J τ (π θ * τ ) -J τ (Alg (i) (π ϕt , λ, τ ))]≤ h i K i T + M i √ T + 2(1 + γ)A max (1 -γ) 2 ϵVar i (P(Γ)).Proof of Theorem 4. Similar to the above proof of Theorem 3. The difference is using two inequalities in Lemma 18 instead of those in Lemma 17 and using Theorem 2 for convergence instead of Theorem 1.The requirement of Theorem 2 is λ > (6L 2 1 + 2L 2 )A max , and the requirement of Lemma 18 is λ ≥ . Then, the bound is1 T T t=1E t E τ ∼P(Γ) [J τ (π θ * τ ) -J τ (Alg (3) (π ϕt , λ, τ ))]≤h 3 K 3 T + M 3 √ T + 4γL 2 1 A max (1 -γ) 2 ϵ + λ 1 -γVar 3 (P(Γ)),≤h 3 K 3 T + M 3 √ T + ((6 + 4γ)L 2 1 + 2L 2 )A max (1 -γ) 2 ϵVar 3 (P(Γ)),In all the proofs in Sections N.1 and N.1, we can replace as A max to A ′ max , where A ′ max is defined by the maximum advantage function value of policy πϕ ′ , where ϕ ′ = arg min ϕ E τ ∼P(Γ) [D 2 τ,i (π ϕ , πθ * τ )]. It is easy to see A ′ max ≤ A max . For simplification of the assumption statements, theorem statements, and convenience of the proofs, we keep A max in the proofs and Theorems 3 and 4. We actually can make the bound in Theorems 3 and 4 tighter by replacing A max to A ′ max . In the verification of the theoretical results of Section 6, we select λ based on A ′ max and verify the tighter bounds by the experiments.Proof of part (i) of Remark 1 . If the MDP M τ is ergodic, there exists a policy π such that ν π τ (s) ≥ ϵ 0 . As ϕ is bounded, the probability (or probability density) of each action of the softmax policy is larger than 0 and lower bounded by a ϵ 1 > 0. Therefore, the action probability of the policy π(a|s) can be upper bounded by πϕ (a|s)/ϵ 1 for any a. Therefore, ν πϕ τ (s) ≥ ϵ 0 /ϵ 1 .Proof of part (ii) of Remark 1 . If the initial state distribution ρ τ has ρ τ (s) > 0 for any s ∈ S. Since S is bounded, ρ τ (s) ≥ ϵ 2 for any s ∈ S. Then, ν πϕ τ (s) ≥ (1 -γ)ϵ 2 .In this paper, we provide several theorems, where the hyper-parameter selection, e.g., λ, is provided by the theorems. The theoretical analysis usually chooses hyper-parameters, which are sometimes conservative. In practice, we can tune them to improve the performance.• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: * 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. 

* 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.
questions: questions: * Please address the aforementioned weaknesses.

* In Line 178: does NPG mean Natural Policy Gradient? If yes, maybe state it explicitly. 

* Is it possible to formulate a similar bound for other meta-RL algorithms, such as RL2 [1] or VariBAD [2]? 

* 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?\
\
The 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. 
* 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?

[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.

[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: limitations: The authors addressed the limitations of the proposed algorithm in section P.
paper_summary: paper_summary: This paper proposes an optimization framework to learn the meta-prior for task-specific policy adaptation.
strength_weakness: strength_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 ? 
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.
questions: questions: see the weaknesses
limitations: limitations: yes, the author has provided that
paper_summary: paper_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.
strength_weakness: strength_weakness: ### W1. 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.

### W2. 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.

### W3. Comparison with Broader Range of Methods

While 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.
questions: questions: ### Q1. Hyperparameter Sensitivity

How sensitive is the proposed method to the choice of hyperparameters? 

### Q2. 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?

### Q3. Practical Deployment

What 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: 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.

Comments: title: Acknowledgement
Supplementary answer for the reviewer's comment
comment: Thanks for your reply.

These references help to improve the clarity of the discussion above. I didn't find references [2,3] in the manuscript, and I think that it would be beneficial to add them.

I raised my score since the authors answered all my concerns.
thank you, that answers my question.
Thanks for your reply.

The categorization of meta-RL approaches and the comparison of the differences between the two categories are justified in [1]. The experiments conducted in [2,3] show that optimization-based meta-RL methods are more robust to sub-optimal meta-policies and can handle tasks outside the training distribution.


[1] Beck, Jacob, et al. "A survey of meta-reinforcement learning", 2023.

[2] Xiong, Zheng, et al. "On the Practical Consistency of Meta-Reinforcement Learning Algorithms", 2021.

[3] Finn, Chelsea, et al. "Meta-Learning and Universality: Deep Representations and Gradient Descent Can Approximate any Learning Algorithm", 2018.
I thank the authors for their detailed response. 

The categorization of existing meta-RL algorithms provided in the global rebuttal answer helps to clarify the differences between the various meta-RL algorithms and place the proposed method relating to the existing approaches. Adding this discussion to the paper would improve the contribution of the manuscript.  

The discussion explains that although optimization-based meta-RL methods hold worse performance than black-box methods, they are more robust to sub-optimal meta-policies and can handle tasks outside the training distribution, compared with black-box methods (such as RL2 and VariBAD).
 
Can you provide a reference that supports this claim? I understand that the motivation for black-box algorithms such as VariBAD or RL2 was to learn the prior distribution over tasks and theoretically should not work with test tasks outside this prior distribution, but is there anyone who performed any experiment that validates that optimization-based methods work better in such scenarios?

I appreciate the added comparison to the recent baseline and the detailed answers to my questions.
I appreciate the authors for the detailed responses.

I still think this is a good submission worth an acceptance, so I maintain my assessment.
We thank the reviewer again for reviewing our work. Here, we have supplementary answers to the reviewer's questions.

>**Question 1. In Line 178: does NPG mean Natural Policy Gradient? If yes, maybe state it explicitly.**

**Answer:** Yes. Thanks for pointing it out. We will clarify it in the revised manuscript.

>**Question 4. 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**

**Answer:** In this manuscript, our algorithm performs (i) multiple-step policy optimization on one-time data collection, i.e., for each iteration of the meta-test, we collect data on the current policy and adapt the policy using multiple optimization steps. MAML performs (ii) one-step policy optimization on one-time data collection, i.e., for each iteration of the meta-test, it collects data on the current policy and adapts the policy using a one-step policy gradient. As indicated in lines 680-690, the computation times of (i) and (ii) are comparable for one iteration. On the other hand, the optimality of our algorithm is better than MAML for a single iteration, i.e.,  higher data efficiency of the proposed algorithm. So, our algorithm takes fewer iterations and less training time to reach a given optimality requirement, i.e., speed up the adaptation process. The speed-up is due to the higher data efficiency and the better optimality.