On the Convergence Theory of Debiased Model-Agnostic Meta-Reinforcement Learning
Year: 2021

Abstract:
We consider Model-Agnostic Meta-Learning (MAML) methods for Reinforcement Learning (RL) problems, where the goal is to find a policy using data from several tasks represented by Markov Decision Processes (MDPs) that can be updated by one step of stochastic policy gradient for the realized MDP. In particular, using stochastic gradients in MAML update steps is crucial for RL problems since computation of exact gradients requires access to a large number of possible trajectories. For this formulation, we propose a variant of the MAML method, named Stochastic Gradient Meta-Reinforcement Learning (SG-MRL), and study its convergence properties. We derive the iteration and sample complexity of SGMRL to find an -first-order stationary point, which, to the best of our knowledge, provides the first convergence guarantee for model-agnostic meta-reinforcement learning algorithms. We further show how our results extend to the case where more than one step of stochastic policy gradient method is used at test time. Finally, we empirically compare SG-MRL and MAML in several deep RL environments.

heading: 1 Introduction
text: Meta-learning has recently attracted much attention as a learning to learn approach that enables quick adaptation to new tasks using past experience and data. This is a particularly promising approach for Reinforcement Learning (RL) where in several applications, such as robotics, a group of agents encounter new tasks and need to learn new behaviors or policies through a few interactions with the environment building on previous experience [1–9]. Among various forms of Meta-learning, gradient-based Model-Agnostic Meta-Learning (MAML) formulation [1] is a particularly effective approach which, as its name suggests, can be applied to any learning problem that is trained with gradient-based updates. In MAML, we exploit observed tasks at training time to find an initial model that is trained in a way that rapidly adapts to a new unseen task at test time, after running a few steps of a gradient-based update with respect to the loss of the new task.
The MAML formulation can be extended to RL problems if we represent each task as a Markov Decision Process (MDP). In this setting, we assume that we are given a set of MDPs corresponding to the tasks that we observe during the training phase and assume that the new task at test time is drawn from an underlying probability distribution. The goal in Model-Agnostic Meta-Reinforcement Learning (MAMRL) is to exploit this data to come up with an initial policy that adapts to a new task (drawn from the same distribution) at test time by taking a few stochastic policy gradient steps [1].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Several algorithms have been proposed in the context of MAMRL [1, 9–12] which demonstrate the advantage of this framework in practice. None of these methods, however, are supported by theoretical guarantees for their convergence rate or overall sample complexity. Moreover, these methods aim to solve a specific form of MAMRL that does not fully take into account the stochasticity aspect of RL problems. To be more specific, the original MAMRL formulation proposed in [1] assumes performing one step of policy gradient to update the initial model at test time. However, as mentioned in the experimental evaluation section in [1], it is more common in practice to use stochastic policy gradient, computed over a batch of trajectories, to update the initial model at test time. This is mainly due to the fact that computing the exact gradient of the expected reward is not computationally tractable due to the massive number of possible state-action trajectories. As a result, the algorithm developed in [1] is designed for finding a proper initial policy that performs well after one step of policy gradient, while in practice it is implemented with stochastic policy gradient steps. Due to this difference between the formulation and what is used in practice, the ascent step used in MAML takes a gradient estimate which suffers from a non-diminishing bias. As the variance of gradient estimation is also non-diminishing, the resulting algorithm would not achieve exact first-order optimality. To be precise, in stochastic nonconvex optimization, if we use an unbiased gradient estimator, along with a small stepsize or a large batch size to control the variance, the iterates converge to a stationary point. However, if we use a biased estimator with non-vanishing bias and variance, exact convergence to a stationary point is not achievable, even if the variance is small.
Contributions. The goal of this paper is to solve the modified formulation of model-agnostic metareinforcement learning problem in which we perform a stochastic policy gradient update at test time instead of (deterministic) policy gradient. To do so, we propose a novel stochastic gradientbased method for Meta-Reinforcement Learning (SG-MRL), which is designed for stochastic policy gradient steps at test time. We show that SG-MRL implements an unbiased estimate of its objective function gradient which allows achieving first-order optimality in non-concave settings. Moreover, we characterize the relation between batch sizes and other problem parameters and the best accuracy that SG-MRL can achieve in terms of gradient norm. We show that, for any > 0, SG-MRL can find an -first-order stationary point if the learning rate is sufficiently small or the batch of tasks is large enough. To the best of our knowledge, this is the first result on the convergence of MAMRL methods. Moreover, we show that our analysis can be extended to the case where more than one step of stochastic policy gradient is taken during test time. For simplicity, we state all the results in the body of the paper for the single-step case and include the derivations of the general multiple steps case in the appendices. We also empirically validate the proposed SG-MRL algorithm in larger-scale environments standard in modern reinforcement learning applications, including a 2D-navigation problem, and a more challenging locomotion problem simulated with the MuJoCo library.
Related work. Although this paper provides the first theoretical study of MAML for RL, several recent papers have studied the complexity analysis of MAML in other contexts. In particular, the iMAML algorithm which performs an approximation of one step of proximal point method (instead of a few steps of gradient descent) in the inner loop was proposed in [13]. The authors focus on the deterministic case, and show that, assuming the inner loop loss function is sufficiently smooth, i.e., the regularized inner loop function is strongly convex, iMAML converges to a first-order stationary point. Another recent work [14] establishes convergence guarantees of the MAML method to first-order stationarity for non-convex settings. Also, [15] extends the theoretical framework in [14] to the multiple-step case. However, the results in [14, 15] cannot be applied to the reinforcement learning setting. This is mainly due to the fact that the probability distribution over possible trajectories of states and actions varies with the policy parameter, leading to a different algorithm that has an additional term which makes the analysis, such as deriving an upper bound on the smoothness parameter, more challenging. We will discuss this point in subsequent sections.
The online meta-learning setting has also been studied in a number of recent works [16–18]. In particular, [17] studies this problem for convex objective functions by casting it in the online convex optimization framework. Also, [16] extends the model-agnostic setup to the online learning case by considering a competitor which adapts to new tasks, and propose the follow the meta leader method which obtains a sublinear regret for strongly convex loss functions.
It is also worth noting that another notion of bias that has been studied in the MAMRL literature [10, 19] differs from what we consider in our paper. More specifically, as we will show later, the derivative of the MAML objective function requires access to the second-order information, i.e., Hessian. In [1], the authors suggest a first-order approximation which ignores this second-order term.
This leads to a biased estimate of the derivative of the MAML objective function, and a number of recent works [10, 19] focus on providing unbiased estimates for the second-order term. In contrast, here we focus on biased gradient estimates where the bias stems from the fact that in most real settings we do not have access to all possible trajectories and we only have access to a mini-batch of possible trajectories. In this case, even if one has access to the second-order term required in the update of MAML, the bias issue we discuss here will remain.

