Meta-learning empowers artificial intelligence to increase its efficiency by learning how to learn. Unlocking this potential involves overcoming a challenging meta-optimisation problem.

We propose an algorithm that tackles this problem by letting the meta-learner teach itself. The algorithm first bootstraps a target from the meta-learner, then optimises the meta-learner by minimising the distance to that target under a chosen (pseudo-)metric.

Focusing on meta-learning with gradients, we establish conditions that guarantee performance improvements and show that the metric can control meta-optimisation.

Meanwhile, the bootstrapping mechanism can extend the effective meta-learning horizon without requiring backpropagation through all updates.

We achieve a new state-of-the art for model-free agents on the Atari ALE benchmark and demonstrate that it yields both performance and efficiency gains in multi-task meta-learning. Finally, we explore how bootstrapping opens up new possibilities and find that it can meta-learn efficient exploration in an  $\varepsilon$-greedy $Q$-learning agent—without backpropagating through the update rule.

§ INTRODUCTION

In a standard machine learning problem, a learner or agent learns a task by iteratively adjusting its parameters under a given update rule, such as Stochastic Gradient Descent (SGD). Typically, the learner's update rule must be tuned manually. In contrast, humans learn seamlessly by relying on previous experiences to inform their learning processes [Spelke & Kinzler, 2007].

For a (machine) learner to have the same capability, it must be able to learn its update rule (or such inductive biases). Meta-learning is one approach that learns (parts of) an update rule by applying it for some number of steps and then evaluating the resulting performance [Schmidhuber, 1987, Hinton & Plaut, 1987, Bengio et al., 1991]. For instance, a well-studied and often successful approach is to tune parameters of a gradient-based update, either online during training on a single task [Bengio, 2000, Maclaurin et al., 2015, Xu et al., 2018, Zahavy et al., 2020], or meta-learned over a distribution of tasks [Finn et al., 2017, Rusu et al., 2019, Flennerhag et al., 2020, Jerfel et al., 2019, Denevi et al., 2019]. More generally, the update rule can be an arbitrary parameterised function [Hochreiter et al., 2001, Andrychowicz et al., 2016, Kirsch et al., 2019, Oh et al., 2020], or the function itself can be meta-learned jointly with its parameters [Alet et al., 2020, Real et al., 2020].

Meta-learning is challenging because to evaluate an update rule, it must first be applied. This often leads to high computational costs. As a result most works optimise performance after $K$ applications of the update rule and assume that this yields improved performance for the remainder of the learner's lifetime [Bengio et al., 1991, Maclaurin et al., 2015, Metz et al., 2019]. When this assumption fails, meta-learning suffers from a short-horizon bias [Wu et al., 2018, Metz et al., 2019]. Similarly, optimizing the learner's performance after $K$ updates can fail to account for the process of learning, causing another form of myopia [Flennerhag et al., 2019, Stadie et al., 2018, Chen et al., 2016, Cao et al., 2019]. Challenges in meta-optimisation have been observed to cause degraded lifetime performance [Lv et al., 2017, Wichrowska et al., 2017], collapsed exploration [Stadie et al., 2018, Chen et al., 2016], biased learner updates [Stadie et al., 2018, Zheng et al., 2018], and poor generalisation performance [Wu et al., 2018, Yin et al., 2020, Triantafillou et al., 2020].

We argue that defining the meta-learner's objective directly in terms of the learner's objective—i.e. the performance after $K$ update steps—creates two bottlenecks in meta-optimisation. The first bottleneck is curvature: the meta-objective is constrained to the same type of geometry as the learner; the second is myopia: the meta-objective is fundamentally limited to evaluating performance within the $K$-step horizon, but ignores future learning dynamics. Our goal is to design an algorithm that removes these.

The algorithm relies on two main ideas. First, to mitigate myopia, we introduce the notion of bootstrapping a target from the meta-learner itself, a meta-bootstrap, that infuses information about learning dynamics in the objective. Second, to control curvature, we formulate the meta-objective in terms of minimising distance (or divergence) to the bootstrapped target, thereby controlling the meta-loss landscape. In this way, the meta-learner learns from its future self. This leads to a bootstrapping effect where improvements beget further improvements. We present a detailed formulation in <Ref>; on a high level, as in previous works, we first unroll the meta-learned update rule for $K$ steps to obtain the learner's new parameters. Whereas standard meta-objectives optimise the update rule with respect to (w.r.t.) the learner's performance under the new parameters, our proposed algorithm constructs the meta-objective in two steps:

* It bootstraps a target from the learner's new parameters. In this paper, we generate targets by continuing to update the learner's parameters—either under the meta-learned update rule or another update rule—for some number of steps.

* The learner's new parameters—which are a function of the meta-learner's parameters—and the target are projected onto a matching space. A simple example is Euclidean parameter space. To control curvature, we may choose a different (pseudo-)metric space. For instance, a common choice under probabilistic models is the Kullback-Leibler (KL) divergence.

The meta-learner is optimised by minimising distance to the bootstrapped target. We focus on gradient-based optimisation, but other optimisation routines are equally applicable. By optimising meta-parameters in a well-behaved space, we can drastically reduce ill-conditioning and other phenomena that disrupt meta-optimisation. In particular, this form of Bootstrapped Meta-Gradient () enables us to infuse information about future learning dynamics without increasing the number of update steps to backpropagate through. In effect, the meta-learner becomes its own teacher. We show that can guarantee performance improvements (<Ref>) and that this guarantee can be stronger than under standard meta-gradients (<Ref>). Empirically, we find that provides substantial performance improvements over standard meta-gradients in various settings. We obtain a new state-of-the-art result for model-free agents on Atari (<Ref>) and improve upon MAML [Finn et al., 2017] in the few-shot setting (<Ref>). Finally, we demonstrate how enables new forms of meta-learning, exemplified by meta-learning $\varepsilon$-greedy exploration (<Ref>).

§ RELATED WORK

Bootstrapping as used here stems from temporal difference (TD) algorithms in reinforcement learning (RL) [Sutton, 1988]. In these algorithms, an agent learns a value function by using its own future predictions as targets. Bootstrapping has recently been introduced in the self-supervised setting [Guo et al., 2020, Grill et al., 2020]. In this paper, we introduce the idea of bootstrapping in the context of meta-learning, where a meta-learner learns about an update rule by generating future targets from it.

Our approach to target matching is related to methods in multi-task meta-learning [Flennerhag et al., 2019, Nichol et al., 2018] that meta-learn an initialisation for SGD by minimising the Euclidean distance to task-optimal parameters. generalise this concept by allowing for arbitrary meta-parameters, matching functions, and target bootstraps. It is further related the more general concept of self-referential meta-learning [Schmidhuber, 1987, Schmidhuber, 1993], where the meta-learned update rule is used to optimise its own meta-objective.

Target matching under KL divergences results in a form of distillation [Hinton et al., 2015], where an online network (student) is encouraged to match a target network (teacher). In a typical setup, the target is either a fixed (set of) expert(s) [Hinton et al., 2015, Rusu et al., 2015] or a moving aggregation of current experts [Teh et al., 2017, Grill et al., 2020], whereas bootstraps a target by following an update rule. Finally, is loosely inspired by trust-region methods that introduce a distance function to regularize gradient updates [Pascanu & Bengio, 2014, Schulman et al., 2015, Tomar et al., 2020, Hessel et al., 2021].

§ BOOTSTRAPPED META-GRADIENTS

[name=main, hide axis,
colormap=whiteblackcolor(-1cm)  = (white);color(1cm) = (black), scale=1.1]

3[patch,patch refines=4,shader=faceted interp,patch type=biquadratic, opacity=0.15]
table[z expr=x^2-y^2-2*x+y]

x y
-2 -2
2 -2
2 2
-2 2
0 -2
2 0
0 2
-2 0
0 0

3[black, patch, mesh, patch type=quadratic spline, color=black]
(-2, 1.54, 5.2) (-1, 1.0, 3) (-1.5, 1.3, 3.8)

3[black, dashed, patch, mesh, patch type=cubic spline, color=black]
coordinates (-1.05, 1.125, 3.025) (1.57, -2, -2) (-0.3, 0.53, 2.59) (0.57, 0.3, -0.4)

3[black, dotted, thick, patch, mesh, patch type=quadratic spline, color=black]
coordinates (-2, 1.54, 5.2) (-0.8, 0.5, -1) (-1, 0.5, 3)

3[mark=*, black, point meta=explicit symbolic, nodes near coords]
coordinates (-2, 1.54, 5.2)[$\bx$];
3[mark=*, black, point meta=explicit symbolic, nodes near coords]
coordinates (-1, 1.0, 3)[$\,\,\,\,\,\,\,\,\,\bx^{(K)}$];
3[black, point meta=explicit symbolic, nodes near coords]
coordinates (-1.5, 1.4, 3.7)[$\bw$];
3[black, point meta=explicit symbolic, nodes near coords]
coordinates (-1.1, 0.3, 1.6)[$\tilde{\bw}$];
3[mark=*, black, point meta=explicit symbolic, nodes near coords]
coordinates (1.57, -2, -2)[$\,\,\,\,\,\,\,\,\,\,\tilde{\bx}$];

[hide axis, at=($(main.south west)+(0cm,-5.7cm)$), anchor=south west, scale=1.1]

3[surf, mesh, opacity=0.15, colormap=whiteblackcolor(-1cm)  = (white);color(1cm) = (blue),  shader=faceted interp, domain=-5:5]exp(-1*((x-1.5)^2+(y-1.5)^2)/2^2);

3[surf, mesh, opacity=0.30, colormap=whiteblackcolor(-1cm)  = (white);color(1cm) = (red),  shader=faceted interp, domain=-5:5]exp(-0.5*((x+1.5)^2+(y+1.5)^2)/2^2);

3[black, point meta=explicit symbolic, nodes near coords]
coordinates (1.5, 2, 0.3)[$\pi_{\bx^{(K)}}$];
3[black, point meta=explicit symbolic, nodes near coords]
coordinates (-1.5, -2, 0.2)[$\pi_{\tilde{\bx}}$];

(6.5, 1) node[above] $(\bx, f(\bx))$;
(6.5, -1.8) node[below] $(\bs, \pi_{\bx}(\bs))$;

[myarrow, dotted]  (3.1, 2.9)  to (3, 3.2);

[myarrow]  (3.4, -1.67) to (4.2, -1.53);

[myarrow]  (1.3, 1) to[bend right] (1.3, -1.8);
[]  (1, -0.4) node[right] $\nabla_w \mu(\tilde{\bx}, \bx^{(K)}(\bw))$;

[myarrow]  (6, -1.8) to[bend right] (6, 1);
[]  (6, -0.4) node $\pi$;

Bootstrapped Meta-Gradients.

We begin in the single-task setting and turn to multi-task meta-learning in <Ref>. The learner's problem is to minimize a stochastic objective $f(\bx) \coloneqq \E{\ell(\bx; \bzeta)}$ over a data distribution $p(\bzeta)$, where $\bzeta$ denotes a source of data and $\bx \in \cX \subset \rR^{n_x}$ denotes the learner's parameters. In RL, $f$ is typically the (negative) expected value of a policy $\pi_{\bx}$; in supervised learning, $f$ may be the expected negative log-likelihood under a probabilistic model $\pi_{\bx}$. We provide precise formulations in <Ref>.

The meta-learner's problem is to learn an update rule $\alg: \cX \times \cH \times \cW \to \cX$ that updates the learner's parameters by $\bx^{(1)} = \bx + \alg(\bx, \bh, \bw)$ given $\bx \in \cX$, a learning state $\bh \in \cH$, and meta-parameters $\bw \in \cW \subset \rR^{n_w}$ of the update rule. We make no assumptions on the update rule other than differentiability in $\bw$. As such, $\alg$ can be a recurrent neural network [Hochreiter et al., 2001, Wang et al., 2016, Andrychowicz et al., 2016] or gradient descent [Bengio, 2000, Maclaurin et al., 2015, Finn et al., 2017]. The learning state $\bh$ contains any other data required to compute the update; in a black-box setting $\bh$ contains an observation and the recurrent state of the network; for gradient-based updates, $\bh$ contains the (estimated) gradient of $f$ at $\bx$ along with any auxiliary information; for instance, SGD is given by $\bx^{(1)} = \bx - \alpha \nabla_x f(\bx)$ with $\bh = \nabla_x f(\bx), \, \bw = \alpha \in \rR_{+}$.

The standard meta-gradient () optimises meta-parameters $\bw$ by taking $K$ steps under $\alg$ and evaluating the resulting learner parameter vector under $f$. With a slight abuse of notation, let $\bx^{(K)}(\bw)$ denote the learner's parameters after $K$ applications of $\alg$ starting from some $(\bx, \bh, \bw)$, where $(\bx, \bh)$ evolve according to $\alg$ and the underlying data distribution. The update is defined by

\begin{equation}\label{eq:mg}
\bw^\prime = \bw - \beta \, \nabla_{\bw} f\left(\bx^{(K)}(\bw)\right), \qquad \beta \in \rR_{+}.
\end{equation}

Extensions involve averaging the performance over all iterates $\bx^{(1)}, \ldots, \bx^{(K)}$ [Andrychowicz et al., 2016, Chen et al., 2016, Antoniou et al., 2019] or using validation data in the meta-objective [Bengio et al., 1991, Maclaurin et al., 2015, Finn et al., 2017, Xu et al., 2018]. We observe two bottlenecks in the meta-objective in <Ref>. First, the meta-objective is subject to the same curvature as the learner. Thus if $f$ is ill-conditioned, so will the meta-objective be. Second, the meta-objective is only able to evaluate the meta-learner on dynamics up to the $K$th step, but ignores effects of future updates.

To tackle myopia, we introduce a Target Bootstrap () $\xi: \cX \mapsto \cX$ that maps the meta-learner's output $\bx^{(K)}$ into a bootstrapped target $\tilde{\bx} = \xi(\bx^{(K)})$. We focus on s that unroll $\varphi$ a further $L-1$ steps before taking final gradient step on $f$, with targets of the form $\tilde{\bx} = \bx^{(K+L-1)} - \alpha \nabla f(\bx^{(K+L-1)})$. This encourages the meta-learner to reach future states on its trajectory faster while nudging the trajectory in a descent direction. Crucially, regardless of the bootstrapping strategy, we do not backpropagate through the target. Akin to temporal difference learning in RL [Sutton, 1988], the target is a fixed goal that the meta-learner should try to produce within the $K$-step budget.

Finally, to improve the meta-optimisation landscape, we introduce a matching function $\mu: \cX \times \cX \to \rR_{+}$ that measures the (dis)similarity between the meta-learner's output, $\bx^{(K)}(\bw)$, and the target, $\tilde{\bx}$, in a matching space defined by $\mu$ (see <Ref>). Taken together, the update is defined by

\begin{equation}\label{eq:btm}
\tilde{\bw} = \bw - \beta \, \nabla_{\bw} \, \mu\left(\tilde{\bx}, \, \bx^{(K)}(\bw) \right), \qquad \beta \in \rR_{+},
\end{equation}

where the gradient is with respect to the second argument of $\mu$. Thus, describes a family of algorithms based on the choice of matching function $\mu$ and $\xi$. In particular, is a special case of under matching function $\mu(\tilde{\bx}, \bx^{(K)}) = \| \tilde{\bx} - \bx^{(K)} \|_2^2 $ and $\xi(\bx^{(K)}) = \bx^{(K)} - \frac{1}{2}\nabla_x f(\bx^{(K)})$, since the bootstrapped meta-gradient reduces to the standard meta-gradient:

\begin{equation}\label{eq:equivalence}
\nabla_w {\left\| \tilde{\bx} - \bx^{(K)}(\bw) \right\|}_2^2
= - 2 D \left(\tilde{\bx} - \bx^{(K)}\right)
= D \nabla_x f\left(\bx^{(K)}\right)
= \nabla_w f\left(\bx^{(K)}(\bw)\right),
\end{equation}

where $D$ denotes the (transposed) Jacobian of $\bx^{(K)}(\bw)$. For other matching functions and target strategies, produces different meta-updates compared to . We discuss these choices below.

