Title: ASSESSING GENERALIZATION IN TD METHODS FOR DEEP REINFORCEMENT LEARNING Anonymous

Abstract: Current Deep Reinforcement Learning (DRL) methods can exhibit both data inefficiency and brittleness, which seem to indicate that they generalize poorly. In this work, we experimentally analyze this issue through the lens of memorization, and show that it can be observed directly during training. More precisely, we find that Deep Neural Networks (DNNs) trained with supervised tasks on trajectories capture temporal structure well, but DNNs trained with TD(0) methods struggle to do so, while using TD(λ) targets leads to better generalization.

1. INTRODUCTION:

Deep neural networks (DNNs) trained on supervised learning tasks using i.i.d. data have shown the capacity to learn quickly even from a small amount of samples (Hardt et al., 2016) . Intuitively, this is due to each sample also providing information about the estimate corresponding to other samples; research suggests that DNNs first extract structures that are informative of the modes of the data (even if later on they can also memorize see Zhang et al. (2016) ; Arpit et al. (2017) ), and that they can transfer well (Yosinski et al., 2014; Li et al., 2015) , even from relatively few samples. In contrast, in Deep Reinforcement Learning (DRL), the number of samples required for an agent to learn successfully is often very high; many modern algorithms struggle to perform well until they acquire tens of millions of samples (Mirowski et al., 2016; Vinyals et al., 2017; Hessel et al., 2018) , and some even diverge to bad solutions (Anschel et al., 2017) . While there are many facets to sample complexity and brittleness, we posit that a contributing factor is a lack of what we call gradient update generalization, i.e., whether performing updates at one state provides useful information about the value/policy at other states.

Generalization in RL is of two types: (a) generalization to unseen states-will an agent trained on a single MDP pick the optimal action for a state it has never seen before? (b) generalization to unseen tasks-will an agent trained on a distribution of MDPs know how to act in an MDP it has never seen before? Both of these facets are actively studied. For example, Farebrother et al. (2018) expose some generalization failures on the Atari domain (Bellemare et al., 2013) and study the impact of regularization, Zhang et al. (2018) study the generalization capabilities of DRL agents on randomized mazes, Packer et al. (2018) study the extrapolation capabilities of DRL agents trained on a distribution of environment parameters (e.g. pole mass in CartPole) outside of the training distribution, Cobbe et al. (2018) find that even on procedurally generated environments, DRL agents can easily overfit on their training set unless regularized, Oh et al. (2017) study the embedding regularizations necessary for agents to generalize to new instruction sequences on navigation tasks.

In this study, we are not interested in measuring state generalization (i.e. predictions for unseen states), nor task generalization (i.e. in terms of the quality of the behaviour), but rather generalization within the process of stochastic gradient learning. In other words, since any kind of generalization must arise through the accumulation of parameter updates, it seems useful to measure whether these parameter updates are themselves general. To this end, we propose the measure of gradient update generalization, best understood as a side-effect of neural networks sharing parameters over their entire input space. That is, updating parameters after seeing one state will change the prediction for virtually all other states; we are interested in measuring that change.

TD methods are a broad class of RL algorithms that form a target for an update by utilizing the current estimate of the value function. They include TD(0) and TD(λ) methods for estimating the value of a fixed policy, as well as Sarsa and Q-learning algorithms for control. TD methods have achieved success in some challenging tasks (Tesauro, 1995; Mnih et al., 2013; Hessel et al., 2018) , but they are also known to have problems when coupled with function approximation (Sutton, 1995; Baird, 1995; Tsitsiklis & Van Roy, 1997; Chung et al., 2018) . Previous studies explicitly addressed problems such as leakage propagation in TD (Penedones et al., 2018) , while others aimed to provide sampling improvements (Schaul et al., 2015; Andrychowicz et al., 2017; Fu et al., 2019) , explicit temporal regularization (Thodoroff et al., 2018) , or auxiliary tasks which push the agent to learn more about the temporal structure in the data (Jaderberg et al., 2016) .

To our knowledge, no study to date has focused on the dynamics of the generalization process itself, within TD-based DRL methods1 such as deep Q-Learning (Riedmiller, 2005; Mnih et al., 2013 ), Sarsa (Rummery & Niranjan, 1994) , and TD(λ) (Sutton, 1988; Schulman et al., 2015) . For this study, we introduce the aforementioned measure of gradient update generalization, which enables us to differentiate the learning behaviours of different methods. Overall, we find that:

1. when doing a TD(0) update for a single state, parameters change in such a way that the value prediction of other states is generally not affected, surprisingly even for states that are close either temporally or in an annotated "ground truth" state space; 2. DNNs trained with TD(0), in contrast with DNNs trained on a memorization task or using a supervised objective, do not entirely memorize their state space, yet also do not generalize in the way we would expect; 3. both the choice of optimizer and the nature of the objective impact the generalization behaviours of models; in particular, when increasing the λ parameter in TD(λ), DNNs appear to capture more temporal structure.

2. TECHNICAL BACKGROUND:

A Markov Decision Process (MDP) (Bellman, 1957; Sutton & Barto, 2018 ) M = S, A, R, P, γ consists of a state space S, an action space A, a reward function R : S → R and a transition probability distribution P (s |s, a). RL agents aim to optimize the expectation of the long-term return:

EQUATION

where γ ∈ [0, 1) is called the discount factor. Policies π(a|s) map states to action distributions.

Value functions V π and Q π map states/states-action pairs to expected returns, and can be expressed recursively:

EQUATION

While V π could also be learned via regression to observed values of G, these recursive equations give rise to the Temporal Difference (TD) update rules for policy evaluation, relying on current estimates of V to bootstrap, e.g.:

EQUATION

where α ∈ [0, 1) is the step-size. Bootstrapping leads also to algorithms such as Q-Learning (Watkins & Dayan, 1992) and fitted-Q (Ernst et al., 2005; Riedmiller, 2005) :

EQUATION

Sarsa (Rummery & Niranjan, 1994) :

L Sarsa (S t , A t , R t , S t+1 , A t+1 ) = [Q θ (S t , A t )-(R t +γQ θ (S t+1 , A t+1 ))] 2 with A t ∼ π(S t ) (6)

and TD(λ), which trades off between the unbiased target G(S t ) and the biased TD(0) target (biased due to relying on the estimated V (S t+1 )), using a weighted averaging of future targets called a λ-return (Sutton, 1988; Munos et al., 2016) :

EQUATION

(note that the return depends implicitly on the trajectory followed from S t ). When λ = 0, the loss is simply (V θ (S t ) -(R t + γV θ (S t+1 )))2 , leading to the algorithm called TD(0) (Sutton, 1988) .

3. UPDATE GENERALIZATION IN DEEP RL:

We will now define the measure we propose in order to quantify the speed at which generalization to unseen states occurs, and to characterize the structure under which this generalization occurs. We define gradient update generalization as the expected improvement in the loss function L : Θ × X → R after updating parameters θ ∈ Θ, on sample X U ∈ X , using update function U L : Θ × X → Θ (e.g. SGD or a semi-gradient methods like TD(0)):

EQUATION

If generalization from the samples in X U to X is good, this measure of gain should be large, and intuitively fewer other samples should be needed to achieve a desired level of performance. On the other hand, if on average the loss only decreases for the samples X U used in training, then more data in X -X U will have to be visited before the model can learn. Hence, this measure is related to both sample complexity and the speed of learning (see Fig. 15 for empirical confirmation of this phenomenon).

As computing the exact expectation is usually intractable, we empirically measure gains on different subsets X ⊂ X . In particular, when X is chosen to be a slice around X U in the replay buffer, we write Y near . We also subscript Y with the corresponding loss' subscript, e.g. for (5), L QL , we write Y QL . In this study, we are interested in TD-based methods that rely heavily on bootstrapping, Q-Learning, Sarsa, and TD(λ), and measure Y using their respective losses, (5), (6), and (8).

Structure in DNNs A common intuition in deep learning (Zhang et al., 2016; Arpit et al., 2017; Zhang et al., 2018) is that DNNs first learn about the structure of their data, meaning the underlying (usually linear) factors of variation of the data being mapped into the hidden units' space via parameter sharing. These factors of variation are usually conceptualized as a low-dimensional space where each dimension explains part of the data (Bengio et al., 2013) . It is commonly assumed that a model which generalizes well will naturally capture these factors in the configuration of its parameters, in which case the gradient of the prediction w.r.t. all examples sharing the same latent factors of variation will be very close; updating with only one sample will change the prediction for all the related examples. Hence, a DNN which captures structure correctly should show high gradient update generalization.