heading: 2 Problem formulation
text: Let {Mi}i be the set of Markov Decision Processes (MDPs) representing different tasks1. We assume these MDPs are drawn from a distribution p (which we can only draw samples from), and also the time horizon is fixed and is equal to {0, 1, ...,H} for all tasks. For the i-th MDP denoted by Mi, which corresponds to task i, we denote the set of states and actions by Si and Ai, respectively. We also assume the initial distribution over states in Si is given by µi(·) and the transition kernel is denoted by Pi, i.e., the probability of going from state s ∈ Si to s′ ∈ Si given taking action a ∈ Ai is Pi(s′|s, a). Finally, we assume at state s and by taking action a, the agent receives reward ri(s, a). To summarize, an MDPMi is defined by the tuple (Si,Ai, µi, Pi, ri). For MDPMi, the actions are chosen according to a random policy which is a mixed strategy over the set of actions and depends on the current state, i.e., if the system is in state s ∈ Si, the agent chooses action a ∈ Ai with probability πi(a|s). To search over the space of all policies, we assume these policies are parametrized with θ ∈ Rd, and denote the policy corresponding to parameter θ by πi(·|·; θ). A realization of states and actions in this setting is called a trajectory, i.e., a trajectory of MDPMi can be written as τ = (s0, a0, ..., sH , aH) where ah ∈ Ai and sh ∈ Si for any 0 ≤ h ≤ H . Note that, given the above assumptions, the probability of this particular trajectory is given by
qi(τ ; θ) := µi(s0) H∏ h=0 πi(ah|sh; θ) H−1∏ h=0 Pi(sh+1|sh, ah). (1)
Also, the total reward received over this trajectory isRi(τ) := ∑H h=0 γ
hri(sh, ah), where 0 ≤ γ ≤ 1 is the discount factor. As a result, for MDPMi, the expected reward obtained by choosing policy π(·|·; θ) is given by Ji(θ) := Eτ∼qi(·;θ) [Ri(τ)] . (2) It is worth noting that the gradient∇Ji(θ) admits the following characterization [20–22]
∇Ji(θ) = Eτ∼qi(·;θ) [gi(τ ; θ)] , (3) where gi(τ ; θ) is defined as
gi(τ ; θ) := H∑ h=0 ∇θ log πi(ah|sh; θ)Rhi (τ), (4)
if we define Rhi (τ) as Rhi (τ) := ∑H t=h γ
tri(st, at). In practice, evaluating the exact value of (3) is not computationally tractable. Instead, one could first acquire a batch Di,θ of trajectories drawn independently from distribution qi(·; θ), and then, estimate∇Ji(θ) by
∇̃Ji(θ,Di,θ) := 1 |Di,θ| ∑
τ∈Di,θ gi(τ ; θ). (5)
Also, we denote the probability of choosing (with replacement) an independent batch of trajectories Di,θ by qi(Di,θ; θ) (see Appendix A.1 for a remark on this). In this setting, the goal of Model-Agnostic Meta-Reinforcement Learning problem introduced in [1] is to find a good initial policy that performs well in expectation when it is updated using one or a few steps of stochastic policy gradient with respect to a new task. In particular, for the case of performing one step of stochastic policy gradient, the problem can be written as2
max θ∈Rd
V1(θ) := Ei∼p [ EDitest [ Ji ( θ + α∇̃Ji(θ,Ditest) )]] . (6)
1To simplify the analysis, we assume the number of tasks is finite 2From now on, we suppress the θ dependence of batches to simplify the notation.
Note that by solving this problem we find an initial policy (Meta-policy) that in expectation performs well if we evaluate the output of our procedure after running one step of stochastic policy gradient on this initial policy for a new task.
This formulation can be extended to the setting with more than one step of stochastic policy gradient as well. To state the problem formulation in this case, let us first define Ψi which is an operator that takes model θ and batch Di as input and performs one step of stochastic gradient policy at point θ and with respect to function Ji and batch Di, i.e., Ψi(θ,Di) := θ + α∇̃Ji(θ,Di). Now, we extend problem (6) to the case where we are looking for an initial point which performs well on expectation after it is updated with ζ steps of stochastic policy gradient with respect to a new MDP drawn from distribution p. This problem can be written as
max θ∈Rd Vζ(θ) := Ei∼p [ E{Ditest,t}ζt=1 [ Ji ( Ψi(. . . (Ψi(θ,Ditest,1) . . .),Ditest,ζ) )] ] , (7)
where the operator Ψi is applied ζ times inside the expectation. In this paper, we establish convergence properties of policy gradient methods for both single step and multiple steps of stochastic gradient cases, but for simplicity in the main text we focus on the single step case.

