summaries: The paper is concerned with meta reinforcement learning. The author(s) introduced a framework for learning high-order derivatives of value functions using off-policy evaluation. Specifically, the author(s) proposed to adopt existing off-policy evaluation methods to derive the value estimator and then take the derivative with respect to the target parameters to construct the estimate. This technique is further adopted to implement meta reinforcement learning.  This paper considers meta-RL with gradient-based adaptations, which relies heavily on the estimation of the Hessians of value functions. Though there are previous approaches that focus on unbiased/biased estimations of Hessian. This paper gives a unified view for estimating higher-order derivatives of value functions, through the lens of off-policy evaluation. This subsumes several previous works, also sheds some light on the bias-variance tradeoff of the estimate. Empirically, the new proposed second-order estimate is also incorporated in meta-RL algorithms to showcase the empirical efficiency.  This paper uses Huang and Jiang (2020) to talk about gradient-based meta learning in reinforcement learning using the language of off-policy evaluation. The logical connection behind those concepts stands from the fact that policy gradient methods in reinforcement learning are in fact instances of the likelihood ratio derivative estimator, which itself stems from important sampling. Proposition 3.2 and 3.3 are obtained from Huang and Jiang. Proposition 3.1 tries to extend their results to talk about higher order derivatives. The author's finally propose to use ideas from Taylor policy optimization from Tang et al. (2020) as a variance reduction method within the doubly robust policy gradient framework of Huang and Jiang.    The paper uses the recently developed framework of Taylor expansions for value functions (ref [29] in the paper), expands the results, and shows how they could be applied to Off-Policy Evaluation, and by a non-trivial extension to meta-learning. The main algorthmic contribution of the paper is the application of the ideas to meta-learning, but I feel the main contribution is a conceptual one, further developing the ideas from [29] and drawing theoretical connections between OPE and meta-learning.  The paper includes an experimental section demonstrating marginal improvement over baselines in several domains.
abstractText: Model-agnostic meta-reinforcement learning requires estimating the Hessian matrix of value functions. This is challenging from an implementation perspective, as repeatedly differentiating policy gradient estimates may lead to biased Hessian estimates. In this work, we provide a unifying framework for estimating higherorder derivatives of value functions, based on off-policy evaluation. Our framework interprets a number of prior approaches as special cases and elucidates the bias and variance trade-off of Hessian estimates. This framework also opens the door to a new family of estimates, which can be easily implemented with auto-differentiation libraries, and lead to performance gains in practice. We open source the code to reproduce our results1.
authors.name: Yunhao Tang
authors.name: Tadashi Kozuno
authors.name: Mark Rowland
references.authors: Volodymyr Mnih Koray Kavukcuoglu David Silver Alex Graves Ioannis Antonoglou Daan Wierstra Martin Riedmiller
references.title: Playing atari with deep reinforcement learning
references.venue: arXiv preprint arXiv:1312.5602,
references.authors: David Silver Aja Huang Chris J Maddison Arthur Guez Laurent Sifre George Van Den Driessche Julian Schrittwieser Ioannis Antonoglou Veda Panneershelvam Marc Lanctot
references.title: Mastering the game of go with deep neural networks and tree
references.venue: search. nature,
references.authors: Sergey Levine Chelsea Finn Trevor Darrell Pieter Abbeel
references.title: End-to-end training of deep visuomotor policies
references.venue: The Journal of Machine Learning Research,
references.authors: Chelsea Finn Pieter Abbeel Sergey Levine
references.title: Model-agnostic meta-learning for fast adaptation of deep networks
references.venue: In International Conference on Machine Learning,
references.authors: Ziyu Wang Tom Schaul Matteo Hessel Hado Van Hasselt Marc Lanctot Nando De Freitas
references.title: Dueling network architectures for deep reinforcement learning
references.venue: arXiv preprint arXiv:1511.06581,
references.authors: Yan Duan John Schulman Xi Chen Peter L Bartlett Ilya Sutskever Pieter Abbeel
references.title: Rl2: Fast reinforcement learning via slow reinforcement learning
references.venue: arXiv preprint arXiv:1611.02779,
references.authors: Rein Houthooft Richard Y Chen Phillip Isola Bradly C Stadie Filip Wolski Jonathan Ho Pieter Abbeel
references.title: Evolved policy gradients
references.venue: arXiv preprint arXiv:1802.04821,
references.authors: Junhyuk Oh Matteo Hessel Wojciech M Czarnecki Zhongwen Xu Hado van Hasselt Satinder Singh David Silver
references.title: Discovering reinforcement learning algorithms
references.venue: arXiv preprint arXiv:2007.08794,
references.authors: Zhongwen Xu Hado van Hasselt Matteo Hessel Junhyuk Oh Satinder Singh David Silver
references.title: Meta-gradient reinforcement learning with an objective discovered online
references.venue: arXiv preprint arXiv:2007.08433,
references.authors: Kate Rakelly Aurick Zhou Chelsea Finn Sergey Levine Deirdre Quillen
references.title: Efficient off-policy meta-reinforcement learning via probabilistic context variables
references.venue: In International conference on machine learning,
references.authors: Luisa Zintgraf Kyriacos Shiarlis Maximilian Igl Sebastian Schulze Yarin Gal Katja Hofmann Shimon Whiteson
references.title: Varibad: A very good method for bayes-adaptive deep rl via metalearning
references.authors: Zhongwen Xu Hado P van Hasselt David Silver
references.title: Meta-gradient reinforcement learning
references.venue: In Advances in neural information processing systems,
references.authors: Tom Zahavy Zhongwen Xu Vivek Veeriah Matteo Hessel Junhyuk Oh Hado van Hasselt David Silver Satinder Singh
references.title: A self-tuning actor-critic algorithm
references.venue: arXiv preprint arXiv:2002.12928,
references.authors: Pedro A Ortega Jane X Wang Mark Rowland Tim Genewein Zeb Kurth-Nelson Razvan Pascanu Nicolas Heess Joel Veness Alex Pritzel Pablo Sprechmann
references.title: Meta-learning of sequential strategies
references.authors: Richard S Sutton David A McAllester Satinder P Singh Yishay Mansour
references.title: Policy gradient methods for reinforcement learning with function approximation
references.venue: In Advances in neural information processing systems,
references.authors: Kavosh Asadi Michael L Littman
references.title: An alternative softmax operator for reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: James Bradbury Roy Frostig Peter Hawkins Matthew James Johnson Chris Leary Dougal Maclaurin George Necula Adam Paszke Jake VanderPlas Skye Wanderman-Milne Qiao Zhang
references.title: JAX: composable transformations of Python+NumPy programs, 2018
references.authors: Adam Paszke Sam Gross Soumith Chintala Gregory Chanan Edward Yang Zachary DeVito Zeming Lin Alban Desmaison Luca Antiga Adam Lerer
references.title: Automatic differentiation in pytorch
references.authors: Hao Liu Richard Socher Caiming Xiong
references.title: Taming maml: Efficient unbiased metareinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: Jakob Foerster Gregory Farquhar Maruan Al-Shedivat Tim Rocktäschel Eric Xing Shimon Whiteson
references.title: Dice: The infinitely differentiable monte carlo estimator
references.venue: In International Conference on Machine Learning,
references.authors: Gregory Farquhar Shimon Whiteson Jakob Foerster
references.title: Loaded dice: Trading off bias and variance in any-order score function gradient estimators for reinforcement
references.authors: Jingkai Mao Jakob Foerster Tim Rocktäschel Maruan Al-Shedivat Gregory Farquhar Shimon Whiteson
references.title: A baseline for any order gradient estimation in stochastic computation graphs
references.venue: In International Conference on Machine Learning,
references.authors: Jonas Rothfuss Dennis Lee Ignasi Clavera Tamim Asfour Pieter Abbeel
references.title: Promp: Proximal meta-policy search
references.venue: arXiv preprint arXiv:1810.06784,
references.authors: John Schulman Nicolas Heess Theophane Weber Pieter Abbeel
references.title: Gradient estimation using stochastic computation graphs
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Doina Precup Richard S Sutton Sanjoy Dasgupta
references.title: Off-policy temporal-difference learning with function approximation
references.venue: In ICML,
references.authors: Nan Jiang Lihong Li
references.title: Doubly robust off-policy value evaluation for reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: Sham Kakade John Langford
references.title: Approximately optimal approximate reinforcement learning
references.venue: In ICML,
references.authors: Yunhao Tang Michal Valko Rémi Munos
references.title: Taylor expansion policy optimization
references.venue: arXiv preprint arXiv:2003.06259,
references.authors: Martín Abadi Paul Barham Jianmin Chen Zhifeng Chen Andy Davis Jeffrey Dean Matthieu Devin Sanjay Ghemawat Geoffrey Irving Michael Isard
references.title: Tensorflow: A system for large-scale machine learning
references.venue: In 12th {USENIX} symposium on operating systems design and implementation ({OSDI}
references.authors: Richard S Sutton Andrew G Barto
references.title: Reinforcement learning: An introduction, volume 1
references.venue: MIT press Cambridge,
references.authors: Maruan Al-Shedivat Trapit Bansal Yuri Burda Ilya Sutskever Igor Mordatch Pieter Abbeel
references.title: Continuous adaptation via meta-learning in nonstationary and competitive environments
references.venue: arXiv preprint arXiv:1710.03641,
references.authors: Bradly C Stadie Ge Yang Rein Houthooft Xi Chen Yan Duan Yuhuai Wu Pieter Abbeel Ilya Sutskever
references.title: Some considerations on learning to explore via meta-reinforcement learning
references.venue: arXiv preprint arXiv:1803.01118,
references.authors: Vijay R Konda John N Tsitsiklis
references.title: Actor-critic algorithms. In Advances in neural information processing systems, pages 1008–1014
references.authors: Alekh Agarwal Sham M Kakade Jason D Lee Gaurav Mahajan
references.title: Optimality and approximation with policy gradient methods in markov decision processes
references.venue: In Conference on Learning Theory,
references.authors: Miroslav Dudík Dumitru Erhan John Langford Lihong Li
references.title: Doubly robust policy evaluation and optimization
references.venue: Statistical Science,
references.authors: Philip Thomas Emma Brunskill
references.title: Data-efficient off-policy policy evaluation for reinforcement learning
references.venue: In International Conference on Machine Learning,
references.authors: Jiawei Huang Nan Jiang
references.title: From importance sampling to doubly robust policy gradient
references.venue: In International Conference on Machine Learning,
references.authors: Hao Liu Yihao Feng Yi Mao Dengyong Zhou Jian Peng Qiang Liu
references.title: Action-depedent control variates for policy optimization via stein’s identity
references.venue: arXiv preprint arXiv:1710.11198,
references.authors: Cathy Wu Aravind Rajeswaran Yan Duan Vikash Kumar Alexandre M Bayen Sham Kakade Igor Mordatch Pieter Abbeel
references.title: Variance reduction for policy gradient with action-dependent factorized baselines
references.venue: arXiv preprint arXiv:1803.07246,
references.authors: George Tucker Surya Bhupatiraju Shixiang Gu Richard Turner Zoubin Ghahramani Sergey Levine
references.title: The mirage of action-dependent baselines in reinforcement learning
references.venue: In International conference on machine learning,
references.authors: Horia Mania Aurelia Guy Benjamin Recht
references.title: Simple random search provides a competitive approach to reinforcement learning
references.venue: arXiv preprint arXiv:1803.07055,
references.authors: Mark Rowland Will Dabney Rémi Munos
references.title: Adaptive trade-offs in off-policy learning
references.venue: arXiv preprint arXiv:1910.07478,
references.authors: Rémi Munos Tom Stepleton Anna Harutyunyan Marc Bellemare
references.title: Safe and efficient off-policy reinforcement learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: John Schulman Sergey Levine Pieter Abbeel Michael Jordan Philipp Moritz
references.title: Trust region policy optimization
references.venue: In International Conference on Machine Learning,
references.authors: John Schulman Filip Wolski Prafulla Dhariwal Alec Radford Oleg Klimov
references.title: Proximal policy optimization algorithms
references.venue: arXiv preprint arXiv:1707.06347,
references.authors: Lasse Espeholt Hubert Soyer Remi Munos Karen Simonyan Volodymir Mnih Tom Ward Yotam Doron Vlad Firoiu Tim Harley Iain Dunning
references.title: Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures
references.venue: arXiv preprint arXiv:1802.01561,
references.authors: Steven Kapturowski Georg Ostrovski John Quan Remi Munos Will Dabney
references.title: Recurrent experience replay in distributed reinforcement learning
references.authors: Alireza Fallah Aryan Mokhtari Asuman Ozdaglar
references.title: On the convergence theory of gradientbased model-agnostic meta-learning algorithms
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: Kaiyi Ji Junjie Yang Yingbin Liang
references.title: Multi-step model-agnostic meta-learning: Convergence and improved algorithms
references.venue: arXiv preprint arXiv:2002.07836,
references.authors: Emanuel Todorov Tom Erez Yuval Tassa
references.title: Mujoco: A physics engine for model-based control
references.venue: In Intelligent Robots and Systems (IROS),
references.authors: Diederik P Kingma Max Welling
references.title: Auto-encoding variational bayes
references.venue: arXiv preprint arXiv:1312.6114,
sections.heading: 1 Introduction
sections.text: Recent years have witnessed the success of reinforcement learning (RL) in challenging domains such as game playing [1], board games [2], and robotics control [3]. However, despite such breakthroughs, state-of-the-art RL algorithms are still plagued by sample inefficiency, as training agents requires orders of magnitude more samples than humans would experience to reach similar levels of performance [1, 2]. One hypothesis on the source of such inefficiencies is that standard RL algorithms are not good at leveraging prior knowledge, which implies that whenever presented with a new task, the algorithms must learn from scratch. On the contrary, humans are much better at transferring prior skills to new scenarios, an innate ability arguably obtained through evolution over thousand of years.
  Meta-reinforcement learning (meta-RL) formalizes the learning and transfer of prior knowledge in RL [4]. The high-level idea is to have an RL agent that interacts with a distribution of environments at meta-training time. The objective is that at meta-testing time, when the agent interacts with previously unseen environments, it can learn much faster than meta-training time. Here, faster learning is measured by the number of new samples needed to achieve a good level of performance. If an agent can achieve good performance at meta-testing time, it embodies the ability to transfer knowledge from prior experiences at meta-training time. meta-RL algorithms can be constructed in many ways, such as those based on recurrent memory [5, 6], gradient-based adaptations [4], learning loss functions [7–9], probabilistic inference of context variables [10–12], online adaptation of hyper-parameters within a single lifetime [13, 14] and so on. Some of these formulations have mathematical connections; see e.g. [15] for an in-depth discussion.
  We focus on gradient-based adaptations [4], where the agent carries out policy gradient updates [16] at both meta-training and meta-testing time. Conceptually, since meta-RL seeks to optimize the
  1https://github.com/robintyh1/neurips2021-meta-gradient-offpolicy-evaluation
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  way in which the agent adapts itself in face of new environments, it needs to differentiate through the policy gradient update itself. This effectively reduces the meta-RL problem into estimations of Hessian matrices of value functions.
  Challenges for computing Hessian matrix of value functions. To calculate Hessian matrices (or unbiased estimates thereof) for supervised learning objectives, it suffices to differentiate through gradient estimates, which can be easily implemented with auto-differentiation packages [17–19]. However, it is not the case for value functions in RL. Intuitively, this is because value functions are defined via expectations with respect to distributions that themselves depend on the policy parameters of interest, whereas in supervised learning the expectations are defined with respect to a fixed data distribution. As a result, implementations that do not take this into account may lead to estimates [4] whose bias is not properly characterized and might have a negative impact on downstream applications [20].
  Motivated by this observation, a number of prior works suggest implementation alternatives that lead to unbiased Hessian estimates [21], with potential variance reduction [22, 23, 20]; or biased estimates with small variance [24]. However, different algorithms in this space are motivated and derived in seemingly unrelated ways: for example, [21–23] derive code-level implementations within the general context of stochastic computation graphs [25]. On the other hand, [24] derives the estimates by explicitly analyzing certain terms with potentially high variance, which naturally produces bias in the final estimate. Due to apparently distinct ways of deriving estimates, it is not immediately clear how all such methods are related, and whether there could be other alternatives.
  Central contribution. We present a unified framework for estimating higher-order derivatives of value functions, based on the concept of off-policy evaluation. The main insights are summarized in Table 1, where most aforementioned prior work can be interpreted as special cases of our framework. Our framework has a few advantages: (1) it conceptually unifies a few seemingly unrelated prior methods; (2) it elucidates the bias and variance trade-off of the estimates; (3) it naturally produces new methods based on Taylor expansions of value functions [29].
  After a brief background introduction on meta-RL in Section 2, we will discuss the above aspects in detail in Section 3. From an implementation perspective, we will show in Section 4.1 that both the general framework and the new method can be conveniently implemented in auto-differentiation libraries [30, 19], making it amenable in a practical setup. Finally in Section 5, we validate important claims based on this framework with experimental insights.
sections.heading: 2 Background
sections.text: We begin with the notation and background on RL and meta-RL.
sections.heading: 2.1 Task-based reinforcement learning
sections.text: Consider a Markov decision process (MDP) with state space X and action space A. At time t ≥ 0, the agent takes action at ∈ A in state xt ∈ X , receives a reward rt and transitions to a next state xt+1 ∼ p(·|xt, at). Without loss of generality, we assume a single starting state x0. Here, we assume the reward rt = r(xt, at, g) to be a deterministic function of state-action pair (xt, at) and the task variable g ∈ G. The task variable g ∼ pG is resampled for every episode. For example, xt ∈ X is the sensory space of a running robot, at ∈ A is the control, g is the episodic target direction in which to run and r(xt, at, g) is the speed in direction g. A policy π : X → P(A) specifies a distribution over actions at each state. For convenience, we define
  the value function V π(x, g) := Eπ [ ∑∞ t=0 γ tr(xt, at, g) | x0 = x] and Q-function Qπ(x, a, g) :=
  Eπ [ ∑∞ t=0 γ tr(xt, at, g) | x0 = x, a0 = a]. Without loss of generality, we assume the policy to be smoothly parameterized as πθ with parameter θ ∈ RD. We further assume that the MDPs terminate within a finite horizon of H <∞ under any policy.
sections.heading: 2.2 Gradient-based meta-reinforcement learning
sections.text: The motivation of meta-RL is to identify a policy πθ such that given a task g, after updating the parameter from θ to θ′ with a parameter update computed under rewards r(x, a, g), the resulting policy πθ′ performs well. Formally, define U(θ, g) ∈ RD as a parameter update to θ, for example, one policy gradient ascent step. Model-agnostic meta-learning (MAML) [4] formulates meta-RL as optimizing the value function at the updated policy Eg∼pG [V πθ′ (x, g)] where θ′ = θ+U(θ, g) is the updated policy. The optimization is with respect to the initial policy parameter θ. The aim is to find θ such that it entails fast learning (or adaptation) to the environment, through the inner loop update operator U(θ, g), that leads to high-performing updated policy θ′. Consider the following problem,
  max θ
  F (θ) := Eg∼pG [V πθ′ (x0, g)] , θ′ = θ + U(θ, g). (1)
  We can decompose the meta-gradient into two terms based on the chain rule,
  ∇θF (θ) = Eg∼pG [∇θF (θ, g)] := Eg∼pG [∇θθ′∇θ′V πθ′ (x0, g)] (2)
  where∇θθ′ = I+∇θU(θ, g) ∈ RD×D is a matrix, and∇θ′V πθ′ (x0, g) is the vanilla policy gradient evaluated at the updated parameter θ′ [31]. A straightforward way to optimizing Eqn (1) is to carry out the outer loop update θ ← θ + α∇θF (θ) with learning rate α > 0.
  Policy gradient update. Following MAML [4], we focus on policy gradient update where U(θ, g) = η∇θV πθ (x0, g) for a fixed step size η > 0. The matrix ∇θU(θ, g) = η∇2θV πθ (x0, g) is the Hessian of the value function with respect to policy parameters; henceforth, we define Hθ(x0, g) := ∇2θV πθ (x0, g) ∈ RD×D.
  Estimating meta-gradients. Practical algorithms construct stochastic estimates of the metagradients using a finite number of samples. In Eqn (2), we decompose the meta-gradients into the multiplication of a Hessian matrix with a policy gradient vector. Given a fixed task variable g, a common practice of prior work is to construct the gradient estimate as the product of the Hessian estimate and the policy gradient estimate ∇̂F (θ, g) = (I + ηĤθ(x0, g))∇̂θ′V πθ′ (x0, g); see, e.g., [4, 32, 33, 24, 21–23, 20]. See Algorithm 1 for the full pseudocode for estimating meta-gradients by sampling multiple tasks. Since there is a large literature on constructing accurate estimates to policy gradient (e.g., actor-critic algorithms use baselines for variance reduction [34]), the main challenge consists in estimating the Hessian matrix accurately.
  Bias of common plug-in estimators. Common practices in meta-RL algorithms rely on the premise that if both Hessian and policy gradient estimates are unbiased, then the meta-gradient estimate is unbiased too.
  E [ Ĥθ(x0, g) ] = Hθ(x0, g),E [ ∇̂θ′V πθ′ (x0, g) ] = ∇θ′V πθ′ (x0, g)⇒ E [ ∇̂θF (θ, g) ] = ∇θF (θ, g).
  Unfortunately, this is not true. This is because the two estimates are in general correlated when the sample size is finite, leading to the bias of the overall estimate. We provide further discussions in Appendix A. For the rest of the paper, we follow practices of prior work and focus on the properties of Hessian estimates, leaving a more proper treatment of this bias to future work.
sections.heading: 3 Deriving Hessian estimates with off-policy evaluation
sections.text: Since the meta-gradient estimates are computed by averaging over task variables g ∼ pG , in the following, we focus on Hessian estimates at a single state and task variable Hθ(x, g) with a fixed g. In this section, we also drop the dependency of the value function on g, such that, e.g., V πθ (x0) ≡ V πθ (x0, g) and Q(x, a, g) ≡ Q(x, a).
sections.heading: 3.1 Off-policy evaluation: maintaining higher-order dependencies on parameters
sections.text: We assume access to data (xt, at, rt)∞t=0 generated under a behavior policy µ. Off-policy evaluation [26] consists in building estimators V̂ πθ (x, g) using the behavior data such that V̂ πθ (x) ≈ V πθ (x)
  Algorithm 1 Pseudocode for computing meta-gradients for the MAML objective for i=1,2...n do
  Sample task variable gi ∼ pG . Sample B trajectories under policy πθ; Compute B-trajectory policy gradient estimate ∇̂θV πθ (x0, gi), update parameter θ′ = θ + ∇̂θV πθ (x0, gi). Compute B-trajectory Hessian estimate Ĥθ(x0, gi) and an unbiased policy gradient estimate at θ′, i.e., ∇̂θ′V πθ (x0, g). Compute the i-th meta-gradient estimate ∇̂F (θ, gi) = ( I + ηĤθ(x0, gi) ) ∇̂θ′V πθ′ (x0, gi).
  end for Output averaged meta-gradient estimate 1n ∑n i=1 ∇̂θF (θ, gi).
  for a range of target policies πθ. Note that the estimate V̂ πθ (x) is a random variable depending on (xt, at, rt) ∞ t=0, it is also a function of θ. The approximation V̂
  πθ (x) ≈ V πθ (x) implies that V̂ πθ (x) is indicative of how the value function V πθ (x) depends on θ, and hence maintains the higher-order dependencies on θ. Throughout, we assume πθ(a|x) > 0, µ(a|x) > 0 for all (x, a) ∈ X ×A.
  Example: step-wise importance sampling (IS) estimate. As a concrete example, consider the unbiased step-wise IS estimate V̂ πθIS (x0) = ∑∞ t=0 γ t ( Πs≤tρ θ s ) rt where ρθs := πθ(as|xs)/µ(as|xs). Since the value function V πθ (x) is in general a highly non-linear function of θ (see discussions in [35]) we see that V̂ πθIS (x0) retains such dependencies via the sum of product of IS ratios.
sections.heading: 3.2 Warming up: deriving unbiased estimates with variance reduction
sections.text: We start with a general result based on the intuition above: given an estimate V̂ πθ (x) to V πθ (x), we can directly use the mth-order derivative∇mθ V̂ πθ (x) ∈ RD K
  as an estimate to∇Kθ V πθ (x). We introduce two assumptions: (A.1) V̂ πθ (x) is mth-order differentiable w.r.t. θ almost surely. (A.2)∥∥∥∇mθ V̂ πθ (x)∥∥∥∞ < M for some constant M for the order m of interest. These assumptions are fairly mild; see further details in Appendix C. The following result applies to general unbiased off-policy evaluation estimates.
  Proposition 3.1. Assume (A.1) and (A.2) are satisfied. Further assume we have an estimator V̂ πθ (x) which is unbiased (Eµ [ V̂ πθ′ (x) ] = V πθ′ (x)) for all θ′ ∈ N(θ) where N(θ) is some
  open set that contains θ. Under some additional mild conditions, the mth-order derivative of the estimate ∇mθ V̂ πθ (x0) are unbiased estimates to the mth-order derivative of the value function Eµ [ ∇mθ V̂ πθ (x) ] = ∇mθ V πθ (x) for m ≥ 1.
  Doubly-robust estimates. As a special case, we describe the doubly-robust (DR) off-policy evaluation estimator [36, 27, 37]. Assume we have access to a state-action dependent critic Q(x, a, g), and we use the notation Q(x, π(x)) := ∑ a Q(x, a)π(a|x). The DR estimate is defined recursively as follows,
  V̂ πθDR (xt) = Q(xt, πθ(xt)) + ρ θ t ( rt + γV̂ πθ DR (xt+1)−Q(xt, at) ) . (3)
  The DR estimate is unbiased for all πθ and subsumes the step-wise IS estimate as a special case when Q(x, a) ≡ 0. If the critic is properly chosen, e.g., Q(x, a) ≈ Qπθ (x, a), it can lead to significant variance reduction compared to V̂ πθIS (x0). By directly differentiating the estimate ∇mθ V̂ πθ DR (x), we derive estimators for higher-order derivatives of the value function; the result for the gradient in Proposition 3.2 was shown in [38].
  Proposition 3.2. Define πt := πθ(at|xt) and let δt := rt + γV̂ πθDR (xt+1)−Q(xt, at) be the sampled temporal difference error at time t. Note that∇θ log πt ∈ RD and∇2θ log πt ∈ RD×D. The estimates
  of higher-order derivatives can be deduced recursively, and in particular for m = 1, 2,
  ∇θV̂ πθDR (xt) = ∇θQ(xt, πθ(xt)) + ρ θ t δt∇θ log πt + γρθt∇θV̂ πθ DR (xt+1), (4)
  ∇2θV̂ πθ DR (xt) = ρ θ t δt ( ∇2θ log πt +∇θ log πt∇θ log πTt ) + γρθt∇θV̂ πθ DR (xt)∇θ log π T t
  + γρθt∇θ log πt∇θV̂ πθ DR (xt) T +∇2θQ(xt, πθ(xt)) + γρθt∇2θV̂ πθ DR (xt+1). (5)
  Bias and variance of Hessian estimates. Proposition 3.1 implies that∇θV̂πθ (x0) and∇2θV̂πθ (x0) are both unbiased. To analyze the variance, we start with m = 1: note that when on-policy µ = πt [16], ∇θV πθDR (x0) recovers a form of gradient estimates similar to actor-critic policy gradient with action-dependent baselines [39–41]; when Q(x, a) is only state dependent, ∇θV̂ πθDR (x) recovers the common policy gradient estimate with state-dependent baselines [34]. As such, the estimates are computed with potential variance reduction due to the critic. Previously, [38] started with the DR estimate and derived a more general result for the on-policy first-order case. For the Hessian estimate, we expect a similar effect of variance reduction as shown in experiments.
  Recovering prior work on estimates to higher-order derivatives. When applied to meta-RL, DiCE [21] and its follow-up variants [22, 42] can be seen as special cases of∇2θV̂ πθ DR (x) with different choices of the critic Q when evaluated on-policy µ = πθ. See Table 1 for the correspondence between prior work and their equivalent formulations under the framework of off-policy evaluation. We will discuss detailed pseudocode in Section 4.1. See also Appendix F for more details.
sections.heading: 3.3 Trading-off bias and variance with Taylor expansions
sections.text: Starting from unbiased off-policy evaluation estimates V̂ πθ (x), we can directly construct unbiased estimates to higher-order derivatives by differentiating the original estimate to obtain ∇mθ V̂ πθ (x). However, unbiased estimates can have large variance. Though it is possible to reduce variance through the critic, as we will show experimentally, this is not enough to counter the high variance due to products of IS ratios. This leads us to consider trading off bias with variance [43].
  Since we postulate that the products of IS ratios lead to high variance, we might seek to control the number of IS ratios in the estimate. We briefly introduce Taylor expansion policy optimization (TayPO) [29], a natural framework to control for the number of IS ratios in the value estimate.
  Taylor expansions of value functions. Consider the value function V πθ (x0) as a function of πθ. Using the idea of Taylor expansions, we can express V πθ (x0) as a sum of polynomials of πθ − µ. We start by defining the K th-order increment as Uπθ0 (x0) = V
  µ(x0), which does not contain any IS ratio (zeroth order); and for K ≥ 1,
  UπθK (x0) := Eµ [ ∞∑ t1=0 ∞∑ t2=t1+1 ... ∞∑ tK=tK−1+1 γtK ( ΠKi=1(ρ θ ti − 1) ) Qµ(xtK , atK )︸ ︷︷ ︸
  Û πθ K (x0)
  ] . (6)
  Intuitively, the K th-order increment only contains product of K IS ratios. Equation (6) also yields a natural sample-based estimate ÛπθK (x0), which we will discuss later. The K
  th-order Taylor expansion is defined as the partial sum of increments V πθK (x0) := ∑K k=0 U πθ k (x0). Since V πθ K (x0) consists of products of up to K IS ratios, it is effectively the K th-order Taylor expansion of the value function. The properties are summarized as follows.
  Proposition 3.3. (Adapted from Theorem 2 of [29].) Define ∥π − µ∥1 := maxx ∑
  a |π(a|x) − µ(a|x)|. Let C be a constant and ε = 1−γγ . Then the following holds for all K ≥ 0,
  V πθ (x0, g) = V πθ K (x0, g)︸ ︷︷ ︸
  K-th order expansion
  +C(∥πθ − µ∥1 /ε) K+1︸ ︷︷ ︸
  residual
  , (7)
  If ∥πθ − µ∥1 < ε, then V πθ (x0) = limK→∞ V πθ K (x0) = Eµ [ ∑∞ k=0 U πθ k (x0)].
  Sample-based estimates to Taylor expansions of value functions. As shown in Equation (6), ÛπθK (x0) is an unbiased estimate to U πθ K (x0). We can naturally define the sample-based estimate to the K th-order Taylor expansion, called the TayPO-K estimate,
  V̂ πθK (x0) := K∑ k=0 Ûπθk (x0). (8)
  The expression of Ûπθ (x0) contains O(TK) terms if the trajectory is of length T . Please refer to Appendix E for further details on computing the estimates in linear time O(T ) with sub-sampling. Note that V̂ πθK (x0) is a sample-based estimate whose bias against the value function is controlled by the residual term which decays exponentially when πθ and µ are close. Similar to how we derived the unbiased estimate∇mθ V̂ πθ DR (x), we can differentiate through the TayPO-K value estimate to produce estimates to higher-order derivatives∇mθ V̂ πθ K (x0).
  Bias and variance of Hessian estimates. TayPO-K trades-off bias and variance with choices of K. To understand the variance, note that TayPO-K limits the number multiplicative IS ratios to be K. Though it is difficult to compute the variance, we argue that the variance generally increases with K as the number of IS ratios increase [26, 27, 44]. We characterize the bias of TayPO-K as follows.
  Proposition 3.4. Assume (A.1) and (A.2) hold. Also assume ∥πθ − µ∥1 ≤ ε = (1− γ)/γ. For any tensor x, define ∥x∥∞ := maxi |x[i]|. The K th-order TayPO objective produces the following bias in estimating high-order derivatives,∥∥∥Eµ [∇mθ V̂ πθK ] (x0)−∇mθ V πθ (x0)∥∥∥∞ ≤ ∞∑ k=K+1 ∥∇mθ U πθ k (x0)∥∞ . (9)
  Hence the upper bound for the bias decreases as K increases. Importantly, when on-policy µ = πθ, the K th-order TayPO objective preserves up to K th-order derivatives for any K ≥ 0,
  Eµ [ ∇mθ V̂ πθ K (x0) ] = ∇mθ V πθ (x0),∀m ≤ K. (10)
  Though IS ratios ρθt evaluate to 1 when on-policy, they maintain the parameter dependencies in differentiations. As such, higher-order expansions contains products of IS ratios of higher orders, and maintains the high-order dependencies on parameters more accurately. There is a clear trade-off between bias and variance mediated by K. When K increases, the higher-order derivatives are maintained more accurately in expectation, leading to less bias. However, the variance increases too.
  Recovering prior work as special cases. Recently, [24] proposed a low variance curvature (LVC) Hessian estimate. This estimate is equivalent to the TayPO-K estimate with K = 1. As also noted by [24], their objective function bears similarities to first-order policy search algorithms [28, 45, 46], which have in fact been interpreted as first-order special cases of ∇θV̂ πθK (x) with K = 1 [29]. Importantly, based on Proposition 3.4, the LVC estimate only maintains the first-order dependency perfectly but introduces bias when approximating the Hessian, even when on-policy.
  Limitations. Though the above framework interprets a large number of prior methods as special cases, it has some limitations. For example, the derivation of Hessian estimates based on the DR estimate (Proposition 3.2) involves estimates of the value function V̂ πθDR (xt). In practice, when near on-policy πθ ≈ µ, one might replace the DR estimate V̂ πθDR by other value function estimate, such as plain cumulative sum of returns or TD(λ), V̂ πθTD(λ) [22, 23] in Eqn (4). As such, the practical implementation might not strictly adhere to the conceptual framework. In addition, TMAML [20] is not incorporated as part of this framework: we show in Appendix B that the control variate introduced by TMAML in fact biases the overall estimate.
sections.heading: 4 From Hessian estimates to meta-gradient estimates
sections.text: A practical desiteratum for meta-gradient estimates is that it can be implemented in a scalable way using auto-differentiation frameworks [30, 19]. Below, we discuss how this can be achieved.
sections.heading: 4.1 Auto-differentiating off-policy evaluation estimates for Hessian estimates
sections.text: In practice, we seek Hessian estimates that could be implemented with the help of an established framework, such as auto-differentiation libraries [30, 19]. Now we discuss how to conveniently implement ideas discussed in the previous section.
  Algorithm 2 Example: an off-policy evaluation subroutine for computing the DR estimate Require: Inputs: Trajectory (xt, at, rt)Tt=0, target policy πθ, behavior policy µ, (optional) critic Q.
  Initialize V̂ = Q(xT , πθ(xT ), g). for t = T − 1, . . . 0 do
  Compute IS ratio ρθt = πθ(at|xt)/µ(at|xt). Recursion: V̂ ← Q(xt, πθ(at), g) + γρθt (rt + γQ(xt+1, πθ(xt+1), g)−Q(xt, at)) + γρθt V̂ .
  end for Output V̂ as an estimate to V πθ (x0, g).
  Auto-differentiating the estimates. We can abstract the off-policy evaluation as a function eval(D, θ) that takes in some data D and parameter θ, and outputs an estimate for V πθ (x0, g). In particular, D includes the trajectories and θ is input via the policy πθ. As an example, Algorithm 2 shows that for the doubly-robust estimator, the dependency of the estimator on θ is built through the recursive computation by eval(D, θ). In fact, if we implement Algorithm 2 with an auto-differentiation framework (for example, Tensorflow or PyTorch [17–19]), the higher-order dependency of V̂ on θ is maintained through the computation graph. We can compute the Hessian estimate by directly differentiating through the function output∇Kθ V̂ = ∇Kθ eval(D, θ) ≈ ∇Kθ V πθ (x0, g). In Appendix F we show how the estimates could be conveniently implemented, as in many deep RL agents (see, e.g., [44, 5, 47, 48]). We also show concrete ways to compute estimates with TayPO-K based on [29].
sections.heading: 4.2 Practical implementations of meta-gradient estimates
sections.text: In Equation (2), we write the meta-gradient estimate as a product between an Hessian estimate and a policy gradient. In practice, the meta-gradient estimate is computed via Hessian-vector products to avoid explicitly computing the Hessian estimate of size D2. As such, the meta-gradient estimate could be computed by auto-differentiating through a scalar objective. See Appendix F for details.
  Bias and variance of meta-gradient estimates. Intuitively, the bias and variance of the Hessian estimates translate into bias and variance of the downstream meta-gradient estimates. Prior work has showed that low variance of meta-gradient estimates lead to faster convergence [49, 50]. However, it is not clear how the bias (such as bias introduced by the Hessian estimates, or the bias due to correlated estimates) theoretically impacts the convergence. We will study empirically the effect of bias and variance in experiments, and leave further theoretical study to future work.
sections.heading: 5 Experiments
sections.text: We now carry out several empirical studies to complement the framework developed above. In Section 5.1, we use a tabular example to investigate the bias and variance trade-offs of various estimates, to assess the validity of our theoretical insights. We choose a tabular example because it is straightforward to compute exact higher-order derivatives of value functions and make comparison. In Section 5.2.1 and Section 5.2.2, we apply the new second-order estimate in high-dimensional meta-RL experiments, to assess the potential performance gains in a more practical setup. Though we can compute TayPO-K order estimates for general K, we focus on K ≤ 2 in experiments. Below, we also address TayPO-1 and TayPO-2 estimates as the first and second-order estimates respectively.
sections.heading: 5.1 Investigating the bias and variance trade-off of different estimates
sections.text: We study the bias and variance trade-off of various estimates using a tabular exmaple. We consider random MDPs with |X | = 10, |A| = 5. The transition matrix of the MDPs are sampled from a Dirichlet distribution. See Appendix G for further details. The policy πθ is parameterized as πθ(a|x) = exp(θ(x, a))/ ∑ b exp(θ(x, b)). The behavior policy µ is uniform and θ is initialized so that θ(x, a) = log π(a|x) where π = (1− ε)µ+ επd for some deterministic policy πd and parameter ε ∈ [0, 1]. The hyper-parameter ε measures the off-policyness. In this example, there is no task variable. As performance metrics, we measure the component-wise correlation between the true derivatives∇Kθ V πθ (x0) (computed via an oracle) where x0 is a fixed starting state, and its estimates
  ∇Kθ V̂ πθ (x0), as commonly used in prior work [21–23]. The estimates are averaged across N samples. We study the effect of different choices of the off-policy estimate V̂ πθ , as a function of off-policyness ε and sample size N . We report results with mean± standard error over 10 seeds.
  Effect of off-policyness. In Figure 1(a) and (b), we let N = 1000 and show the performance as a function of ε. When ε increases (more off-policy), the accuracy measures of most estimates decrease. This is because off-policyness generally increases both bias and variance (large IS ratios ρθ). At this level of sample size, the performance of the second-order estimate degrades more slowly than other estimates, making it the dominating estimate across all values of ε. We also include truncated DR estimate using min(ρθt , ρ) as a baseline inspired by V-trace [44, 47]. The truncation is motivated by controlling the variance of the overall estimate. However, the estimate is heavily biased and does not perform well unless πθ ≈ µ. See Appendix F for more.
  Consider the case when ε = 0 and the setup is on-policy. When estimating the policy gradient, almost all estimates converge to the optimal level of accuracy, except for the step-wise IS estimate, where the variance still renders the performance sub-optimal. However, when estimating the Hessian matrix, the first-order estimate converges to a lower accuracy than both second-order estimate and DR estimate. This validates our theoretical analysis, as both the second-order estimate and DR estimate are unbiased when on-policy.
  Effect of sample size. Figure 1(c) shows the accuracy measures as a function of sample size N when fixing ε = 0.5. Note that since sample sizes directly influence the variance, the results show the variance properties of different estimates. When N is small, the first-order estimate dominates due to smaller variance; however, when N increases, the first-order estimate is surpassed by the second-order estimate, due to higher bias. For more results and ablation on high-dimensional environments, see Appendix G.
sections.heading: 5.2 High-dimensional meta-RL problems
sections.text: Next, we study the practical gains entailed by the second-order estimate in high-dimensional meta-RL problems. We first introduce a few important algorithmic baselines, and how the second-order estimate is incorporated into a meta-RL algorithm.
  Baseline algorithms. All baseline algorithms use plain stochastic gradient ascent as the inner loop optimizer: θ′ = θ + η∇θV̂ πθ (x0, g) where g ∼ pG is a sampled goal and V̂ πθ (x0, g) is a sample-based estimate of policy gradients averaged over n trajectories. Different algorithms differ in how the inner loop loss is implemented, such that auto-differentiation produces different Hessian estimates: these include TRPO-DiCE [21–23], TRPO-MAML [4], TRPO-FMAML [4], TRPO-EMAML [32, 33]. Please refer to Appendix G for further details. Note despite the name, TRPO-DiCE baseline uses DR estimate to estimate Hessians. We implement the second-order
  estimate using the proximal meta policy search (PROMP) [24] as the base algorithm. By default, PROMP uses the first-order estimate. Our new algorithm is named PROMP-TayPO-2.
sections.heading: 5.2.1 Continuous control in 2D environments
sections.text: Environment. We consider a simple 2-D navigation task introduced in [24]. The state xt is the coordinate of a ball placed inside a room, the action at is the direction in which to push the ball. The goal g ∈ R4 is an one-hot encoding of which corner of the room contains positive rewards. With 3 adaptation steps, the agent should ideally navigate to the desired corner indicated by g.
  Training performance. In Figure 1(d), we show the performance curves of various baseline algorithms. Though MAML and EMAML learns quickly during the initial phase of training, they ultimately become unstable. TRPO-DiCE generally underperforms other methods potentially due to bias. On the other hand, FMAML and PROMP both reduce variance at the cost of bias, but they both achieve a slightly lower level of performance compared to PROMP-TayPO-2. Overall, PROMP-TAyPO-2 achieves much more stable training curves compared to others, potentially owing to the better bias and variance trade-off in the Hessian estimates.
sections.heading: 5.2.2 Large scale locomotion experiments
sections.text: Environments. We consider the set of meta-RL tasks based on simulated locomotion in MuJoCo [51]. Across these tasks, the states xt consist of robotic sensory inputs, the actions at are torque controls applied to the robots. The task g is defined per environment: for example, in random goal environment, g ∈ R2 is a random 2-d goal location that the robot should aim to reach. Experiment setup. We adapt the open source code base by [24] and adopt exactly the same experimental setup as [24]. At each iteration, the agent samples n = 40 task variables. For each task, the agent carries out K = 1 adaptation computed based on B = 20 trajectories sampled from the environment, each of length T = 100. See Appendix G for further details on the architecture and other hyper-parameters. We report averaged results with mean± std over 10 seeds.
  Results. The training performance of different algorithmic baselines are shown in Figure 2. Comparing TRPO-DiCE, TRPO-MAML and PROMP: we see that the results are compatible with those reported in [24], where PROMP outperforms TRPO-MAML, while TRPO-DiCE generally performs the worst potentially due to high variance in the gradient estimates. As a side observation, TRPO-FMAML generally underperforms TRPO-MAML, which implies the necessity of carrying out approximations to the Hessian matrix beyond the identity matrix. PROMP-TayPO-2 slightly outperforms PROMP in a few occasions, where the new algorithm achieves slightly faster learning speed and sometimes higher final performance. However, overall, we see that the empirical gains are marginal. This implies that under the default setup of these meta-RL experiments, the variance might be a major factor in gradient estimates, and the first-order estimate is near optimal compared to other estimates. See Appendix G for additional experiments.
sections.heading: 6 Conclusion
sections.text: We have unified a number of important prior work on meta-gradient estimations for model-agnostic meta-RL. Our analysis entails the derivations of prior methods based on the unifying framework of
  differentiating through off-policy evaluation estimates. This framework provides a principled way to reason about the bias and variance in the higher-order derivative estimates of value functions, and opens the door to a new family of estimates based on novel off-policy evaluation estimates. As an important example, we have theoretically and empirically studied the properties of the family of TayPO-based estimates. It is worth noting that this framework further suggests any future advances in off-policy evaluation could be conveniently imported into potential improvements in meta-gradient estimates. As future work, we hope to see the applications of such principled estimates in broader meta-RL applications.
  Acknowledgement. The authors thank David Abel for reviewing an early draft of this work and providing very useful feedback. Yunhao and Tadashi are thankful for the Scientific Computation and Data Analysis section at the Okinawa Institute of Science and Technology (OIST), which maintains a cluster we used for many of our experiments.
title: Unifying Gradient Estimators for Meta-Reinforcement Learning via Off-Policy Evaluation