Temporal structure in RL Data used in RL algorithms usually exhibits two additional types of structure: coherence of the inputs in a trajectory over time (e.g. pixel values in adjacent frames are often similar), and smoothness of the value function in time (in the sparse-reward case with γ close to 1, V (S t ) ≈ γV (S t+1 ), which is smooth in time, aside from rare discontinuities upon seeing rewards).

Since RL data consists of trajectories which often have strong temporal structure of both types, we hypothesize that the gain Y near of temporally correlated examples should increase closer in time to the sample used in the update.

Parameter sharing Another indirect measure of update generalization related to parameter sharing is the difference since last visit, which we denote as ∆. At each update iteration k, we compute the difference between the value V θ k (s) or Q θ k (s, a) predicted from the current parameters, θ k , and V θ last(s) (s) or Q θ last(s) (s, a) , i.e. the prediction made the last time state s was used for a gradient update. 2 To illustrate, if V θ was a lookup table, ∆ would always be 0, while for a DNN, when states are aliased together, ∆ should accurately reflect the effect of parameter sharing after performing sequences of updates (in contrast, (9) uses only a single update).

3.1. EXPERIMENTAL SETUP:

We will now perform a series of experiments aimed at assessing the amount of generalization of various bootstrapping algorithms, compared to supervised learning, in combination with DNNs.

First, we test whether DNNs have a large gradient update generalization gain when trained under ideal conditions (data generated by expert policies and labelled with correct values, which can be used in supervised learning). Then, we test the policy evaluation case (using the same input data, but bootstrapped targets instead of supervised learning). We then test the usual control case, when no expert trajectories are available. Finally, we measure the effect of TD(λ) on generalization gain in policy evaluation, as well as test Q-Learning's robustness to withheld data.

We perform our experiments on the Atari environment (Bellemare et al., 2013) , with the stochastic setup recommended by Machado et al. (2018) . We use a standard DQN architecture (Mnih et al., 2013) .

In order to generate expert trajectories, we use rollouts from a policy trained with Rainbow (Hessel et al., 2018) ; we denote D * a dataset of transitions obtained with this agent, and θ * the parameters after training that agent. For control experiments, we use Mnih et al. ( 2013)'s Q-Learning setup.

When measuring Y near we choose the nearest 60 examples in time to a given state-action pair (30 previous and 30 following on the same trajectory).

3.2. ASSESSING TEMPORAL STRUCTURE WITH SUPERVISED LEARNING:

In this experiment, we will assess if temporal structure, as described above, exists and can be captured by our architecture. To do so, we train DNNs starting from random parameters but with "ideal" targets coming from the expert parameters θ * and expert trajectories D * ; this removes all non-stationarity from the learning. We train Q θ with 3 different objectives:

MC:

EQUATION

Reg:

L reg (s, a; θ) = (Q θ (s, a) -Q θ * (s, a)) 2 (11) TD * : L T D * (s, a, r, s; θ) = (Q θ (s, a) -(r + γ max a Q θ * (s , a ))) 2 (12)

where by G (D * ) (s) we denote the Monte-Carlo return within the dataset D * , as in (1). Note that since L T D * "bootstraps" to θ * , this should be roughly equivalent to L reg , the latter being plain supervised learning (or some sort of distillation, à-la Hinton et al. ( 2012)).

Results are visualized in Fig. 1 for experiments ran on MsPacman, Asterix, and Seaquest for 10 runs each. Results are averaged over these three environments (they have similar magnitudes and variance).

Learning rates are kept constant, they affect the magnitude but not the shape of these curves.

We draw two conclusions from these results. First, as seen in Fig. 1a & 1b, all curves tend to have large gains around x = 0 (the sample used in the update), especially from indices -10 to 10, showing that there is some amount of temporal structure captured by both objectives. Since Q θ * is a good approximation, we expect that