Matching Function Of primary concern to us are models that output a probabilistic distribution, $\pi_{\bx}$. A common pseudo-metric over a space of probability distributions is the Kullback-Leibler (KL) divergence. For instance, Natural Gradients [Amari, 1998] point in the direction of steepest descent under the KL-divergence, often approximated through a KL-regularization term [Pascanu & Bengio, 2014]. KL-divergences also arise naturally in RL algorithms [Kakade, 2001, Schulman et al., 2015, Schulman et al., 2017, Abdolmaleki et al., 2018]. Hence, a natural starting point is to consider KL-divergences between the target and the iterate, e.g. $\mu(\tilde{\bx}, \bx^{(K)}) = \KL{\pi_{\tilde{\bx}}}{\pi_{\bx^{(K)}}}$. In actor-critic algorithms [Sutton et al., 1999], the policy defines only part of the agent—the value function defines the other. Thus, we also consider a composite matching function over both policy and value function.

Target Bootstrap We analyze conditions under which guarantees performance improvements in <Ref> and find that the target should co-align with the gradient direction. Thus, in this paper we focus on gradient-based s and find that they perform well empirically. As with matching functions, this is a small subset of all possible choices; we leave the exploration of other choices for future work.

§ PERFORMANCE GUARANTEES

In this analysis, we restrict attention to the noise-less setting (true expectations). In this setting, we ask three questions: (1) what local performance guarantees are provided by ? (2) What performance guarantees can provide? (3) How do these guarantees relate to each other? To answer these questions, we analyse how the performance around $f(\bx^{(K)}(\bw))$ changes by updating $\bw$ either under standard meta-gradients (<Ref>) or bootstrapped meta-gradients (<Ref>).

First, consider improvements under the update. In online optimisation, the update can achieve strong convergence guarantees if the problem is well-behaved [van Erven & Koolen, 2016], with similar guarantees in the multi-task setting [Balcan et al., 2019, Khodak et al., 2019, Denevi et al., 2019]. A central component of these results is that the update guarantees a local improvement in the objective. <Ref> below presents this result in our setting, with the following notation: let ${\| \bu \|}_{A} \coloneqq \sqrt{\left\langle \bu,  \, {A \bu} \right\rangle}$ for any square real matrix $A$. Let $G^T = D^T D \in \rR^{n_x \times n_x}$, with $D \coloneqq {\left[\frac{\partial}{\partial \bw} \bx^{(K)}(\bw)\right]}^T \in \rR^{n_w \times n_x}$. Note that $\nabla_w f(\bx^{(K)}(\bw)) = D \nabla_x f(\bx^{(K)})$.

Let $\bw^\prime$ be given by <Ref>. For $\beta$ sufficiently small, $f\big(\bx^{(K)}(\bw^\prime)\big) - f\big(\bx^{(K)}(\bw) \big) = -\beta {\| \nabla_x f(\bx^{(K)}) \|}_{G^T}^2 + O(\beta^2) < 0$.

We defer all proofs to <Ref>. <Ref> relates the gains obtained under standard meta-gradients to the local gradient norm of the objective. Because the meta-objective is given by $f$, the update is not scale-free <cit.>, nor invariant to re-parameterisation. If $f$ is highly non-linear, the meta-gradient can vary widely, preventing efficient performance improvement. Next, we turn to , where we assume $\mu$ is differentiable and convex, with $0$ being its minimum.

Let $\tilde{\bw}$ be given by <Ref> for some $\xi$. The update satisfies

\begin{equation*}
f\big(\bx^{(K)}(\tilde{\bw}) \big) - f\big(\bx^{(K)}(\bw) \big) = \frac{\beta}{\alpha} \left(\mu(\tilde{\bx}, \bx^{(K)} - \alpha G^T \bg) - \mu(\tilde{\bx}, \bx^{(K)}) \right) + o(\beta(\alpha + \beta)).
\end{equation*}

For $(\alpha, \beta)$ sufficiently small, there exists infinitely many $\xi$ for which $f\big(\bx^{(K)}(\tilde{\bw})\big) - f\big(\bx^{(K)}(\bw)\big) < 0$. In particular, $\xi(\bx^{(K)}) = \bx^{(K)} - \alpha G^T \bg$ yields improvements

\begin{equation*}
f\big(\bx^{(K)}(\tilde{\bw}) \big) - f\big(\bx^{(K)}(\bw) \big) = - \frac{\beta}{\alpha} \mu(\tilde{\bx}, \bx^{(K)}) + o(\beta(\alpha + \beta)) < 0.
\end{equation*}

This is not an optimal rate; there exists infinitely many s that yield greater improvements.

<Ref> portrays the inherent trade-off in ; targets should align with the local direction of steepest descent, but provide as much learning signal as possible. Importantly, this theorem also establishes that $\mu$ directly controls for curvature as improvements are expressed in terms of $\mu$. While the $\xi^\alpha_G(\bx^{(K)}) \coloneqq \bx^{(K)} - \alpha G^T \bg$ yields performance improvements that are proportional to the meta-loss itself, larger improvements are possible by choosing a that carries greater learning signal (by increasing $\mu(\tilde{\bx}, \bx^{(K)})$). To demonstrate that can guarantee larger improvements to the update rule than , we consider the $\xi^\alpha_G$ with $\mu$ the (squared) Euclidean norm. Let $r \coloneqq \|\nabla f\left(\bx^{(K)}\right)\|_2 / \| G^T \nabla f\left(\bx^{(K)}\right) \|_2$ denote the gradient norm ratio.

Let $\mu = \| \cdot \|_2^2 $ and $\tilde{\bx} = \xi_G^r(\bx^{(K)})$. Let $\bw^\prime$ be given by <Ref> and $\tilde{\bw}$ be given by <Ref>. For $\beta$ sufficiently small,
$f\big(\bx^{(K)}(\tilde{\bw}) \big) \leq f\big(\bx^{(K)}(\bw^\prime)\big)$, strictly if $G G^T \neq G^T$ and $G^T \nabla_x f(\bx^{(K)}) = \0$.

Discussion Our analysis focuses on an arbitrary (albeit noiseless) objective $f$ and establishes that can guarantee improved performance under a variety of s. We further show that can yield larger local improvements than . To identify optimal s, further assumptions are required on $f$ and $\mu$, but given these <Ref> can serve as a starting point for more specialised analysis. Empirically, we find that taking $L$ steps on the meta-learned update with an final gradient step on the objective performs well. <Ref> exposes a trade-off for targets that are “far” away. Empirically, we observe clear benefits from bootstraps that unroll the meta-learner for several steps before taking a gradient step on $f$; exploring other forms of bootstraps is an exciting area for future research.

§ REINFORCEMENT LEARNING

We consider a typical reinforcement learning problem, modelled as an MDP $\cM = (\cS, \cA, \cP, \cR, \gamma)$. Given an initial state $\bs_0 \in \cS$, at each time step $t \in \rN$, the agent takes an action $\ba_t \sim \pi_{\bx}(\ba \g \bs_t)$ from a policy $\pi: \cS \times \cA \to [0, 1]$ parameterised by $\bx$. The agent obtains a reward $r_{t+1} \sim \cR(\bs_t, \ba_t, \bs_{t+1})$ based on the transition $\bs_{t+1} \sim \cP(\bs_{t+1} \g \bs_{t}, \ba_{t})$. The action-value of the agent's policy given a state $\bs_0$ and action $\ba_0$ is given by $Q_{\bx}(\bs_0, \ba_0) \coloneqq \E{\sum_{t=0}^\infty \gamma^t r_{t+1} \g \bs_0, \ba_0, \pi_{\bx}}$ under discount rate $\gamma \in [0, 1)$. The corresponding value of policy $\pi_{\bx}$ is given by $V_{\bx}(\bs_0) \coloneqq \Ed{\ba_0 \sim \pi_{\bx}(\ba | \bs_0)}{Q_{\bx}(\bs_0, \ba_0)}$.

The agent's problem is to learn a policy that maximises the value given an expectation over $\bs_0$, defined either by an initial state distribution in the episodic setting (e.g. Atari, <Ref>) or the stationary state-visitation distribution under the policy in the non-episodic setting (<Ref>). Central to RL is the notion of policy-improvement, which takes a current policy $\pi_{\bx}$ and constructs a new policy $\pi_{\bx^\prime}$ such that $\E{V_{\bx^\prime}} \geq \E{V_{\bx}}$.
A common policy-improvement step is $\arg\max_{\bx^\prime} \Ed{a \sim \pi_{\bx^\prime}(a|s)}{Q_{\bx}(s, a)}$.

Most works in meta-RL rely on actor-critic algorithms [Sutton et al., 1999]. These treat the above policy-improvement step as an optimisation problem and estimate a policy-gradient [Williams & Peng, 1991, Sutton et al., 1999] to optimise $\bx$. To estimate $V_{\bx}$, these introduce a critic $v_{\bz}$ that is jointly trained with the policy. The policy is optimised under the current estimate of its value function, while the critic is tracking the value function by minimizing a Temporal-Difference (TD) error. Given a rollout $\tau = (\bs_0, \ba_0, r_{1}, \bs_{1}, \ldots, r_T, \bs_{T})$, the objective is given by $f(\bx, \bz) = \epsilon_{\text{PG}} \, \ell_{\text{PG}}(\bx) + \epsilon_{\text{EN}} \, \ell_{\text{EN}}(\bx) + \epsilon_{\text{TD}} \, \ell_{\text{TD}}(\bz)$, $\epsilon_{\text{PG}}, \epsilon_{\text{EN}}, \epsilon_{\text{TD}} \in \rR_{+}$, where

\begin{equation}\label{eq:actor-critic}
\begin{aligned}
\ell_{\text{EN}}(\bx) &= \sum_{t \in \tau}\sum_{\ba \in \cA} \pi_{\bx}(\ba \g \bs_t) \log \pi_{\bx}(\ba \g \bs_t), \qquad
\ell_{\text{TD}}(\bz) = \frac12 \sum_{t \in \tau} {{\left(G^{(n)}_{t} - v_{\bz}(\bs_t)\right)}^2}, \\
\ell_{\text{PG}}(\bx) &= - \sum_{t \in \tau} \rho_t \log \pi_{\bx}(\ba_t \g \bs_t) \left(G^{(n)}_t - v_{\bz}(\bs_t) \right),
\end{aligned}
\end{equation}

where $\rho_t$ denotes an importance weight and $G^{(n)}_t$ denotes an $n$-step bootstrap target. Its form depends on the algorithm; in <Ref>, we generate rollouts from $\pi_{\bx}$ (on-policy), in which case $\rho_t=1$ and $G^{(n)}_t = \sum_{i=0}^{(n-1)} \gamma^{i} r_{t+i+1} + \gamma^{n} v_{\bar{\bz}}(\bs_{t+n}) \, \forall t$, where $\bar{\bz}$ denotes fixed (non-differentiable) parameters. In the off-policy setting (<Ref>), $\rho$ corrects for sampling bias and $G_t^{(n)}$ is similarly adjusted.

§.§ A non-stationary and non-episodic grid world

Non-stationary grid-world (<Ref>). Left: Comparison of total returns under an actor-critic agent over 50 seeds. Right: Learned entropy-regularization schedules. The figure depicts the average regularization weight ($\epsilon$) over 4 task-cycles at 6M steps in the environment.

$\varepsilon$-greedy exploration under a $Q(\lambda)$-agent.

We begin with a tabular grid-world with two items to collect. Once an item is collected, it is randomly re-spawned. One item yields a reward of $+1$ and the other a reward of $-1$. The reward is flipped every 100,000 steps. To succeed, a memory-less agent must efficiently re-explore the environment. We study an on-policy actor-critic agent with $\epsilon_{\text{PG}}=\epsilon_{\text{TD}}=1$. As baseline, we tune a fixed entropy-rate weight $\epsilon = \epsilon_{\text{EN}}$. We compare against agents that meta-learn $\epsilon$ online. For , we use the actor-critic loss as meta-objective ($\epsilon$ fixed), as per <Ref>. The setup is described in full in <Ref>

Our primary focus is on the effect of bootstrapping. Because this setup is fully online, we can generate targets using the most recent $L-1$ parameter updates and a final agent parameter update using $\epsilon=0$. Hence, the computational complexity of is constant in $L$ under this implementation (see <Ref>). We define the matching function as the KL-divergence between $\bx^{(K)}$ and the target, $\mu(\tilde{\bx}, \bx^{(K)}(\bw)) = \KL{\pi_{\tilde{\bx}}}{\pi_{\bx^{(K)}}}$.

<Ref> presents our main findings. Both and learn adaptive entropy-rate schedules that outperform the baseline. However, fails if $\epsilon=0$ in the meta-objective, as it becomes overly greedy (<Ref>). shows no clear benefit of longer meta-learning horizons, indicating that myopia stems from the objective itself. In contrast, exhibits greater adaptive capacity and is able to utilise greater meta-learning horizons. Too short horizons induce myopia, whereas too long prevent efficient adaptation. For a given horizon, increasing $K$ is uniformly beneficial. Finally, we find that outperforms for a given horizon without backpropagating through all updates. For instance, for $K=8$, outperforms with $K=1$ and $L=7$. Our ablation studies (<Ref>) show that increasing the target bootstrap length counters myopia; however, using the meta-learned update rule for all $L$ steps can derail meta-optimization.

Next, we consider a new form of meta-learning: learning $\varepsilon$-greedy exploration in a $Q(\lambda)$-agent (precise formulation in <Ref>). While the $\varepsilon$ parameter has a similar effect to entropy-regularization, $\varepsilon$ is a parameter applied in the behaviour-policy while acting. As it does not feature in the loss function, it is not readily optimized by existing meta-gradient approaches. In contrast, can be implemented by matching the policy derived from a target action-value function, precisely as in the actor-critic case. An implication is that can meta-learn without backpropagating through the update rule. Significantly, this opens up to meta-learning (parts of) the behaviour policy, which is hard to achieve in the setup as the behaviour policy is not used in the update rule. <Ref> shows that meta-learning $\varepsilon$-greedy exploration in this environment significantly outperforms the best fixed $\varepsilon$ found by hyper-parameter tuning. As in the actor-critic case, we find that responds positively to longer meta-learning horizons (larger $L$); see <Ref>, <Ref> for detailed results.

§.§ Atari

High-performing RL agents tend to rely on distributed learning systems to improve data efficiency [Kapturowski et al., 2018, Espeholt et al., 2018]. This presents serious challenges for meta-learning as the policy gradient becomes noisy and volatile due to off-policy estimation [Xu et al., 2018, Zahavy et al., 2020]. <Ref> suggests that can be particularly effective in this setting under the appropriate distance function. To test these predictions, we adapt the Self-Tuning Actor-Critic <cit.> to meta-learn under on the 57 environments in the Atari Arcade Learning Environment <cit.>.

Human-normalized score across the 57 games in Atari ALE. Left: per-game difference in score between and our implementation of STACX$^*$ at 200M frames. Right: Median scores over learning compared to published baselines. Shading depict standard deviation across 3 seeds.

Protocol We follow the original IMPALA setup [Espeholt et al., 2018], but we do not downsample or gray-scale inputs. Following the literature, we train for 200 million frames and evaluate agent performance by median Human Normalized Score (HNS) across 3 seeds [Espeholt et al., 2018, Xu et al., 2018, Zahavy et al., 2020].

STACX The IMPALA actor-critic agent runs multiple actors asynchronously to generate experience for a centralized learner. The learner uses truncated importance sampling to correct for off-policy data in the actor-critic update, which adjusts $\rho$ and $\hat{V}$ in <Ref>. The STACX agent [Zahavy et al., 2020] is a state-of-the-art meta-RL agent. It builds on IMPALA in two ways: (1) it introduces auxiliary tasks in the form of additional objectives that differ only in their hyper-parameters; (2) it meta-learns the hyper-parameters of each loss function (main and auxiliary). Meta-parameters are given by $\bw = (\gamma^i, \epsilon^i_{\text{PG}}, \epsilon^i_{\text{EN}}, \epsilon^i_{\text{TD}}, \lambda^i, \alpha^i )_{i=1}^{1+n}$, where $\lambda$ and $\alpha$ are hyper-parameters of the importance weighting mechanism and $n=2$ denotes the number of auxiliary tasks. STACX uses the IMPALA objective as the meta-objective with $K=1$. See <Ref> for a complete description.

