Metatrace Actor-Critic: Online Step-Size Tuning by Meta-gradient Descent for Reinforcement Learning Control

1 Introduction

In the supervised learning setting, there are a variety of optimization methods that build on stochastic gradient descent (SGD) for tuning neural network parameters. Applying ordinary SGD is difficult due to the sensitivity to the step-size parameter, which controls the magnitude of each update, as well as potential for wide variation in the gradient magnitude across different dimensions. Methods like RMSProp [Tieleman and Hinton, 2012] and ADAM [Kingma and Ba, 2014] aim to accelerate learning and improve stability by approximately accounting for higher order gradients of a fixed loss surface. While these methods are effective in the supervised case, they do not translate straightforwardly to online reinforcement learning (RL), where targets incorporate future estimates and subsequent observations are correlated.

The eligibility trace method is a key component used in RL to control the degree of bootstrapping from future estimates. However, this further complicates the analogy with supervised learning, as individual updates do not correspond to a gradient descent step toward any target on their own. Instead, the error signal is broken up into a series of updates such that only the sum of updates over time optimizes it. The appropriate analogy to the previously mentioned SGD techniques from supervised learning is not clear in this setting.

To apply these SGD techniques in the RL setting, a common strategy is to make the RL problem as close to the supervised learning problem as possible. Techniques that help to achieve this include multiple actors [Mnih et al., 2016], large experience replay buffers [Mnih et al., 2015], and separate online and target networks [Van Hasselt et al., 2016]. These all help smooth gradient noise and mitigate non-stationarity. However, they do so at the cost of losing the advantages of online updating. These advantages include lower computation and memory use, learning immediately from new experience, and allowing a single agent to learn from its own trajectories.

We propose Metatrace, a novel set of algorithms that tune the step-size parameter online for the actor-critic algorithm. Metatrace applies meta-gradient descent, propagating gradients through the optimization algorithm itself, to derive stepsize tuning algorithms specifically for the online RL control problem. These algorithms build on the incremental deltabar-delta (IDBD) approach [Sutton, 1992] while solving an open issue of previous work. To be exact, we use an eligibility trace-like mechanism to allow the meta-objective to account for time-dependent weights in an online manner. We apply this insight to define algorithms for tuning a scalar step-size, as well as a vector of step-sizes. Finally, we propose a mixed version that leverages the benefits of both, and integrate the algorithm with entropy regularization and normalization of the metaupdate to improve performance in practice.

We evaluate Metatrace for actor-critic with eligibility traces (AC(λ)). Our experiments include a classic mountain car problem to demonstrate the efficiency of the algorithms and a drifting version of mountain car to explore the performance of meta-gradient descent with a non-stationary state representation. Finally, we evaluate Metatrace for training a deep neural network online in the original training-set games of the Arcade Learning Environment (ALE) [Bellemare et al., 2013]. Without the use of either multiple actors or experience replay, our method learns faster and achieves better performance than an optimal fixed step-size in most of the games.

2 RelatedWork

Meta-learning has a long history dating back to Schmidhuber's thesis [Schmidhuber, 1987], where a genetic programming algorithm was applied to evolve better genetic programming algorithms. Our work is closely related to IDBD [Sutton, 1992] and autostep [Mahmood et al., 2012], which are meta-gradient descent procedures for step-size tuning in the supervised learning case. Also closely related are SID and NOSID [Dabney, 2014], which analogize meta-gradient descent procedures for the SARSA(λ) method [Sutton and Barto, 2018]. Our approach differs primarily by explicitly accounting for time-varying weights in the optimization objective for the step-size. We also extend the approach to AC(λ) and to vector-valued step-sizes, as well as a mixed version which combines scalar and vector step-sizes.

Meta-gradient RL [Xu et al., 2018] applies meta-gradient descent to optimize γ and λ in AC(λ). They use multiple parallel agents, deviating from the online RL case we focus on.

It is worth noting that previous works such as TIDBD and its extension AutoTIDBD [Kearney et al., 2019] tune vector step-sizes online. That work focuses on TD(λ) for prediction, and explores both vector and scalar step-sizes. They demonstrate that both scalar and vector AutoTIDBD outperform ordinary TD(λ), while vector AutoTIDBD outperforms a variety of scalar step-size adaptation methods. Aside from focusing on control rather than prediction, our methods differ from TIDBD in the meta-objective optimized by the step-size tuning: they use one step TD error, while we use a more general multi-step objective.

Our neural network experiments draw inspiration from the work of Elfwing et al. [Elfwing et al., 2018], to our best knowledge the only prior work to apply online RL with eligibility traces to train a deep neural network. In their case, the neural network is used as a function approximator in SARSA(λ). They do not explore step-size tuning.