heading: 2.1 Second-order information of the expected reward
text: Due to the inner gradient in V1(θ), i.e., the objective function of the MAML problem in (6), the gradient of the function V1(θ) requires access to the second-order information of the expected reward function J(θ). To facilitate further analysis, in this subsection we formally present a characterization of expected reward Hessian and its unbiased estimate over a batch of trajectories. In particular, the expected reward Hessian∇2Ji(θ) is given by (see [22] for more details)
∇2Ji(θ) = Eτ∼qi(·;θ) [ui(τ ; θ)] , ui(τ ; θ) :=∇θνi(τ ; θ)∇θ log qi(τ ; θ) >+∇2θνi(τ ; θ) (8)
where νi(τ ; θ) is given by νi(τ ; θ) := ∑H h=0 log πi(ah|sh; θ)Rhi (τ).
Recall that the reward function is defined as Rhi (τ) := ∑H t=h γ
tri(st, at). It is worth noting that based on the expression in (4) we can write gi(τ ; θ) = ∇θνi(τ ; θ). Similar to policy gradient, policy Hessian can be estimated over a batch of trajectories Di independently drawn with respect to qi(; θ). Specifically, for a given dataset Di, we can define ∇̃2Ji(θ,Di)
∇̃2Ji(θ,Di) := 1 |Di| ∑ τ∈Di ui(τ ; θ) (9)
as an unbiased estimator of the Hessian ∇2Ji(θ). We will use the expressions for the Hessian ∇2Ji(θ) in (8) and the Hessian approximation ∇̃2Ji(θ,Di) in (9) to introduce our proposed method for solving the Meta-RL problem in (6) and its generalized version in (7).

heading: 3 Model-agnostic meta reinforcement learning
text: In this section, we first propose a method to solve the stochastic gradient-based MAML Reinforcement Learning problem introduced in (6). Then, we discuss how to extend the proposed method to the setting that we solve a multi-step MAML problem as introduced in (7). We close the section by discussing the differences between our proposed method and the Meta-RL method proposed in [1] and clarify why these two methods are solving two different problems.