Q θ * (s, a) ≈ (r + γ max a Q θ * (s , a

)), so L reg and L T D * have similar targets and we expect them to have similar behaviours. Indeed, in Fig. 1 their curves mostly overlap. Second, there is a clear asymmetry between training on expectations (i.e. the learned Q(s, a) or max a Q(s , a )) and high-variance Monte-Carlo returns (red and blue curves in Fig. 1a ). We hypothesize that since the returns G are computed from the same state sequence that is used to measure the gain, G is truly informative of the expected value of future states. Strangely, this does not seem to be the case for past states, which is surprising. 3 On the other hand, while G appears more informative of future expected returns, it is not particularly more informative of future sampled returns than past returns, which explains the symmetric nature of the MC gain shown in Fig. 1b . Another striking distinction in these curves appears between the Adam (Kingma & Ba, 2015) and RMSProp (Hinton et al., 2012) optimizers. 4 When moving far away from s, RMSProp tends to induce a negative gain, while Adam tends to induce a near-zero gain. This is seen in Fig. 1a where RMSProp's TD gain is below 0 for states more than 10 steps away from the sample used in an update. Note that similar differences appear in virtually all following experiments, which we discuss later.

3.3. POLICY EVALUATION AND TD GAIN:

We have seen that DNNs can capture some temporal structure and have good gradient update generalization when given good quality inputs and targets. We will now remove the expert targets generated using the pretrained θ * , but we will keep the expert inputs. This corresponds to policy evaluation on expert trajectories, and we would expect to see slightly worse generalization than in the previous case.

We run policy evaluation with 2 objectives, L QL and L Sarsa as defined in (5), and (6) respectively, using a frozen target to bootstrap (Mnih et al., 2013) , updated after every 10k minibatches. Experiments are run on 24 Atari environments (see A.1.1) for 10 runs each. Gain results are visualized in Fig. 2 , averaged over the 24 environments.

The main observation from Fig. 2a is how narrow the peak around 0 is, suggesting that whenever a state's value is updated, the prediction for other states does not change much in expectation, as if the representation were almost tabular, with estimates for encountered states being memorized. The conclusion we draw is that, with a fixed data distribution, DNNs bootstrapping to an evolving target network will not proprely capture temporal structure, but will still be able to learn (at least in the sense of correctly approximating the value function).

Another worrying observation is that RMSProp consistently has negative expected gain for nearby samples (but large, larger than Adam, positive gain on X U , the minibatch sample), suggesting that parameters trained with this optimizer memorize input-output pairs rather than assign capacity to generalize.

3.4. COMPARING MEMORIZATION BEHAVIOUR IN POLICY EVALUATION:

The previous results established that some amount of memorization is done during TD-based policy evaluation. Quantifying memorization is still an open problem, but in this experiment we offer an 1a , almost no temporal structure is captured, which can be seen by how narrow the curve is around distance 0.

interesting qualitative inspection to confirm that TD-based methods may lie somewhere between pure memorization (acting like a lookup table) and strong generalization (capturing all latent factors).

In Zhang et al. (2016) , the authors compare images classifiers trained with true labels to classifiers trained with random labels (in which case the model has to simply memorize the labels), finding that, surprisingly, both can reach 0 training error. While this suggests that DNNs may also memorize when given the true labels, further studies showed many behavioural differences between the two setups, notably that DNNs first captured structure, and only afterwards fit random noise (Arpit et al., 2017) .

Taking inspiration from Zhang et al. (2016) , we assign a random class in [N ] to every state in D * , change our Q function to be a usual classifier with N outputs, and introduce a new objective, L rand , which is simply the cross-entropy between the random class and the prediction. Experiments are run on MsPacman, Breakout, and Seaquest. We use datasets of sizes 10k, 100k, and 500k, and use N ∈ {2, 10, 50}. Interestingly, the architecture of Mnih et al. (2013) that is reused here struggles to reach 0 error5 (for example, a model trained with 10k samples with N = 2 reaches 5.7% error, while a model trained with 500k and N = 50 totally fails at 85% error, see Table ??). Fig. 3 shows the evolution during training of the distribution of ∆(S, A) = Q(S, A; θ current ) -Q(S, A; θ last(S) ), where θ last(S) represents the value of the parameters when S was last used in a minibatch update, and θ current represents the value of the parameters right before using S for the most recent update. If the parameters were those of a look-up table, ∆ would always be 0. For losses other than L rand (Q-Learning, Sarsa, and MC) we reuse the results of the previous section (with a dataset size of 500k).