3 Background

We consider the RL problem, where a learning agent interacting with an environment strives to maximize a reward signal. The problem is formalized as a Markov decision process 〈S, A, p, r, γ〉. We consider stochastic environments and stochastic policies. At each time-step the agent observes the state St ∈ S and selects an action At ∈ A. Based on St and At, the next state St+1 is generated by p(St+1|St,At). The agent additionally observes a reward Rt+1, generated by r : S×A → R. We focus on the control problem, where an agent learns, through interaction with the environment, a policy π that maximizes the expected return Gt = ∑∞k=0 γ kRt+k+1, with discount factor γ ∈ [0, 1].

Action-value methods like Q-learning are often used for RL control [Mnih et al., 2015, Watkins and Dayan, 1992]. However, actor-critic (AC) methods, which more directly optimize the expected return, are becoming increasingly popular in Deep RL [Espeholt et al., 2018]. We will focus on AC, but our proposed method is general enough to be applied to other RL algorithms. AC methods learn a state value function for the current policy, as well as a policy which attempts to maximize that value function. In particular, we will derive Metatrace for actor-critic with eligibility traces, AC(λ) [Degris et al., 2012, Schulman et al., 2015].

We define the objective of AC(λ) in terms of the lambda return, which is recursively defined as

Gλw,t bootstraps future evaluations to a degree controlled by λ. Here we define Gλw,t for a fixed weight vector w; in Section 4, we will extend this to a time varying wt. Also, define the TD-error δt = Rt + γVw(St+1) - Vw(St). Then we can expand Gλw,t as the current state value estimate plus the sum of future discounted δt values as

TD(λ) can be understood as performing gradient descent along the mean squared error (Gλw,t - Vw(St))2 between the value function Vw and the lambda return Gλw,t . In the derivation of TD(λ), the target Gλw,t is taken as a constant despite its dependence on w. For this reason, TD(λ) is often called a semi-gradient method. Intuitively, this reflects our desire to modify our current estimate to match our future estimates, not the other way around. AC(λ), combines this mean squared error objective with a policy improvement term, such that the combined objective represents a trade-off between the quality of our value estimates and the performance of our policy:

As is in TD(λ), we aim to perform semi-gradient descent to minimize equation (2). Along with Gλw,t , Vw(St) in the right sum is taken to be constant. Similar to previous arguments, the intuition is that we wish to improve our actor under the evaluation of our critic, instead of modifying our critic to make our actor's performance look better. With this caveat in mind, by the policy gradient theorem [Sutton et al., 2000], the expectation of the gradient of the right term in equation (2) is approximately equal to the negated gradient of the expected return. This approximation is accurate to the extent that our advantage estimate (Gλw,t -Vw(St)) is accurate. Descending the gradient of the right half of Jλ(w) is then ascending the gradient of an estimate of expected return. Taking the semi-gradient of equation (2) yields

Now, define for compactness

so that, applying equation (1), we can rewrite

and define the eligibility trace at time t as zt = t∑ k=0(γλ)t-k ∂Uw(Sk) ∂w , such that

Offline AC(λ) makes updates in the direction of equation (3). Online AC(λ), analogous to online TD(λ), is an approximation to this offline version (exact in the limit of quasi-static weights) that updates weights after every time-step. Advantages of the online version include making immediate use of new information, and being applicable to continual learning 1 . Online AC(λ) is defined by the following set of equations:

Where α is the step-size parameter, controlling the magnitude of each update. In practice, performance can be highly sensitive the the value of α, hence tuning it online as we do in this work is a worthwhile goal.

4 Algorithm

We present three variations of Metatrace for control using AC(λ): scalar (single α for all model weights), vector (one α per model weight), and finally a "mixed" version that attempts to leverage the benefits of both. Additionally, we discuss two practical improvements over the basic algorithm: normalization that helps to mitigate parameter sensitivity across problems and avoid divergence; and entropy regularization, which is commonly employed in AC to avoid premature convergence [Mnih et al., 2016].

4.1 Scalar Metatrace for AC(λ)

For convenience, we define our step-size as α = eβ , similar to IDBD [Sutton, 1992]. We desire to optimize α to allow our weights to efficiently track the non-stationary AC(λ) objective. To account for non-stationarity in the representation, we define the objective with time-dependent weights

Gλt with no subscript w is defined as Gλt = Vwt (St) + ∑∞k=t (γλ)k-t δk, where δk = Rk +γVwk (Sk+1)-Vwk (Sk).

1 Continual learning is the setting where an agent interacts with an environment indefinitely, with no distinct episodes.