heading: 3.1 MAML for stochastic meta-RL
text: Our goal in this section is to propose an efficient method for solving the stochastic Meta-RL problem in (6). To do so, we propose a stochastic gradient MAML method for Meta-Reinforcement Learning (SG-MRL) that aims at solving problem (6) by following the update of stochastic gradient descent for the objective function V1(θ). To achieve this goal one need to find an unbiased estimator of the gradient ∇V1(θ) which in some MAML settings is not trivial (for more details see Section 4.1 in [14]), but we show that for problem (6) an unbiased estimate of ∇V1(θ) can be efficiently computed.
Let us start by pointing out that the gradient of the function V1(θ) defined in (6) is given by ∇V1(θ) = ∇θ [ Ei EDitest [ Ji ( θ + α∇̃Ji(θ,Ditest) )]] = EiEDitest [ (I+α∇̃2Ji(θ,Ditest))
×∇Ji(θ+α∇̃Ji(θ,Ditest)) + Ji(θ+α∇̃Ji(θ,Ditest)) ∑
τ∈Ditest
∇θ log πi(τ ; θ) ]
(10)
with the convention that for τ = (s0, a0, ..., sH , aH) we define πi(τ ; θ) as
πi(τ ; θ) := H∏ h=0 πi(ah|sh; θ). (11)
Recall that the expected reward function Ji(θ) and its gradient ∇Ji(θ) are defined in (2) and (3), respectively, and ∇̃Ji(θ,Ditest) and ∇̃2Ji(θ,Ditest) are the stochastic estimates of the gradient and Hessian corresponding to Ji(θ) that are formally defined in (5) and (9), respectively.
Note that the first term in the definition of ∇V1(θ) in (10), i.e., (I +α∇̃2Ji(θ,Ditest))∇Ji(θ+ α∇̃Ji(θ,Ditest)), is the term that gives the gradient of an MAML problem (see, e.g., [16]), while the second term, i.e., Ji(θ + α∇̃Ji(θ,Ditest)) ∑ τ∈Ditest
∇θ log πi(τ ; θ), is specific to the RL setting since the probability distribution pi itself depends on the parameter θ. For more details regarding the derivation ∇Vζ(θ) for any ζ ≥ 1, we refer the reader to Appendix C. We solve the optimization problem in (6) by using gradient ascent step to update the parameter θ, i.e., following the update θk+1 = θk + β∇V1(θk) at iteration k. However, computing the gradient ∇V1(θk) may not be tractable in many cases due to the large number of tasks and the size of the action and state spaces. In our proposed SG-MRL method we therefore replace the gradient ∇V1(θk) with its estimate computed as follows: At iteration k + 1, we first choose a subset Bk of the tasks (MDPs), where each task is drawn independently from the probability distribution p. The SG-MRL outlined in Algorithm 1 is implemented at two levels: (i) inner loop and (ii) outer loop. In the inner loop, for each task Ti with i ∈ Bk, we draw a batch of trajectories Diin according to qi(·; θk) to compute the stochastic gradient ∇̃Ji(θk,Diin) as defined in Section 2. This estimate is then used to compute a model θik+1 corresponding to task Ti by a single iteration of stochastic policy gradient,
θik+1 = θk + α∇̃Ji(θk,Diin). (12)
For simplicity, we assume that the size of Bk is equal to B for all k, and the size of dataset Diin is fixed for all tasks and at each iteration, and we denote it by Din.
In the outer loop, we compute the next iterate θk+1 using the iterates {θik+1}i∈Bk that are computed in the inner loop. In particular, we follow the update θk+1 = θk + β∇̃V1(θk), where
∇̃V1(θk) := 1
B ∑ i∈Bk [ (I + α∇̃2Ji(θk,Diin))∇̃Ji(θk + α∇̃Ji(θk,Diin),Dio) (13)
+ J̃i ( θk + α∇̃Ji(θk,Diin),Dio ) ∑ τ∈Diin ∇θ log πi(τ ; θk) ]
in which ∇̃2Ji(θk,Diin) is policy Hessian estimate defined in (9) and for each task Ti, the dataset Dio is a new batch of trajectories that are drawn based on the probability distribution qi(·; θik+1); Again, for simplicity, we assume that the size of dataset Dio is fixed for all tasks and at each iteration denoted by Do. SG-MRL is summarized in Algorithm 1.
It can be verified that if all the gradients and Hessians in SG-MRL update were exact, then the outcome of the update of SG-MRL would be equivalent to the outcome of gradient ascent update for the function V1, i.e., θk+1 = θk + β∇V1(θk). Note that by computing the expected value of ∇̃V1(θk) first with respect to the random set Dio, then with respect to Din, and finally with respect to Bk, we obtain that E[∇̃V1(θk)] = ∇V1(θk). Therefore, the stochastic gradient ∇̃V1(θk) is an unbiased estimator of the gradient∇V1(θk). The SG-MRL method can also be extended and used for solving the multi-step MAML problem defined in (7). To do so, at each iteration, we first perform ζ steps of policy stochastic gradient in the
Algorithm 1: Proposed SG-MRL method for Meta-RL Input:Initial iterate θ0 repeat
Draw a batch of i.i.d. tasks Bk⊆I with size B = |Bk|; for all Ti with i ∈ Bk do
Sample a batch of trajectories Diin w.r.t. qi(·; θk); Set θik+1 = θk + α∇̃Ji(θk,Diin);
end for Sample a batch of trajectories Dio w.r.t. qi(·; θik+1); Set θk+1 = θk
+ β
B ∑ i∈Bk (( I + α∇̃2Ji(θk,Diin) ) ∇̃Ji ( θik+1,Dio ) + Additional term in SG-MRL︷ ︸︸ ︷ J̃i ( θik+1,Dio ) ∑ τ∈Diin ∇θ log πi(τ ; θk) )
k ← k + 1 until not done
inner loop, and then take one step of stochastic gradient ascent with respect to an unbiased estimator of ∇Vζ(θ). More details on the implementation of SG-MRL for that case is provided in Appendix C.

