Observational Overfitting in Reinforcement Learning
Authors: Xingyou Song
Yiding Jiang
Stephen Tu
Yilun Du
Behnam Neyshabur
Venue:  (2020)
Keywords: observational
overfitting
reinforcement
learning
generalization
implicit
regularization
overparametrization

Abstract: A major component of overfitting in model-free reinforcement learning (RL) involves the case where the agent may mistakenly correlate reward with certain spurious features from the observations generated by the Markov Decision Process (MDP). We provide a general framework for analyzing this scenario, which we use to design multiple synthetic benchmarks from only modifying the observation space of an MDP. When an agent overfits to different observation spaces even if the underlying MDP dynamics is fixed, we term this observational overfitting. Our experiments expose intriguing properties especially with regards to implicit regularization, and also corroborate results from previous works in RL generalization and supervised learning (SL). 

Published as a conference paper at ICLR 2020
OBSERVATIONAL OVERFITTING IN REINFORCEMENT LEARNING
Xingyou Song", Yiding Stephen Tu, Behnam Neyshabur
Google
(xingyousong, ydjiag anng, stephentu, mwyshabuy regggeebrrbbbbbbeggglle...ooo
Yilun Du
MIT yi yilundu@mit.edu
ABSTRACT
A major component of overfitting in model-free reinforcement learning (RL) in- volves the case where the agent may mistakenly correlate reward with certain spurious features from the observations generated by the Markov Decision Process (MDP). We provide a general framework for analyzing this scenario, which we use to design multiple synthetic benchmarks from only modifying the observation space an MDP. When an agent overfits to different observation spaces even if the underlying MDP dynamics is fixed, we term this observational overfitting. Our experiments expose intriguing properties especially with regards to implicit regu- larization, and also corroborate results from previous works in RL generalization and supervised learning (SL).
INTRODUCTION
Generalization for RL has recently grown to be an important topic for agents to perform well in unseen environments. Complication arises when the dynamics of the environments entangle with the observation, which is often high-dimensional projection of the true latent state. One particular framework, which we denote by zero-shot supervised framework frameeeork. (Zhang et al. 2018af c, Nichol al. 2018 Justesen et al., 2018) and is used to study RL generalization, to treat it analogous to MDP's, train
classical supervised learning (SI.) problem i.e. assume there exists a distribution jointly a finite "training set" sampled from this distribution, and check expected performance on the entire distribution, with the fixed trained policy. In this framework, there is a spectrum of
analysis, ranging from almost purely theoretical analysis (Wang et al. 2019 Asadi al. 2018 to full empirical results on diverse environments (Zhang et al. 2018c Packer et al. 2018).
However, there is lack analysis in the middle of this spectrum. On the theoretical side, previous work do not provide analysis for the case when the underlying MDP is relatively complex and requires the policy to be a non-linear function approximator such as a neural network. On the empirical side, there is no common ground between recently proposed empirical benchmarks. This is partially caused by multiple confounding factors for RI. generalization that can be hard identify and separate. For instance, an agent can overfit to the MDP dynamics of the training set, such as for control in Mujoco (Pinto al. 2017: Rajeswaran et al. 2017). In other cases, an RNN-based policy can overfit to maze-like tasks in exploration (Zhang al. 2018c), observations (Bellemare et al. [0122] Machado et al. 2018). Furthermore, various hyperparameters such as the batch-size in SGD (Smith al. 20188), choice of optimizer (Kingma & Ba 2014), discount factor y (Jiang et al. 2015) and regularizations such as entropy (Ahmed et al. 2018) and weight norms (Cobbe al. 2018) can also affect generalization.
exploit determinism and avoid using
Wook partially performed as an OpenAl Fellow.
Work performed during the Google AT Residency Program. http::/ rest dency

---

Published as a conference paper at ICLR 2020
Due to these confounding factors, it can be unelear what parts of the MDP or policy are actually contributing to overfitting or generalization in a principled manner, especially in empirical studies with newly proposed benchmarks. In order to isolate these factors, we study one broad factor affecting generalization that is most correlated with themes in St., specifically observational overfitting, where an agent overfits due properties of the observation which irrelevant the latent dynamics of the MDP family. To study this factor, we fix single underlying MDP's dynamics and generate distribution of MDP's by only modifying the observational outputs.
Our contributions in this paper are the following:
1. We discuss realistic instances where observational overfitting may occur and its difference from other confounding factors, and design a parametric theoretical framework to induce observational overfitting that can be applied any underlying MDP.
2. We study observational overfitting with linear quadratic regulators (LQR) in a synthetic environment and neural networks such as multi-layer perceptrons (MLPs) and convolutions in classic Gym environments. A primary novel result we demonstrate for all cases is that implicit regularization occurs in this setting in RL. We further test the implicit regularization hypothesis on the benchmark CoinRun from using MLPs, even when the underlying MDP dynamics are changing per level.
3. In the Appendix, we expand upon previous experiments by including full training curve and hyperparamters. We also provide an extensive analysis of the convex one-step L.QR case under the observational overfitting regime, showing that under Gaussian initialization of the policy and using gradient descent on the training cost, a generalization gap must necessarily exist.
The structure of this paper is outlined as follows: Section 2 discusses the motivation behind this work and the synthetic construction to abstract certain observation effects. Section demonstrates numerous experiments using this synthetic construction that suggest implicit regularization is at work. Finally, Section 3.4 tests the implicit regularization hypothesis on CoinRun, as well ablates various ImageNet architectures and margin metrics in the Appendix.
MOTIVATION AND RELATED WORK
We start by showing an example of observational overfitting Figure This example highlights the issues surrounding MDP's with rich, textured observations specifically, the agent use any features that are correlated with progress, even those which may not generalize across levels. This is an important issue for vision-based policies, many times it is not obvious what part of the observation causes an agent to act or generalize.
SCORE
SCORE
THE 0:04
TIME
1:45
RINGS
RINGS
9
Figure 1: Example of observational overfitting in Sonic from Gym Retro Nichol et al. 2018). Saliency maps (Greydanus et al., 2018) highlight (in red) the top-left timer and background objects such as clouds and textures because they are correlated with progress, as they move backwards while agent is moving forwards. The agent could memorize optimal actions for training levels even if its observation was only from the timer, and "blacking-our" the timer consistently improved generalization performance (see Appendix A.2.3).
Currently most architectures used in model-free RL are simple (with fewer than one million parame- ters) compared to the much larger and more complex ImageNet architectures used for classification.
2

---

Published as a conference paper at ICLR 2020
This is due to the fact that most RL environments studied either have relatively simple and highly structured images (e.g. Atari) compared to real world images, or conveniently do not directly force the agent to observe highly detailed images. For instance in large scale RL such as DOTA2 (OpenAI 2018) or Starcraft 2 (Vinyals et al. 2017), the agent observations are internal minimaps pertaining to object xy-locations, rather than human-rendered observations.
2.1 WHAT HAPPENS IN OBSERVATION SPACE?
Several artificial benchmarks (Zhng et al. 2018b Gamrian & Goldberg 2019) have been proposed before to portray this notion of overfitting, where agent must deal with changing background however, a key difference in our work is that we explicitly require the "background" to be correlated with the progress rather than loosely correlated (e.g. through determinism between the background and the game avatar) or not at all. This makes a more explicit connection to causal inference (Arjovsky et al. 2019; Heinze- Deml & Meinshausen 2019 Heinze-Demn et al., 2019) where spurious correlations between ungeneralizable features and progress may make training easy, but are detrimental to test performance because they induce false attributions.
Previously, many works interpret the decision-making of an agent through saliency and other network visualizations (Greydanus et al. 2018: SSuch et al., 2018) on common benchmarks such as Atari Other recent works such (Igl et al. 2019) analyze the interactions between noise-injecting explicit regularizations and the information bottleneck. However, our work is motivated by learning theoretic frameworks capture this phenomena, there is vast literature understanding the generalization
properties of SL classifiers (Vapnik & Chervonenkis 1971 McAllester 1999; Bartlett & Mendelson 2002) and in particular neural networks (Neyshabur al. 20155; Dziugaite & Roy [017 Neyshabur et al. 2017: Bartlett et al., 2017] Arora et al.) 2018c). For an RL policy with high- high-dimensional observations, we hypothesize its overfitting can come from more theoretically principled reasons, as opposed to purely good inductive biases on game images.
As an example of what may happen in high dimensional observation space, consider linear least squares regression task where given the set X E Rmxxd and Y E RT, we want to find w E Rd that minimizes l (x,r(w) (w) = ||Y -xwll² where m is the number of samples and d is the input dimension. We know that if X X is full rank (hence d I m), εx,y (.) has unique global minimum Y. On the other hand if X X is not full rank (eg. when m < d), then there are
2 = (XTX)) XT.. many global minima w* such that = Xw Luckily, if we use any gradient based optimization to minimize the loss and initialize with w = O. the solution will only span column spaces of X and converges to minimum E norm solution among all global minima due to implicit regularization (Gunasekar al.] (017). Thus a high dimensional observation space with low dimensional state space can induce multiple solutions, some of which are not generalizable to other functions or MDP's but one could hope that implicit regularization would help avoiding this issue. We analyze this case in further detail for the convex one-step LQR case in Section 3.1 and Appendix A.4.3
2.2 NOTATION
In the zero-shot framework for RL generalization, assume there exists distribution D over MDP's M for which there exists a fixed policy Tht that can achieve maximal return on expectation over MDP's generated from the distribution. An appropriate finite training set Mirasn = {MI...., } can then be created by repeatedly randomly sampling M DD Thus for MDP M and any policy π, expected episodic reward is defined as (TT.
In many empirical cases, the support of the distribution D is made by parametrized MDP's where some process, given parameter 6. creates a mapping 0 + MMg (e.g. through procedural generation). and thus we may simplify notation and instead define a distribution @ that induces D. which implies a set of samples redefine reward RMo (T(
θ Oprain =
b,} also induces a Merain = (Mi,..., M, and we may
'Given any X with full rank X X, it is possible to create many global minima by projecting the data onto high dimensions using a semi-orthogonal matrix Z E Rxxdd where d' > m 2 and Zz T = La. Therefore, we the loss (x (w) = ||Y 7 will have many global optima w² with Y XZw"
3

---

Published as a conference paper at ICLR 2020
Puyyposstons, Heath, Scom Row Strm (5)
Tredegmand
W
(s(e)
(a)
(b)
Figure 2: (a) Visual Analogy of the Observation Function. (b) Our combinations for 1-D (top) and 2-D (bottom) images for synthetic tasks.
As a simplified model of the observational problem from Sonic, we can construct mapping Ma by first fixing a base MDP M (S, A. T), which corresponds to state space, action space, reward, and transition. The only effect of is to introduce an additional observation function óg : S + O where the agent receives input from the high dimensional observation space O rather than from the state space S. Thus, for our setting, actually parameterizes POMDP family which can be thought of simply combination of base MDP M and an observational function Φe. hence Mg = oo).
Let Otrain (01,..., )n) be set of n i.i.d. samples from θ, and suppose we train æ to optimize reward against (Ma 0 O.rain]. The objective Jg(TT) [Beriin] Eg,c@rramn Ra, (T) is the average reward over this empirical sample. We want to generalize to the distribution O which can be expressed as the average episode reward R over the full distribution, i.e. Je( Ee (T)). Thus we define the generalization gap J3(T)) Je(T).
2.3 SETUP
We model the effects of Figure more generally, specific to sidescroller games. We assume that there is an underlying state (e.g. xy-locations of objects in a game), whose features may be very well structured, but that this state has been projected to high dimensional observation space by 6g. To abstract the notion of generalizable and non-generalizable features, we construct a simple and natural candidate class of functions, where
ss(s) h(f(ss)
In this setup. f()) is function invariant for the entire MDP population é, while ga(-) is a function dependent on the sampled parameter 0. is "combination" function which combines the two outputs of of and to produce final observation. While f projects this latent data into salient and important, invariant features such as the avatar, monsters, and items, Go projects the latent data to unimportant features that do not contribute to extra generalizable information, and can cause overfitting, such as the changing background or textures. visual representation shown in Figure
2 This is simplified but still insightful model relevant in more realistic settings. For instance, in settings where ge does matter, learning this separation and miskiideniffiatiin YYu et al. 2017 Peng al.) 2018) could potentially help fast adaptation in meta-learning (Finn et al. 2017). From now we denote this setup as the (f, g) -scheme.
This setting also leads to more interpretable generalization bounds Lemma 2 of (Wang al. 2019) provides a high probability (1 5) bound for the "intrinsic" generalization gap when m levels are
sampled: gap S Rad, (Rn) O log(1/8)
where
m Σ o, Ro (T) i=1
Rad (Rn) = E(g Bmm@m
Eoc(-1,413
sup JElT m
(2)
4

---

Published as a conference paper at ICLR 2020
is the Rademacher Complexity under the MDP, where 0 are the S parameters used in the original work, and the transition T and initialization I are fixed, therefore omitted, to accommodate our setting.
The Rademacher Complexity term captures how invariant policies in the set II with respect to 8. For most RL benchmarks, this is not interpretable due to multiple confounding factors such as the varying level dynamics. For instance, it is difficult to imagine what behaviors or network weights a policy would possess in order to produce the same total rewards, regardless of changing dynamics.
However, in our case, because the environment parameters 0 are only from go. the Rademacher Complexity is directly based on how much the policy "looks at" go. More formally, let IT be the set of policies π which are not be affected by changes in i.c. VaT (de(s) 0 Vs and thus Rg (T*) Reonst v0, which implies that the environment parameter 0 has no effect on the reward; hence Radm (RT-) (o [sup= m >> ReRestt]] 0.
2.4 ARCHITECTURE AND IMPLICIT REGULARIZATION
Normally in a MDP such as game, the concatenation operation may be dependent time (c.g. textures move around in the frame). In the scope this work, we simplify the concatenation effect and assume (-)) ) is a static concatenation, but still are able demonstrate insightful properties. We note that this inductive bias on h allows explicit regularization to trivially solve this problem, by penalizing policy's 's first layer that is used to "view" go (s) (Appendix A.1.I. hence we only focus on implicit regularizations.
This setting is naturally attractive analyzing architectural differences, it is more closely related in spirit to image classifiers and SL. One particular line of work to explain the effects of certain architectural modifications in SL such as overparamettrization and residual connections implicit regularization (Neyshabur et al. [2015a Gunasekar et al. [0177] Neyshabur 2017), as overparametriza- tion through more layer depth and wider layers has proven to have no 4p reguullariiition equivalent (Arora et al., 2019), but rather precondition the dynamics during training. Thus, in order to fairly experimentally measure this effect, we always use fixed hyperparameters and only vary based on architecture. In this work, we only refer to architectural implicit regularization techniques, which do not have a explicit regularization equivalent. Some techniques e.g. coordinate descent (Bradley et al.. 2011) are equivalent to explicit & rrrguularizztion.
EXPERIMENTS
3.1
OVERPARAMITERIZED LQR
We first analyze the case of the LQR surrogate for what may occur in deep RL, which has been done before for various topics such as sample complexity (Dean et al., 2019) and model-based RL 2019). This analogous analyzing linear/logistic regression (Kakade al.) 2008 McAllester 2003) as a surrogate to understanding extensions to deep SL. techniques (Neyshabur et al. 2018a Bartlett al. 2017). In particular, this has numerous benefits the cost (negative of reward) function is deterministic, and allows exact gradient descent (i.c. the policy can differentiate through the cost function) opposed to necessarily using stochastic gradients in normal RL, and thus can cleanly provide evidence of implicit regularization. Furthermore, in terms of gradient dynamics and optimization, LQR readily possesses nontrivial qualities compared linear regression, as the LQR cost is a non-convex function but all of its minima are global minima (Fazel et al. 2018) 8).
TTu & Recht
To show that overparametrization alone an important implicit regularizer in RI, LQR allows the use of linear policies (and consequently also allows stacking linear layers) without requiring stochastic output such as discrete Gumbel-softmax or for the continuous case, a parametrized Gaussian. This is setting able to show that overparametrization alone can affect gradient dynamics, and is not consequence of extra representation power due to additional non- non-lincarities in the policy. There have been multiple recent works this finear-laeer stacking in SL and other theoretical problems such as matrix factorization and matrix completion (Arora et al.) 2018b a Gunasekar et al. 2017), but to our knowledge, we the first to analyze this case in the context of RL. generalization.
5