The difference between Fig. 3a and Fig. 3b-d is compelling, and somewhat reassuring. In Fig. 3a the log-likelihood for ∆ = 0 is above -2 (white) showing that it is very unlikely for the prediction at a state to have changed by more than ±0.01 when it is updated. In contrast, the distribution of ∆ is more spread out in Fig. 3b-d . Combined with the fact that the memorization experiment does not reach 0 error, this allows us to confidently claim that DQN is not fully memorizing its state space. Even though the gain curve in Fig. 2 is very close to 0, except at the update sample (i.e. temporal structure is poorly captured), some structure is captured by DNNs that allow them to learn about a state without having to use it explicitly in an update. In (a) the DNN is forced to memorize, as such the density of ∆ is concentrated around 0 (thin red/white band). In (b-c), Q-Learning and Sarsa, the density is much less peaked at 0 (larger yellow/green bands) as the DNN learns about states without visiting them. In (d) the DNN learns quickly presumably without memorizing (the distribution of ∆ is more spread out and not as concentrated around 0, seen by the larger yellow/green band), as it is trained on Monte-Carlo returns, and quickly converges as can be seen by the high density of positive ∆s early. In (e,f) we see the effect of using λ returns (see appendix A.6 for all values of λ).

3.5. TD GAIN IN CONTROL:

Having removed θ * in section 3.3, we now additionally remove D * and simply perform Q-Learning from scratch on MsPacman, Asterix, and Seaquest for 10M steps.

Results are shown in Fig. 4 . Interestingly, while Q-Learning does not have as strong a gain as the regressions from Fig. 1 , it has a larger gain than policy evaluation. This may have several causes, and we investigate two:

• Initially, because of the random exploratory policy, the DNN sees little data, and may be able to capture a minimal set of factors of variation; then, upon seeing new states, the extracted features are forced to be mapped onto those factors of variation, improving them, leading to a natural curriculum. By looking at the singular values of the last hidden layer's matrix after 100k steps, we do find that there is a consistently larger spread in the policy evaluation case than the control case (see appendix A.3), showing that in the control case fewer factors are initially captured. This effect diminishes as training progresses. • Having run for 10M steps, control models could have been trained on more data and thus be forced to generalize better; this turns out not to be the case, as measuring the same quantities for only the first 500k steps yields very similar magnitudes (see appendix A.4).

Interestingly, these results are consistent with those of Agarwal et al. (2019) , who study off-policy learning. Among many other results, Agarwal et al. (2019) find that off-policy-retraining a DQN model on another DQN agent's lifetime set of trajectories yields much worse performance on average. While the authors suggest the strongly off-policy aspect of this experiment as the cause, our results still show differences between control-Q-Learning and policy-evaluation-Q-Learning, which are both done "on-policy" in our setup, suggesting there are more factors at play than only off-policyness.

Note that we also additionally run experiments with SGD and Momentum-SGD optimizers to highlight the difference between Adam, that has a momentum component, and RMSprop, which only scales per-parameter learning rates. Predictably, Momentum-SGD's behaviour is similar to Adam, and SGD's to RMSprop.

3.6. TD(λ) AND RELIANCE ON BOOTSTRAPPING:

TD(λ) trades off between the immediate biased estimates of the future values and the true return through its λ parameter. To observe the effect of this parameter we perform policy evaluation on D * with the L T D(λ) objective on MsPacman.

Results are shown in Fig. 5 , where we can observe that (1) increasing λ increases near gain without overly increasing update-sample gain (2) as for L M C , there is an asymmetry: updating informs us more about the future than about the past, on average. Results for the distribution of ∆ are shown in Fig. 3(e, f ) (and appendix A.6), where we see that the closer λ is to 1, the more the TD(λ) objective creates updates that affect all states.