heading: 3.2 Comparing SG-MRL with other model-agnostic meta-RL methods
text: In this section, we discuss the difference between our SG-MRL method and recent Meta-RL methods. In particular, we focus on the MAML method in [1] for solving RL problems. Before discussing the differences between these two methods, let us first recap the update of the MAML method in [1].
The main formulation proposed in [1] which was followed in other works such as [10] is slightly different from the one in this paper as they assume the agent has access to the exact gradient of the new task, and hence, they consider the following MAML problem
max θ∈Rd
V̂1(θ) := Ei∼p [Ji (θ + α∇Ji(θ))] . (14)
As mentioned, the main difference between (6) and (14) is that the former tries to find a good initial policy that leads to a good solution after running one step of stochastic gradient ascent, while the latter finds an initial policy that produces a good policy after running one step of gradient ascent. Remark 1. Problems in (6) and (14) are both valid formulations for Meta-RL. In practice, however, it is often computationally intractable to evaluate the exact gradient of the expected reward and we often have only access to its stochastic gradient. Hence, it might be more practical to solve (6) instead of (14) as it finds an initial policy that performs well after running one step of stochastic gradient, unlike (14) that finds a policy that performs well after running one step of gradient update.
In a nutshell, the MAML method proposed in [1] tries to solve the problem in (14) by following the update of stochastic gradient ascent for the objective function V̂1(θ). To be more precise, note that the gradient of the loss function V̂1(θ) defined in (14) can be expressed as
∇V̂1(θ) = ∇θEi∼p [Ji (θ + α∇Ji(θ))] = Ei∼p [( I + α∇2Ji(θ) ) ∇Ji (θ + α∇Ji(θ)) ] . (15)
Note that the expression for the gradient of V̂1(θ) in (15) is different from the expression for the gradient of V1(θ) in (10). In particular, the extra term Ji(θ + α∇̃Ji(θ,Ditest)) ∑ τ∈Ditest
∇θ log πi(τ ; θ) that appears in (15) is caused by the fact that we use stochastic gradients in the definition of the function V1(θ), while exact gradients are used in the definition of V̂1(θ).
Considering the expression for the gradient of V̂1(θ) in (15), a natural approach to approximate ∇V̂1(θ) is to replace the gradients and Hessians corresponding to the expected reward Ji(θ) by their stochastic approximations. In other words, one can use the approximation ∇̃V̂1(θk) which is defined as the average over (I + α∇̃2Ji(θk,Diin))∇̃Ji(θk + α∇̃Ji(θk,Diin),Dio) for all i ∈ Bk, i.e.,
∇̃V̂1(θk) := 1
B ∑ i∈Bk ( I + α∇̃2Ji(θk,Diin) ) ∇̃Ji ( θik,Dio ) (16)
where θik := θk + α∇̃Ji(θk,Diin). Here the procedure for computing the sample sets Diin and Dio is the same as the one in SG-MRL. Once ∇̃V̂1(θk) is computed the new variable θk+1 can be computed by following the update of stochastic gradient ascent, i.e., θk+1 = θk + β ∇̃V̂1(θk). The description of the Meta-RL method in [1] and its implementation at two levels (inner and outer) is similar to the one in Algorithm 1, except the highlighted additional term which is not included in MAML update.
Note that the gradient estimate ∇̃V̂1(θk) in (16) is a biased estimate of the exact gradient ∇V̂1(θk) defined in (15). This is due to the fact that ∇̃Ji(θk + α∇̃Ji(θk,Diin),Dio) is a biased estimate of ∇Ji(θ + α∇Ji(θ)) because of the term ∇̃Ji(θk,Diin) inside it. In other words, MAML method proposed by [1] uses a biased estimate of the gradient in this case. Note that, in general optimization analyses, when we have access to biased gradient estimators, even with diminishing or small stepsize, we might only converge to a neighborhood of the optimal solution, where the radius of our convergence depends on the bias. To resolve this issue, one needs to control the bias in the gradient directions and lower the bias as time progresses using some debiasing techniques. For instance, the work in [23] studies this problem in detail for debiasing MAML in the supervised learning setting.
On the other hand, our proposed SG-MRL method does not suffer from this issue since computing an unbiased estimator of the gradient for the objective function considered in (6) is relatively simple. In fact, in the following section, we show that SG-MRL is provably convergent and characterize its complexity to find an approximate first-order stationary point of (6) and its generalized version defined in (7).

