Meta-Gradient Reinforcement Learning
The goal of reinforcement learning algorithms is to estimate and/or optimise the value function. However, unlike supervised learning, no teacher or oracle is available to provide the true value function. Instead, the majority of reinforcement learning algorithms estimate and/or optimise a proxy for the value function. This proxy is typically based on a sampled and bootstrapped approximation to the true value function, known as a return. The particular choice of return is one of the chief components determining the nature of the algorithm: the rate at which future rewards are discounted; when and how values should be bootstrapped; or even the nature of the rewards themselves. It is well-known that these decisions are crucial to the overall success of RL algorithms. We discuss a gradient-based meta-learning algorithm that is able to adapt the nature of the return, online, whilst interacting and learning from the environment. When applied to 57 games on the Atari 2600 environment over 200 million frames, our algorithm achieved a new state-of-the-art performance.
The central goal of reinforcement learning (RL) is to optimise the agent's return (cumulative reward); this is typically achieved by a combination of prediction and control. The prediction subtask is to estimate the value function -the expected return from any given state. Ideally, this would be achieved by updating an approximate value function towards the true value function. The control subtask is to optimise the agent's policy for selecting actions, so as to maximise the value function. Ideally, the policy would simply be updated in the direction that increases the true value function. However, the true value function is unknown and therefore, for both prediction and control, a sampled return is instead used as a proxy. A large family of RL algorithms [Sutton, 1988, Rummery and Niranjan, 1994, van Seijen et al., 2009, Sutton and Barto, 2018, including several state-of-the-art deep RL algorithms [Mnih et al., 2015, van Hasselt et al., 2016, Hessel et al., 2018, Espeholt et al., 2018, are characterised by different choices of the return.
The discount factor γ determines the time-scale of the return. A discount factor close to γ = 1 provides a long-sighted goal that accumulates rewards far into the future, while a discount factor close to γ = 0 provides a short-sighted goal that prioritises short-term rewards. Even in problems where long-sightedness is clearly desired, it is frequently observed that discounts γ < 1 achieve better results [Prokhorov and Wunsch, 1997], especially during early learning. It is known that many algorithms converge faster with lower discounts [Bertsekas and Tsitsiklis, 1996], but of course too low a discount can lead to highly sub-optimal policies that are too myopic. In practice it can be better to first optimise for a myopic horizon, e.g., with γ = 0 at first, and then to repeatedly increase the discount only after learning is somewhat successful [Prokhorov and Wunsch, 1997].
The return may also be bootstrapped at different time horizons. An n-step return accumulates rewards over n time-steps and then adds the value function at the nth time-step. The λ-return [Sutton, 1988, Sutton andBarto, 2018] is a geometrically weighted combination of n-step returns. In either case, the meta-parameter n or λ can be important to the performance of the algorithm, trading off bias and variance. Many researchers have sought to automate the selection of these parameters [Kearns and  Singh,
There are potentially many other design choices that may be represented in the return, including off-policy corrections [Espeholt et al., 2018, target networks [Mnih et al., 2015], emphasis on certain states [Sutton et al., 2016], reward clipping [Mnih et al., 2013], or even the nature of the rewards themselves [Randløv and Alstrøm, 1998, Singh et al., 2005, Zheng et al., 2018.
In this work, we are interested in one of the fundamental problems in reinforcement learning: what would be the best form of return for the agent to maximise? Specifically, we propose to learn the return function by treating it as a parametric function with tunable meta-parameters η, for instance including the discount factor γ, or the bootstrapping parameter λ [Sutton, 1988]. The meta-parameters η are adjusted online during the agent's interaction with the environment, allowing the return to both adapt to the specific problem, and also to dynamically adapt over time to the changing context of learning. We derive a practical gradient-based meta-learning algorithm and show that this can significantly improve performance on large-scale deep reinforcement learning applications.
A gradient-based hyper-parameter technique for reinforcement learning is proposed, and implemented on top of the IMPALA architecture. The algorithm consists in estimating the gradient of an objective J’ w.r.t. hyper-parameters eta, using the chain rule: d_J’/d_eta = d_J’ / d_theta’ * d_theta’ / d_eta, where theta’ = theta + f(tau, theta, eta) is the updated vector of model parameters after observing trajectory tau with current parameters theta and hyper-parameters eta. In other words, we look for a small change in hyper-parameters that would improve the performance of the agent after a parameter update, as measured by the objective J’. This objective is based on independently sampled trajectories tau’ and a fixed set of hyper-parameters eta’. In order to accommodate the fluctuations in hyper-parameters eta, they are provided as input to the actor and critic networks. The main experiments are on Atari, where eta = {gamma, lambda} (respectively the discount factor and the bootstrapping parameter in TD(lambda)). They show a significant improvement over the standard IMPALA architecture (which uses the best gamma = 0.995 and lambda = 1 found by grid search), in terms of median human-normalized score.  There is no doubt this is an interesting paper. Just the fact that the discount factor matters so much (huge improvement with vanilla IMPALA when going from 0.99 to 0.995, but poor results at 0.999) is quite notable to me: to my knowledge it is not something that had been investigated previously (on Atari specifically). I actually find this somewhat worrying, since it sheds doubts on the validity of the standard practice of training with gamma = 0.99 then evaluating on the total accumulated reward for benchmarking purpose, as is done in almost all deep RL papers evaluated on Atari... but this is another discussion.  The core empirical results are convincing enough: there is a relatively consistent improvement over the baseline IMPALA, which is a solid benchmark. It is still pretty far from Ape-X DQN but since the number of environment steps is much lower, this may not be a fair comparison to make. As shown in Fig. 2 of the Appendix, though, there are some games where the proposed technique clearly hurts: it would have been interesting to try and understand what is going on in these games that makes the hyper-parameter adaptation scheme fail. In addition, I believe there should have been some comparison to other hyper-parameter adaptation techniques, since the ability to improve on a fixed gamma over all games is not particularly surprising (given the highly varying nature of Atari games). At the very least, a comparison to grid search should have been done where one would pick the best gamma *for each game*.  I would also argue that the proposed method is not just a hyper-parameter adaptation scheme: since hyper-parameters eta are provided as input to the actor and critic, the model is essentially performing multi-task learning (learning to predict returns at multiple timescales). It has been observed before that additional tasks can have a beneficial effect (ex: the UNREAL agent), and in my opinion this begs the question as to whether the improvement comes mostly from changing eta or from learning to predict over multiple eta’s. Note that even if eta eventually converges to a fixed value, the optimization w.r.t. J’ encourages updates that give good results for eta’ != eta, so the model is still learning with at least two time scales. Related to this last point, the motivation given by the authors for adding eta as a model input is that “the return function gη(τ ) is non-stationary”, but it is not clear to me whether this is the main one, since eta does not change that fast. Another clearly important factor, not mentioned in the paper, is that it allows to compute J’ on eta’ != eta, while otherwise it would seem difficult to optimize J’ with the “wrong” hyper-parameters (by the way please mention 1.4 earlier, or add a reference to it in 1.2, because eq. 11 got me puzzled for a while due not being aware of that yet). To summarize, my point is that even if there is no doubt the method works, I wish there had been more efforts to understand why.  In this respect, the illustrative examples from Section 2 could have help shed light on the inner workings of the algorithm. Unfortunately I found them extremely confusing. I suspect that my understanding of “state-dependent” hyper-parameter may not match the actual implementation. For instance when I think of a state-dependent gamma, to me it means that the Bellman equation would be written V(s) = E[R(s)] + gamma_s V(s’), where gamma_s is the state-dependent discount factor. But then it makes no sense for gamma_s to be near zero in “noise” states in Fig. 1a, as it would mean we only learn V(s) from the noise R(s), which can’t be right. The algorithm also learned a specific high value for gamma_9 while gamma should not matter in that state, since the next state is terminal and thus V(s’) = 0. The second example (Fig. 1b) is equally confusing, if not more. Since even-numbered states are aliased, the agent sees them as a single state. That state is visited as often as a bottleneck state (contradicting “The fully observed bottleneck states are visited frequently”), and has essentially the same properties regarding the noise in the (immediate) reward distribution: a random (due to aliasing) number chosen among -r1, .. -rn (vs. among r1, ..., rn in a bottleneck state). I may have misunderstood the meaning of “aliased” states, in which case a clarification would be appreciated. In any case, I was unable to derive a better understanding of the proposed method from these two toy examples.  There are other unclear parts in the paper, even if the high-level idea is easy to grasp. One of them is how the dependence of the actor pi and critic v on the hyper-parameters eta is handled w.r.t. gradient computations: the derivations in 1.2 and 1.3 assume that v and pi do not depend on eta. But then 1.4 adds such a dependency... Are you actually backpropagating through the whole computational graph, or “cutting” this specific part of the gradient? (and in the former case, does that include backpropagating through the IMPALA importance sampling weights?). I believe this is an important point to clarify and motivate. Other unclear points include: - The inclusion of d_thera / d_eta in eq. 3 (first term). I do not understand what it is supposed to represent. From my point of view, when starting from theta, modifying eta has no effect on theta itself: it can only change future values theta’. The “accumulative trace” approximation looks fishy to me as I fail to see what it is meant to approximate: I see it simply as a momentum applied to d_f / d_eta. Note also that when reading the text it is not obvious that this is a recursive update with z’ being the new value of z used in the nest iteration. - The motivation for keeping only the policy gradient objective when defining J’ in eq. 14. It is not obvious to me that this is the best choice, since a better critic v could also have a positive impact on the agent’s performance. - The motivation for using gamma’ = 0.995 in Atari experiments: should not it be chosen based on the performance of the adaptive algorithm, rather than the best fixed gamma? - The exact meaning of batches (“meta batch size” in Table 2): is it the case that J’ is actually evaluated over a mini-batch of trajectories, instead of a single trajectory tau’ as the equations suggest? - More generally, adding the pseudo-code of the algorithm in the Appendix would be very helpful, especially with 1.5 showing there are important implementation “details”  Minor points (missing from original review, but thankfully the character limit is gone): - I would suggest to remove eta from the definition of n-step returns in eq. 6 since the proposed method can’t optimize discrete hyper-parameters (a limitation, by the way, which is not clearly stated in the abstract & conclusion) - In eq. 8 dividing J by two would slightly simplify subsequent equations - Caption of Fig. 1: “the first one shows how the meta-parameter γ or λ adapts” => please specify “for each state” - What is the value of n in experiments? Is it the “unroll length” 20? - l. 177 please refer to Fig. 1 (top), as trying to understand the examples from their text description is difficult - Please specify the values of respectively lambda and gamma used in the two illustrative examples - l. 202 why not write eta = {gamma, lambda} ? - In Atari do you use lambda’ = 1? If yes how do you deal with the fact a sigmoid can’t be equal to 1 (footnote 2) and you need the logit as input to the actor and critic to compute J’? (the same question actually arises for the illustrative examples) - In Appendix Fig. 2 and 3 please specify eta’  Regarding the author response:  First, thank you for the detailed response. My main concerns have been addressed by the extra results related to the grid search on gamma and the multi-task experiment, so I've changed by recommendation to accept. A few follow-up remarks that hopefully you can take into account when preparing the final version:  1. You motivated including d_theta / d_eta in eq. 3 with a recurrent view of theta as a function of eta (response l. 35). However, in practice eta has not been kept fixed during the previous steps (since the algorithm is adapting it), and thus theta is not just a function of the current eta, but depends of the value of eta at each previous timestep. As a result this derivative still makes no sense to me (NB: and even if eta had been kept fixed, I am still not sure it would be a good idea to follow this gradient, since we're never going back in time to "improve the past" -- changing eta only affects future updates)  2. In your first toy example (Fig. 1a) you say that (response l. 27) “in noisy states setting e.g. gamma2 ≈ 0 avoids receiving the "noise" reward”. However this effectively shuts down all subsequent rewards as well when e.g. computing the value function for the very first state. I don’t see how one can properly estimate the long-term value v_1 of the first state (with gamma’ = 1) if gamma_2 = 0 since the only return the agent will see from state 1 is 0.1.  3. Your second example (Fig. 1b) finally "clicked" for me when I wrote down what the return would look like depending on when to bootstrap (with binary lambda's). For instance using as target either r_i + v(aliased_state) or r_i - r_i + v(bottleneck_state). It becomes clear that the second one is less noisy since the two consecutive rewards immediately cancel each other in the return. So maybe you could write it down explicitly in the paper as well (possibly in the Appendix if not enough room).  4. Regarding point R2.7 in your response, I actually didn't think of using gamma'_t = gamma_t. I had in mind a simpler "classical" hyper-parameter selection strategy, e.g. doing a grid-search over gamma'. I don't disagree that in the absence of other any information, using gamma' = the best fixed gamma seems like a sensible solution, however it remains a somewhat arbitrary choice that was not motivated in the submission.  Thanks!  ========  One last thing, regarding point 1: I posted the following on the reviewers’ discussion board, to try and explain my point of view to fellow reviewers (none of them could understand the role of mu by the way, so I really hope this part gets fixed in a final version):  I see the meta-optimization problem as an iterative procedure, where at each step we start from the previous theta and want the update f (as in eq. 1) to improve on the meta-objective J'. We can control f through hyper-parameters eta, and eq. 2 tells us the direction to follow in the hyper-parameter space.  This direction requires computing d_theta' / d_eta, which from eq. 1 is *equal* to d_f / d_eta, because theta is the (fixed) starting point at the current step, and is not affected by any subsequent change to eta. Plugging this in eq. 2, we get that d_J' / d_eta = d_J' / d_theta' * d_f / d_eta, which is indeed the update direction that is being used when when mu = 0 (see eq. 5 where z' = d_f / d_eta).  So, to me, mu=0 is not an approximation, it yields the correct update direction for the optimization objective. Using mu > 0 amounts to adding momentum to the gradient d_f / d_eta, which I guess could be argued to stabilize training in some situations. Note that it's not exactly similar to regular momentum in SGD because this momentum is not applied to the final update direction (eq. 2), but only to one of its components. So it's not really clear what's going to happen with mu > 0, and since all experiments reported in the submission are with mu=0, there's no way to tell how sensitive performance is to changes to this parameter.  That being said, since from my point of view mu=0 is the natural thing to do, I would not reject the paper based only on its lack of clarity regarding mu's role.