We conduct ceteris-paribus comparisons that only alter the meta-objective: agent parameter updates are identical to those in STACX. When $L=1$, the target takes a gradient step on the original IMPALA loss, and hence the only difference is the form of the meta-objective; they both use the same data and gradient information. For $L>1$, the first $L-1$ steps bootstrap from the meta-learned update rule itself. To avoid overfitting, each of the $L-1$ steps use separate replay data; this extra data is not used anywhere else. To understand matching functions, we test policy matching and value matching. Policy matching is defined by $\mu(\tilde{\bx}, \bx^{(K)}(\bw)) = \KL{\pi_{\tilde{\bx}}}{\pi_{\bx^{(1)}}}$; we also test a symmetric KL-divergence (KL-S). Value matching is defined by $\mu(\tilde{\bz}, \bz^{(1)}(\bw)) \coloneqq \E{(v_{\tilde{z}} - v_{z^{(1)}})^2}$.

<Ref> presents our main comparison. with $L=1$ and policy-matching (KL) obtains a median HNS of ~$500\%$, compared to ~$350\%$ for STACX. Recall that for $L=1$, uses the same data to compute agent parameter update, target update, and matching loss; hence this is an apples-to-apples comparison. Using both policy matching and value matching (with $0.25$ weight on the latter) further improves the score to ~$520\%$ and outperforms STACX across almost all 57 games, with a few minor exceptions (left panel, <Ref>). These results are obtained without tuning hyper-parameters for . Finally, extending the meta-learning horizon by setting $L=4$ and adjusting gradient clipping from $.3$ to $.2$ obtains a score of ~$610\%$.

Ablations on Atari. Left: human normalized score decomposition of w.r.t. optimizer (SGD, RMS), matching function (L2, KL, KL & V), and bootstrap steps ($L$). with (SGD, L2, $L\!=\!1$) is equivalent to STACX. Center: episode return on Ms Pacman for different $L$. Right: distribution of episode returns over all 57 games, normalized per-game by mean and standard deviation. All results are reported between 190-200M frames over 3 independent seeds.

In <Ref>, we turn to ablations. In the left-panel, we deconstruct into STACX (i.e., ) and compare performances. We find that roughly 45% of the performance gains comes from curvature correction (given by using RMSProp in the target bootstrap). The matching function can further control curvature to obtain performance improvements, accounting for roughly 25%. Finally, increasing $L$, thereby reducing myopia, accounts for about 30% of the performance improvement. Comparing the cosine similarity between consequtive meta-gradients, we find that improves upon STACX by two orders of magnitude. Detailed ablations in <Ref>.

The center panel of <Ref> provides a deep-dive in the effect of increasing the meta-learning horizon ($L>1$) in Ms Pacman. Performance is uniformly increasing in $L$, providing further support that can increase the effective meta-horizon without increasing the number of update steps to backpropagate through. A more in-depth analysis <Ref> reveals that $K$ is more sensitive to curvature and the quality of data. However, bootstrapping only from the meta-learner for all $L$ steps can lead to degeneracy (<Ref>, <Ref>). In terms of replay (<Ref>), while standard degrades with more replay, benefits from more replay in the target bootstrap.

The right panel of <Ref> studies the effect of the matching function. Overall, joint policy and value matching exhibits best performance. In contrast to recent work [Tomar et al., 2020, Hessel et al., 2021], we do not find that reversing the KL-direction is beneficial. Using only value-matching results in worse performance, as it does not optimise for efficient policy improvements. Finally, we conduct detailed analysis of scalability in <Ref>. While is 20% slower for $K=1,L=1$ due to the target bootstrap, it is 200% faster when uses $K=4$ and uses $K=1,L=3$.

§ MULTI-TASK FEW-SHOT LEARNING

Multi-task meta-learning introduces an expectation over task objectives. is applied by computing task-specific bootstrap targets, with the meta-gradient being the expectation over task-specific matching losses. For a general multi-task formulation, see <Ref>; here we focus on the few-shot classification paradigm. Let $f_{\cD}: \cX \to \rR$ denote the negative log-likelihood loss on some data $\cD$. A task is defined as a pair of datasets $(\cD_{\tau}, \cD_{\tau}^\prime)$, where $\cD_{\tau}$ is a training set and $\cD_{\tau}^\prime$ is a validation set. In the $M$-shot-$N$-way setting, each task has $N$ classes and $\cD_{\tau}$ contains $M$ observations per class.

The goal of this experiment is to study how the objective behaves in the multi-task setting. For this purpose, we focus on the canonical MAML setup [Finn et al., 2017], which meta-learns an initialisation $\bx^{(0)}_\tau = \bw$ for SGD that is shared across a task distribution $p(\tau)$. Adaptation is defined by $\bx^{(k)}_\tau = \bx^{(k-1)}_\tau + \alpha \nabla f_{\cD_{\tau}}(\bx^{(k-1)}_\tau)$, with $\alpha \in \rR_{+}$ fixed. The meta-objective is the validation loss in expectation over the task distribution: $\mathbb{E}[{f_{\cD_{\tau}^\prime}(\bx^{(K)}_\tau(\bw))}]$. Several works have extended this setup by altering the update rule ($\varphi$) [Lee & Choi, 2018, Zintgraf et al., 2019, Park & Oliva, 2019, Flennerhag et al., 2020]. As our focus is on the meta-objective, we focus on comparisons with MAML.

MiniImagenet 5-way-5-shot meta-test performance. Left: performance as a function of meta-training batches. Center: performance as a function of wall-clock time. Right: best reported performance under each $K$. Error bars depict standard deviation across 3 seeds.

For each task, a target $\tilde{\bx}_\tau$ is bootstrapped by taking $L$ SGD steps from $\bx^{(K)}_\tau$ using validation data. The objective is the expected distance, $\mathbb{E}[\mu(\tilde{\bx}_\tau, \bx^{(K)}_\tau)]$. The KL-divergence as matching function has an interesting connection to . The target $\tilde{\bx}_\tau$ can be seen as an “expert” on task $\tau$ so that is a form of distillation [Hinton et al., 2015]. The log-likelihood loss used by is also a KL divergence, but w.r.t. a “cold” expert that places all mass on the true label. Raising the temperature in the target can allow to transfer more information [Hinton & Plaut, 1987].

Setup We use the MiniImagenet benchmark [Vinyals et al., 2016] and study two forms of efficiency: for data efficiency, we compare meta-test performance as function of the number of meta-training batches; for computational efficiency, we compare meta-test performance as a function of training time. To reflect what each method would achieve for a given computational budget, we report meta-test performance for the hyper-parameter configuration with best meta-validation performance. For , we tune the meta-learning rate $\beta \in \{10^{-3}, 10^{-4}\}$, $K\in\{1, 5, 10\}$, and options to use first-order approximations (<cit.> or <cit.>). For , we tune $\beta \in \{10^{-3}, 10^{-4}\}$, $K\in\{1,5\}$, as well as $L\in\{1,5,10\}$, and the direction of the KL.

The left panel of <Ref> presents results on data efficiency. For few meta-updates, and are on par. For 50 000 meta-updates and beyond, achieves strictly superior performance, with the performance delta increasing over meta-updates.

The central panel presents results on computational efficiency; we plot the time required to reach a given meta-test performance. This describes the relationship between performance and computational complexity. We find exhibits better scaling properties, reaching the best performance of in approximately half the time.

Finally, in the right panel, we study the effect of varying $K$. achieves higher performance for both $K=1$ and $K=5$. We allow to also use $K=10$, but this did not yield any significant gains. We conduct an analysis of the impact has on curvature and meta-gradient variance in <Ref>. To summarise, we find that significantly improves upon the meta-objective, both in terms of data efficiency, computational efficiency, and final performance.

§ CONCLUSION

In this paper, we have put forth the notion that efficient meta-learning does not require the meta-objective to be expressed directly in terms of the learner's objective. Instead, we present an alternative approach that relies on having the meta-learner match a desired target.

Here, we bootstrap from the meta-learned update rule itself to produce future targets. While using the meta-learned update rule as the bootstrap allows for an open-ended meta-learning process, some grounding is necessary.

As an instance of this approach, we study bootstrapped meta-gradients, which can guarantee performance improvements under appropriate choices of targets and matching functions that can be larger than those of standard meta-gradients. Empirically, we observe substantial improvements on Atari and achieve a new state-of-the-art, while obtaining significant efficiency gains in a multi-task meta-learning setting. We explore new possibilities afforded by the target-matching nature of the algorithm and demonstrate that it can learn to explore in an $\epsilon$-greedy $Q$-learning agent.

§.§.§ Acknowledgements

The authors would like to thank Guillaume Desjardins, Junhyuk Oh, Louisa Zintgraf, Razvan Pascanu, and Nando de Freitas for insightful feedback on earlier versions of this paper. The author are also grateful for useful feedback from anonymous reviewers, that helped improve the paper and its results. This work was funded by DeepMind.

[Abdolmaleki et al., 2018]
Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas
Heess, and Martin Riedmiller.
Maximum a Posteriori Policy Optimisation.
In International Conference on Learning Representations, 2018.

[Alet et al., 2020]
Ferran Alet, Martin F. Schneider, Tomas Lozano-Perez, and Leslie Pack
Meta-Learning Curiosity Algorithms.
In International Conference on Learning Representations, 2020.

[Amari, 1998]
Shun-Ichi Amari.
Natural Gradient Works Efficiently in Learning.
Neural computation, 100 (2):0 251–276, 1998.

[Andrychowicz et al., 2016]
Marcin Andrychowicz, Misha Denil, Sergio Gómez, Matthew W Hoffman, David
Pfau, Tom Schaul, and Nando de Freitas.
Learning to Learn by Gradient Descent by Gradient Descent.
In Advances in Neural Information Processing Systems, 2016.

[Antoniou et al., 2019]
Antreas Antoniou, Harrison Edwards, and Amos J. Storkey.
How to Train Your MAML.
In International Conference on Learning Representations, 2019.

[Balcan et al., 2019]
Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar.
Provable Guarantees for Gradient-Based Meta-Learning.
In International Conference on Machine Learning, 2019.

[Bellemare et al., 2013]
M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling.
The Arcade Learning Environment: An Evaluation Platform for General
Journal of Artificial Intelligence Research, 47:0
253–279, 2013.

[Bengio, 2000]
Yoshua Bengio.
Gradient-Based Optimization of Hyperparameters.
Neural computation, 120 (8):0 1889–1900,

[Bengio et al., 1991]
Yoshua Bengio, Samy Bengio, and Jocelyn Cloutier.
Learning a Synaptic Learning Rule.
Université de Montréal, Département d'informatique et de recherche
opérationnelle, 1991.

[Cao et al., 2019]
Y Cao, T Chen, Z Wang, and Y Shen.
Learning to Optimize in Swarms.
Advances in Neural Information Processing Systems, 2019.

[Chen et al., 2016]
Yutian Chen, Matthew W. Hoffman, Sergio Gomez Colmenarejo, Misha Denil,
Timothy P. Lillicrap, and Nando de Freitas.
Learning to learn for Global Optimization of Black Box Functions.
In Advances in Neural Information Processing Systems, 2016.

[Denevi et al., 2019]
Giulia Denevi, Dimitris Stamos, Carlo Ciliberto, and Massimiliano Pontil.
Online-Within-Online Meta-Learning.
In Advances in Neural Information Processing Systems, 2019.

[Deng et al., 2009]
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.
Imagenet: A Large-Scale Hierarchical Image Database.
In Computer Vision and Pattern Recognition, 2009.

[Espeholt et al., 2018]
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward,
Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, et al.
Impala: Scalable Distributed Deep-RL with Importance Weighted
Actor-Learner Architectures.
In International Conference on Machine Learning, 2018.

[Finn et al., 2017]
Chelsea Finn, Pieter Abbeel, and Sergey Levine.
Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks.
In International Conference on Machine Learning, 2017.

[Flennerhag et al., 2019]
Sebastian Flennerhag, Pablo G. Moreno, Neil D. Lawrence, and Andreas Damianou.
Transferring Knowledge across Learning Processes.
In International Conference on Learning Representations, 2019.

[Flennerhag et al., 2020]
Sebastian Flennerhag, Andrei A. Rusu, Razvan Pascanu, Francesco Visin, Hujun
Yin, and Raia Hadsell.
Meta-Learning with Warped Gradient Descent.
In International Conference on Learning Representations, 2020.

[Grant et al., 2018]
Erin Grant, Chelsea Finn, Sergey Levine, Trevor Darrell, and Thomas L.
Recasting Gradient-Based Meta-Learning as Hierarchical Bayes.
In International Conference on Learning Representations, 2018.

[Grill et al., 2020]
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre
Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan
Guo, Mohammad Gheshlaghi Azar, Bilal Piot, koray kavukcuoglu, Remi Munos, and
Michal Valko.
Bootstrap Your Own Latent: A New Approach to Self-Supervised
In Advances in Neural Information Processing Systems, 2020.

[Guo et al., 2020]
Zhaohan Daniel Guo, Bernardo Avila Pires, Bilal Piot, Jean-Bastien Grill,
Florent Altché, Rémi Munos, and Mohammad Gheshlaghi Azar.
Bootstrap Latent-Predictive Representations for Multitask
Reinforcement Learning.
In International Conference on Machine Learning, 2020.

[Hessel et al., 2021]
Matteo Hessel, Ivo Danihelka, Fabio Viola, Arthur Guez, Simon Schmitt, Laurent
Sifre, Theophane Weber, David Silver, and Hado van Hasselt.
Muesli: Combining Improvements in Policy Optimization.
arXiv preprint arXiv:2104.06159, 2021.

[Hinton et al., 2015]
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.
Distilling the Knowledge in a Neural Network.
arXiv preprint arXiv:1503.02531, 2015.

[Hinton & Plaut, 1987]
Geoffrey E. Hinton and David C. Plaut.
Using Fast Weights to Deblur Old Memories.
In Cognitive Science Society, 1987.

[Hochreiter et al., 2001]
Sepp Hochreiter, A. Steven Younger, and Peter R. Conwell.
Learning To Learn Using Gradient Descent.
In International Conference on Artificial Neural Networks,

[Jerfel et al., 2019]
Ghassen Jerfel, Erin Grant, Tom Griffiths, and Katherine A Heller.
Reconciling Meta-Learning and Continual Learning with Online
Mixtures of Tasks.
In Advances in Neural Information Processing Systems, 2019.

[Jouppi et al., 2017]
Norman P Jouppi, Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal,
Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, and Al Borchers.
In-Datacenter Performance Analysis of a Tensor Processing Unit.
In International Symposium on Computer Architecture, 2017.

[Kakade, 2001]
Sham M Kakade.
A Natural Policy Gradient.
In Advances in Neural Information Processing Systems, 2001.

[Kapturowski et al., 2018]
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney.
Recurrent Experience Replay in Distributed Reinforcement Learning.
In International Conference on Learning Representations, 2018.

[Khodak et al., 2019]
Mikhail Khodak, Maria-Florina F Balcan, and Ameet S Talwalkar.
Adaptive Gradient-Based Meta-Learning Methods.
Advances in Neural Information Processing Systems, 2019.

[Kirsch et al., 2019]
Louis Kirsch, Sjoerd van Steenkiste, and Jürgen Schmidhuber.
Improving Generalization in Meta Reinforcement Learning Using
Learned Objectives.
arXiv preprint arXiv:1910.04098, 2019.

[Lee & Choi, 2018]
Yoonho Lee and Seungjin Choi.
Gradient-Based Meta-Learning with Learned Layerwise Metric and
In International Conference on Machine Learning, 2018.

[Lv et al., 2017]
Kaifeng Lv, Shunhua Jiang, and Jian Li.
Learning Gradient Descent: Better Generalization and Longer
In International Conference on Machine Learning, 2017.

[Machado et al., 2018]
Marlos C. Machado, Marc G. Bellemare, Erik Talvitie, Joel Veness, Matthew
Hausknecht, and Michael Bowling.
Revisiting the Arcade Learning Environment: Evaluation Protocols and
Open Problems for General Agents.
Journal of Artificial Intelligence Research, 61:0
523–562, 2018.

[Maclaurin et al., 2015]
Dougal Maclaurin, David Duvenaud, and Ryan Adams.
Gradient-Based Hyperparameter Optimization Through Reversible
In International conference on machine learning, pp.  2113–2122. PMLR, 2015.

[Metz et al., 2019]
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha
Understanding and Correcting Pathologies in the Training of Learned
In International Conference on Machine Learning, 2019.

[Mnih et al., 2013]
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis
Antonoglou, Daan Wierstra, and Martin Riedmiller.
Playing Atari with Deep Reinforcement Learning.
arXiv preprint arXiv:1312.5602, 2013.