heading: 4 Theoretical results
text: In this section, we study the convergence properties of the proposed SG-MRL method and characterize its overall complexity for finding a policy that satisfies the first-order optimality condition for the objective function Vζ(θ) defined in (7). To do so, we first formally define the first-order optimality condition that we aim to achieve. Definition 1. A random vector θ ∈ Rd is called an -approximate first-order stationary point (FOSP) for problem (7) if it satisfies E[‖∇Vζ(θ )‖] ≤ .
We next state the main assumptions that we use to derive our results. Assumption 1. The reward functions ri are nonnegative and uniformly bounded, i.e., there exists a constant R such that for any task i, state s ∈ Si, and action a ∈ Ai, we have 0 ≤ ri(a|s) ≤ R. Assumption 2. There exist constants G and L such that for any i and for any state s ∈ Si, action a ∈ Ai, and parameter θ ∈ Rd, we have ‖∇θ log πi(a|s; θ)‖ ≤ G and ‖∇2θ log πi(a|s; θ)‖ ≤ L.
Both assumptions are customary in the policy gradient literature and have been used in other papers to obtain convergence guarantees for policy gradient methods [24, 22, 25]. Assumption 3. There exists a constant ρ such that for any i and for any state s ∈ Si, action a ∈ Ai, and parameters θ1, θ2 ∈ Rd, we have ‖∇2θ log πi(a|s; θ1)−∇2θ log πi(a|s; θ2)‖ ≤ ρ‖θ1 − θ2‖.
This assumption is also customary in the analysis of MAML-type algorithms [14, 16]. In particular, in Appendix B we provide more insight into the conditions in Assumptions 2 and 3 by focusing on the special case of softmax policy parametrization.