These results seem to indicate that TD(λ) better captures factors of variation. One cause could be that the more one relies on a sequence of DNN predictions (i.e. the sequence of n-step returns of the λ-return depend on the successive V (S t+i )) to build a target, the more correlation there is between states and targets (due to DNN smoothness), and the more temporal coherence there is (and thus more opportunities for DNNs to capture the temporal dimension's correlations). This is hard to verify empirically, but we can proxy the correlation measure via the similarity between gradients. We do indeed find that the closer λ is to 1, the higher the average cosine similarity between gradients is (see appendix A.5). This suggests that it may be advantageous to use λ-returns in environments where generalization is important.

3.7. TESTING GENERALIZATION WITH AN INTRA-TASK TEST SET:

Another way to assess whether agents fail to properly generalize in the sense of statistical inferencemaking predictions about states without visiting them -is to create a test set to measure generalization error. We do so on the MsPacman Atari environment, as it contains many opportunities for generalization in translational invariances (locally, the optimal action only depends on the surrounding configuration of the agent, reward pellets, ghosts). We train our agent with the usual DQN setup (Mnih et al., 2013) but prevent the insertion of a state into the replay buffer with some probability p. More specifically, we use the RAM (ground truth) state information to exclude observations from training. We run 5 seeds for each p ∈ {0, 0.1, 0.25, 0.5}.

Results are shown in Fig. 6 , where we see that witholding only 10% of states already slightly affects agents. At 50%, performance is significantly reduced. While this is somewhat expected and consistent with the literature (Farebrother et al., 2018) , it again attests that TD-based methods can struggle with generalization, as observed also by Packer et al. (2018) , who study interpolation and extrapolation failures in deep RL agents.

3.8. ADDITIONAL OBSERVATIONS:

On other structures Our figures mostly show gradient update generalization gain as a function of "time" (temporal distance within a trajectory), but there might be structure elsewhere. We measured gain as a function of 3 different metrics: ground truth state distance by reusing the Annotated Atari RAM of Anand et al. (2019) , value distance (as DNNs may alias states with the same value), and feature distance. Unfortunately, we were unable to find correlations (see appendix A.2).

On convergence Figures 1, 2, and 4 show values averaged over the course of training. We find that except in the first few iterations, these curves remain constant throughout training (see figures in A.4) and show no sign of convergence. This is also consistent with previous studies, as DQN is known to not converge on Atari (Anschel et al., 2017) .

On variance While V ar(Y L ) tends to be large, we find that the confidence interval of the mean is always small, and would barely appear on most of our plots. Additionally, although generalization gain is typically a fraction of the magnitude of the value function, it is consistently non-zero.

On optimizers We find that the systematic differences we see between Adam and RMSProp also occur in behaviour, where control agents trained with RMSProp tend to get slightly more reward. An interpretation of our results is that RMSProp memorizes faster than Adam: it has much larger on-sample gain, it tends to make the singular values of the weight matrices larger, and it has negative near-sample gain, suggesting that capacity is spent memorizing on average. In Atari tasks, memorization can be an efficient strategy (although it is sensitive to noise, see Machado et al. (2018) ). Hence, the better performance of RMSProp on Atari is consistent with our claims. This property may not be as desireable in more complex environments requiring generalization.

4. DISCUSSION:

RL is generally considered a harder problem than supervised learning. Hence, the fact that TD-style methods require more samples than supervised learning when used with deep nets is not necessarily surprising. However, with the same data and the same final targets (the "true" value function), it is not clear why TD updates lead to parameters that generalize worse than supervised learning. This could be a problem, as most RL methods rely on the TD mechanism in one way or another. In particular, our results show that both Q-Learning and Sarsa generalize poorly, leading to DNNs that memorize the training data (not unlike table lookup). Our results also suggest that TD(λ), although not widely used in recent DRL, improves generalization. Finally, we find differences between Adam and RMSProp that we initially did not anticipate. Very little work has been done to understand and improve the coupling between optimizers and TD, and our results indicate that this would be an important future work direction.

Our work suggests that the RL community should pay special attention to the current research on generalization in DNNs, because approaching the TD bootstrapping mechanism as a supervised learning problem does not seem to leverage the full generalization potential of DNNs. Value distance DNNs might alias together (blend into a single point in latent space) all states that have the same value. This would mean that changing the value prediction for one of those states will change the value prediction for all other aliased states. In Figure 7b we see that this effect might occur in the [0, 0.02] bin, where TD gain tends to be positive for TD methods. For Monte-Carlo returns in MsPacman, the effect is negative on average in the [0, 0.02] bin, but otherwise positive from [0.02, 0.3]. There seems to be no correlation otherwise to TD methods. Feature distance We perform again a similar experiment on MsPacman, but using as a distance metric the cosine similarity of activations in the second to last layer. While we do find a minor correlation with distance, its magnitude is very small. In addition, this correlation is easily explained by the geometry of the shallow neural network we use. Since we use leaky ReLUs and measure distance in the second to last layer, when any two states are close in the hidden space, changing the mapping to the output for one state will change the output for the other state with high probability. Thus what we observe here is closer to how much states are entangled in the hidden space rather than a real measure of how update generalization is linked to distance (in true or hidden space). Interestingly, hidden states trained with SGD seem much more entangled, their cosine distance is often 0. This does not seem to be the case with networks trained with Adam and RMSProp.

A.3 SINGULAR VALUES, CONTROL VS POLICY EVALUATION:

Figure 9 shows the spread of singular values after 100k minibatch updates on MsPacman for the Q-Learning objective and Adam/RMSProp. The difference between the control case and policy evaluation supports our hypothesis that policy evaluation initially captures more factors of variation.

It remains unclear if the effect of the control case initially having fewer captured factors of variation leads to a form of feature curriculum.

Figure 10 shows the spread of singular values after 500k minibatch updates for TD(λ). Interestingly, larger λ values yield larger singular values and a wider distribution. Presumably, TD(λ) having a less biased objective allows the parameters to capture all the factors of variation faster rather than to rely on bootstrapping to gradually learn them.

Note that current literature suggests that having fewer large singular values is a sign of generalization in classifiers, see in particular Oymak et al. (2019) , as well as Morcos et al. (2018) and Raghu et al. (2017) . It is not clear whether this holds for regression, nor in our case for regression to value functions, but interestingly all runs (even for TD(λ)), have a dramatic cutoff in singular values after about the 200th SV, suggesting that there may be in this order of magnitude many underlying factors in MsPacman, and that by changing the objective and the data distribution, a DNN may be able to capture them faster or slower. Another interesting observation with respect to the evluation of TD gain from Fig. 3 is that the density is asymmetric, predictions tend to increase during training. This is consistent with the fact that DNNs are initialized to predict 0 in expectation, while value functions for agents that receive mostly positive rewards will tend to be positive. Also note that Fig. 3 In Figure 15 we plot, for an agent trained on MsPacman, the lifetime agent reward (i.e. the AUC of a curve as in Figure 6 ) as a function of the lifetime average near TD gain Y near T D . The line is a linear regression of the points, with a correlation coefficient of r = 0.4337. We vary the capacity of the agent by changing the number of hidden units of every layer, between 0.25× and 4times the original size. Figure 13 : Measuring the distribution of cosine similarity. The y axis shows the density of a given cosine similarity (x axis) between ∇ θ L T D(λ) (S i ) and ∇ θ L T D(λ) (S j ) for 20k (i, j) pairs in the replay buffer. The distributions for positive cosine similarities are similar for all values of λ. On the other hand, on the left side of the plot we can see that when λ gets closer to 0, there are more and more gradients "pointing the wrong way", i.e. with a negative cosine similarity. The labels show the expected cosine similarity over the replay buffer (E = ...), which show that as λ increases, gradients are more similar. Interestingly there are almost no pairs of states with a cosine similarity of 0.

:

In contrast, policy-gradient algorithms such as PPO(Schulman et al.,

2017) A3C(Mnih et al., 2016) and SAC(Haarnoja et al., 2018) are capable of learning good policies without necessarily having learned a good value function, and although interesting results have emerged to understand learning behaviours in policy-gradient methods(Ilyas et al., 2018), these methods build upon TD and analyzing them would add undesired confounders.

In practice, we simply cache the value prediction for all states in a replay buffer (as states in a continuous state space are unlikely to be encountered many times), and update the cache after a minibatch update (for those states only).

A possible explanation is that, due to the exponential discounting nature of returns (V (St) ≈ γ k V (S t+k ) aside discontinuities when R = 0), the correlation between the current and future returns simply has a larger magnitude than with past returns. This might push DNNs to prefer to "assign capacity" w.r.t. future returns.

It has been reported that Adam is less sensitive than RMSProp to hyperparameters in value-based methods(Hessel et al., 2018), although evidence suggests it doesn't help policy gradients(Henderson et al., 2018).

This could be due to the particularly shallow architecture ofMnih et al. (2013), as architectures with less parameters but more layers are commonly assumed to have more effective capacity. It has indeed been shown that deeper models can distinguish between exponentially more linear regions(Montufar et al., 2014).

Figures and Tables:

Figure1: Supervised learning on Atari: Gain as a function of distance in the replay buffer from the update sample. We use dotted lines for the point at 0 distance, to emphasize that the corresponding state was used for the update. (a-b) The curve around 0 indicates the temporal structure captured by the TD and regression objectives.

Figure2: Policy evaluation on Atari: Gain as a function of distance in the replay buffer of the update sample. (a) We use dotted lines for the point at 0 distance to emphasize that the corresponding state was used for the update. (a-b) Compared to regression in Fig.1a, almost no temporal structure is captured, which can be seen by how narrow the curve is around distance 0.

L T D(λ) , λ = 0.95

Figure3: Policy evaluation on Atari: evolution of the distribution of ∆, the difference since last visit, during training. In (a) the DNN is forced to memorize, as such the density of ∆ is concentrated around 0 (thin red/white band). In (b-c), Q-Learning and Sarsa, the density is much less peaked at 0 (larger yellow/green bands) as the DNN learns about states without visiting them. In (d) the DNN learns quickly presumably without memorizing (the distribution of ∆ is more spread out and not as concentrated around 0, seen by the larger yellow/green band), as it is trained on Monte-Carlo returns, and quickly converges as can be seen by the high density of positive ∆s early. In (e,f) we see the effect of using λ returns (see appendix A.6 for all values of λ).

Near TD gain, Y near T D , zoom excluding XU , i.e. distance 0, to show the magnitude of generalization

Figure4: Q-Learning on Atari: Gain as a function of distance in the replay buffer of the update sample. (a-b) Compared to policy evaluation, gain appears to be better, but not as large as for regression. (b) For Adam and RMSProp, we include the corresponding curves for policy evaluation in lighter shades.

Figure 5: TD gain for policy evaluation with TD(λ) & Adam. Note the larger gain as λ goes to 1, as well as the asymmetry around 0.

Policy evaluation, TD gain as a function of distance in value predictions.

Figure 7: TD gain as a function of other metrics. Shaded regions are the standard error to the mean.

Figure 8: Policy evaluation with L QL , TD gain as a function of cosine distance in hidden space (second to last layer).

Figure 9: Spread of singular values after 100k iterations. Despite having seen roughly the same amount of data, the control experiments generally have seen fewer unique states, which may explain the observed difference. Shaded regions show bootstrapped 95% confidence intervals.

Figures 12 and 13 show cosine similarities between gradients after 500k updates.

Figure 12: Measuring the cosine similarity in a sequence. The y axis shows the similarity between∇ θ L T D(λ) (S t ) and ∇ θ L T D(λ) (S t+k ) for the nearest k ∈ [-30, 30]  neighbours in the replay buffer. The larger λ is, the more similar gradient updates are for two states when those states are close in time. Shaded regions show bootstrapped 95% confidence intervals.

∇ θ L(S i ) and ∇ θ L(S j )

Peer review (iclr2020):
The manuscript is analyzing the *generalization* in TD(lambda) methods. It includes supervised learning from trajectories, on-policy imitation learning, and basic RL setting. Moreover, memoization performance has also been measured. Main conclusion is the fact that TD(0) performs very similar to tabular learning failing to transfer inductive biases between states. There are also additional surprising results about optimization. The empirical study is rather complete and significant. It raises interesting questions for the community and states some clear open problems. Results are conclusive and interesting. I believe it is a study which a practitioner using TD-based method should be aware of. Hence, I believe it is impactful. On the other hand, the manuscript has some significant issues which need to be resolved as follows: - One major issue is calling the analyzed metric *generalization*. Generalization by definition requires something beyond what is seen. I believe the quantity defined in (9) is generalization. However, it can not be computed. Hence, calling its empirical version, *generalization* is confusing and a clear misuse of the term. I strongly urge authors to call the observed quantity something else. *Empirical expected improvement*, *gradient regularity*, *expected gain*, etc. are some candidates come to my mind. - The optimization aspect is very interesting; however, it confuses the exposition significantly. I think it is better to give all results using adam first, and then showing the comparisons between adam and rmsprop later would be much more readable and easier to understand. - There are some clarity issues in the explanation of the experiments. Figure 3 is very confusing and it requires multiple reading to be understandable. A clearer visualization or a better explanation would improve the paper. - I am puzzled about why the authors did not use Q_MC in policy evaluation experiments (Section 3.3). I think it can very well be used in a straightforward manner. It would be an interesting addition to the experiments. Minor Nitpicks: - Memorization section is not clear. The discussion on N is very confusing as *14.4% for N = 2 and of 16.1% for N = 50* does not match any of *10.5%, 22.7%, and 34.2%* Can you give full error table in appendix? Overall, I like the study and suggest to accept it hoping authors can fix the issues I raise during rebuttal period.