Our derivation is similar to Section 4.3.1 of Dabney's thesis [Dabney, 2014], but explicitly accounts for the timedependency of wt. Regarding each wt as a function of β, differentiating equation (5) under the same semi-gradient treatment used in AC(λ) yields

To handle the above objective, we define an auxiliary eligibility trace as

such that

As z itself is a sum of first-order derivatives with respect to w, we approximate ∂zt ∂w = 0. Since log(πwt (At|St)) necessarily involves some non-linearity, this is a first-order approximation even in the linear case. Furthermore, in the control case, the weights affect action selection. Action selection, in turn, affects expected weight updates. Hence, there are additional higher order effects of modifying β on the expected weight updates. As is in Dabney's thesis [Dabney, 2014], we do not account for this effect. We leave the question open of how to account for this interaction in the online setting, and to what extent it would make a difference in the algorithm. With the above reasoning, let h(t) denote ∂wt/∂β, we update h(t) as

Following equation (6)-(8), our Scalar Metatrace for AC(λ) is described by

Where µ is the meta-step-size parameter, controlling the update magnitude for the step-size parameter itself. The update

Algorithm 1 Normalized Scalar Metatrace for actor-critic

• 17: end for

to zβ is an online computation of equation (6). The update to β is exactly analogous to the AC(λ) weight update but with equation (7) in place of equation (3). The update to h computes equation (8) online. The full algorithm is detailed in Algorithm 1, including entropy regularization and normalization to be described shortly.

4.2 Vector Metatrace for AC(λ)

For the vector case, we denote αi = eβi to be the ith element of a vector of step-sizes. Each element αi corresponds to one weight such that the update for each weight element in AC(λ) will use the associated αi. Having a separate αi for each weight enables the algorithm to individually adjust how quickly it tracks each feature. This is particularly important when the state representation is non-stationary, including the case where neural network-based models are used. We expect our algorithm to assign high step-size to fast-changing, useful features while annealing the step-size of features that are either mostly stationary or not useful to avoid tracking noise.

Taking each wt to be a function of βi for all i, and following IDBD [Sutton, 1992] in using the approximation ∂wi,t ∂βj = 0 for all i ̸= j, differentiating equation (2) with respect to βi yields

Similarly we define an auxiliary eligibility trace, which is

Algorithm 2 Normalized Vector Metatrace for actor-critic

vectorized in this section, with elements

such that

To compute h(t) ˙= ∂wi,t ∂βi we use the immediate generalization of the scalar case and the approximation ∂wi,t ∂βj = 0, which yields

Therefore, Vector Metatrace for AC(λ) is described by

where ⊙ denotes the Hadamard product. The full algorithm is detailed in Algorithm 2.

We now describe three variations based on Scalar Metatrace and Vector Metatrace that can be helpful in practice.

Mixed Metatrace

We explore a mixed algorithm where a vector correction to the step-size -→β is learned for each weight and added to a global value ˆ β which is learned collectively for all weights. The idea is that through ˆ β Mixed Metatrace can make use of all available data to learn a good base step-size, while -→β can be adjusted per parameter where it is useful. We omit the algorithm for this case for brevity: it is a straightforward combination of the scalar and vector algorithms.

Entropy Regularization

In practice, it is often helpful to add an entropy bonus,

-ψ ∞∑

mature convergence [Mnih et al., 2016]. We found it helpful to also include the entropy bonus in the meta-objective, which requires modification to the step-size tuning procedure. This modification is included in Algorithms 1 and 2.

Normalization

As discussed in autostep [Mahmood et al., 2012], even in the supervised learning case, the meta-gradient descent algorithms discussed so far can be unstable and sensitive to the parameter µ. To combat this, we normalize the meta-update, and clip the step-size to avoid overshooting in a manner analogous to the procedure introduced in autostep.

5 Experiments and Results

5.1 Mountain Car

We begin by testing Scalar Metatrace on the mountain car domain from OpenAI Gym [Brockman et al., 2016]. A reward of -1 is given for each time-step until the goal is reached or 200 steps are taken. In this experiment, we use linear function approximation with tile-coding for state representation. The tiling size is 10 × 10 where 16 tilings create a feature vector of size 1600. The learning algorithm is based on AC(λ) with γ fixed to 0.99 and λ fixed to 0.8 in all experiments. For mountain car, we use no entropy regularization.

Figure 1a shows the results for a variety of α values without step-size tuning. α values were chosen as powers of 2 which range from excessively low to excessively high (where the algorithm diverges). Figure 1b shows the results for Normalized Scalar Metatrace with different initial α values. In contrast to the untuned baseline, the learning curves of different αs ares very similar. Though the µ value has to be specified, similar results hold for a broad range of µ values below µ ≥ 2-6 , above which the algorithm becomes unstable.