heading: 4.1 Convergence of SG-MRL
text: Next, we study the convergence of our proposed SG-MRL for solving the Model-Agnostic MetaReinforcement Learning problem in (7). To do so, we show two important intermediate results. First, we show that the function Vζ(θ) is smooth. Second, we show the unbiased estimator of the gradient ∇Vζ(θ) denoted by ∇̃Vζ(θk) has a bounded norm. Building on these two results, we will derive the convergence of SG-MRL. To prove these two intermediate results, we first state the following lemma on the Lipschitz property of the expected reward function Ji and its first and second derivatives for any MDPMi. This lemma not only plays a key role in our analysis, but also can be of independent interest in general for analyzing meta-reinforcement learning algorithms. Lemma 1. Recall the definitions of gi(τ ; θ) in (4) and ui(τ ; θ) in (8) for trajectory τ ∈ (Si×Ai)H+1 and policy parameter θ ∈ Rd. If Assumptions 1-3 hold, then for any MDPMi we have:
i) For any τ and θ, we have ‖gi(τ ; θ)‖ ≤ ηG := GR(1−γ)2 . As a consequence, ‖∇Ji(θ)‖, ‖∇̃Ji(θ,Di)‖ ≤ ηG for any θ and any batch of trajectories Di. Further, this implies that Ji(.) is smooth with parameter ηG.
ii) For any τ and θ, we have ‖ui(τ ; θ)‖ ≤ ηH := ((H+1)G 2+L)R
(1−γ)2 . As a consequence,
‖∇2Ji(θ)‖, ‖∇̃2Ji(θ,Di)‖ ≤ ηH for any θ and any batch of trajectories Di. Further, this implies that∇Ji(.) is smooth with parameter ηH .
iii) For any batch of trajectoriesDi, ∇̃2Ji(θ,Di) is smooth with parameter ηρ := (2(H+1)GL+ρ)R(1−γ)2 .
By exploiting the results in Lemma 1, we can prove the promised results on the Lipschitz property of ∇Vζ(θ) as well as boundedness of its unbiased estimator ∇̃Vζ(θ). In the following proposition, due to space limitation and for the the ease of notation we only state the result for the case that ζ = 1; however, the general version of these results along with their proofs are available in Appendix F. Proposition 1. Consider the objective function V1 defined in (6) for the case that α ∈ (0, 1/ηH ] where ηH is given in Lemma 1. Suppose that the conditions in Assumptions 1-3 are satisfied. Then,
i) V1(θ) is smooth with parameter LV := αηρηG + 4ηH + 8RDin(H + 1)(L+DinG
2(H + 1)) (17) where ηG and ηρ are defined in Lemma 1.
ii) For any choices of Bk, {Dio}i and {Diin}i, the norm of stochastic gradient ∇̃V1(θk) defined in (13) at iteration k is bounded above by‖∇̃V1(θk)‖ ≤ GV :=2GR [ (1−γ)−2 +Din(H + 1) ] .
The smoothness parameter for the RL problem has been previously characterized (as an example see [22]), but, to the best of our knowledge, this is the first result on the smoothness parameter of the meta-RL function. Proving Proposition 1 is the main challenge in our analysis, since it establishes that our formulation satisfies the relevant assumptions needed for our main result in the next theorem.
Now, we present our main result on the convergence of SG-MRL to a first-order stationary point for the Meta-reinforcement learning problem in defined (7). We state our main result for the special case of ζ = 1, but the general statement of the theorem along with its proof can be found in Appendix G. Theorem 1. Consider V1 defined in (6) for the case that α ∈ (0, 1/ηH ] where ηH is defined in Lemma 1. Suppose Assumptions 1-3 are satisfied, and recall the definitions of LV and GV from Proposition 1. Consider running SG-MRL (Algorithm 1) with β ∈ (0, 1/LV ]. Then, for any 1 > > 0, SG-MRL finds a solution θ such that E[‖∇V1(θ )‖2] ≤ 2G 2 V LV β BDo + 2, after running for
at most O(1)Rβ min { 1 2 , BDo G2V LV β } iterations.
Next we characterize the complexity of SG-MRL for finding an -first-order stationary point solution. Corollary 1. Suppose the hypotheses of Theorem 1 hold. Then, for any > 0, SG-MRL achieves -first-order stationarity by setting: (i) BDo ≥ 8G2V / 2 and β = 1/LV requiring O( −2) iterations and computing O( −2) stochastic gradients per iteration; or (ii) β = O( −2) and BDo = O(1) which requires O( −4) iterations and O(1) stochastic gradient evaluations per iteration.
The conditions in Corollary 1 identify two settings under which SG-MRL finds an −FOSP after a finite number of iterations, abd both settings overall require O( −4) stochastic gradient evaluations. Remark 2. While we mainly focused on the case ζ = 1, we provide the general statement of the results for any ζ in the Appendix. Note that the downside of increasing ζ is that the smoothness parameter grows exponentially with respect to ζ (see Theorem 3), which means that we need to take a smaller learning rate that leads to a slower convergence rate. However, on the positive side, by increasing ζ we train a model that better adapts to a new task.