[Nichol et al., 2018]
Alex Nichol, Joshua Achiam, and John Schulman.
On First-Order Meta-Learning Algorithms.
arXiv preprint ArXiv:1803.02999, 2018.

[Oh et al., 2020]
Junhyuk Oh, Matteo Hessel, Wojciech M Czarnecki, Zhongwen Xu, Hado P van
Hasselt, Satinder Singh, and David Silver.
Discovering Reinforcement Learning Algorithms.
In Advances in Neural Information Processing Systems,
volume 33, 2020.

[Park & Oliva, 2019]
Eunbyung Park and Junier B Oliva.
In Advances in Neural Information Processing Systems, 2019.

[Pascanu & Bengio, 2014]
Razvan Pascanu and Yoshua Bengio.
Revisiting Natural Gradient for Deep Networks.
In International Conference on Learning Representations, 2014.

[Peng & Williams, 1994]
Jing Peng and Ronald J. Williams.
Incremental Multi-Step Q-Learning.
In International Conference on Machine Learning, 1994.

[Raghu et al., 2020]
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals.
Rapid Learning or Feature Reuse? Towards Understanding the
Effectiveness of MAML.
In International Conference on Learning Representations, 2020.

[Ravi & Larochelle, 2017]
Sachin Ravi and Hugo Larochelle.
Optimization as a Model for Few-Shot Learning.
In International Conference on Learning Representations, 2017.

[Real et al., 2020]
Esteban Real, Chen Liang, David R. So, and Quoc V. Le.
AutoML-Zero: Evolving Machine Learning Algorithms From Scratch.
In International Conference on Machine Learning, 2020.

[Rusu et al., 2015]
Andrei A Rusu, Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins,
James Kirkpatrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and
Raia Hadsell.
Policy Distillation.
arXiv preprint arXiv:1511.06295, 2015.

[Rusu et al., 2019]
Andrei A. Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu,
Simon Osindero, and Raia Hadsell.
Meta-Learning with Latent Embedding Optimization.
In International Conference on Learning Representations, 2019.

[Schmidhuber, 1987]
Jürgen Schmidhuber.
Evolutionary Principles in Self-Referential Learning.
PhD thesis, Technische Universität München, 1987.

[Schmidhuber, 1993]
Jürgen Schmidhuber.
A 'self-referential' weight matrix.
In International Conference on Artificial Neural Networks,
pp.  446–450. Springer, 1993.

[Schmitt et al., 2020]
Simon Schmitt, Matteo Hessel, and Karen Simonyan.
Off-Policy Actor-Critic with Shared Experience Replay.
In International Conference on Machine Learning, 2020.

[Schraudolph, 1999]
Nicol N. Schraudolph.
Local Gain Adaptation in Stochastic Gradient Descent.
In International Conference on Artificial Neural Networks,

[Schulman et al., 2015]
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp
Trust Region Policy Optimization.
In International Conference on Machine Learning, 2015.

[Schulman et al., 2017]
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.
Proximal Policy Optimization Algorithms.
arXiv preprint arXiv:1707.06347, 2017.

[Spelke & Kinzler, 2007]
Elizabeth S. Spelke and Katherine D Kinzler.
Core Knowledge.
Developmental science, 100 (1):0 89–96, 2007.

[Stadie et al., 2018]
Bradly C. Stadie, Ge Yang, Rein Houthooft, Xi Chen, Yan Duan, Yuhuai Wu, Pieter
Abbeel, and Ilya Sutskever.
Some Considerations on Learning to Explore via Meta-Reinforcement
In Advances in Neural Information Processing Systems, 2018.

[Sutton, 1988]
Richard S. Sutton.
Learning to Predict by the Methods of Temporal Differences.
Machine learning, 30 (1):0 9–44, 1988.

[Sutton et al., 1999]
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour.
Policy Gradient Methods for Reinforcement Learning with Function
In Advances in Neural Information Processing Systems,
volume 99, 1999.

[Teh et al., 2017]
Yee Whye Teh, Victor Bapst, Wojciech M Czarnecki, John Quan, James Kirkpatrick,
Raia Hadsell, Nicolas Heess, and Razvan Pascanu.
Distral: Robust Multitask Reinforcement Learning.
In Advances in Neural Information Processing Systems, 2017.

[Tomar et al., 2020]
Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh.
Mirror Descent Policy Optimization.
arXiv preprint arXiv:2005.09814, 2020.

[Triantafillou et al., 2020]
Eleni Triantafillou, Tyler Zhu, Vincent Dumoulin, Pascal Lamblin, Utku Evci,
Kelvin Xu, Ross Goroshin, Carles Gelada, Kevin Swersky, and Pierre-Antoine
Meta-Dataset: A Dataset of Datasets for Learning to Learn from Few
International Conference on Learning Representations, 2020.

[van Erven & Koolen, 2016]
Tim van Erven and Wouter M Koolen.
MetaGrad: Multiple Learning Rates in Online Learning.
In Advances in Neural Information Processing Systems, 2016.

[Vinyals et al., 2016]
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan
Matching Networks for One Shot Learning.
In Advances in Neural Information Processing Systems, 2016.

[Wang et al., 2016]
Jane X. Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z. Leibo,
Rémi Munos, Charles Blundell, Dharshan Kumaran, and Matthew Botvinick.
Learning to Reinforcement Learn.
In Annual Meeting of the Cognitive Science Society, 2016.

[Wichrowska et al., 2017]
Olga Wichrowska, Niru Maheswaranathan, Matthew W. Hoffman, Sergio Gómez
Colmenarejo, Misha Denil, Nando de Freitas, and Jascha Sohl-Dickstein.
Learned Optimizers that Scale and Generalize.
In International Conference on Machine Learning, 2017.

[Williams & Peng, 1991]
Ronald J Williams and Jing Peng.
Function Optimization using Connectionist Reinforcement Learning
Connection Science, 30 (3):0 241–268, 1991.

[Wu et al., 2018]
Yuhuai Wu, Mengye Ren, Renjie Liao, and Roger B. Grosse.
Understanding Short-Horizon Bias in Stochastic Meta-Optimization.
In International Conference on Learning Representations, 2018.

[Xu et al., 2018]
Zhongwen Xu, Hado P. van Hasselt, and David Silver.
Meta-Gradient Reinforcement Learning.
In Advances in Neural Information Processing Systems, 2018.

[Yin et al., 2020]
Mingzhang Yin, George Tucker, Mingyuan Zhou, Sergey Levine, and Chelsea Finn.
Meta-Learning without Memorization.
In International Conference on Learning Representations, 2020.

[Zahavy et al., 2020]
Tom Zahavy, Zhongwen Xu, Vivek Veeriah, Matteo Hessel, Junhyuk Oh, Hado P van
Hasselt, David Silver, and Satinder Singh.
A Self-Tuning Actor-Critic Algorithm.
Advances in Neural Information Processing Systems, 33, 2020.

[Zheng et al., 2018]
Zeyu Zheng, Junhyuk Oh, and Satinder Singh.
On Learning Intrinsic Rewards for Policy Gradient Methods.
Advances in Neural Information Processing Systems, 2018.

[Zintgraf et al., 2019]
Luisa Zintgraf, Kyriacos Shiarli, Vitaly Kurin, Katja Hofmann, and Shimon
Fast Context Adaptation via Meta-Learning.
In International Conference on Machine Learning, 2019.

Bootstrapped Meta-Learning: Appendix

§ CONTENTS

<Ref>: proofs accompanying <Ref>.

<Ref>: non-stationary Grid-World (<Ref>).

<Ref>: ALE Atari (<Ref>).

<Ref>: Multi-task meta-learning, Few-Shot Learning on MiniImagenet (<Ref>).

§ PROOFS

This section provides complete proofs for the results in <Ref>. Throughout, we assume that $(\bx^{(0)}, \bh^{(0)}, \bw)$ is given and write $\bx \coloneqq \bx^{(0)}, \, \bh \coloneqq \bh^{(0)}$. We assume that $\bh$ evolves according to some process that maps a history $H^{(k)} \coloneqq (\bx^{(0)}, \bh^{(0)}, \ldots, \bx^{(k-1)}, \bh^{(k-1)}, \bx^{(k)})$ into a new learner state $\bh^{(k)}$, including any sampling of data (c.f. <Ref>). Recall that we restrict attention to the noiseless setting, and hence updates are considered in expectation. We define the map $\bx^{(K)}(\bw)$ by

\begin{align*}
\bx^{(1)} &= \bx^{(0)} + \, \varphi\big(\bx^{(0)}, \bh^{(0)}, \bw\big)\\
\bx^{(2)} &= \bx^{(1)} + \, \varphi\big(\bx^{(1)}, \bh^{(1)}, \bw\big)\\
\vphantom{\bx^{(2)}} &\,\,\,\vdots \\
\bx^{(K)} &= \bx^{(K-1)} + \, \varphi\big(\bx^{(K-1)}, \bh^{(K-1)}, \bw\big).
\end{align*}

The derivative $\frac{\partial}{\partial \bw} \bx^{(K)}(\bw)$ differentiates through each step of this process [Hochreiter et al., 2001]. As previously stated, we assume $f$ is Lipschitz and that $\bx^{(K)}$ is Lipschitz w.r.t. $\bw$. We are now in a position to prove results from the main text. We re-state them for convenience.

Let $\bw^\prime$ be given by <Ref>. For $\beta$ sufficiently small, $f\big(\bx^{(K)}(\bw^\prime)\big) - f\big(\bx^{(K)}(\bw) \big) = -\beta {\| \nabla_x f(\bx^{(K)}) \|}_{G^T}^2 + o(\beta^2) < 0$.

Define $\bg \coloneqq \nabla_x f(\bx^{(K)}(\bw))$. The meta-gradient at $(\bx, \bh, \bw)$ is given by $\nabla_w f(\bx^{(K)}(\bw)) = D \bg$. Under <Ref>, we find $\bw^\prime = \bw - \beta D \bg$. By first-order Taylor Series Expansion of $f$ around $(\bx, \bh, \bw^\prime)$ with respect to $\bw$:

\begin{equation*}
\begin{aligned}
f\big(\bx^{(K)}(\bw^\prime) \big)
&=  f\big(\bx^{(K)}(\bw) \big) + \inp{D \bg}{\bw' - \bw} + o(\beta^2 {\| \bg \|}^2_{G^T}) \\
&=  f\big(\bx^{(K)}(\bw) \big) - \beta  \inp{D \bg}{D \bg} + o(\beta^2 {\| \bg \|}^2_{G^T}) \\
&=  f\big(\bx^{(K)}(\bw) \big) - \beta  {\| \bg \|}^2_{G^T}  + o(\beta^2 {\| \bg \|}^2_{G^T} ),
\end{aligned}
\end{equation*}

with ${\| \bg \|}_{G^T}^2 \geq 0$ by virtue of positive semi-definiteness of $G$. Hence, for $\beta^2$ small the residual vanishes and the conclusion follows.

Let $\tilde{\bw}$ be given by <Ref> for some $\xi$. The update satisfies

\begin{equation*}
f\big(\bx^{(K)}(\tilde{\bw}) \big) - f\big(\bx^{(K)}(\bw) \big) = \frac{\beta}{\alpha} \left(\mu(\tilde{\bx}, \bx^{(K)} - \alpha G^T \bg) - \mu(\tilde{\bx}, \bx^{(K)}) \right) + o(\beta(\alpha + \beta)).
\end{equation*}

For $(\alpha, \beta)$ sufficiently small, there exists infinitely many $\xi$ for which $f\big(\bx^{(K)}(\tilde{\bw})\big) - f\big(\bx^{(K)}(\bw)\big) < 0$. In particular, $\xi(\bx^{(K)}) = \bx^{(K)} - \alpha G^T \bg$ yields improvements

\begin{equation*}
f\big(\bx^{(K)}(\tilde{\bw}) \big) - f\big(\bx^{(K)}(\bw) \big) = - \frac{\beta}{\alpha} \mu(\tilde{\bx}, \bx^{(K)}) + o(\beta(\alpha + \beta)) < 0.
\end{equation*}

This is not an optimal rate; there exists infinitely many s that yield greater improvements.

The bootstrapped meta-gradient at $(\bx, \bh, \bw)$ is given by

\begin{equation*}
\nabla_w \mu\Big(\tilde{\bx}, \, \bx^{(K)}(\bw)\Big) = D \bu, \quad \text{where} \quad \bu \coloneqq {\nabla_z \mu\big(\tilde{\bx}, \, \bz \big) \Big|}_{\bz = \bx^{(K)}}.
\end{equation*}

Under <Ref>, we find $\tilde{\bw} = \bw - \beta D \bu$. Define $\bg \coloneqq \nabla_x f(\bx^{(K)})$. By first-order Taylor Series Expansion of $f$ around $(\bx, \bh, \tilde{\bw})$ with respect to $\bw$:

\begin{align}
f\big(\bx^{(K)}(\tilde{\bw}) \big)
%&=  f\big(\bx^{(K)}(\bw) \big) + \inp{D \bg}{\tilde{\bw} - \bw} + R(\tilde{\bw}, \bw ) \nonumber \\
&= f\big(\bx^{(K)}(\bw) \big) + \inp{D \bg}{\tilde{\bw} - \bw} + o(\beta^ 2\| D \bu \|_2^2) \nonumber \\
&= f\big(\bx^{(K)}(\bw) \big) - \beta  \inp{D \bg}{D \bu} + o(\beta^ 2\| D \bu \|_2^2)  \nonumber \\
&=  f\big(\bx^{(K)}(\bw) \big) - \beta  \inp{\bu}{G^T \bg} + o(\beta^ 2\| \bu \|_{G^T}^2). \label{eq:bmg-descent-ts}
\end{align}

To bound the inner product, expand $\mu(\tilde{\bx}, \, \cdot)$ around a point $\bx^{(K)} + \bd$, where $\bd \in \rR^{n_x}$, w.r.t. $\bx^{(K)}$:

\begin{equation*}
\mu(\tilde{\bx}, \bx^{(K)} + \bd) = \mu(\tilde{\bx}, \bx^{(K)}) + \left\langle \bu, \, \bd \right\rangle  + o(\| \bd \|_2^2).
\end{equation*}

Thus, choose $\bd = - \alpha G^T \bg$, for some $\alpha \in \rR_{+}$ and rearrange to get

\begin{equation*}
- \beta \inp{\bu}{G^T \bg} =
\frac{\beta}{\alpha} \left( \mu(\tilde{\bx}, \bx^{(K)}  - \alpha G^T \bg) -  \mu(\tilde{\bx}, \bx^{(K)}) \right) + o(\alpha \beta \| \bg \|_{G^T}^2).
\end{equation*}

Substitute into <Ref> to obtain

\begin{align}\label{eq:bmg-descent-fn}
f\big(\bx^{(K)}(\tilde{\bw}) \big) - f\big(\bx^{(K)}(\bw) \big)
&= \frac{\beta}{\alpha} \left(\mu(\tilde{\bx}, \bx^{(K)} - \alpha G^T \bg) - \mu(\tilde{\bx}, \bx^{(K)}) \right) \\
&+ o(\alpha \beta \| \bg \|_{G^T}^2 + \beta^2 \| \bu \|_{G^T}^2). \nonumber
\end{align}

Thus, the update comes out as the difference between to distances. The first distance is a distortion terms that measures how well the target aligns to the tangent vector $-G^T \bg$, which is the direction of steepest descent in the immediate vicinity of $\bx^{(K)}$ (c.f. <Ref>). The second term measures learning; greater distance carry more signal for meta-learning. The two combined captures the inherent trade-off in ; moving the target further away increases distortions from curvature, but may also increase the learning signal. Finally, the residual captures distortions due to curvature.

Existence. To show that there always exists a target that guarantees a descent direction, choose $\tilde{\bx} = \bx^{(K)} - \alpha G^T \bg$. This eliminates the first distance in <Ref> as the target is perfectly aligned the direction of steepest descent and we obtain

\begin{equation*}
f\big(\bx^{(K)}(\tilde{\bw}) \big) - f\big(\bx^{(K)}(\bw) \big)
= - \frac{\beta}{\alpha} \mu(\tilde{\bx}, \bx^{(K)}) + o(\beta (\alpha + \beta)).
\end{equation*}

The residual vanishes exponentially fast as $\alpha$ and $\beta$ go to $0$. Hence, there is some $(\bar{\alpha}, \bar{\beta}) \in \rR^{2}_{+}$ such that for any $(\alpha, \beta) \in (0, \bar{\alpha}) \times (0, \bar{\beta})$, $f\big(\bx^{(K)}(\tilde{\bw}) \big) - f\big(\bx^{(K)}(\bw) \big) < 0$. For any such choice of $(\alpha, \beta)$, by virtue of differentiability in $\mu$ there exists some neighborhood $N$ around $\bx^{(K)} - \alpha G^T \bg$ for which any $\tilde{\bx} \in N$ satisfy $f\big(\bx^{(K)}(\tilde{\bw}) \big) - f\big(\bx^{(K)}(\bw) \big) < 0$.

Efficiency. We are to show that, given $(\alpha, \beta)$, the set of optimal targets does not include $\tilde{\bx} = \bx^{(K)} - \alpha G^T \bg$. To show this, it is sufficient to demonstrate that show that this is not a local minimum of the right hand-side in <Ref>. Indeed,

\begin{align*}
&\nabla_{\tilde{x}} \left.\left( \frac{\beta}{\alpha} \left(\mu(\tilde{\bx}, \bx^{(K)} - \alpha G^T \bg) - \mu(\tilde{\bx}, \bx^{(K)}) \right) + o(\alpha \beta \| \bg \|_{G^T}^2 + \beta^2 \| \bu \|_{G^T}^2) \right)\right|_{\tilde{\bx} = \bx^{(K)} - \alpha G^T \bg}\\
&= -\frac{\beta}{\alpha} \nabla_{\tilde{x}} \left. \mu(\tilde{\bx}, \bx^{(K)})\right|_{\tilde{\bx} = \bx^{(K)} - \alpha G^T \bg} + \beta^2 \bo \neq \0,
\end{align*}

where $\beta^2 \bo$ is the gradient of the residual ($\| \bu \|_2^2$ depends on $\tilde{\bx}$) w.r.t. $\tilde{\bx} =  \bx^{(K)} - \alpha G^T \bg$. To complete the proof, let $\tilde{\bu}$ denote the above gradient. Construct an alternative target $\tilde{\bx}^\prime = \tilde{\bx} - \eta \tilde{\bu}$ for some $\eta \in \rR_{+}$. By standard gradient descent argument, there is some $\bar{\eta}$ such that any $\eta \in (0, \bar{\eta})$ yields an alternate target $\tilde{\bx}^\prime$ that improves over $\tilde{\bx}$.

We now prove that, controlling for scale, can yield larger performance gains than . Recall that $\xi^\alpha_G(\bx^{(K)}) = \bx^{(K)} - \alpha G^T \nabla f\bx^{(K)}$. Consider $\xi^r_G$, with  $r \coloneqq \| \nabla f(\bx^{(K)}) \|_2 / \| G^T \nabla f(\bx^{(K)}) \|_2$.

Let $\mu = \| \cdot \|_2^2 $ and $\tilde{\bx} = \xi^r_G(\bx^{(K)})$. Let $\bw^\prime$ be given by <Ref> and $\tilde{\bw}$ be given by <Ref>. For $\beta$ sufficiently small,
$f\big(\bx^{(K)}(\tilde{\bw}) \big) \leq f\big(\bx^{(K)}(\bw^\prime)\big)$, with strict inequality if $G G^T \neq G^T$.

Let $\bg \coloneqq \nabla_x f\big(\bx^{(K)}\big)$. By <Ref>, $f\big(\bx^{(K)}(\bw^\prime) \big) - f\big(\bx^{(K)}(\bw) \big) = - \beta \inp{G^T \bg}{\bg} + O(\beta^2)$. From <Ref>, with $\mu = \| \cdot \|_2^2$, $f\big(\bx^{(K)}(\tilde{\bw}) \big) - f\big(\bx^{(K)}(\bw) \big) = - r \inp{G^T \bg}{G^T \bg} + O(\beta(\alpha + \beta))$. For $\beta$ sufficiently small, the inner products dominate and we have

\begin{equation*}
f\big(\bx^{(K)}(\tilde{\bw}) \big) -
f\big(\bx^{(K)}(\bw^\prime) \big) \approx
-\beta \left(r \inp{G^T \bg}{G^T \bg} - \inp{G^T \bg}{\bg}\right).
\end{equation*}

To determine the sign of the expression in parenthesis, consider the problem

\begin{equation*}
\max_{\hphantom{x}{\bv} \in \rR^{n_x}} \, \inp{G^T \bg}{\bv} \qquad \text{s.t.} \quad \| \bv \|_2 \leq 1.
\end{equation*}

Form the Lagrangian $\cL(\bv, \lambda) \coloneqq \inp{G^T \bg}{\bv} - \lambda (\| \bv \|_2 - 1)$. Solve for first-order conditions:

\begin{equation*}
G^T \bg - \lambda \frac{\bv^*}{\| \bv^* \|_2} = 0 \implies \bv^* = \frac{\| \bv^* \|_2}{\lambda} G^T \bg.
\end{equation*}

If $\lambda = 0$, then we must have $\|\bv^*\|_2 0$, which clearly is not an optimal solution. Complementary slackness then implies $\| \bv^* \|_2 = 1$, which gives $\lambda = \| \bv^* \|_2 \|G^T \bg\|_2$ and hence $\bv^* =  G^T \bg / \| G^T \bg \|_2$. By virtue of being the maximiser, $\bv^*$ attains a higher function value than any other $\bv$ with $\| \bv \|_2 \leq 1$, in particular $\bv = \bg / \| \bg \|_2 $. Evaluating the objective at these two points gives

\begin{equation*}
\frac{\inp{G^T \bg}{G^T \bg}}{\| G^T \bg \|_2} \geq \frac{\inp{G^T \bg}{\bg}}{\| \bg \|_2} \implies
r \inp{G^T \bg}{G^T \bg} \geq \inp{G^T \bg}{\bg},
\end{equation*}

where we use that $r = \| \bg \|_2 / \| G^T \bg \|_2$ by definition. Thus $f\big(\bx^{(K)}(\tilde{\bw}) \big) \leq f\big(\bx^{(K)}(\bw^\prime) \big)$, with strict inequality if $G G^T \neq G^T$ and $G^T \bg \neq \0$.

§ NON-STATIONARY NON-EPISODIC REINFORCEMENT LEARNING

Grid-world. The agent's goal is to collect either blue or red squared by navigating the green square.

§.§ Setup

This experiment is designed to provide a controlled setting to delineate the differences between standard meta-gradients and bootstrapped meta-gradients. The environment is a $5\times5$ grid world with two objects; a blue and a red square (<Ref>). Thus, we refer to this environment as the two-colors domain. At each step, the agent (green) can take an action to move either up, down, left, or right and observes the position of each square and itself. If the agent reaches a coloured square, it obtains a reward of either $+1$ or $-1$ while the colour is randomly moved to an unoccupied location. Every 100 000 steps, the reward for each object flips. For all other transitions, the agent obtains a reward of $-0.04$. Observations are constructed by concatenating one-hot encodings of the each $x$- and $y$-coordinate of the two colours and the agent's position, with a total dimension of $2 \times 3 \times 5 = 30$ (two coordinates for each of three objects, with each one-hot vector being $5$-dimensional).

The two-colors domain is designed such that the central component determining how well a memory-less agent adapts is its exploration. Our agents can only regulate exploration through policy entropy. Thus, to converge on optimal task behaviour, the agent must reduce policy entropy. Once the task switches, the agent encounters what is effectively a novel task (due to it being memory-less). To rapidly adapt the agent must first increase entropy in the policy to cover the state-space. Once the agent observe rewarding behaviour, it must then reduce entropy to converge on task-optimal behaviour.

All experiments run on the CPU of a single machine. The agent interacts with the environment and update its parameters synchronously in a single stream of experience. A step is thus comprised of the following operations, in order: (1) given observation, agent takes action, (2) if applicable, agent update its parameters, (3) environment transitions based on action and return new observation. The parameter update step is implemented differently depending on the agent, described below.

§.§ Actor-Critic Experiments

$N$-step RL actor loop

$N$                                                                        Rollout length.
$\bx \in \rR^{n_x}$                                                        Policy parameters.
$\bs$                                                                      Environment state.
$\cB \leftarrow (\bs)$                                                       Initialise rollout.
$t=1, 2, \ldots, N$
$\ba \sim \pi_{\bx}(\bs)$                                                  Sample action.
$\bs, r \leftarrow \operatorname{env}(\bs, \ba)$                           Take a step in environment.
$\cB \leftarrow \cB \cup (\ba, r, \bs)$                                    Add to rollout.
return $\bs$, $\cB$

$K$-step online learning loop

$N, K$                                                                     Rollout length, meta-update length.
$\bx \in \rR^{n_x}$, $\bz \in \rR^{n_z}$, $\bw \in \rR^{n_w}$               Policy, value function, and meta parameters.
$\bs$                                                                      Environment state.
$k=1, 2, \ldots, K$
$\bs$, $\cB \leftarrow \operatorname{ActorLoop}(\bx, \bs, N)$              <Ref>.
$(\bx, \bz) \leftarrow \varphi((\bx, \bz), \cB, \bw)$                      Inner update step.
return $\bs$, $\bx$, $\bz$, $\cB$

Online RL with BMG

$N, K, L$                                                                  Rollout length, meta-update length, bootstrap length.
$\bx \in \rR^{n_x}$, $\bz \in \rR^{n_z}$, $\bw \in \rR^{n_w}$               Policy, value function, and meta parameters.
$\bs$                                                                      Environment state.
$\bu \leftarrow (\bx, \bz)$
$\bs, \bu^{(K)}, \_ \leftarrow \operatorname{InnerLoop}(\bu, \bw, \bs, N, K)$ $K$-step inner loop, <Ref>.
$\bs, \bu^{(K+L-1)}, \cB \leftarrow \operatorname{InnerLoop}(\bu^{(K)}, \bw, \bs, N, L-1)$ $L-1$ bootstrap, <Ref>.
$\tilde{\bu} \leftarrow \bu^{(K+L-1)} - \alpha \nabla_u \ell(\bu^{(K+L-1)}, \cB)$ Gradient step on objective $\ell$.
$\bw \leftarrow \bw - \beta \nabla_w \mu(\tilde{\bu}, \bu^{(K)}(\bw))$            BMG outer step.
$\bu \leftarrow \bu^{(K+L-1)}$                                             Continue from most resent parameters.

The first agent we evaluate is a simple actor-critic which implements a softmax policy ($\pi_{\bx}$) and a critic ($v_{\bz}$) using separate feed-forward MLPs. Agent parameter updates are done according to the actor-critic loss in <Ref> with the on-policy n-step return target. For a given parameterisation of the agent, we interact with the environment for $N=16$ steps, collecting all observations, rewards, and actions into a rollout (<Ref>). When the rollout is full, the agent update its parameters under the actor-critic loss with SGD as the optimiser (<Ref>). To isolate the effect of meta-learning, all hyper-parameters except the entropy regularization weight ($\epsilon = \epsilon_{\text{EN}}$) are fixed (<Ref>); for each agent, we sweep for the learning rate that yields highest cumulative reward within a 10 million step budget. For the non-adaptive baseline, we additionally sweep for the best regularization weight.

To meta-learn the entropy regularization weight, we introduce a small MLP with meta-parameters $\bw$ that ingests a statistic $\bt$ of the learning process—the average reward over each of the 10 most recent rollouts—and predicts the entropy rate $\epsilon_{\bw}(\bt) \in \rR_{+}$ to use in the agent's parameter update of $\bx$. To compute meta-updates, for a given horizon $T=K$ or $T=K+(L-1)$, we fix $\bw$ and make $T$ agent parameter updates to obtain a sequence $(\tau_{1}, \bx^{(1)}, \bz^{(1)}, \ldots, \tau_{T}, \bx^{(T)}, \bz^{(T)})$.

is optimised by averaging each policy and entropy loss encountered in the sequence, i.e. the meta-objective is given by $\frac{1}{T}\sum_{t=1}^T \ell^t_{\text{PG}}(\bx^{(t)}(\bw)) + \epsilon_{\text{meta}} \ell^{t}_{\text{EN}}(\bx^{(t)}(\bw))$, where $\epsilon_{\text{meta}} \in \{0, 0.1\}$ is a fixed hyper-parameter and $\ell^t$ implies that the objective is computed under $\tau_t$.

is optimised by computing the matching loss $\mu_{\tau_T}(\tilde{\bx}, \bx^{(K)}(\bw))$, where $\tilde{\bx}$ is given by $\tilde{\bx} = \bx^{(T)} - \beta \nabla_x (\ell^{T}_{\text{PG}}(\bx^{(T)}) + \epsilon_{\text{meta}} \ell^{T}_{\text{EN}}(\bx^{(T)}))$. That is to say, the “unrolls” the meta-learner for $L-1$ steps, starting from $(\bx^{(K)}, \bz^{(K)})$, and takes a final policy-gradient step ($\epsilon_{\text{meta}} = 0$ unless otherwise noted). Thus, in this setting, our exploits that the first $(L-1)$ steps have already been taken by the agent during the course of learning (<Ref>). Moreover, the final $L$th step only differs in the entropy regularization weight, and can therefore be implemented without an extra gradient computation. As such, the meta-update under exhibit no great computational overhead to the update. In practice, we observe no significant difference in wall-clock speed for a given $K$.

Fixed entropy-regularization

Meta-gradients + regularization

Bootstrapped meta-gradients

Total rewards on two-colors with actor-critics. Shading: standard deviation over 50 seeds.

Range of the entropy of a softmax-policy over time (2-colors). Each shaded area shows the difference between the entropy 3333 steps after the agent observes a new entropy and the entropy after training on the reward-function for 100000 steps. Meta-gradients without explicit entropy-regularization (left) reduce entropy over time while Bootstrapped meta-gradients (right) maintain entropy with a large enough meta-learning horizon. Averaged across 50 seeds.

Main experiment: detailed results The purpose of our main experiment <Ref> is to (a) test whether larger meta-learning horizons—particularly by increasing $L$—can mitigate the short-horizon bias, and (b) test whether the agent can learn an exploration schedule without explicit domain knowledge in the meta-objective (in the form of entropy regularization). As reported in <Ref>, we find the answer to be affirmative in both cases. To shed further light on these findings, <Ref> reports cumulative reward curves for our main experiment in <Ref>. We note that tends to collapse for any $K$ unless the meta-objective is explicitly regularized via $\epsilon_{\text{meta}}$. To characterise why fail for $\epsilon_{\text{meta}}=0$, <Ref> portrays the policy entropy range under either or . is clearly overly myopic by continually shrinking the entropy range, ultimately resulting in a non-adaptive policy.

Ablations for actor-critic agent with . Each shaded area shows the range of entropy regularization weights generated by the meta-learner. The range is computed as the difference between $\epsilon$ at the beginning and end of each reward-cycle. Left: entropy regularization weight range when $K=1$ and $L=7$. Center: entropy regularization weight range when $K=1$ and $L=1$. Right: For $K=1$ effect of increasing $L$ with or without meta-entropy regularization. Result aggregated over 50 seeds.

Total reward on two-colors with an actor-critic agent and different matching functions for . Shading: standard deviation over 50 seeds.

Ablation: meta-regularization To fully control for the role of meta-regularization, we conduct further experiments by comparing with and without entropy regularization (i.e. $\epsilon_{\text{meta}}$) in the $L$th target update step. <Ref> demonstrates that indeed suffers from myopia when $L=1$, resulting in a collapse of the entropy regularization weight range. However, increasing the meta-learning horizon by setting $L=7$ obtains a wide entropy regularization weight range. While adding meta-regularization does expand the range somewhat, the difference in total return is not statistically significant (right panel, <Ref>).

Ablation: target bootstrap Our main takes $L-1$ steps under the meta-learned update rule, i.e. the meta-learned entropy regularization weight schedule, and an $L$th policy-gradient step without entropy regularization. In this ablation, we very that taking a final step under a different update rule is indeed critical. <Ref> shows that, for $K=1$ and $L\in\{1, 7\}$, using the meta-learned update rule for all target update steps leads to a positive feedback loop that results in maximal entropy regularization, leading to a catastrophic loss of performance (right panel, <Ref>).

Ablation: matching function Finally, we control for different choices of matching function. <Ref> contrasts the mode-covering version, KL-1, with the mode-seeking version, KL-2, as well as the symmetric KL. We observe that, in this experiment, this choice is not as  significant as in other experiments. However, as in Atari, we find a the mode-covering version to perform slightly better.

§.§ Q-learning Experiments

Agent In this experiment, we test Peng's $Q(\lambda)$ [Peng & Williams, 1994] agent with $\varepsilon$-greedy exploration. The agent implements a feed-forward MLP to represent a Q-function $q_{\bx}$ that is optimised online. Thus, agent parameter update steps do not use batching but is done online (i.e. on each step). To avoid instability, we use a momentum term that maintains an Exponentially Moving Average (EMA) over the agent parameter gradient. In this experiment we fix all hyper-parameters of the update rule (<Ref>) and instead focuses on meta-learned $\varepsilon$-greedy exploration.

Results on two-colors under a $Q(\lambda)$ agent with meta-learned $\varepsilon$-greedy exploration under . Averaged over 50 seeds.

We implement in a similar fashion to the actor-critic case. The meta-learner is represented by a smaller MLP $\varepsilon_{\bw}(\cdot)$ with meta-parameters $\bw$ that ingests the last 50 rewards, denoted by $\bt$, and outputs the $\varepsilon$ to use on the current time-step. That is to say, given meta-parameters $\bw$, the agent's policy is defined by

\begin{equation*}
\pi_{\bx}(\ba \g \bs_t, \bt_t, \bw) = \begin{cases}
1-\varepsilon_{\bw}(\bt_t) + \frac{\varepsilon_{\bw}(\bt_t)}{|A|} \quad &\text{if} \quad \ba = \argmax_{\bb} q_{\bx}(\bs_t, \bb) \\[1em]
\frac{\varepsilon_{\bw}(\bt_t)}{|A|} \quad &\text{else}.
\end{cases}
\end{equation*}

Policy-matching This policy can be seen as a stochastic policy which takes the Q-maximizing action with probability $1-\varepsilon$ and otherwise picks an action uniformly at random. The level of entropy in this policy is regulated by the meta-learner. We define a by defining a target policy under $q_{\tilde{\bx}}$, where $\tilde{\bx}$ is given by taking $L$ update steps. Since there are no meta-parameters in the update rule, all $L$ steps use the same update rule. However, we define the target policy as the greedy policy

\begin{equation*}
\pi_{\tilde{\bx}}(\ba \g \bs_t) = \begin{cases}
1 \quad &\text{if} \quad \ba = \argmax_{\bb} q_{\tilde{\bx}}(\bs_t, \bb) \\[1em]
0\quad &\text{else}.
\end{cases}
\end{equation*}

The resulting update is simple: minimize the KL-divergence $\mu^\pi(\tilde{\bx}, \bx) \coloneqq \KL{\pi_{\tilde{\bx}}}{\pi_{\bx}}$ by adjusting the entropy in $\pi_{\bx}$ through $\varepsilon_{\bw}$. Thus, policy-matching under this target encourages the meta-learner to match a greedy policy-improvement operation on a target $q_{\tilde{\bx}}$ that has been trained for a further $L$ steps. More specifically, if $\argmax_{\bb} q_{\tilde{\bx}}(\bs, \bb) = \argmax_{\bb} q_{\bx}(\bs, \bb)$, so that the greedy policy improvement matches the target, then the matching loss is minimised by setting $\varepsilon=0$. If greedy policy improvement does not correspond, so that acting greedily w.r.t. $q_{\bx}$ does not match the target, then the matching loss is minimised by increasing entropy, i.e. increasing $\varepsilon$. The meta-objective is defined in terms of $\bx$ as it does not require differentiation through the update-rule.

'Value'-matching A disadvantage of policy matching is that it provides a sparse learning signal: $\varepsilon$ is increased when the target-policy differs from the current policy and decreased otherwise. The magnitude of the change depends solely on the current value of $\varepsilon$. It is therefore desirable to evaluate alternative matching functions that provide a richer signal. Inspired by value-matching for actor-critic agents, we construct a form of 'value' matching by taking the expectation over $q_{\bx}$ under the induced stochastic policy, $u_{\bx}(\bs) \coloneqq \sum_{\ba \in \cA} \pi_{\bx}(\ba \g \bs) q_{\bx}(\bs, \ba)$. The resulting matching objective is given by

\begin{equation*}
\mu^u(\tilde{\bx}, \bx) = \E{{\left(u_{\tilde{\bx}}(\bs) - u_{\bx}(\bs; \bt, \bw)\right)}^2}.
\end{equation*}

While the objective is structurally similar to value-matching, $u$ does not correspond to well-defined value-function since $q_{\bx}$ is not an estimate of the action-value of $\pi_{\bx}$.

Detailed results <Ref> shows the learned $\varepsilon$-schedules for different meta-learning horizons: if $L$ is large enough, the agent is able to increase exploration when the task switches and quickly recovers a near-optimal policy for the current cycle. <Ref> further shows that a richer matching function, in this case in the form of 'value' matching, can yield improved performance.

Two-colors hyper-parameters

Inner Learner
Optimiser     SGD

Learning rate     0.1

Batch size     16 (losses are averaged)

$\gamma$     0.99

$\mu$     $\operatorname{KL}(\pi_{\tilde{x}} || \pi_{x'})$

MLP hidden layers ($v$, $\pi$)     2

MLP feature size ($v$, $\pi$)     256

Activation Function     ReLU

Optimiser     Adam

$\epsilon$ (Adam)     $10^{-4}$

$\beta_1, \beta_2$     0.9, 0.999

Learning rate candidates     $\{3\cdot 10^{-6}, 10^{-5}, 3\cdot 10^{-5}$$, 10^{-4}, 3\cdot10^{-4}\}$

MLP hidden layers ($\epsilon$)     1

MLP feature size ($\epsilon$)     32

Activation Function     ReLU

Output Activation     Sigmoid

Inner Learner
Optimiser     Adam

Learning Rate     $3\cdot 10^{-5}$

$\epsilon$ (Adam)     $10^{-4}$

$\beta_1, \beta_2$     0.9, 0.999

Gradient EMA     0.9

$\lambda$     0.7

$\gamma$     0.99

MLP hidden layers (Q)     2

MLP feature size (Q)     256

Activation Function     ReLU

Learning Rate     $10^{-4}$

$\epsilon$ (Adam)     $10^{-4}$

$\beta_1, \beta_2$     0.9, 0.999

Gradient EMA     0.9

MLP hidden layers ($\epsilon$)     1

MLP feature size ($\epsilon$)     32

Activation Function     ReLU

Output Activation     Sigmoid

§ ATARI

Setup Hyper-parameters are reported in <Ref>. We follow the original IMPALA [Espeholt et al., 2018] setup, but do not down-sample or gray-scale frames from the environment. Following previous works [Xu et al., 2018, Zahavy et al., 2020], we treat each game level as a separate learning problem; the agent is randomly initialized at the start of each learning run and meta-learning is conducted online during learning on a single task, see <Ref>. We evaluate final performance between 190-200 million frames. All experiments are conducted with $3$ independent runs under different seeds. Each of the 57 levels in the Atari suite is a unique environment with distinct visuals and game mechanics. Exploiting this independence, statistical tests of aggregate performance relies on a total sample size per agent of $3 \times 57=171$.

Agent We use a standard feed-forward agent that received a stack of the 4 most recent frames [Mnih et al., 2013] and outputs a softmax action probability along with a value prediction. The agent is implemented as a deep neural network; we use the IMPALA network architecture without LSTMs, with larger convolution kernels to compensate for more a complex input space, and with a larger conv-to-linear projection. We add experience replay (as per [Schmitt et al., 2020]) to allow multiple steps on the target. All agents use the same number of online samples; unless otherwise stated, they also use the same number of replay samples. We ablate the role of replay data in <Ref>.

STACX The IMPALA agent introduces specific form of importance sampling in the actor critic update and while STACX largely rely on the same importance sampling mechanism, it differs slightly to facilitate the meta-gradient flow. The actor-critic update in STACX is defined by <Ref> with the following definitions of $\rho$ and $G$. Let $\bar{\rho} \geq \bar{c} \in \rR_{+}$ be given and let $\nu: \cS \times \cA \to [0, 1]$ represent the behaviour policy that generated the rollout. Given $\pi_{\bx}$ and $v_{\bar{\bz}}$, define the Leaky V-Trace target by

\begin{align*}
\eta_t &\coloneqq \pi_{\bx}(\ba_t \g \bs_t) \, / \, \nu(\ba_t \g \bs_t) \\
\rho_t &\coloneqq \alpha_{\rho} \min\{\eta_t, \bar{\rho}\} + (1-\alpha_{\rho}) \eta_t \\
c_i &\coloneqq \lambda \left(\alpha_c \min\{\eta_i, \bar{c} \} + (1-\alpha_{c}) \eta_i \right) \\
\delta_t &\coloneqq \rho_t \left(\gamma v_{\bar{\bz}}(\bs_{t+1}) + r_{t+1} - v_{\bar{\bz}}(\bs_{t})\right) \\
G^{(n)}_t &= v_{\bar{\bz}}(\bs_t) + \sum_{i=0}^{(n-1)} \gamma^{i} \left(\prod_{j=0}^{i-1} c_{t+j}\right) \delta_{t+i},
\end{align*}

with $\alpha_{\rho} \geq \alpha_{c}$. Note that—assuming $\bar{c} \geq 1$ and $\lambda=1$—in the on-policy setting this reduces to the n-step return since $\eta_t =1$, so $\rho_t=c_t=1$. The original v-trace target sets $\alpha_{\rho}=\alpha_{c}=1$.

STACX defines the main “task” as a tuple $(\pi^{0}, v^{0}, f(\cdot, \bw_0))$, consisting of a policy, critic, and an actor-critic objective (<Ref>) under Leaky V-trace correction with meta-parameters $\bw_0$. Auxiliary tasks are analogously defined tuples $(\pi^i, v^i, f(\cdot, \bw_i))$, $i \geq 1$. All policies and critics share the same feature extractor but differ in a separate MLP for each $\pi^i$ and $v^i$. The objectives differ in their hyper-parameters, with all hyper-parameters being meta-learned. Auxiliary policies are not used for acting; only the main policy $\pi^{0}$ interacts with the environment. The objective used to update the agent's parameters is the sum of all tasks (each task is weighted through $\epsilon_{\text{PG}}, \epsilon_{\text{EN}}, \epsilon_{\text{TD}}$). The objective used for the update is the original IMPALA objective under fixed hyper-parameters $\bp$ (see Meta-Optimisation in <Ref>). Updates to agent parameters and meta-parameters happen simultaneously on rollouts $\tau$. Concretely, let $\bm$ denote parameters of the feature extractor, with $(\bx_i, \bz_i)$ denoting parameters of task $i$'s policy MLP and critic MLP. Let $\bu_i \coloneqq (\bm, \bx_i, \bz_i)$ denote parameters of $(\pi^i, v^i)$, with $\bu \coloneqq (\bm, \bx_0, \bz_0, \ldots \bx_n, \bz_n)$. Let $\bw = (\bw_0, \ldots, \bw_n)$ and denote by $\bh$ auxiliary vectors of the optimiser. Given (a batch of) rollout(s) $\tau$, the STACX update is given by

\begin{align*}
\big( \bu^{(1)}, \bh^{(1)}_u \big) &= \operatorname{RMSProp}\left(\bu, \bh_u, \bg_u\right)  &&&  \bg_u &= \nabla_{u} \sum_{i=1}^n f_\tau\big(\bu_i; \bw_i\big)&&\\
\big(\bw^{(1)}, \bh^{(1)}_{w}\big) &= \operatorname{Adam}\left(\bw, \bh_w, \bg_w \right) &&& \bg_w &=  \nabla_w f_\tau\big(\bu^{(1)}_0(\bw); \bp\big).&&
\end{align*}

We use the same setup, architecture, and hyper-parameters for as for STACX unless otherwise noted; the central difference is the computation of $\bg_w$. For $L=1$, we compute the bootstrapped meta-gradient under $\mu_\tau$ on data $\tau$ by

\begin{equation*}
\bg_w = \nabla_w \mu_\tau\left(\tilde{\bu}_0, \bu^{(1)}_0(\bw)\right), \quad \text{where} \quad \big(\tilde{\bu}_0, \_\big) = \operatorname{RMSProp}\left(\bu^{(1)}_0, \bh^{(1)}_u, \nabla_u f_\tau\big(\bu^{(1)}_0; \bp \big)\right).
\end{equation*}

Note that the target uses the same gradient $\nabla_u f(\bu^{(1)}_0; \bp)$ as the outer objective in STACX; hence, does not use additional gradient information or additional data for $L=1$. The only extra computation is the element-wise update required to compute $\tilde{\bu}_0$ and the computation of the matching loss. We discuss computational considerations in <Ref>. For $L>1$, we take $L-1$ step under the meta-learned objective with different replay data in each update. To write this explicitly, let $\tau$ be the rollout data as above. Let $\tilde{\tau}^{(l)}$ denote a separate sample of only replay data used in the $l$th target update step. For $L>1$, the is described by the process

\begin{align*}
\big( \tilde{\bu}^{(1)}_0, \tilde{\bh}_{u}^{(1)}\big) &= \operatorname{RMSProp}\left(\bu^{(1)}_0, \bh_u^{(1)}, \bg_u^{(1)} \right), &&& \bg_u^{(1)} &=  \nabla_u \sum_{i=1}^n f_{ \tilde{\tau}^{(1)}}\big(\bu^{(1)}_i; \bw_i \big) &&\\
\big( \tilde{\bu}^{(2)}_0, \tilde{\bh}_{u}^{(2)}\big) &= \operatorname{RMSProp}\left(\tilde{\bu}^{(1)}_0, \tilde{\bh}_{u}^{(1)}, \tilde{\bg}^{(1)}_u\right), &&& \tilde{\bg}_u^{(1)} &=  \nabla_u \sum_{i=1}^n f_{\tilde{\tau}^{(2)}}\big(\tilde{\bu}^{(1)}_i; \bw_i \big) \\
\big(\tilde{\bu}_0, \_ \big) &= \operatorname{RMSProp}\left(\tilde{\bu}^{(L-1)}_0, \tilde{\bh}_{u}^{(L-1)}, \tilde{\bg}^{(L-1)}_u \right), &&& \tilde{\bg}_{u}^{(L-1)} &= \nabla_u f_{\tau}\big(\tilde{\bu}^{(L-1)}_0, \bp \big).&&
\end{align*}

Targets and corresponding momentum vectors are discarded upon computing the meta-gradient. This corresponds to following the meta-learned update rule for $L-1$ steps, with a final step under the IMPALA objective. We show in <Ref> that this final step is crucial to stabilise meta-learning. For pseudo-code, see <Ref>.

Matching functions are defined in terms of the rollout $\tau$ and with targets defined in terms of the main task $\bu_0$. Concretely, we define the following objectives:

\begin{align*}
\mu^{\pi}_\tau\left(\tilde{\bu}_0, \bu^{(1)}_0(\bw) \right) &= \KL{\pi_{\tilde{\bu}_0}}{\pi_{\bu^{(1)}_0(\bw)}}, \\[1em]
\mu^{v}_\tau\left(\tilde{\bu}_0, \bu^{(1)}_0(\bw) \right) &= \E{{\left(v_{\tilde{\bu}_0} - v_{\bu^{(1)}_0(\bw)}\right)}^2}, \\[1em]
\mu^{\pi + v}_\tau\left(\tilde{\bu}_0, \bu^{(1)}_0(\bw) \right) &= \mu^\pi_\tau\left(\tilde{\bu}_0, \bu^{(1)}_0(\bw) \right) + \lambda \mu^v_\tau\left(\tilde{\bu}_0, \bu^{(1)}_0(\bw) \right), \qquad \lambda=0.25, \\[1em]
\mu^{L2}\left(\tilde{\bu}_0, \bu^{(1)}_0(\bw) \right) &= {\left\| \tilde{\bu}_0 - \bu^{(1)}_0(\bw) \right\|}_2.
\end{align*}

Distributed $N$-step RL actor loop

$N$                                                                        Rollout length.
$\cR$                                                                      Centralised replay server.
$d$                                                                        Initial state method.
$c$                                                                        Parameter sync method.
$|\cB| = N$
$\cR \leftarrow \cR \cup \cB$                                            Send rollout to replay.
$\bx \leftarrow c()$                                                     Sync parameters from learner.
$\bs \leftarrow d(\bs)$                                                    Optional state reset.
$\cB \leftarrow (\bs)$                                                     Initialise rollout.
$\ba \sim \pi_{\bx}(\bs)$                                                  Sample action.
$\bs, r \leftarrow \operatorname{env}(\bs, \ba)$                           Take a step in environment.
$\cB \leftarrow \cB \cup (\ba, r, \bs)$                                    Add to rollout.

$K$-step distributed learning loop

$\cB_1, \cB_2, \ldots, \cB_K$                                              $K$ $N$-step rollouts.
$\bx \in \rR^{n_x}$, $\bz \in \rR^{n_z}$, $\bw \in \rR^{n_w}$               Policy, value function, and meta parameters.
$k=1, 2, \ldots, K$
$(\bx, \bz) \leftarrow \varphi((\bx, \bz), \cB_k, \bw)$                      Inner update step.
return $\bx$, $\bz$

Distributed RL with BMG

$N, K, L, M$                                                               Rollout length, meta-update length, bootstrap length, parallel actors.
$\bx \in \rR^{n_x}$, $\bz \in \rR^{n_z}$, $\bw \in \rR^{n_w}$               Policy, value function, and meta parameters.
$\bu \leftarrow (\bx, \bz)$
Initialise $\cR$ replay buffer                                               Collects $N$-step trajectories $\cB$ from actors.
Initialise $M$ asynchronous actors                                           Run concurrently, <Ref>.
$\{\cB^{(k)}\}_{k=1}^{K+L} \sim \cR$                                           Sample $K$ rollouts from replay.
$\bu^{(K)} \leftarrow \operatorname{InnerLoop}(\bu, \bw, \{\cB^{(k)}\}_{k=1}^K)$ $K$-step inner loop, <Ref>.
$\bu^{(K+L-1)} \leftarrow \operatorname{InnerLoop}(\bu^{(K)}, \bw, \{\cB^{(l)}\}_{l=K}^{L-1})$ $L-1$-step bootstrap, <Ref>.
$\tilde{\bu} \leftarrow \bu^{(K+L-1)} - \alpha \nabla_u \ell(\bu^{(K+L-1)}, \cB^{(K+L)})$ Gradient step on objective $\ell$.
$\bw \leftarrow \bw - \beta \nabla_w \mu(\tilde{\bu}, \bu^{(K)}(\bw))$         BMG outer step.
$\bu \leftarrow \bu^{K}$                                                       Optional: continue from $K+L-1$ update.
Send parameters $\bx$ from learner to actors.

Atari hyper-parameters

ALE [Bellemare et al., 2013]
Frame dimensions (H, W, D)                          160, 210, 3

Frame pooling                                       None

Frame grayscaling                                   None

Num. stacked frames                                 4

Num. action repeats                                 4

Sticky actions [Machado et al., 2018]               False

Reward clipping                                     $[-1, 1]$

$\gamma=0$ loss of life                             True

Max episode length                                  108 000 frames

Initial noop actions                                30

IMPALA Network [Espeholt et al., 2018]
Convolutional layers                                4

Channel depths                                      $64, 128, 128, 64$

Kernel size                                         3

Kernel stride                                       1

Pool size                                           3

Pool stride                                         2

Padding                                             'SAME'

Residual blocks per layer                           2

Conv-to-linear feature size                         $512$

STACX [Zahavy et al., 2020]
Auxiliary tasks                                     2

MLP hidden layers                                   2

MLP feature size                                    $256$

Max entropy loss value                              0.9

Unroll length                                       20

Batch size                                          18

of which from replay            12

of which is online data         6

Replay buffer size                                  10 000

LASER [Schmitt et al., 2020] KL-threshold        2

Optimiser                                           RMSProp

Initial learning rate                               $10^{-4}$

Learning rate decay interval                        200 000 frames

Learning rate decay rate                            Linear to 0

Momentum decay                                      0.99

Epsilon                                             $10^{-4}$

Gradient clipping, max norm                         0.3

$\gamma$, $\lambda$, $\bar{\rho}$, $\bar{c}$, $\alpha$      $0.995$, $1$, $1$, $1$, $1$

$\epsilon_{\text{PG}}$, $\epsilon_{\text{EN}}$, $\epsilon_{\text{TD}}$      $1$, $0.01$, $0.25$

Optimiser                                           Adam

Learning rate                                       $10^{-3}$

$\beta_1, \beta_2$                                  $0.9$, $0.999$

Epsilon                                             $10^{-4}$

Gradient clipping, max norm                         0.3

§.§ Decomposition

Atari decomposition. We report human normalized score (median, quantiles, $\frac{1}{2}$IQR) between 190-200M frames over all 57 games, with 3 independent runs for each configuration.

In this section, we decompose the agent to understand where observed gains come from. To do so, we begin by noting that—by virtue of <Ref>—STACX is a special case of under $\mu(\tilde{\bu}, \bu^{(1)}_0(\bw)) = \| \tilde{\bu} - \bu^{(1)}_0(\bw) \|_2^2$ with $\tilde{\bu} = \bu^{(1)}_0 - \frac12 \nabla_u f_\tau(\bu^{(1)}_0; \bp)$. That is to say, if the target is generated by a pure SGD step and the matching function is the squared L2 objective. We will refer to this configurations as . From this baseline—i.e. STACX—a minimal change is to retain the matching function but use RMSProp to generate the target. We refer t o this configuration as . From <Ref>, we should suspect that correcting for curvature should improve performance. While RMSProp is not a representation of the metric $G$ in the analysis, it is nevertheless providing some form of curvature correction. The matching function can then be used for further corrections.

<Ref> shows that changing the target update rule from SGD to RMSProp, thereby correcting for curvature, yields a substantial gain. This supports our main claim that can control for curvature and thereby facilitate meta-optimisation. Using the squared Euclidean distance in parameter space (akin to [Nichol et al., 2018, Flennerhag et al., 2019]) is surprisingly effective. However, it exhibits substantial volatility and is prone to crashing (c.f. <Ref>); changing the matching function to policy KL-divergence stabilizes meta-optimisation. Pure policy-matching leaves the role of the critic—i.e. policy evaluation—implicit. Having an accurate value function approximation is important to obtain high-quality policy gradients. It is therefore unsurprising that adding value matching provides a statistically significant improvement. Finally, we find that can also mitigate myopia by extending the meta-learning horizon, in our by unrolling the meta-learned update rule for $L-1$ steps. This is roughly as important as correcting for curvature, in terms of the relative performance gain.

Meta-gradient cosine similarity and variance per-game at 50-150M frames over 3 seeds.

KL     KL & V     L2     STACX

Cosine similarity     0.19 (0.02)     0.11 (0.01)     0.001 (1e-4)     0.009 (0.01)

Meta-gradient variance     0.05 (0.01)     0.002 (1e-4)     2.3e-9 (4e-9)     6.4e-4 (7e-4)

Meta-gradient norm  variance     49     68     47     44

Ms Pacman
Cosine similarity     0.11 (0.006)     0.03 (0.006)     0.002 (4e-4)     -0.005 (0.01)

Meta-gradient variance     90 (12)     0.8 (0.2)     9.6e-7 (2e-8)     0.9 (0.2)

Meta-gradient norm  variance     2.1     7.9     4.2     2.1

Star Gunner
Cosine similarity     0.13 (0.008)     0.07 (0.001)     0.003 (5e-4)     0.002 (0.02)

Meta-gradient variance     4.2 (1.1)     1.5 (2.3)     1.9e-7 (3e-7)     0.06 (0.03)

Meta-gradient norm  variance     6.1     6.6     11.7     6.5

To further support these findings, we estimate the effect has on ill-conditioning and meta-gradient variance on three games where both STACX and exhibit stable learning (to avoid confounding factors of non-stationary dynamics): Kangaroo, Star Gunner, and Ms Pacman. While the Hessian of the meta-gradient is intractable, an immediate effect of ill-conditioning is gradient interference, which we can estimate through cosine similarity between consecutive meta-gradients. We estimate meta-gradient variance on a per-batch basis. <Ref> presents mean statistics between 50M and 150M frames, with standard deviation over 3 seeds. achieves a meta-gradient cosine similarity that is generally 2 orders of magnitude larger than that of STACX. It also explicitly demonstrates that using the KL divergence as matching function results in better curvature relative to using the L2 distance. The variance of the meta-gradient is larger for BMG than for STACX (under KL). This is due to intrinsically different gradient magnitudes. To make comparisons, we report the gradient norm to gradient variance ratio, which roughly indicates signal to noise. We note that in this metric, tends to be on par with or lower than that of STACX.

§.§ Effect of Replay

Atari, learning curves on MS Pacman for $\operatorname{KL} \& V$. $L=4,R$ computes the $L$the step on only replay data. $L=4,w$ uses the meta-learned objective for the $L$th step (with $L$th step computed on online and replay data, as per default). Shading depicts standard deviation across $3$ seeds.

We find that extending the meta-learning horizon by taking more steps on the target leads to large performance improvements. To obtain these improvements, we find that it is critical to re-sample replay data for each step, as opposed to re-using the same data for each rollout. <Ref> demonstrates this for $L=4$ on MsPacman. This can be explained by noting that reusing data allows the target to overfit to the current batch. By re-sampling replay data we obtain a more faithful simulation of what the meta-learned update rule would produce in $L-1$ steps.

The amount of replay data is a confounding factor in the meta-objective. We stress that the agent parameter update is always the same in any experiment we run. That is to say, the additional use of replay data only affects the computation of the meta-objective. To control for this additional data in the meta-objective, we consider a subset of games where we see large improvements from $L>1$. We run STACX and with $L=1$, but increase the amount of replay data used to compute the meta-objective to match the total amount of replay data used in the meta-objective when $L=4$. This changes the online-to-replay ratio from $6:12$ to $6:48$ in the meta objective.

<Ref> shows that the additional replay data is not responsible for the performance improvements we see for $L=4$. In fact, we find that increasing the amount of replay data in the meta-objective exacerbates off-policy issues and leads to reduced performance. It is striking that can make use of this extra off-policy data. Recall that we use only off-policy replay data to take the first $L-1$ steps on the target, and use the original online-to-replay ratio ($6:12$) in the $L$th step. In <Ref>, we test the effect of using only replay for all $L$ steps and find that having online data in the $L$th update step is critical. These results indicate that can make effective use of replay by simulating the effect of the meta-learned update rule on off-policy data and correct for potential bias using online data.

Atari experience replay ablation. We report episode returns, normalized to be in the range $[0, \text{max return}]$ for each game for ease of comparison. Shading depicts standard deviation across $3$ seeds. $D$ denotes default configuration for $L=1$, with $L=4$ analgously defined. $R$ denotes $L=1$, but with additional replay in the meta-objective to match the amount of replay used in $L=4$.

§.§ L vs K

Given that increasing $L$ yields substantial gains in performance, it is interesting to compare against increasing $K$, the number of agent parameter updates to backpropagate through. For fair comparison, we use an identical setup as for $L>1$, in the sense that we use new replay data for each of the initial $K-1$ steps, while we use the default rollout $\tau$ for the $K$th step. Hence, the data characteristics for $K>1$ are identical to those of $L>1$.

However, an important difference arise because each update step takes $K$ steps on the agent's parameters. This means that—withing the 200 million frames budget, $K>1$ has a computational advantage as it is able to do more updates to the agent's parameters. With that said, these additional $K-1$ updates use replay data only.

<Ref> demonstrates that increasing $K$ is fundamentally different from increasing $L$. We generally observe a loss of performance, again due to interference from replay. This suggests that target bootstrapping allows a fundamentally different way of extending the meta-learning horizon. In particular, these results suggests that meta-bootstrapping allows us to use relatively poor-quality (as evidence by $K>1$) approximations to long-term consequences of the meta-learned update rule without impairing the agent's actual parameter update. Finally, there are substantial computational gains from increasing the meta-learning horizon via $L$ rather than $K$ (<Ref>).

Atari $K$ vs $L$ ablation. We report episode returns, normalized to be in the range $[0, \text{max return}]$ for each game for ease of comparison. Shading depicts standard deviation across $3$ seeds. $D$ denotes default configuration for $L=1$, with $L=4$ analogously defined. $K=2$ denotes $L=1$, but $K=2$ steps on agent parameters.

§.§ Computational characteristics

Atari: Computational characteristics as a function of network size (see <Ref>) and meta-learning horizon $H$. When $H=K$, we vary the number of update steps to backpropagate through (with $L=1$ for ). When $H=L$, we vary the number of target update steps (with $K=1$). Measurements are taken over the first 20 million learning frames on the game Pong.

IMPALA's distributed setup is implemented on a single machine with 56 CPU cores and 8 TPU [Jouppi et al., 2017] cores. 2 TPU cores are used to act in 48 environments asynchronously in parallel, sending rollouts to a replay buffer that a centralized learner use to update agent parameters and meta-parameters. Gradient computations are distributed along the batch dimension across the remaining 6 TPU cores. All Atari experiments use this setup; training for 200 millions frames takes 24 hours.

<Ref> describes the computational properties of STACX and as a function of the number of agent parameters and the meta-learning horizon, $H$. For STACX, the meta-learning horizon is defined by the number of update steps to backpropagate through, $K$. For , we test one version which holds $L=1$ fixed and varies $K$, as in for STACX, and one version which holds $K=1$ ficed and varies $L$. To control for network size, we vary the number of channels in the convolutions of the network. We use a base of channels per layer, $x = (16, 32, 32, 16)$, that we multiply by a factor $1, 2, 4$. Thus we consider networks with kernel channels $1x = (16, 32, 32, 16)$, $2x = (32, 64, 64, 32)$, and $4x = (64, 128, 128, 64)$. Our main agent uses a network size (<Ref>) equal to $4 x$. We found that larger networks would not fit into memory when $K>1$.

First, consider the effect of increasing $K$ (with $L=1$ for ). For the small network ($1x$), is roughly on par with STACX for all values of $K$ considered. However, exhibits poorer scaling in network size, owing to the additional update step required to compute the target bootstrap. For $4x$, our main network configuration, we find that is 20% slower in terms of wall-clock time. Further, we find that neither STACX nor can fit the $4x$ network size in memory when $K=8$.

Second, consider the effect of increasing $L$ with (with $K=1$). For $1x$, we observe no difference in speed for any $H$. However, increasing $L$ exhibits a dramatic improvement in scaling for $H>2$—especially for larger networks. In fact, $L=4$ exhibits a factor $2$ speed-up compared to STACX for $H=4, 4x$ and is two orders of magnitude faster for $H=8, 2x$.

§.§ Additional results

<Ref> presents per-game results learning curve for main configurations considered in this paper. <Ref> presents mean episode returns per game between 190-200 millions frames for all main configurations. Finally, we consider two variations of in the $L=1$ regime (<Ref>); one version (NS) re-computes the agent update after updating meta-parameters in a form of trust-region method. The other version (DB) exploits that the target has a taken a further update step and uses the target as new agent parameters. While NS is largely on par, interestingly, DB fails completely.

§.§ Data and hyper-parameter selection

Atari , alternative meta-update strategies. NS re-computes the agent-update the meta-update, akin to a trust-region method. DB uses the bootstrap target as the next agent parameters. Shading depicts standard deviation across 3 seeds.

We use the ALE Atari environment, publicly available at <https://github.com/mgbellemare/Arcade-Learning-Environment>, licensed under GNU GPL 2.0. Environment hyper-parameters were selected based on prior works [Mnih et al., 2013, Espeholt et al., 2018, Zahavy et al., 2020, Schmitt et al., 2020]. Network, optimisation and meta-optimisation hyper-parameters are based on the original STACX implementation and tuned for optimal performance. Our median human normalized score matches published results. For , we did not tune these hyper-parameters, except for $L>1$. In this case, we observed that unique replay data in the initial $L-1$ steps was necessary to yield any benefits. We observed a tendency to crash, and thus reduced the gradient clipping ratio from $.3$ to $.2$. For configurations that use both policy and value matching, we tuned the weight on value matching by a grid search over $\{0.25, 0.5, 0.75\}$ on Ms Pacman, Zaxxon, Wizard of Wor, and Seaquest, with $0.25$ performing best.

§ MULTI-TASK META-LEARNING

§.§ Problem Formulation

Let $p(\tau)$ denote a given task distribution, where $\tau \in \rN$ indexes a task $f^\tau$. Each task is also associated with distinct learner states $\bh_\tau$ and task parameters $\bx_\tau$, but all task learners use the same meta-learned update rule defined by meta-parameters $\bw$. Hence, the meta-learner's problem is again to learn an update rule, but now in expectation over all learning problems. The update (<Ref>) thus takes the form $\bw^\prime = \bw - \beta \nabla_w \mathbb{E}_\tau [f^\tau(\bx^{(K)}_\tau(\bw))]$, where the expectation is with respect to $(f^\tau, \bh_\tau, \bx_\tau)$ and $\bx^{(K)}_\tau(\bw)$ is the $K$-step update on task $\tau$ given $(f^\tau, \bh_\tau, \bx_\tau)$. Since $p(\tau)$ is independent of $\bw$, this update becomes $\bw^\prime = \bw - \beta  \mathbb{E}_\tau [\nabla_wf^\tau(\bx^{(K)}_\tau(\bw))]$, i.e. the single-task meta-gradient in <Ref> in expectation over the task distribution.

With that said, the expectation involves integrating over $(\bh_\tau, \bx_\tau)$. This distribution is defined differently depending on the problem setup. In few-shot learning, $\bx_\tau$ and $\bh_\tau$ are typically a shared initialisations [Finn et al., 2017, Nichol et al., 2018, Flennerhag et al., 2019] and $f^\tau$ differ in terms of the data [Vinyals et al., 2016]. However, it is possible to view the expectation as a prior distribution over task parameters [Grant et al., 2018, Flennerhag et al., 2020]. In online multi-task learning, this expectation often reduces to an expectation over current task-learning states [Rusu et al., 2015, Denevi et al., 2019].

The update is analogously defined. Given a $\xi$, define the task-specific target $\tilde{\bx}_\tau$ given $\bx^{(K)}_\tau$ by $\xi(\bx^{(K)}_\tau)$. The meta-loss takes the form $\bw^\prime = \bw - \beta \nabla_w \mathbb{E}_\tau [\mu_\tau(\tilde{\bx}_\tau, \bx^{(K)}_\tau(\bw))]$, where $\mu_\tau$ is defined on data from task $\tau$. As with the update, as the task distribution is independent of $\bw$, this simplifies to $\bw^\prime = \bw - \beta \mathbb{E}_\tau [ \nabla_w \mu_\tau(\tilde{\bx}_\tau, \bx^{(K)}_\tau(\bw))]$, where $\mu_\tau$ is the matching loss defined on task data from $\tau$. Hence, as with , the multi-task update is an expectation over the single-task update in <Ref>. See <Ref> for a detailed description.

§.§ Few-Shot MiniImagenet

Setup MiniImagenet [Vinyals et al., 2016, Ravi & Larochelle, 2017] is a sub-sample of the Imagenet dataset [Deng et al., 2009]. Specifically, it is a subset of 100 classes sampled randomly from the 1000 classes in the ILSVRC-12 training set, with 600 images for each class. We follow the standard protocol [Ravi & Larochelle, 2017] and split classes into a non-overlapping meta-training, meta-validation, and meta-tests sets with 64, 16, and 20 classes in each, respectively. The datasset is licenced under the MIT licence and the ILSVRC licence. The dataset can be obtained from <https://paperswithcode.com/dataset/miniimagenet-1>. $M$-shot-$N$-way classification tasks are sampled following standard protocol [Vinyals et al., 2016]. For each task, $M=5$ classes are randomly sampled from the train, validation, or test set, respectively. For each class, $K$ observations are randomly sampled without replacement. The task validation set is constructed similarly from a disjoint set of $L=5$ images per class. We follow the original MAML protocol for meta-training [Finn et al., 2017], taking $K$ task adaptation steps during meta-training and $10$ adaptation steps during meta testing.

Hyper-parameter sweep per computational budget.

$\beta$     $\{0.0001, 0.001\}$         $\{0.0001, 0.001\}$

$K$         $\{1, 5, 10\}$              $\{1, 5\}$

$L$         —                         $\{1, 5, 10\}$

$\mu$       —                         $\{\KL{\tilde{\bx}}{\cdot}, \KL{\cdot}{\tilde{\bx}}\}$

FOMAML      $\{$ True, False $\}$      —

ANIL        $\{$ True, False $\}$      —
Total       24      24

We study how the data-efficiency and computational efficiency of the meta-objective compares against that of the meta-objective. To this end, for data efficiency, we report the meta-test set performance as we vary the number of meta-batches each algorithm is allow for meta-training. As more meta-batches mean more meta-tasks, this metric captures how well they leverage additional data. For computational efficiency, we instead report meta-test set performace as a function of total meta-training time. This metric captures computational trade-offs that arise in either method.

For any computational budget in either regime (i.e. $N$ meta-batches or $T$ hours of training), we report meta-test set performance across 3 seeds for the hyper-configuration with best validation performance (<Ref>). This reflects the typical protocol for selecting hyper-parameters, and what each method would attain under a given budget. For both methods, we sweep over the meta-learning rate $\beta$; for shorter training runs, a higher meta-learning is critical to quickly converge. This however lead to sub-optimal performance for larger meta-training budgets, where a smaller meta-learning rate can produce better results. The main determinant for computational cost is the number of steps to backpropagate through, $K$. For , we sweep over $K\in\{1, 5\}$. For , we sweep over $K\in\{1, 5, 10\}$. We allow $K=10$ for MAML to ensure fair comparison, as can extend its effective meta-learning horizon through the target bootstrap; we sweep over $L\in\{1, 5, 10\}$. Note that the combination of $K$ and $L$ effectively lets interpolate between different computational trade-offs. Standard does not have this property, but several first-order approximations have been proposed: we allow the approach to switch from a full meta-gradient to either the FOMAML approximation [Finn et al., 2017] or the ANIL approximation [Raghu et al., 2020].

Model, compute, and shared hyper-parameters We use the standard convolutional model [Vinyals et al., 2016], which is a 4-layer convolutional model followed by a final linear layer. Each convolutional layer is defined by a $3\times3$ kernel with $32$ channels, strides of $1$, with batch normalisation, a ReLU activation and $2 \times 2$ max-pooling. We use the same hyper-parameters of optimisation and meta-optimisation as in the original MAML implementation except as specified in <Ref>. Each model is trained on a single machine and runs on a V100 NVIDIA GPU.

§.§ Analysis

Meta-training steps per second for MAML and on $5$-way-$5$-shot MiniImagenet. Standard deviation across 5 seeds in parenthesis.

$K$     $L$     $H=K+L$     MAML     BMG
1     1     2     14.3 (0.4)     12.4 (0.5)

5     6     -     6.9 (0.3)

10     11     -     4.4 (0.1)
5     1     6     4.4 (0.06)     4.2 (0.04)

5     10     -     3.2 (0.03)

10     15     -     2.5 (0.01)
10     1     11     2.3 (0.01)     2.2 (0.01)

5     15     -     1.9 (0.01)

10     20     -     1.7 (0.01)
15     -     15     1.4 (0.01)     -

20     -     20     1.1 (0.01)      -

In terms of data-efficiency, <Ref> reports best hyper-parameters for each data budget. For both and , we note that small budgets rely on fewer steps to backpropagate through and a higher learning rate. tends to prefer a higher target bootstrap in this regime. switches to backpropagation through $K>1$ sooner than , roughly around 70 000 meta-updates, while switches around 120 000 meta-updates. This accounts for why can achieve higher performance faster, as it can achieve similar performance without backpropagating through more than one update. It is worth noting that as is given larger training budgets, to prevent meta-overfitting, shorter target bootstraps generalize better. We find that other hyper-parameters are not important for overall performance.

In terms of computational efficiency, <Ref> reports best hyper-parameters for each time budget. The pattern here follows a similar trend. does btter under a lower learning rate already after $4$ hours, whereas switches after about 8 hours. This data highlights the dominant role $K$ plays in determining training time.

We compare wall-clock time per meta-training step for various values of $K$ and $L$ <Ref>.  In our main configuration, i.e. $K=5, L=10$, achieves a throughput of $2.5$ meta-training steps per second, compared to $4.4$ for MAML, making $50\%$ slower. In this setting, has an effective meta-learning horizon of $15$, whereas MAML has a horizon of $5$. For MAML to achieve an effective horizon of $15$, it's throughput would be reduced to $1.4$, instead making MAML $56\%$ slower than .

Finally, we conduct a similar analysis as on Atari (<Ref>) to study the effect has on ill-conditioning and meta-gradient variance. We estimate ill-conditioning through cosine similarity between consecutive meta-gradients, and meta-gradient variance on a per meta-batch basis. We report mean statistics for the 5-way-5-shot setup between 100 000 and 150 000 meta-gradient steps, with standard deviation over 5 independent seeds, in <Ref>.

Effect of on ill-conditioning and meta-gradient variance on $5$-way-$5$-shot MiniImagenet. Estimated meta-gradient cosine similarity ($\theta$) between consecutive gradients, meta-gradient variance ($\rV$), and meta-gradient norm to variance ratio ($\rho$). Standard deviation across 5 independent seeds.

MAML             BMG

$K$     $L$     $\theta$     $\rV$     $\rho$     $\theta$     $\rV$     $\rho$
1     1     0.17 (0.01)     0.21 (0.01)     0.02 (0.02)     0.17 (0.01)     0.0002 (5e-6)     0.59 (0.03)

0.18 (0.01)     0.001 (1e-5)      0.23 (0.01)

0.19 (0.01)     0.0003 (2e-5)      0.36 (0.01)
5     1     0.03 (0.01)     0.07 (0.009)     0.08 (0.03)     0.03 (0.005)     0.01 (9e-5)     0.84 (0.03

0.04 (0.005)     0.001 (5e-5)      0.46 (0.02)

0.05 (0.004)     0.003 (3e-5)      0.18 (0.02)

Unsurprisingly, MAML and are similar in terms of curvature, as both can have a KL-divergence type of meta-objective. obtains greater cosine similarity as $L$ increases, suggesting that can transfer more information by having a higher temperature in its target. However, exhibits substantially lower meta-gradient variance, and the ratio of meta-gradient norm to variance is an order of magnitude larger.

Supervised multi-task meta-learning with BMG

$K, L$                                        meta-update length, bootstrap length
$M, N, T$                                     meta-batch size, inner batch size, meta-training steps.
$\bx \in \rR^{n_x}$, $\bw \in \rR^{n_w}$      model and meta parameters.
$\bg \leftarrow 0$                                       Initialise meta-gradient.
$i=1, 2, \ldots, M$
$\tau \sim p(\tau)$                                  Sample task.
$\bx_\tau \leftarrow \bx$                      For MAML, set $\bx = \bw$.
$k=1, 2, \ldots, K$
$\bzeta_\tau \sim p_{\text{train}}(\bzeta \g \tau)$       Sample batch of task training data.
$\bx_\tau = \bx_\tau + \varphi(\bx_\tau, \bzeta_\tau, \bw)$  Task adaptation.
$\bx^{(K)} \leftarrow \bx$                                 $K$-step adaptation.
$l=1, 2, \ldots, L-1$
$\bzeta_\tau \sim p_{\text{test}}(\bzeta \g \tau)$       Sample batch of task test data.
$\bx_\tau = \bx_\tau + \varphi(\bx_\tau, \bzeta_\tau, \bw)$  $L-1$ step bootstrap.
$\bzeta_\tau \sim p_{\text{test}}(\bzeta \g \tau)$
final gradient step Assign target.
$\tilde{\bx}_\tau = \bx_\tau - \alpha \nabla_x \ell(\bx_\tau, \bzeta_\tau)$
$\tilde{\bx}_\tau \leftarrow \bx_\tau + \varphi(\bx_\tau, \bzeta_\tau, \bw)$
$\bg \leftarrow \bg + \nabla_w \mu(\tilde{\bx}_\tau, \bx^{(K)}(\bw))$
$\bw \leftarrow \bw - \frac{\beta}{M} \bg$         BMG outer step.

Data-efficiency: mean meta-test accuracy over 3 seeds for best hyper-parameters per data budget. $\mu=1$ corresponds to $\KL{\tilde{\bx}}{\cdot}$ and $\mu=2$ to $\KL{\cdot}{\tilde{\bx}}$.

Step (K)      $\beta$      $K$     $L$     $\mu$     Acc. (%)      $\beta$     $K$     FOMAML     ANIL      Acc. (%)

10            $10^{-3}$                         1                      10                  1         61.4            $10^{-3}$                          1                False             True          61.7

20            $10^{-3}$                         1                      10                  1         61.8            $10^{-3}$                          1                False            False          61.9

30            $10^{-3}$                         1                      10                  1         62.5            $10^{-3}$                         10                False             True          62.3

40            $10^{-3}$                         5                       1                  1         63.1            $10^{-3}$                          5                False            False          62.7

50            $10^{-3}$                         5                       1                  1         63.5            $10^{-3}$                         10                False             True          62.9

60            $10^{-3}$                         5                       1                  1         63.7            $10^{-3}$                          1                False            False          63.0

70            $10^{-3}$                         1                       1                  2         63.7            $10^{-3}$                          5                False            False          63.0

80            $10^{-3}$                         5                       1                  1         63.7            $10^{-4}$                          5                False            False          63.1

90            $10^{-3}$                         5                       1                  1         63.8            $10^{-3}$                          5                False            False          63.3

100           $10^{-3}$                         1                       1                  2         63.8            $10^{-4}$                          5                False            False          63.4

110           $10^{-3}$                         1                       1                  2         63.9            $10^{-4}$                          5                False            False          63.6

120           $10^{-4}$                         5                       5                  1         63.9            $10^{-4}$                          5                False            False          63.6

130           $10^{-4}$                         5                      10                  1         64.0            $10^{-4}$                          5                False            False          63.6

140           $10^{-4}$                         5                       5                  1         64.1            $10^{-4}$                          5                False            False          63.6

150           $10^{-4}$                         5                       5                  1         64.2            $10^{-4}$                         10                False             True          63.6

160           $10^{-4}$                         5                       5                  1         64.3            $10^{-4}$                          5                False            False          63.6

170           $10^{-4}$                         5                       5                  1         64.4            $10^{-4}$                          5                False            False          63.7

180           $10^{-4}$                         5                       5                  1         64.5            $10^{-4}$                         10                False            False          63.8

190           $10^{-4}$                         5                      10                  1         64.6            $10^{-4}$                          5                False            False          63.9

200           $10^{-3}$                         5                      10                  2         64.7            $10^{-4}$                         10                False            False          64.0

210           $10^{-4}$                         5                       1                  1         64.7            $10^{-4}$                          5                False            False          64.1

220           $10^{-4}$                         5                       5                  1         64.7            $10^{-4}$                         10                False            False          64.2

230           $10^{-4}$                         5                       5                  1         64.8            $10^{-4}$                          5                False            False          64.2

240           $10^{-4}$                         5                       1                  2         64.8            $10^{-4}$                          5                False            False          64.1

250           $10^{-4}$                         5                       5                  1         64.9            $10^{-4}$                          5                False            False          64.1

260           $10^{-4}$                         5                       1                  1         64.9            $10^{-4}$                          5                False            False          64.0

270           $10^{-4}$                         5                       1                  1         64.8            $10^{-4}$                          5                False            False          63.9

280           $10^{-4}$                         5                       1                  1         64.8            $10^{-4}$                          5                False            False          63.8

290           $10^{-4}$                         5                       1                  1         64.7            $10^{-4}$                          5                False            False          63.8

300           $10^{-4}$                         5                       5                  1         64.7            $10^{-4}$                          5                False            False          63.8

Computational-efficiency: mean meta-test accuracy over 3 seeds for best hyper-parameters per time budget. $\mu=1$ corresponds to $\KL{\tilde{\bx}}{\cdot}$ and $\mu=2$ to $\KL{\cdot}{\tilde{\bx}}$.

Time (h)      $\beta$      $K$     $L$     $\mu$     Acc. (%)      $\beta$     $K$     FOMAML     ANIL      Acc. (%)

1                    $10^{-3}$                       1                       1                  2         63.5            $10^{-3}$                        1                False            False          63.0

2                    $10^{-3}$                       1                       1                  2         63.6            $10^{-3}$                       10                False             True          63.0

3                    $10^{-3}$                       5                       1                  1         63.7            $10^{-3}$                        5                False            False          63.0