5.2 DriftingMountain Car

Motivated by the noisy, non-stationary experiment from IDBD [Sutton, 1992], we create drifting mountain car by adding noise and non-stationarity to the state representation. The environment is intended to provide a proxy for the issues inherent in representation learning such as using a neural network function approximator. We use the same tiling features as in the original mountain car experiment. However, at each time-step, each feature has a chance to randomly flip from indicating activation with 1 to -1 and vice-versa. We define a uniform flipping probability per time step across all features that we refer to as the drift rate, which is 6 × 10-6 in our experiment. Additionally, we add 32 noisy features which are 1 or 0 with probability 0.5 for every time-step.

Figure 1: Return v.s. training episodes on mountain car for a variety of initial α values with and without step-size tuning. Each curve shows the average of 10 random seeds, smoothed over 20 episodes.

Due to the non-stationarity, an arbitrarily small α is not asymptotically optimal, as it is unable to track the changing features. Because of the noise, a scalar α will be suboptimal as well. Nonzero αi values for noisy features lead to weight updates when that feature is active in a particular state. This random fluctuation adds noise to the learning process. The noise can be avoided by annealing associated αis to zero, which is what Vector and Mixed Metatrace are expected to achieve. We demonstrate the effectiveness in Figure 2, for Scalar, Vector, and Mixed Metatrace methods along with a baseline with no online tuning. The best µ value for each method was selected from {2-i |i ∈ {6, ..., 11}}. We observe that Mixed Metatrace maintains the most stable performance in the presence of non-stationarity.

To better understand the algorithm, we illustrate the evolution of various elements of the log step-size β under Mixed Metatrace, in Figure 3. Value βs refer to the log step-sizes of weights associated with the value function while policy βs refer to those associated with the policy. Noisy βs refer to the weights attached to noisy features, while informative βs refer to those associated with the tile-coding which are expected to be useful. While all the step-sizes associated with noisy features are suppressed compared to the informative features, we observe a much stronger separation between the noisy and informative features for the value function than for the policy. One possible reason for this is that small errors in the value function have far more impact on optimizing the objective J β λ in mountain car than small imperfections in the policy. Learning a good policy requires fine-grained ability to distinguish the value of similar states, as individual actions will have a relatively minor impact on the car. On the other hand, errors in the value function in one state have a large negative impact on both the value learning of other states and the ability to learn a good policy.

5.3 Arcade Learning Environment

Finally, we test our algorithm with the 5 original trainingset games of the ALE [Bellemare et al., 2013]. We use a convolutional neural network architecture similar to that used in DQN [Mnih et al., 2013], with SiLU and dSiLU activations to improve the performance in the online setting [Elfwing et al., 2018]. The policy and value network share all but the final output layer. We fix µ = 1 × 10-3 and run all experiments up to 1.25 × 107 observed frames. We use sticky actions to add stochasticity to the environments [Machado et al., 2017]. Figure 4 shows the results of the ALE experiments.

Metatrace significantly decreases the sensitivity to the initial choice of α. In most cases, Metatrace also improves the performance while accelerating learning. In space invaders, each α value tested outperforms the best α without online tuning. In seaquest, two of the three do. In asterix, the final performance of all initial αs with Metatrace was similar to the best-untuned α value, but the learning process is much faster. In beam rider, however, using no online tuning results in faster learning, especially for a well-chosen initial α. This result is possibly due to the high α sensitivity and high sample complexity in the game. The impact of changes in α only occurs after a very long period, making the online tuning especially difficult. In future work, it would be interesting to explore howMetatrace could be made robust to this issue.

6 Conclusion

We propose Metatrace, a novel set of algorithms based on meta-gradient descent for reinforcement learning, which performs step-size tuning for AC(λ). Our result extends the methods of IDBD [Sutton, 1992] and autostep [Mahmood et al., 2012] from supervised learning to reinforcement learning, which involves several technical challenges. To achieve this, we derive an eligibility trace-like mechanism to allow the meta-objective to account for time-dependent weights. We show that that Scalar Metatrace improves robustness to initial step-size choice, while Mixed Metatrace facilitates learning in an RL problem with non-stationary state representation. We also empirically test our approach for training a neural network online for several games in the Arcade Learning Environment, with nonlinear function approximation, where the state representation is inherently unstable. In most of the games, Metatrace allows a range of initial step-sizes to learn faster. Metatrace can also achieve better performance compared to the best-fixed choice of the step-size.