---

Published as a conference paper at ICLR 2020
We explicitly describe setup follows: for given 0 we let f(s) We while go(s) We where We. Wa are semi-orthogonal matrices, to prevent information loss relevant to outputting the optimal action, as the state is transformed into the observation. Hence, if s, is the underlying state
W
at time f, then the observation is or Wo
8; and thus the action is
Ko,, where K is the
policy matrix. While We remains constant matrix, we sample W6 randomly, using the "level ID" integer 0 as the seed for random generation. In terms of dimensions, if is of shape datates then also projects to a shape of dstate. while go projects to a much larger shape dnoises implying that the observation to the agent is of dimension daignal + dnoise. In experiments, set as default (dsignal, )nosee) = (100, 1000).
If I.P. is the unique minimizer of the original cost function, then the unique minimizer of the population W.P.T T 0
cost is K.
However, if we have a single level, then there exist multiple solutions,
aW. PT
Yo. This extra bottom component W causes overfitting. In Appendix A.4.3 we show that in the 1-step LQR case (which can be extended to convex losses whose gradients are linear the input), gradient descent cannot remove this component, and thus overfitting necessarily occurs.
for instance a WP
Furthermore, we find that increasing droise increases the generalization gap in the LQR setting. This is empirically verified in Figure 3 using an actual non-convex LQR loss, and the results suggest that the gap scales by O (. In terms of overparametrization, we experimentally added more (100 x 100) linear layers K KoK1,.... ...., K, and increased widths for a 2-layer case (Figure 3. and observe that both settings reduce the generalization gap, and also reduce the norms (spectral, nuclear, Frobenius) of the final end-to-end policy K, without changing its expressiveness. This suggests that gradient descent under overparametrization implicitly biases the policy towards a "simpler" model in the LQQ case.
Varying Layers
2-Layer, Varying Width
1.0
1.0
Generalization (Log) va Dimension (Log)
0.8
0.8
Nommalized Value
Gap (e")
0.6
0.6
0.4
M41
0.2
0.2
Sped Pood
Gap Log Noise 1/2-Slopa Fit Line
"ood
0.0
6.5 Noisa Dimonsioo (e*)
3 Num Extra Layers
5
7
10
11
12
Width
Figure 3: (Left) We show that the generalization gap vs noise dimension is tight as the noise dimension increases, showing that this bound is accurate. (Middle and Right) LQQ Generalization Gap vs
Number of Intermediate Layers. We plotted different & Ei= ||AIL.
TAT terms without exponents, as
powers of those terms are monotonic transforms since |||||_ > VA and ||A|], ||A||| p. ||Al| We [|
see that the naive spectral bound diverges at layers, and the weight-counting sums are too loose.
As a surrogate model for deep RI., one may ask the generalization gap of the final end-to-end policy K can be predicted by functions of the layers Ko. Ky. This is important question as is a required base case for predicting generalization when using stochastic policy gradient with nonlinear activations such as ReLU Tanh. From examining the distribution of singular values on K (Appendix [..end. I...II.. we find that more layers does not bias the policy towards a low rank solution in the nonconvex LQR case, unlike (Arora et al. 2018b) which shows this does occur for matrix completion, and in general, convex losses. Ultimately, we answer in the negative: intriguingly, SL. bounds have very little predictive power in the RL domain case.

---

Published as a conference paper at ICLR 2020
To understand why SL bounds may be candidates for the LQR case, note that basic smoothness bound ((K) - C(K) I O K - K* (Appendix (..4) can lead to very similar reasoning with SL bounds. Since setup is similar to SL in that "LQR levels" which may be interpreted
dataset,
we use bounds of the form A A- where A is "macro" product term A = II |K 2 Io K;
derivable from the fact that || & ||]]] in the linear case, and &b is weight-counting term
which deals with the overparametrized case, such as Ei=
I. l (Nyyshabur et al. 2018a) ||
2/3 3
or +-
Σ
J.J.IhI [K
Bartlett et al. 2017). However, the &b terms increase too rapidly as
shown in Figure 3 Terms such as Frobenius product (Golowich et al. 2018) and Fischer-Rao (Liang et al.] 2 are effective for the SL depth case, but are both ineffective in the LQR depth case. For width, the only product which is effective is the nuclear norm product.
3.2 PROJECTED GYM ENVIRONMENTS
In Section 3.1 we find that observational overfitting exists and overparametrization potentially helps in the linear setting. In order to analyze the case when the underlying dynamics are nonlinear, we let . be a classic Gym environment and we generate MMa- (M, wx) by performing the exact same (f, (..g)-ssemmm as the LQR case, i.e. sampling 0 to produce an observation function We
(s))s =
8. We again can produce training/test sets of MDPs by repeatedly sampling 0, and Wg
for policy optimization, we use Proximal Policy Gradient (Schulman et al. 2017).
Although bounds on the smoothness term R₂(T)) - Re(T') affects upper bounds on Rademacher Complexity (and thus generalization bounds), we have no such theoretical guarantees in the Mujoco case as it is difficult to analyze the smoothness term for complicated transitions such as Mujoco's s physics simulator. However, in Figure we can observe empirically that the underlying state dynamics has significant effect on generalization performance as the policy nontrivially increased test performance such as in CartPole-vl and Swimmer-v2, while could not for others. This suggests that the Rademacher complexity and smoothness the reward function vary highly for different environments.
CarlPole-v1
HallCheetah-v2
Hopper-v2
500
3000
2000
2500
1750
400
2000
1500
300
1500
1250
1000
1000
200
500
750
100
0
500
250
Reward
-500
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Reacher-v2
Swimmer-
Walker2d-v2
120
3500
0
-100
100
3000
2500
-200
80
2000
-30
60
1500
-400
-500
40
1000
-600
20
500
-700
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
1e8
1e8
1e8
Fram
esst
Total Timesteps
Figure 4: Each Mujoco task is given 10 training levels (randomly sampling go parameters). We used a 2-layer ReLU policy, with 128 hidden units each. Dimensions of outputs of (f.g) were (30, 100) respectively.
Even though it is common practice to use basic (2-layer) MLPs in these classic benchmarks, there are highly nontrivial generalization effects from modifying on this class of architectures. Our results in
7

---

Published as a conference paper at ICLR 2020
Figures 5 and 6 show that increasing width and depth for basic MLPs can increase generalization and is significantly dependent on the choice of activation, and other implicit regularizations such as using residual layers also improve generalization. Specifically, switching between ReLU and Tanh activations produces different results during overparametrization. For instance, increasing Tanh layers improves generalization CartPole-vl, and width increase with ReLU helps Swimmer-v2. Tanh is noted to consistently improve generalization performance. However, stacking Tanh layers comes a cost also producing vanishing gradients which can produce subpar training performance, for e.g. HalfCheetah. To allow larger depths, we use ReLU residual layers, which also improves generalization and stabilizes training.
CartPole-v1, 10 Levels, Varying Layers
HalfCheetah-v2. 50 Levels, Varying Layers
500
4000
3500
400
3000
Reward
300
Tarh Town
Tarh Tex:
2500
ISLL Tren
2000
200
RuUU
1500
1000
Hesdual
100
500
ReLU
2
5
7
4
5
7
Number Layers
Layers
Figure 5: Effects of Depth.
CartPole-v1, 10 Levels, Varying Width
Swimmer-v2 30 Levels, Varying Width
500
120
400
100
Reward
Tran Tost
Reward
300
80
200
80
Tesh Text
de UiTrer
ReLU Tee
8
10
11
12
13
5
6
8 Width,
10
11
Width.
Figure 6: Effects of Width.
Previous work (Zhang al. 2018c) did not find such architectural pattern for GridWorld environ- ments, suggesting that this effect may exist primarily for observational overfitting cases. While there have been numerous works which avoid overparametrization on simplifying policies (Rajeswaran et al., 20177: Mania et al.] 2018) or compactifying networks (Choromanski et al., 2018 Gaier & 2019), we instead find that there are generalization benefits to overparametrizztion even the nonlinear control case.
3.3 DECONVOLUTIONAL PROJECTIONS
From the above results with MIPs, may wonder if similar results may carry convolutional networks, as they are widely used for riseed RL tasks. As ground truth reference for our experiment, the canonical networks proven generalize well in the dataset CoinRun, which are from worst to best, NatureCNN Mnih et al. (201)). IMPALA Espeholt et al, (2018). and IMPALA- LARGE (IMPALA with more residual blocks and higher convolution depths), which have respective parameter numbers (600K, 622K, 823K).
We setup a similar (chh)m appropriate for the inductive bias convolutions, by passing the vanilla Gym ID state corresponding to joint locations and velocities, through multiple deconvolutions. We do so rather than using the RGB image from env. render () to enforce that the actual state indeed low dimensional and minimize complications in experimentation, e.g. inference of velocity information would require frame-stacking.
Specifically in our setup, we project the actual state to fixed length, reshaping it into square, and replacing f and ge both with the same aathooonall--initalizzze
deconvolution architecture to each produce a 84 84 image (but go 's network weights are still generated by 01,... .... fn similar to before). We combine the two outputs by using one half of the "image" from f. and one half from go. as shown back in Figure
8

---

Published as a conference paper at ICLR 2020
CartPole-v2. 50 Levels
Swimmer-v2, 10 Levels
Reacher-v2 5 Levels
500
120
100
800
80
-400
200
NattreGNN
100
20
-800
IMPALA
IMPALA
2
0.0 0.5
1.0
1.5
20
2.5
3.0
3.5
4.0
1000
0.0
0.2
0.4
0.6
0.8
1,0
127
Total Timesteps
167
1e7
Figure 7: Performance of architectures the synthetic Gym- dataset. To cleanly depict test performance, training curves are replaced with horizontal (max env. reward) and vertical black lines (avg. timestep when all networks reach max reward).
NatureCNN
IMPALA
IMPALA-Large
20
20
1.0
1.5
2.0
0.5
1.0
1.5
25
3.0
0.0
0.5
20
25
3.0
ter
Total Timestaps
167
167
Figure 8: We only show the observation from go(s), which tests memorization capacity on Swimmer-v2.
Figure shows that the same ranking between the three architectures exists as well the Gym- Decony dataset. We show that generalization ranking among "'tureCNN/IMPAALVIIMPA LARGE remains the same regardless of whether we our synthetic constructions CoinRun. This suggests that the RI generalization quality convolutional architecture not limited to real world data, as our test purely uses numeric observations, which are not based on human-prior, From these findings, one may conjecture that these RL generalization performances are highly correlated and may be due to common factors.
One of these factors we suggest is due to implicit regularization. In order to support this claim, we perform a memorization test by only showing ge 's output to the policy. This makes the dataset impossible to generalize to, as the policy network cannot invert every single observation function go.,( (-)} simultaneously. /Zhang et al. (201cc) also constructs memorization test for mazes and grrldworlds, and showed that more parameters increased the memorization ability of the policy. While it is intuitive that more parameters would incur more memorization, we show in Figure [ that this is perhaps not complete picture when implicit regularization is involved.
(,,
Using the underlying MDP as a Swimmer-v2 environment, we see that NatureCNN, IMPALA, IMPALA-LARGE have reduced memorization performances. IMPALA-LARGE. which has more depth parameters and more residual layers (and thus technically has more capacity), memorizes less than IMPALA due its inherent inductive bias. While memorization performance is dampened in 8 perform another deconvolution memorization test using an LQR as the underlying MDP in Appendix A.1.I that shows that there can exist specific hard limits memorization, which also follows the same ranking above.
3.4 OVERPARAMETRIZZATIN IN COINRUN
further test our overparametrization hypothesis from Sections 3.1 to the CoinRun benchmark, using unlimited levels for training. For MLP networks, we downsized CoinRun from native 64 x 64 to 32 x 32, and flattened the 32 x 32 x 3 image for input to an MLP. Two significant differences from the synthetic relevant and irrelevant CoinRun features change locations across the 1-D input vector. Regardless, in Figure 9 we show that overparametrization still improve generalization in this more realistic
that 1. Inherent dynamics
changing per level in CoinRun, and 2. The

---

Published as a conference paper at ICLR 2020
RL benchmark, much akin to (Neyshabur et al.
2018b) which showed that overparametrizzatoon for
MLP's improved generalization on 32 x 32 x 3
CIFAR-I0.
Soinrun-Unlimited MLP Depth (ReLU)
Coinrun-Unlimited, MLP Width (ReLU)
8
6
Reward
Reward
4
Layers
4
Layers
Layerr
With
Layors
2
2048 Widh
Laaers
4095 Width
Layers
01552 Wadth
0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0 1e7
Total Timesteps
1e7
Total Timesteps
Figure 9: Overparametrization improves generalization for CoinRun.
While we also extend the case of aargepparamete convolutional networks using ImageNet networks in Appendix | an important question is how to predict the generalization gap only from the of metrics, popular in the SL community are margin distributions (Jiang et al. 2018 Bartlett et al. 2017). as they deal with the case for softmax outputs which do not explicitly penalize the weight norm of network, by normalizing the "confidence" margin of the logit outputs. While using margins on state-action pairs (from an on-policy replay buffer) is not technically rigorous, one may be curious to see if they have predictive power, especially as MLPs relatively simple to norm-bound. We plotted these margin distributions in Appendix A.2.2 but found that the weight norm bounds used in SL are simply too dominant for this RL case. This, with the bound results found earlier for the LQR case, suggests that current norm bounds are simply too loose for the RL case even though we have shown overparametrization helps generalization in RL, and hopefully this motivates more of the study of such theory.
training phase. A particular
CONCLUSION
We have identified and isolated key component of overfitting in RL as the partieular case of "obser- vational overfitting". which is particularly attractive for studying architectural implicit regularizations. We have analyzed this setting extensively, by examining 3 main components:
1. The analytical case of LQQR and linear policies under exact gradient descent, which lays the foundation for understanding theoretical properties of networks in RL generalization.
2. The empirical but principled Projected- which demonstrates the effects of neural network policies under nonlinear environments.
case for both MI.P and convolutional networks
3. The large scale case for CoinRun, which can be interpreted as case where relevant features are moving across the input, where empirically, MLP overparametrization also improves generalization.
We noted that current network policy bounds using ideas from SL are unable to explain over- parametrization effects in RI, which is an important further direction. In some sense, this area of RL. generalization an extension of static SI. classification from adding extra RI components. For instance, adding nontrivial "combination function" between ff and ge that is dependent on time (to simulate how object pixels move in a real game) is both an RL generalization issue and potentially video classification issue, and extending results to the memory-basse RNN case will also be highly beneficial.
Furthermore, it unclear whether such overparametrizatton effects would occur in off- teffcolicy methods such as Q-lcarning and also ES-based methods. In terms of architectural design, recent works (Jacot al., 2019: Lee et al., 2019) have shed light the properties of asymptotically overparametrized neural networks in the infinite width and depth cases and their performance in SL. Potentially such architectures (and corresponding training algorithm) may be used in the RL setting which can possibly provide benefits, one of which is generalization as shown in this paper. We believe that this work provides an important initial step towards solving these future problems.
et al. 2018 Marriga-Alonse
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGEMENTS
We would like to thank John Schulman for very helpful guidance over the course of this work. We also wish thank Chiyuan Zhang, Ofir Nachum, Aurick Zhou, Daniel Seita, Alexander Irpan, and the OpenAl team for fruitful comments and discussions during the course of this work.
REFERENCES
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy on policy optimization. CoRR, abs/1 111.1 2018.
Martín Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. CoRR, abs/1907.02880 2019. URL
02893
Sanjeev Arora, Nadav Cohen, and Elad Hazan, On the optimization of deep networks: Implicit
acceleration by overparameterization CoRR, abs/1802.06500 2018a. http:ttp://aa
oxg/aba//802.00 06509
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp. 244-253, 2018b.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmssüsssan Stockholm, Sweden, July 10-15, 2018, pp. 254-263, 2018c.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. CoRR, abs//905.. 1905.13655, 2019.
13655
Kavosh Asadi, Dipendra Misra, and Michael L. Littman. Lipschitz continuity in model-based based reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmässsan, Stockholm, Sweden, July 10-15, 2018, pp. 264-273, 2018.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-48) 2002.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalizee margin bounds for neural networks. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 0240. Curran Associates, Inc., 2017.
Mare G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. CoRR, 0bbs/1277.470.. 2012.
Joseph K. Bradley, Aapo Kyrola, Danny Bickson, and Carlos Guestrin. Parallel coordinate descent for I1-regularized loss minimization. In Proceedings of the 28th International Conference on Machine Learning. ICML 2011, Bellevue, Washington, USA, June 28 July 2, 2011, pp. 321-328, 111/331mmmmm iemlpaper. pdf
2011. URL hotthtps::// /ttem.cm.../// wttp://mmmmmmmeeppe///e/c///////
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani. Richard Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässann Stockholm, Sweden, July 10-15, 2018, pp. 969-977, 2018. URL http:://proceeiiggg.... press/ wtt.//ooooo.iiiaccmcc
html
Karl Cobbe, Oleg Klimov, Chris Hesse, Taehoon Kim, and John Schulman. Quantifying generalization in reinforcement learning. CORR, 0tbs/1812.02311 2018.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, Aug 2019.
11

---

Published as a conference paper at ICLR 2020
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008, 2017.
Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron. Vlad Firoiu, Tim Harley, lain Dumning, Shane Legg, and Koray Kavukeuoglu. IMPALA: scalable distributed deep-rl with importance weighted actor-learner architectures. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüsssan, Stockholm, Sweden, July 10-15, 2018, pp. 1406-1415, 2018
Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, pp. 1466-1475, 2018.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pp. 1126-1135, 2017. URL http:
//proceedings mlr wwtppp/assa/ep///p
html
Adam Gaier and David Ha. Weight agnostic neural networks. CoRR, abs/1906.04358, 2019. URL http://arxiv. http://axivv.ogggbb/ba//aaaa
04358
Shani Gamrian and Yoav Goldberg. Transfer learning for related reinforcement learning tasks via image-to-image translation. In Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, pp. 2063-2072, 2019. URL http::/proceediing ngs mlr, prwss/ v97 http///9//////rrr/e ggarr innl 9a .tmml
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional networks as shallow gaussian processes. In 7th International Conference on Learning Rep- resentations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019. URL https //openreview. net htt/://oommmmdisssssaeree
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018., pp. 297-299, 2018. URL
mlr. http://www........ss/sss//// wwweees/v5//olllo///
html
Samuel Greydanus, Anurag Koul, Jonathan Dodge, and Alan Fern. Visualizing and understanding atari agents. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp. 1787-1796, 2018
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6159, 2017.
Christina Heinze-Deml and Nicolai Meinshausen. Conditional variance penalties and domain shift robustness. CoRR, abs/1710/ 177...1116666 11469, 2019. ittp:tt::///zixvoorr/// wtwp/////aaa///oo/a/
11469 11469
Christina Heinze-Deml, Jonas Peters, and Nicolai Meinshausen. Invariant causal prediction for nonlinear models. CoRR, abs/1 7ll//7706.08766, 2019. Btl.:tttps://axxi..crr///.ss
08576
Maximilian Igl, Kamil Ciosek, Yingzhen Li, Sebastian Tschiatschek, Cheng Zhang, Sam Devlin, and Katja Hofmann. Generalization in reinforcement learning with selective noise injection and information bottleneck. Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2019, Beach, CA, USA, 2019.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernl:: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada., pp. 8580-8589, 2018.
12

---

Published as a conference paper at ICLR 2020
Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis. The dependence of effective planning horizon on model accuracy. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 15, pp. 118--1199 Richland, SC, 2015. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 978-1 --400-34433--6
Yiding Jiang, Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the generalization gap in deep networks with margin distributions. CoRR, abs/1810.00113, 2018. URL http:
//axxi..rrg/ab////.... 00110
Niels Justesen, Ruben Rodriguez Torrado, Philip Bontrager, Ahmed Khalifa, Julian Togelius, and Sebastian Risi. Procedural level generation improves generality of deep reinforcement learning. CoRR, abs/1806. 10729, 2018.
otg. absrg///bs//ie aaopaaabs....... 10729
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances Neural Information Processing Systems 21, Proceedings of the Twent--Secon Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-11, 2008, pp. 793-800, 2008
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, 4966/14,,,6,0,, 2014.
Jachoon Lee. Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. CoRR, abs/1902.06720, 2019. URL htt.:/tp:p/aaxi..orr///o///
902. 06700
Tengyuan Liang, Tomaso A. Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geometry, and complexity of neural networks. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, pp. 888-896, 2019. URLLattpp:/procceddiii
m www.mmr......eee...... //////////// h///anng1111 (aang19a..o html
Marlos C. Machado, Mare G. Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Artif. Intell. Res., 61:523-566 562, 2018. doi: 10. 1.jaa////air
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search provides competitive approach to reinforcement learning. CoRR, abs/1803.07055, 2018.
David A McAllester. Pac-bayesian model averaging. In COLT, volume 99, pp. 164-170. Citeseer, 1999.
David A. McAllester. Simplified pac-bayesian margin bounds. In Computational Learning Theory and Kernel Machines, 16th Annual Conference Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, pp. 203-215, 2003, doi: 10. 111-1107977---55005551 378-3-540-45167-
URL /tt.:ttts///o.o..///000.1111
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. CoRR, abs/1312.5602, 2013.
Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arXiv preprint arXiv:1901.01672, 2019.
Behnam Neyshabur. te in deep learning. CoRR, abs/1 2017. URL httt:://arxtv.orrg/bb//////
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. ICLR, 2015a.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401, 2015b.
13

---

Published as a conference paper at ICLR 2020
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring gener- alization in deep learning. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 5949-5958, 2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track net forum? ner.mouumfufouoeoooo
Proceedings, 201 8a. URL
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of over-parraettrization in generalization of neural networks. CoRR, 120/, 2018b. URL httpppp/aaawww...p///a//////////
Alex Nichol, Vicki Pfau, Christopher Hesse, Oleg Klimov, and John Schulman. Gotta learn fast: A new benchmark for generalization in RL. CoRR, abb0/0000000037 2018.
OpenAl. Openai five. CoRR, 2018. URL htt.l/ttpsr//geenaaa.ccc///////p
Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krähenbühl, Vladlen Koltun, and Dawn Song. Assessing generalization in deep reinforcement learning. CoRR, abs/1810. 12282, 2018. URL
httt::/aaxiv..om wwtp://wwwwi...o.///b/aaa..bbaaa
12282
Xue Bin Peng, Marcin Andrychowicz, Wojeiech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE International Conference on Robotics and Automation, ICRA 2018, Brisbane, Australia, May 21-25, 2018, pp. 1-8, 2018. doi: 10.1 httpt:tt////oo org O. 1109/ ICRA. 2018 8 8460528
JCRA.2018.846055
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pp. 28 2817-2826, 2017.
Aravind Rajeswaran, Kendall Lowrey, Emanuel Todorov, and Sham M. Kakade. Towards generaliza- tion and simplicity in continuous control. In Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA. pp. 6553 6564, 2017.
Adam Santoro, Ryan Faulkner, David Raposo, Jack W. Rae, Mike Chrzanowski, Theophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy P. Lillicrap. Relational recurrent neural networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada., pp. 7310-7321. 2018.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. CoRR, hads//777.0634,, 2017.
Samuel I.. Smith, Pieter-Jan Kindermans, Chris Ying, and Quoe Le. Don't decay the learning rate, increase the batch size. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018. URL
https://openreviir net cattrrummid-B11 B1d
Felipe Petroski Such, Vashisht Madhavan. Rosanne Liu, Rui Wang. Pablo Samuel Castro, Yulun Li, Ludwig Schubert, Marc G. Bellemare, Jeff Clune, and Joel Lehman. An atari model zoo for analyzing, visualizing, and comparing deep reinforcement learning agents. CoRR, abs/1812.07069, 2018.
Stephen Tu and Benjamin Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. In Conference Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pp. 3036-3083, 2019. URL mlr. www.pprssssseee v99 /ttlullle html
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Theory of probability and its applications, pp. 1 11-30. Springer, 1971.
14

---

Published as a conference paper at ICLR 2020
Roman Vershynin. Lectures in geometric functional analysis. CoRR, 2009.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, John Quan, Stephen Gaffney, Stig Petersen, Karen Simonyan, Tom Schaul, Hado Hasselt, David Silver, Timothy P. Lillicrap, Kevin Calderone, Paul Keet, Anthony Brunasso, David Lawrence, Anders Ekermo, Jacob Repp, and Rodney Tsing. Starcraft II: A new challenge for reinforcement learning. CoRR. abs/1708.04782, 2017. URL http://:/aat awwiv. org/ abs / 1708 04782
Huan Wang. Stephan Zheng, Caiming Xiong, and Richard Socher. On the generalization gap in reparameterizable reinforcement learning. Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach. California, USA, pp. 2019. URL http:::pppccceeeecccee//
mlr. prw.s Sores//a / http///ang99......c html
Wenhao Yu, Jie Tan, C. Karen Liu, and Greg Turk. Preparing for the unknown: Learning a universal policy with online system identification. In Robotics: Science and Systems XIII, Massachuselts In- stitute of Technology, Cambridge, Massachusetts, USA, July 12-16. 2017, 2017. doi: 10. 1660/77SSS.. 2017.XIII.048. URL httpttp:: /ww. robor wwtp:ooboccccccccciooooccooccoc. wttp://///rssspeeeeeeeeeeeeee html
Amy Zhang, Nicolas Ballas, and Joelle Pineau. A dissection of overfitting and generalization in continuous reinforcement learning. CoRR, abs/ 806.079377 2018a.
Amy Zhang, Yuxin Wu, and Joelle Pineau. Natural environment benchmarks for reinforcement learning. CoRR, abs/18 81 1.00322 2018b.
Chiyuan Zhang, Oriol Vinyals, Rémi Munos, and Samy Bengio. A study on overfitting in deep reinforcement learning. CoRR, Abs/1804.06893, 2018c. URL http://arxiiu org. 1804.085 06893
15

---

Published as a conference paper at ICLR 2020
A.1
FULL PLOTS FOR LQR AND FG-GYM
A.1.1 LQR
Singuler Values for Varying Depths
Singuler Values for Varying Widths
Singuler Valuee
ACc 50
Total Timesteps (8)
Total Timesteps
(b)
Varying Layers, Training
Varying Training
90000
90000
Value
70000
L000 Vilun
70000
60000
60000
50000
50000
40000
40000
30000
30000
20030
300
20000
Gradient Steps
Gradient Steps
(c)
(d)
Test Loss Training Curves, Varying Noise Uliensiions
300000
260000
200000
160000
100000
0
2000
10030
(e)
Figure A1: (a.b): Singular Values for varying depths and widths. (c,d): Train and Test Loss for varying widths and depths. (e): Train and Test Loss for varying Noise Dimensions.
16

---

Published as a conference paper at ICLR 2020
We further verify that explicit regularization (norm based penalties) also reduces generalization gaps. However, explicit regularization may be explained due to the bias of the synthetic tasks, since the first layer's matrix may be regularized only "view" the output of f, especially as regularizing the first layer's weights substantially improves generalization.
HalfCheetah-v2. 50 Levels, Varying Reg.
3000
2500
Reward
2000
1500
Vew
layer
-5
-4
-3 -2
Regularization Coeff. (10%)
Figure A2: Explicit Regularization on layer norms.
We provide another deconvolution memorization test, using an LQR as the underlying MDP. While fg. Gym- Sym--econvv shows that memorization performance is dampened, this test shows that there can exist specific hard limits to memorization. Specifically, NatureCNN can memorize 30 levels, but not 50; IMPALA memorize 2 levels but not 5; IMPALA-LARGE cannot memorize 2 levels all.
Training, Test Rewards NULL)
-2500
Reward/Peffoman
-7500
-10000
-12500
IMPALA_2 evveesss
-15000
IMPALA
levels
-17500
IMPALA LARGE Jevel
-20000
NatureCNN_S90_mee
0.5
2.0
2.5
Training Steps
1e6
Figure A3: Deconvolution memorization test using LQR as underlying MDP.
17

---

Published as a conference paper at ICLR 2020
A.2 EXTENDED LARGE RL RESULTS
A.2.1 LARGE IMAGENET MODELS FOR COINRUN
For reference, also extend the case networks. We experimentally verify in Table I that large ImageNet models perform very differently RL than SL. We note that default network with the highest test reward was IMPALA-LARGE-BA (IMPALA-LARGE, with Batchnorm) at R 5.5 test score.
pareeeereeeter convolutional networks using ImageNet
In order to verify that this is inherently a feature learning problem rather than a combinatorial problem involving objects, such as in (Santoro et al. 2018), we show that state-of-the-ar attention mechanisms for RL such as Relational Memory Core (RMC) using pure attention on raw 32 x 32 pixels does not perform well here, showing that a large portion of generalization and transfer must be based on correct convolutional setups.
Coinrun-10k (Train, Test)
Architecture
AlexNet-v2
(10.0, 3.0)
CifarNet
(10.0, 3.0)
IMPALA-
(10.0, 5.5)
LARGE BN
-essttt2n-RssNet-22
(10.0, 6.5)
Inception-v4
(10.0, 6.0)
MobileNet-vl
(10.0, 5.5)
MobileNet-v2
(10.0, 5.5)
NASNet-
(10.0, 4.0)
CIFAR
NASNet-
(10.0, 4.5)
Mobile
ResNet-v2-50
(10.0, 5.5)
ResNet-v2-101
(10.0, 5.0)
ResNet-v2-152
(10.0, 5.5)
RMC32x32
(9.0, 2.5)
ShakeShake
(10.0, 6.0)
VGG-A
(9.0, 3.0)
VGG-16
(9.0, 3.0)
Table 1: Raw Network Performance (rounded nearest 0.5) on CoinRun, 100 levels. Images
scaled to default image sizes (32 x 32 or 224 x 224) depending on network input requirement. See Appendix A.2.n f.r training curves.
18

---

Published as a conference paper at ICLR 2020
We provide the training/testing curves for the ImageNet/large convolutional models used. Note the following:
1. RMC32x32 projects the native image from CoinRun from 64 x 64 to 32 32, and uses all pixels as components for attention, after adding the coordinate embedding found (Santoro
al., 2018). Optimal parameters were (mem slots 4, head size 32, num n 4, num blocks = 2, gate -stlle = 'memory").
used during training, only the pure network. 3. VGG-A is a similar but slightly smaller version of VGG-16. Train and Test Performances of Special Architectures on CoinRun-100
2. Auxiliary Loss in ShakeShake
AlexNet-v2
CIFARNet
IMPALA-LARGE-BN
Inceplion-Resnet-e
10
10
10
WA M
Irain test
train
4
1est
2
train
train
test
test
0.0
0.5 1.5 20 2.5
300 led
0
"0.000.88 200.0250..0022200 7...00...5..00. 1011.51.55
0,0.2.0..00080. 1.122 MobileNet-v2
14411
0
0.0 0.2 0.4 0E 08 10 12 14 NASNet-CIFAR tee
Inception-v4
MobileNet-v1
1e6
1el
10
train
train
train
test
test
MW
Performance
2
train
2
test
0,000 250 60D. 26118111
0.0
0.2 0.4 06 0.8 1.2
0.0
0.5
1.0
1.5
2.0
2.5
0 0.0
0.5
20 26 ResNet-v221011
1.0
1.5
NASNet-Mobile le6
RMC32x32
1e6
ResNet-v2-50
165
Irain
brain test
test
train
ww Ayy
fest
4
4
2
train
2
lest
0
0.0 0.5 L.0 1.5 25 3.0 3.5 4.0
0.0
0.5
1.0
1.5
2.0
2.5 1e6
0.0
0.2
0.4
0.5
0.0
1.0
122
ResNet-vv2-152
1e0
ShakeShake
1e6
VGG-A
VGG-16
train
tost
6
train 1ast
8.
train
4
4
tast
2
train fest
2
0.0
022
044
066
0.8
0.0 0.5 1.
3.5
0.5
1.0
1.5
2.0
25
30
0.0
0.5
1.0
20
1w6
Normalized TimeSteps
Figure A4: Large Architecture Training/Testing Curves (Smoothed).
19

---

Published as a conference paper at ICLR 2020
A.2.2 Do STATE-ACTION MARGIN DISTRIBUTIONS PREDICT GENERALIZATION IN RL?
A key question is how to predict the generalization gap only from the training phase. A particular set of metries, popular in the SL community are margin distributions (Jiang et al. 2018 Bartlet et al.) 2017), as they deal with the case for softmax categorical outputs which do not explicitly penalize the weight norm of a network, by normalizing the "confidence" margin of the logit outputs. While using margins on state-action pairs (from an on-policy replay buffer) is not technically rigorous, one may be curious to see if they have predictive power, especially as MIPPs are relatively simple to norm-bound, and as seen from the LQR experiments, the norm of the policy may be correlated with the generalization performance.
For policy, the the margin distribution will be defined as (2. - (x), (a((())mmmat maxisy Fx(x)), where R- R/
Fx (x), is the logit value (before applying softmax) of output y given input 2; and S is the matrix of states in the replay buffer, and R₂ is norm-based Lipschitz measure on the policy network logits. In general, R2 a bound on the Lipschitz constant of the network but can also be simply expressions which allow the margin distribution to have high correlation with the generalization gap. Thus, we use measures inspired by recent literature in SL in which we designate Spectral-L1, Distance, and
measures for Rx,, and replace the classical supervised learning pair (x, y) = (s, a) with the state-action pairs found on-policy.
The expressions for R, (after removing irrelevant constants) follows, with their analogous papers:
3/2 Bartlett et al.
1. Spectral-L1 measure:
(II- [[Wal)
Σ E
| [
2/a 277
2017)
2. Distance measure:
Ei IIW - W 2
Nagarajan & Kolter
2019)
Ww- w Neyshabur et al. 2018a
3. Spectral-Fro measure:
(n(d) I.L [ 11 Σ
IW51
We verify in Figure AS that indeed, simply measuring the raw norms of the policy network is poor way to predict generalization, as it generally increases even as training begins to plateau. This is inherently because the softmax on the logit output does not penalize arbitrarily high logit values, and hence proper normalization is needed.
The margin distribution converges However, unlike SL, the margin distribution is conceptually not fully correlated with RL generaiization on the total reward, as a policy overconfident in some state-action pairs does not imply bad testing performance. This correlation is stronger if there are Lipschitz assumptions on state-action transitions, as noted in (Wang et al. 2 For empirical datasets such as CoinRun, metric-distance between transitioned states is ill-ne however. Nevertheless, the distribution over the on- on-policy replay buffer at each policy gradient iteration a rough measure of overall confidence.
fixed distribution even long after training has plateaued.
Margin Distribut ons acroes time, 2-Laver Width 1024
Deptis
Weight Norms
1200
12000
0000
4000
3000
2002
150
2000
2
2
162
Te30 Tinecto
Figure A5: Margin Distributions across training.
We note that there are two forms of modifications, network dependent (explicit modifications to the policy- norm regularization, dropout, etc.) and data dependent (modifications only the data in the replay buffer- - action stochasticity, data augmentation, etc.). Ultimately however, we find that current
We removed the training sample constant m from all original measures as this is ill-defined for the RL case, when one can generate infinitely many (s,a) pairs. Furthermore, we used the original || [Wll,, in the numerator found in the first version of (Bartlett et al. 2017) rather than the current [|Wa 11...
20

---

Published as a conference paper at ICLR 2020
norm measures R become too dominant in the fraction, leading the monotonic decreases in the means of the distributions as we increase parametrization.
Margin Distributions, Varving Widths Distance
Spectral-L1
Spectral-Fro
8192
8192
5192
4296
4286
4296
1200
512
1000
206
206
206
128
128
128
800
800
5
1e1
1o4
1e2
Margin Distributions. Varving Depths Distance
Spectral-L1
Spectral-Fro
1400
1200
1000
800
600
400
200
2-4
2
2-2
2-1
2-4
2-3
2-2
2
2-4
2-3
2
Figure A6: Margin Distributions at the end of training.
A.2.3 GYM-RETRO (SONIC)
In the Gym-Retro benchmark using Sonic (Nichol et al., 2018), the agent given 47 training levels with rewards corresponding to increases in horizontal location. The policy is trained until 5k reward. At test time, 11 unseen levels are partitioned into starting positions, and the rewards are measured and averaged.
We briefly mention that the agent strongly overfits to the scoreboard (i.e. an artifact correlated with progress in the level), which may be interpreted as part of the output of go(-). (-). In fact, the agent is still able to train to 5k reward from purely observing the timer as the observation. By blacking out this scoreboard with black rectangle, we see increase in test performance.
Settings
IMPALA
NatureCNN
Blackout
1250 40
1141 40
NoBlackout
1130 = 40
1052 + 40
Table IMPALA vs NatureCNN test rewards, with and without Blackout.
A.3 HYPERPARAMETERS AND EXACT SETUPS
A.3.1 EXACT INFINITE LQR
For infinite horizon case, see (Fazel et al. 2018) for the the full solution and notations, Using the same notation (A, B, Q, R), denote C(K)
LaoD 2 Px the cost and u, - Kay, as the
21

---

Published as a conference paper at ICLR 2020
policy, where Pk satisfies the infinite case for the Lyapunov equation:
Pk = - K RK + (A +
BK)
We may calculate the precise LQR cost by vectorizing (i.e. flattening) both sides' matrices and using the Kroncker product 8, which leads to a linear regression problem on Pk. which precise solution, implementable in TensorFlow:
vec Px) = vec(Q) + vec( RK) + [[A - BKY²
( & (A - BK))) vec(Pk)
(4)
Ine - (A- BK) @ (A BK) vec(Px) vec(Q) + vec(K"RRR RK)
(5)
Parameter
Generation
A
Orthogonal initialization, scaled 0.99
B
In
Q
In
R
In
10
K2
Wi
Orthogonal Initialization, scaled 0.5
Table 3: Hyperparameters for LQR
A.3.2 PROJECTION METHOD
The basis for producing f. ge outputs is due using batch matrix multiplication operations, or "BMV". where the same network architecture uses different network weights for each batch dimension, and thus each entry in batchsize of B will be processed by the same architecture, but with different network weights. This is to simulate the effect of ge.. The numeric ID of the environment is used as an index to collect a specific of network weights 0; from a global memory of network weights (c.g. using rensorflow gather). We did not use nonlinear activations for the BMV architectures, as they did not change the outcome of the results.
Architecture
Setup
BMV-Deconv
(filtersize = 2, stride 1, outchannel 8, padding "VALID") outchannel
(filtersize = 4, stride
padding "VALID")
(filtersize = 8, stride 2, outchannel 4, padding "VALID""
(filtersize = 8. stride = 3, outchannel 3. padding "VALID")
BMV-Dense
Dense 30, g Dense 100
A.3.3 IMAGENET MODELS
For the networks used in the supervised learning tasks, direct the reader to the following
repository: httpps://ttttttttiee wwtp:/esw.....coccccot/e www.:wwwww/oooooooooooooo coom///essorrlooo/ccoeeeee
htwppeetttttccctoooeeeaoa factory. We also used the RMC: deepmina//sonnet//bb00/ slim/nets/nets
memory.
A.3.4 PPO PARAMETERS
For the projected gym tasks, used for PPO2 Hyperparameters:
22

---

Published as a conference paper at ICLR 2020
PPO2 Hyperparameters
Values
nsteps
2048
nenvs
16
nminibatches
64
X
0.95
0.99
noptepochs
10
entropy
0.0
learning rate vf coeffiieet
3 10
0.5
max- max-grad-nooe -rad--rrd-ommm
0.5
total time steps
Varying
See (Cobbe et al., 2018 for the default parameters used for CoinRun. We only varied nminibatches in order to fit memory onto GPU. We also did not use RNN additions, in order to measure performance only from the feedforward network the framestackingteemprrll aspect replaced by the option to present the agent velocity in the image.
A.4 THEORETICAL (LQR)
In this section, we use notation consistent with (Fazel et al. 2018) for our base proofs. However, in order avoid confusion with high dimensional policy K described 3.1 denote our low dimensional base policy as P and state as s, rather than 24.
A.4.1 NOTATION AND SETTING
Let ||-I| be the spectral norm of matrix (i.e. largest singular value). Suppose C(P) was the infinite is the state at time f, state
horizon cost for an (A, B, Q. R)-LQR where action -P A 8, + de, and timestep cost of Q&: + at Ray.
transition 8141
C(P) for an infinite horizon LQR, while known to be non-convex, still possess the property that when (C(P*) = 0, pa is a global minimizer, or problem statement rank deficient. ensure that cost C(P) always remains finite, restrict our analysis when P. E P, where P = (P ||||| S a and ||A - BPI| I 1} for some constant a, by choosing A, B and the initialization of P appropriately, using the hyperparameters found in A.3. We further define the
W. Wo
observation modified cost as C(K; We) = C
K
A.4.2 SMOOTHNESS BOUNDS
As described in Lemma of (Fazel 2018
we define
Tp(X)
t=0
Tr(X) and ||>|| supx XX over non-zero symmetric matrices X.
Lemma 27 of (Fazel et al. 2018) provides a bound on the difference C(P') C(P) for two different policies P, P' when LQR parameters A, B, Q, R are fixed. During the derivation, states that when
|P- P'|l < min JC(P) BP FTy F1)
(Q))
IIPII).
then:
C(P') - C(P) < |T (2 P |R] +|| - 21
2 2| 2 B| (II BP + +
P' |P| R|
Lemma 17 also states that:
C(P)
|T <
(8)
min
23

---

Published as a conference paper at ICLR 2020
where
= minn eo (102
Assuming that in our problem setup, To: Q. R, A, B were fixed, this means many of the parameters in the bounds constant, and thus conclude:
C(P)) o (C(P) ([(P))(1P11122 PP
P'I (114A11-B1 |B||| + + +1 P'1)]
(10)
Since assumed | - BP| 1 else (x) is infinite, thus collect the terms:
(C(P) =
C(P)- < o
[IP ( P'1 P - P'1(()
(11)
Since is a bound on ||||| for P E P. note that
|P|| PP P'| + ||| P P'I =
|||| + || P'I))
(12)
< ||P P'Il ||
(I) (|'))) s (3o?) |P P'|l
(13)
From [1,. this leads the bound:
((P))
(14)
Note that this directly implies similar bound in the high dimensional observation in partieular,
T
W
W
W- Wa
if P
= K
c
and P' = K
then | P - |K
K'
= |K K'Il
We
We
A.4.3 GRADIENT DYNAMICS IN 1-STEP LQR
We first start with a convex cost 1-step LQR toy example under this regime, which shows that linear components such as 3 We cannot be removed from the policy by gradient descent dynamics to improve generalization. To shorten notation, let W. E Raxx and Wa E _ppx", where < This is equivalent to setting daignat dstate and dnoise p, and thus the policy K (ex(++)))
W W
In the 1-step LQR, we allow 8o ~ NO, 1). = K then
so and 8 = + with cost & ||
W
W. Wo
C(K; Wo) Eng
- K
I + K
(15)
2
We
2
and
W. W
W We
VC(K;Wo
7 K
(16)
Define the population cost C(K) Ew, [C(K; Wo)]. Let the notation O(p, n) denote the following set orthogonal matrices:
Op,,n) = ( E RRx" W = 7}
We use the shorthand (n)) = Onn
Proposition 1. Suppose that Wa ~ Uni n)) and W. ~ (n)). Then
(i) The minimizer of ((K) unique and given by K, = [-W. 0.
(ii) Thus, the minimizer cost C(K.) =
24

---

Published as a conference paper at ICLR 2020
Proof. By standard properties of the Haar measure O(p, n)), have that B[Wo] Wl 2 Therefore.
0 and
C(K) = n + E
W
W:
)
K
+
tr
K
2 2
We
We
F
n
2
2
tr
T
0
2
+
tr
K
W
p
We can now differentiate C(K):
[
0
VC(K)
K
W
0]
0
Both claims now follow.
A.4.3.1 FINITE SAMPLE GENERALIZATION GAP
As instructive example, consider the case when only possess sample Wo. Note that if == + We
0
then VC(K; Wo) = VC(K"; Wo) +
In particular, we perform
W
gradient descent dynamics Ke+1 = K₁ -//CCK Wo). then we have
K₁ = -Koo mMM + B(I 7M)
+ B
(17)
We We
W
We
where M =
is the Hessian of C(K; Wo) and B =
Note that M has rank
We
We
at most < + and thus at a high level, Ku(l [1 - n) does not diminish if some portion of Ko lies in the orthogonal complement of the range of M. If the initialization is Ko (0, I), then is highly likely we can find a subspace Q C (ange(M) for which KuQ # 0.
This is specific example of the general case where the Hessian of function f(x) degenerate everywhere (e.g. has rank & < n), then an To initialized with e.g. an isotropic Gaussian distribu- tion cannot converge under gradient descent to minimizer that lives the span of the Hessian, as the non-degenerate components do not change. In particular, Proposition 4.7 in (Vershynin) 2009) points to the exact magnitude of the non-degenerate component the relevant subspace Q: (gwN((.1)
The generalization gap may decrease if the number of level samples is high enough. This can be seen by the sample Hessian of Ō(K)= Σ C(K; Wo, being M = 1 E M, where
W. W. Vi. In particular, as m increases, the rank of M increases, which allows Wo. We.
M, =
gradient descent recover the minimizer K, better.
We calculate the exact error of gradient descent on samples of the 1-step LQR problem.
To simplify notation, we rewrite Wo, as W., and interchangeably use the abbreviations for the finite (k.(K) (: (W.)) = 1 E C(K; W.) when necessary. We consider gradient descent Kr+1 K, VC (K,) starting from a random Ko with each entry iid (0, 2²) and n sufficiently small so that gradient descent converges. Let Kxx denote the limit point of gradient descent. We prove the following generalization gap between Koc and Kopt-
Theorem 1. Suppose that n divides p. Fix an m E (l....p/n), Suppose that the samples generated by first sampling a W (Op), and then partitioning the first n m columns of W into Wiy.., Wm. Suppose gradient descent is run with a sufficiently small step size T so that it converges unique limit point Koo. The limit point Koo has the following generalization error:
(W1,..., Wm)
B[C(Ks)) 2
m²n
2
2
11
2(m 1)
2p(m
1)2
m7
m
m
E1E
E2
25

---

Published as a conference paper at ICLR 2020
Here, the expectation is over the randomness the samples {Wike and the initalization Ko- The contribution from E1 is due to the generalization enror of the minimum-now norm stationary point of Cm(: (W The contribution from E2 is due the full-rank initialization of Kg-
1-ştep LQR, Generalization Erjor
1-ştep LQR, Generalization Eryor
80
1000
70
Generalization Error
Generalization Error
-1000
-3000
-4000
10
60
100
400
600
800
1000
m
p
1
1-ştep LQR, Generalization Erfor
Generalization Error
-2
200
Figure A7: Plot of B(C(K (Kxc xx) as a function m, p, n with elsewhere fixed default values 10, p 1000, m = 10, and 1/b = 1.
We remark that proof specifically relies the rank of the Hessian increases, rather than a more common concentration inequality used empirical risk minimization arguments, which leads to ymm scaling. Furthermore, the above expression for a))) does not scale increasingly with poly(p) for the convex 1-Step LQR case, while empirically, the non-convex infinite LQR case does indeed increase from increasing the noise dimension p (as shown in Section 3.1). Interestingly, this suggests that there is an extra contribution from the non-convexity of the cost, where the observation-modia gradient dynamics tends to reach worse optima.
A.4.3.2 PROOF OF THEOREM
Fix integers p with 2 n and suppose that n divides Draw random W E Opp) uniformly from the Haar measure on (p)) and divide W column-wise into Wi, W2, W p/n (that W. RR W.w. W, J, and W.W, = when + j). Also draw Wa (()) uniformly and independent from W. Now we consider the matrix Zm (gm-x((xtp)) for m 1, .... defined as:
WT
W
Zm =
W
WT m
Proposition 2. We have that Zi, is given as:
W.
m++ W. W
2t =
M+1
m W1
Eid
W
m
m++I Σ
W
m+T
if
26

---

Published as a conference paper at ICLR 2020
Proof. Using the fact that W W. I, WTW, Ins and W. W, 0 for i o j. we compute:
I
I
Zm Zm Imo
By the matrix inversion formula we can compute the inverse (7m 4 as the x m block matrix where the diagonal blocks are m and the off-diagonal blocks are m==1 T. We can now write Z using the formula:
m+1
2 = Zm (2 7mm
The result is seen to be:
We
W.
Σ it1
Wi
m+1
W
m m+1
Zimm
W
Proposition We have that:
WoWT DiE W.W.
Ee E W.WT
Pzz
E
W.W. Σ Ee W.W.
Proof. We use the formula Pzz (. - combined with the calculations in the previous proposition.
Now consider the gradient of Cmi
1 m
m
Wa W
))
VC
K
W
Setting (Cm) 0, that minimizers of Cm are solutions to:
m
W
W W.
))
m
We W
K
W
Using our notation above, this is the same as:
K KZ Zm [T
Ix] Zm
The minimum norm solution, denoted Kmin, to this equation is:
Kmin - [Tn
In] (ZthT
Next, recall that C(K) E[Cm (K) is:
W.
C(K) = 2 +
2 tr
K
0
21
+
tr
K
Our next goal is to compute ([C())nn)] First, we observe that:
W.
Wa
W.
tr Kmin
0
0
m
u.W..w.)
m
m
27

---

Published as a conference paper at ICLR 2020
Next, defining B, =
W
1 Eهft
Wi. compute K Kmin as:
WT
B
We
We
K min Kuin
B1
Bm
W
B
m
(m+1))
EE B₂) B 1=1 B
m (m+1))
i=1 Wi) Wi 1
(m+1)²
Therefore:
K- K Kinn
I
m²
p(m + 1)2 (nm).
n
0
(m + 1)2"
Putting everything together, we have that:
n
n² n
C(Kmin) 2 2(m + 1)²
2p(m + 1)² m n
Notice that this final value is not function of the actual realization of W.
We now consider the second source of error, which comes from the initialization Kg. Recall that each entry of Ko drawn iid from (O, 2 Let us consider the gradient descent dynamics:
K++1 K₁ V/ (Kt).
Unrolling the dynamics under our notation:
1-1
K; = Ko(I (n/m) Z,, (n/m) [h
[n]] Zm
(I
(t.mm),,,,n
k=0
is not hard to see that for 17 sufficiently small, as - 00
1-1
-m//m) In 100
lim
In] Zm Σ (1 - (n/m) Z 2mT Zm)
Kmin
k=0
Hence:
K = Kol1 (n/m) 2T, 2m) + Kmin
Call the matrix Mx. = (I (n/m) ZT Zmm
We observe that:
1
MM M Ko 1 0 D1)
C(Kx))
+
tr
2
0
+
(M KJ Kmin + KT KoMo
0
I
0
K K
0
2/
[W]] 0
+ tr
Kg
[. 0
+ tr
Moin
Noticing that Ko is independent of Zm, taking expectations KoKKKoMM
1 EEr
[
0
B[C(Kx))] BBCCkK (BCC(min))
)1)
77
222 2 Etr
1
0
=F[C(Kmin)]
M Mo
11
28

---

Published as a conference paper at ICLR 2020
Above, the fact that [ Kuj
s n Now it is not hard to that for n sufficiently
small, we have that Mo = I Pzz. On the other hand, using []] 0, we have that
m T
0
ZT
m++1
Therefore:
(1 m/(m + 1))
B [ Mxc]
0
(1 m²n/((m 1)p)
Plugging in the previous calculations, this yields
n
m 2 12
x(]( B[C((min))
m +
m + p
29


Reviews:
[{"review_id": "rygLTFZ4YH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper proposes a method for measuring generalization error in reinforcement learning (RL). The paper proposes to disentangle the observations into the features that relevant and not-relevant for the policy and then perturb the non-relevant features while keeping the relevant features constant. If the agent has learned to generalize, then perturbing the non-relevant features should not change the RL score. \n\nComments:\n\n1. The paper addresses an important question in RL:  generalization in the observational space. It is not trivial to define generalization in RL as this differs fundamentally from a SL or unsupervised learning setting.  The paper proposes a metric to measure this generalization error and this can be applied to non-toyish environments.\n\n2. The paper is clearly written and well-motivated. \n\n3.  I do like the proposed method. However, I also see some shortcomings of the method.  \nThe paper proposes to disentangle the features into relevant and non-relevant features. While this might be easier for certain task, it might be much more difficult for other tasks. The relevant features may be some implicit priors that are not easy to extract, for example, the fundamental physics of an environment. I am not sure how this can be addressed in a complicated environment where the relevant features are sampled from an implicit prior.\n\n4. The experiments on CoinRun i think is the most relevant ones. However, in this environments, it seems that although the observational features are quite different (rendering of the environment), the underlying physics or moves/ actions are very much similar. It would be nice to see a more complicated environment where the underlying physics or composition of actions can be different.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SJxnmgeCFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review:\n\nThis paper considers the problem of overfitting in RL through a specific model of overfitting, namely one where noise is introduced in the observation space, independently of the controllable dynamics.  The paper provides both theoretical and empirical insights into the various manifestations of overfitting in this class of domains.\n\nA strength of this paper is to deepen our understanding of the phenomenon of overfitting in RL.  To get a deep understanding of hard problems it is worthwhile to look at sub-classes of problems, and as such the identification of the observational overfitting setting is interesting.  The paper provides insightful findings such as:\n-\tExplicit separation of f and g_theta.\n-\tTheoretical properties of generalization for the specific case of LQR and linear policies.\nThere are also several empirical results, on three contrasting domains which illustrates various aspects of the interaction between parameterization vs generalization.\n\nBut overall, though I read the paper in detail, and am knowledgeable of the topic, I am still struggling with extracting very specific new findings from this work.  Here are a few examples:\np.6:  “We observe empirically that the underlying state dynamics has a significant effect on generalization performance as the policy nontrivially increased test performance” ->  I see where you draw this analysis from the results.  But is this finding new or surprising?  I would have been very comfortable saying (without your results) that the underlying state dynamics can have a significant effect on generalization performance.\np.6: “This suggests that the Rademacher complexity and the weight perturbation bound for rewards vary highly for different environments.”  -> Again, how is this new knowledge?\np.7: “this also suggests that the RL generalization quality of a convolutional architecture is not limited to real world data” -> Same question, what new knowledge have we gained?\n\nPerhaps the key message is that “there are generalization benefits to overparameterization” and that “implicit generalization” plays a key role in controlling this?   If that is the main message, than it is somewhat obfuscated by all the material on LQR, which doesn’t really go in this direction (p.4: “We being with a theorem which implies that a high dimensional observational space directly contributes to overfitting”).  I must say I found most of the material in 3.1 to distrct from the main message – but perhaps it is because I am not very interested in the LQR setting, and did not understand how the findings there supported those in latter sections.\n\nOverall, I would say the paper suffers from some clarity issues.  There are some minor typos, then some key terms of are not sufficiently explained/defined (e.g. g_\\theta in Sec.2.2 is said to project “the latent data to unimportant features”, but then there is discussion of “in settings where $g$ does matter” – I’m confused.)   It’s not clear whether Thm 3.1 is new, or adaptation of existing results.  More broadly, I found Sec.3.1 difficult to follow. The last paragraph of Sec.4 seems superfluous.   I would recommend some good editing throughout.\n\nAnother concern with the work is the fact that several aspects of RL are ignored (e.g. exploration, entropy, \\gamma, noise, stochastic gradients, etc. – as per p.4), yet are known to have an effect on overfitting, perhaps much more than the depth and width of the neural network.  If that’s the case, it is perhaps dangerous to ignore them in the analysis; it is not described in the paper, for the domains studied in the empirical results, whether this is the case or not.  As a result, it’s not clear how far the current analysis carries.  I’m also not clear on the analysis at bottom p.7 “IMPALA-LARGE (…) memorizes less than IMPA due its inherent inductive bias” -> Seems to me IMPALA-LARGE might simply be in underfitting regime.\n\n======\nUpdate post-rebuttal:\nThank you for the thoughtful responses.   Given the other strong reviews, and your careful characterization of various aspects of the work, I am favorable to accepting.  Please try to incorporate elements of this discussion into the paper, which I think will give a richer and more nuanced understanding of the work to future readers.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlLkIImYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Claims: This paper studies instances where observational overfitting is occurring in reinforcement learning, and separates it from other confounding factors contributing to poor generalization. They specifically study observational overfitting with LQR and deep neural networks, and show implicit regularization naturally occurs in this setting.\n\nDecision: Accept. The paper presents relevant bounds on overfitting depending on the dimensionality of the signal and noise. The framework and definition of family of MDPs are interesting and useful, and the focus on the implicit regularization provided by overparameterization when dealing with high dimensional observations with correlated noise is important and useful to decouple from varying dynamics. \n\nSection 3.2 needs more explanation of the experiment, how the train test split is created and if this is on the original rendered images from OpenAI gym or with correlated noise -- I've never seen such stark generalization gaps one the original environments. Are all of these experiments done with the proprioceptive state? Are the experiments in 3.3 then done with learned deconvolutions to generate the 84x84 images? Why this instead of using the rendered images themselves (as f) with added noise parameterized by \\theta?  Fig 8 is also not well explained, there are two sets of lines of each color in the plots with no label as to which is which, I assume these are train and test? Perhaps a plot that shows the generalization gap as the y-axis would be more clear.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a way to analyze overfitting to non-relevant parts of the state space in RL and proposes a framework to measure this type of generalization error. All reviewers agree that the formulation is interesting and useful for practical RL.
Decision: Accept (Poster)