heading: 5 Numerical experiments
text: In this section, we empirically validate the proposed SG-MRL algorithm in larger-scale environments standard in modern reinforcement learning applications. The code is available online3.
3The code is available at https://github.com/kristian-georgiev/SGMRL.
We conduct two experiments: a 2D-navigation problem, and a more challenging locomotion problem simulated with the MuJoCo library [26]. For both experiments, we use a neural network policy with a standard feed-forward neural network and optimize it with vanilla policy gradient [27]. Further implementation details are outlined in Appendix H.
All experiments were conducted in MIT’s Supercloud [28]. Similar to FO-MAML proposed in [1], we use first order implementation of SG-MRL. It is also worth noting that SG-MRL is straightforward to implement as a modification to MAML and requires no additional hyperparameter tuning. Also, SGMRL does not reduce the scalability of MAML. In particular, across experiments, we benchmarked the clock time of SG-MRL against MAML and SG-MRL is consistently at most 1.05 times slower over the course of training. Next, we demonstrate the practicality of SG-MRL in modern deep reinforcement learning problems.
2D-navigation. We consider the problem of a point-mass agent navigating from the origin to a random goal location within a unit-size square centered at the origin ([−0.5, 0.5] × [−0.5, 0.5]). We consider the negative squared distance to the goal location as a reward. Observations consist of the position of the agent within the unit-size square. The action space comprises of all velocities with components clipped in the interval [−0.1, 0.1]. An example of a trajectory is illustrated in Figure 1. In Table 1, we compare the performance of SG-MRL against MAML [1] and E-MAML [29]. We make a comparison with E-MAML since it has a similar spirit to our proposed SG-MRL method, but unlike the proposed algorithm, EMAML is derived from heuristic arguments.
Locomotion: MuJoCo environments. In addition to the 2D-navigation example, we provide a benchmark on a more challenging set of tasks - MuJoCo’s locomotion environments. We benchmark our algorithm against MAML on three different tasks and report the results in Table 2. The tasks involve learning to move in a goal direction (forward/backward), or reach a target velocity. We describe each task in more detail in Appendix H.

heading: 6 Conclusion and future work
text: We studied MAML for RL problems, considering performing a few steps of stochastic policy gradient at test time. Given this formulation, we introduced SG-MRL, and discussed how it differs from the
original MAML algorithm in [1]. Further, we characterized the convergence of SG-MRL method in terms of gradient norm and under a set of assumptions on the policy and reward functions. Our results show that, for any , SG-MRL achieves -first-order stationarity, given that either the learning rate is small enough or the multiplication of task and outer loop batch sizes is sufficiently large.
A shortcoming of our analysis is the requirement on the boundedness of gradient norm (Assumption 2). A natural extension of our work would be extending the theoretical results to the setting that gradient norm is possibly unbounded. Moreover, our results are limited to achieving first-order optimality, while one can exploit techniques for escaping from saddle points to obtain second-order stationarity.

heading: 7 Acknowledgment
text: Alireza Fallah acknowledges support from the Apple Scholars in AI/ML PhD fellowship and the MathWorks Engineering Fellowship. This research is sponsored by the United States Air Force Research Laboratory and the United States Air Force Artificial Intelligence Accelerator and was accomplished under Cooperative Agreement Number FA8750-19-2-1000. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the United States Air Force or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. This research of Aryan Mokhtari is supported in part by NSF Grant 2007668, ARO Grant W911NF2110226, the Machine Learning Laboratory at UT Austin, and the NSF AI Institute for Foundations of Machine Learning.

Review summaries:
This paper studies the Model-Agnostic Meta-Reinforcement-Learning (MAMRL) from a theoretical perspective. In particular, it proposes a modified MAMRL objective along with its unbiased gradient estimator, establishing a new Meta-RL algorithm called SR-MRL. It theoreticallly proves the convergence of SR-MRL and experimentally shows its comparable performance to the original MAML algorithm.

This paper deals with the problem of few-shot meta learning, i.e. where one explicitly optimizes for the performance of doing one (or more) steps of SGD on a new task. This was intially introduced through the MAML method. However, the authors argue that MAML only discusses gradient descent while in practise, approximations lead to doing stochastic gradient desecent instead, thus making the original formulation of the problem biased. To that end, this paper proposes an SGD based meta learning objective, which ensures simpler convergence analysis as well as better performance in two benchmark problems from the RL setting. 

This paper aims to tackle the non-diminishing bias in MAMRL (MAML for RL) due to the stochastic policy gradient update for subtasks. Such bias hinders the first-order optimality when solving MAML with gradient descent. The authors compute the exact gradient of the MAMRL objective and identify the additional term that arises in RL. The authors then estimate such a gradient with an unbiased approximation based on samples and propose SG-MRL that utilizes such approximation to solve MAMRL. The authors show that SG-MRL converges to first-order stationary points under the standard assumptions and further conduct experiments on SG-MRL against baselines in the MuJoCo environment.

This paper proposed a new debiased model-agnostic meta-reinforcement learning algorithm. The main improvement is that the paper considers a more accurate setting where one does not have accurate estimate on the gradient for each task, which is assumed by previous works. One has to estimate the gradient from samples in each task, and the samples themselves depend on the global parameter $\theta$, there will be an extra term for the global gradient.  The authors hence write the exact gradient and show the convergence. Numerical results show good performance.