On Proximal Policy Optimization's Heavy-Tailed Gradients 
Authors: Saurabh Garg
Joshua Zhanson
Emilio Parisotto
Adarsh Prasad
J Zico Kolter
Zachary Chase Lipton
Sivaraman Balakrishnan
Ruslan Salakhutdinov
Pradeep Kumar Ravikumar
Venue:  (2021)
Keywords: Heavy-tailed Gradients
Proximal Policy Optimization
Robust Estimation
Deep Reinforcement Learning

Abstract: Modern policy gradient algorithms, notably Proximal Policy Optimization (PPO), rely on an arsenal of heuristics, including loss clipping and gradient clipping, to ensure successful learning. These heuristics are reminiscent of techniques from robust statistics, commonly used for estimation in outlier-rich ("heavy-tailed") regimes. In this paper, we present a detailed empirical study to characterize the heavy-tailed nature of the gradients of the PPO surrogate reward function. 
We demonstrate pronounced heavy-tailedness of the gradients, specifically for the actor network,  which increases as the current policy diverges from the behavioral one (i.e., as the agent goes further off policy).  Further examination implicates the likelihood ratios and advantages in the surrogate reward as the main sources to the observed heavy-tailedness. Subsequently, we study the effects of the standard PPO clipping heuristics, demonstrating how these tricks primarily serve to offset heavy-tailedness in gradients. Motivated by these connections, we propose incorporating GMOM (a high-dimensional robust estimator) into PPO as a substitute for three clipping tricks, achieving performance close to PPO (with all heuristics enabled) on a battery of MuJoCo continuous control tasks. 

Under review as a conference paper at ICLR 2021
ON PROXIMAL POLICY OPTIMIZATION'S HEAVY-TAILED GRADIENTS
Anonymous authors Paper under double-blind review
ABSTRACT
Modern policy gradient algorithms, notably Proximal Policy Optimization (PPO). rely on an arsenal of heuristics, including loss clipping and gradient clipping. ensure successful learning. These heuristics are reminiscent of techniques from robust statisties, commonly used for estimation in outlier-rich ("heavy-tailed") regimes. In this paper, we present detailed empirical study to characterize the heavy-tailed nature of the gradients of the PPO surrogate reward function. We demonstrate pronounced reavy-tailednee tor network, which increases as the current policy diverges from the behavioral one (i.e., the agent goes further off policy). Further examination implicates the likelihood ratios and advantages in the surrogate reward as the main sources of the observed heavy-tailedness. Subsequently, we study the effects of the standard PPO clipping heuristics, demonstrating how these tricks primarily serve to offset heavy-tailedness gradients. Motivated by these connections, we propose incor- porating GMOM, a high-dimensional robust estimator, into PPO as substitute for three clipping tricks. Our method achieves comparable performance that of PPO with all heuristics enabled on a battery of MuJoCo continuous control tasks.
of the gradients, specifically for the
INTRODUCTION
As Deep Reinforcement Leaminng (DRL) methods have made strides on such diverse tasks as game playing and continuous control (Berner et al., 2019; Silver et al.] 2017 Mnih et al.] (015). policy gradient methods (Williams] 1992] Sutton et al. 2000; Mnih et al. 2016 have emerged as a popular alternative to dynamic programming approaches. Since breakthrough results of Mnih et al.) (2016) demonstrated the applicability of policy gradients in DRI., number of popular variants have emerged (Schulman et al., 2017 Espeholt et al. 2018). Proximal Policy Optimization (PPO) (Schulman et al. 2017)-one of the most popular policy gradient methods
the clipped importance sampling update, an effective heuristic for off-policy learning. However, while their stated motivation for clipping draws upon trust-region enforcement, the behavior of these methods tends to deviate from its key algorithmic principle (Ilyas et al. [0188) and exhibit sensitivity to implementation details (Engstrom et al., 2019). More generally, policy gradient methods are brittle, sensitive to both the random seed and hyperparameter choices, and poorly understood (Ilyas et al.) 2018 Engstrom et al. 2019 Henderson al.
2017 2018 Islam al. 2017). The ubiquity of these issues raises a broader concern about our understanding of policy gradient methods.
In this work, we take step forward towards understanding the workings of PPO, the most prominent and widely used deep policy gradient method. Noting that the heuristics implemented in PPO are evocative of estimation techniques from robust statistics in outlier-rich settings, we conjecture that the heavy-tailed distribution of gradients is the main obstacle addressed by these heuristics. We perform rigorous empirical study to understand the causes of heavy-tailedness in PPO gradients. Furthermore, provide novel perspective on the clipping heuristics implemented in PPO by showing that these heuristics primarily serve to alleviate heavy-tailedness in gradients.
Our first contribution is analyze the role played by each component of the PPO objective in the of the gradients. We observe that as the training proceeds, gradients of both the ac- tor and the critic loss get more heavy-tailed Our findings show that during on-policy gradient steps the advantage estimates are the primary contributors to the heavy-tailed nature of the gradients. Moreover, as oof-policysess increases (i.e. the behavioral policy and actor policy diverge) dur-

---

Under review as a conference paper at ICLR 2021
ing training, the likelihood-ratior that appear in the surrogate objective exacerbates the heavy-tailed behavior. Subsequently, we demonstrate that the clipping heuristics present in standard PPO im- plementations (i.e., gradient clipping, actor objective clipping, and value loss clipping) significantly counteract the heavy-tailedness induced by off-policy training. Finally, motivated by this analysis, present algorithm that uses Geometric Median-of-Means (GMOM), bust aggregation method adapted from the statistics literature. Without using any of the objective clipping and gradient clipping heuristics implemented PPO, the GmоM algorithm nearly matches PPO's 's performance on MuloCo (Todorov et al. 2012) continuous control tasks.
nigh-dimensional
2 PRELIMINARIES
We define a Markov Decision Process (MDP) as a tuple (S, n, v, P), where S represent the set of environments states, AA represent the set of agent actions, R: S x A - is the reward function, y is the discount factor, and P S x A S - R is the state transition probability distribution. The goal in reinforcement learning is to learn a policy Te S x A + R+, parameterized by 0, such that the expected cumulative discounted reward (known as returns) is maximized. Formally, T argmax, (et Et= R(st,
Policy gradient methods directly parameterize the policy (also known as actor network). Since directly optimizing the cumulative rewards can be challenging, modern policy gradient algorithms typically optimize surrogate reward function. Often the surrogate objective includes a likelihood ratio to allow importance sampling from behavior policy To while optimizing policy zo- For example, Schulman et al. (2015a) optimize:
To(ur, 8t) To(a,, 81))
Aro (se, ai)
max (s,, Jao
(1)
where An, =
Quo (st, reward after taking an action a at state s and following me afterwards and Vn, (s) is the value estimate (implemented with critic network).
(lst,aa a.)
Vx (st). Here, Q-function i.e. (x, is the expected discounted
However, the surrogate is indicative of the true reward function only when Ty and To are close in distribution. Different policy gradient methods (Schulman et al. 2015a 2017 Kakade 2002) at-
tempt to enforce the closeness in different ways. In Natural Policy Gradients (Kakade) 2002) and Trust Region Policy Optimization (TRPO) (Schulman et al. 2015a), authors utilize conservation policy iteration with an explicit divergence constraint which provides provable lower bounds guar- antee the improvements of the parameterized policy. On the other hand, PPO (Schulman et al. 2017) implements a clipping heuristic on the likelihood ratio of the surrogate reward function to avoid excessively large policy updates. Specifically, PPO optimizes the following objective:
max (ssr,a))=ao min (clip(p.. 1 c,
c)A (st, at), Pe (st, a:))]
(2)
where Pe: (.. We refer to Pt as likelihood-ratios: Due to a minimum with the unclipped s1) surrogate reward, the PPO objective acts as pessimistic bound on the true surrogate reward. As in standard PPO implementation, we use Generalized Advantage Estimation (GAE) (Schulman et al. 2015b). Moreover, instead of fitting the value network via regression to target values:
LV (Vo. Viarg)
standard implementations fit the value network with a PPO-like objective:
V.V max { Viorg)² (clip (Ve,, Ve. e, Vo. +e) Viarg) )²)
where e is the same value used to clip probability raitos in PPO's loss function (Eq. 9
PPO uses the following training procedure: At any iteration f, the agent creates clone of the current policy ne, which interacts with the environment to collect rollouts B (i.e., state-action pairs {(st, aa))a:) J.W, Then the algorithm optimizes the policy ne and value function Vo for a fixed K gradient steps on the sampled data Since at every iteration the first gradient step taken on the same policy from which the data sampled, we refer these gradient updates as on-policy steps.
2

---

Under review as a conference paper at ICLR 2021
And as for the remaining K - steps, the sampling policy differs from the current agent, refer to these updates as off-policy steps.
Throughout the paper, consider stripped-dows variant of PPO (denoted PPO-NOCLIP) that consists of policy gradient with importance weighting (Eq. D. but has been simplified as follows: i) no likelihood-ratie clipping, i.e., objective function clipping; ii) value network optimized via regression to target values (Eq. ( without value function clipping; and iii) no gradient clipping. Overall PPO-NOCLIP uses the objective summarized in App. A One may argue that since PPO- NOCLIP removes the clipping heuristic from PPO, the unconstrained maximization of Eq. ! may lead excessively large policy updates. App. we empirically justify the use of Eq. b showing that with the small learning rate used in our experiments (tuned hyperparameters in Table []. PPO- NOCLIP maintains a KI. based trust-region like PPO throughout the training. We elaborate this in
App-D M
2.1 FRAMEWORK FOR ESTIMATING HEAVY-TAILEDES TAILEDNESS
We now formalize our setup for studying the distribution of gradients. Throughout the paper, we use the following definition of the heavy-tailed property:
called heavy-tailed if its tail probability (t): =P( 2 t) is asymptoticallly equivalent to t t-a as + oo for some positive number a". Here a determines the heavy-tailedness and a is called tail index w.
Definition 1 (Resnick (2007)). A non-negative random variable
For heavy-tailed distribution with index a², its a-th moment exists only if < a", i.e., B[wa]] do iff a < a". A value of a = 1.0 corresponds to a Cauchy distribution and a* = 0o (i.e., all moments exist) corresponds to a Gaussian distribution. Intuitively, as a decreases, the central peak of the distribution gets higher, the valley before the central peak gets deeper, and the tails get heavier, In other words, the lower the tail-index, the more heavy-tailed the distribution. However, in the finite sample setting, estimating the tail index is notoriously challenging (Simsekli et al.) 2019 Danielsson et al. 2016 Hill 1975).
In this study, we explore three estimators as heuristic measures to understand heavy tails and non- Gaussianity of gradients (refer to App. B for details). (i) Alpha-index estimator which measures alpha-index for symmeteric a-stable distributions. This estimator is derived under the (strong) sumption that the stochastic Gradient Noise (GN) vectors are wordinate-wise independent and fol- low a symmetric alpha-stable distribution. (ii) Underson-Darling test (Anderson & Darling 1954) on random projections of GN to perform Gaussianity testing (Panigrahi et al.] 2019). To our knowl- edge, the deep learning literature has only explored these two estimators for analyzing the heavy- tailed nature of gradients. (iii) Finally, in our work, we propose using Kurtosis. To quantify the Seavy-tailedness relative to normal distribution, ment) of the gradient norms. Given samples {X,), the kurtosis is given by:
measure kurtosis (fourth standardized mo-
K E. (X,-X)+/N
(X, 2
where X is the empirical mean of the samples. With slight breach of notation, we use kurtosis to denote n:1/4, is well known that for a Pareto distribution with shape 2 4, the lower the tail-index (shape parameter a) the higher the kurtosis. For a 4, since the fourth moment non-existent, kurtosis is infinity. While for Gaussian distribution, the kurtosis value is approximately 1.31. In App. B, we show behavior of kurtosis on Gaussian and Pareto data with varying sample sizes and tail-indices for Pareto data.
3 HEAVY-TAILEDNESS IN POLICY-GRADIENTS A CASE STUDY ON PPO
We now examine the distribution of gradients in PPO. To start, we examine the behavior of gradients at only on-policy steps. We fix the policy at the beginning of every training iteration and just consider the gradients for the first step (see App. for details). As the training proceeds, the gradients clearly become more heavy-tailed (Fig. a)). To thoroughly understand this behavior and the contributing factors, we separately analyze the contributions from different components in the loss function. We also separate out the contributions coming from actor and critic networks.
3

---

Under review as a conference paper at ICLR 2021
PPO
10
19
1.0
crtiic
14
35
15
13
13
13
100
X60 On-policy steps
333
400
208
106
230
300
400
548
108
333
100
400
50
On-policy steps
On-poln On-policy steps
(b)
(c)
Figure Heavy-tailedness in PPO during on-poliey iterations. All plots show mean kurtosis aggregated over 8 MuJoCo environments. For other estimators, see App. F For individual environ- ments with error bars, see App. H Increases in Kurtosis implies an increase in heavy-tailedness. Dotted line represents the Kurtosis value for a Gaussian distribution. (a) Kurtosis vs on on-policy iterations for A2C and PPO. Evidently, as training proceeds, the gradients become more heavy- tailed for both the methods. (b) Kurtosis vs on-policy iterations for actor networks in PPO. (c) Kurtosis vs on-policy iterations for critic networks in PPO. Both critic and actor gradients become more heavy-tailed the agent is trained. Note that as the gradients become more heavy-tailed, observe corresponding increase of heavy-tailedness in the advantage estimates (Ax,). How- ever, "actor/A,,, and "critic/A,,, (i.e., actor or critic gradient norm divided by advantage) remain light-tailed throughout the training. In App. E we perform ablation tests to highlight the reason for heavy-tailed behavior of advantages.
Alongside, also perform ablations to understand how PPO heuristics affect the heavy-tailed ture of the gradient distribution. To decouple the behavior of naive policy gradients from PPO optimizations, we consider variant of PPO which we call PPO-NOCLIP as described in Section [ Recall that in nutshell PPO-NOCLIP implements policy gradient with just importance sampling. In what follows, we perform fine-graine iineggrained analysis of PPO at on-policy iterations.
3.1 HEAVY-TAILEDNESS IN ON-POLICY TRAINING
Given the trend of increasing heavy-tailedness in on-policy gradients, first separately analyze the contributions of the actor and critic networks. On both these component network gradients, we observe similar trends, with the heavy-tailedness in the actor gradients being marginally higher than the critic network (Fig. D.. Note that during on-policy steps, since the likelihood-ratios are just 1, the gradient of actor network is given by V, log (To(a,, s.)) Art a.) and the gradient of the critic network is given by V Va (St, ae) where is the behavioral policy. To explain the rising heavy-tailed behavior, we separately plot the advantages Ad, and the advantage divided gradients ( observe that while the advantage divided gradients
ie, V log( To (a))s:)) and Vo).). Strikingly, are not heavy-tailed for both value and policy network, the heavy-tailedness in advantage estimates increases training proceeds. This elucidates that during on-policy updates, outliers in advantage estimates are the only source of heavy-tailedness in actor and critic networks.
To understand the reasons behind the observed characteristic of advantages, we plot value estimates as computed by the critic network and the discounted returns used to calculate advantages (Fig. 7 in App. E We don't observe any discernable heavy-tailedness trends in value estimates and slight increase In returns. However, remarkably, we notice a very similar course of an increase in heavy- tailedness with negative advantages (whereas positive advantages remained light-tailed) as training proceeds. In App. F.3 we also provide evidence to this observation by showing the trends of in- creasing heavy-tailed hehavior with the histograms of (og([A,)) grouped by their sign as training proceeds for one MuJoCo environment (HalfCheetah-v2). This observation highlights that, least in MuJoCo continuous control environments, there is a positive bias of the learned value estimate for actions with negative advantages. And in addition, our experiments also suggest that the outliers in advantages (primarily, in negative advantages) are the root cause of observed heavy- behavior in the actor and critic gradients.
We also analyse the gradients of A2C (Miih et al. 2016) an on-policy RL algorithm and observe similar trends (Fig. [a)) but at relatively smaller degree of seavy-tailedness. Although they start
4

---

Under review as a conference paper at ICLR 2021
Initilization
50 % of Max Reward
Max Reward
crilic rañls actort/atin
Kurtosis
ratios actontratio
Kurtosis
14
criic
ralies
55
303
55
730
10e
zee 253 300
Off-policy steps
Off-policy steps
Off-policy steps
Figure 2: Heavy-tailedness in PPO-NOCLIP during off- steps at various stages of training iterations in MuloCo environments. All plots show mean kurtosis aggregated over 8 Mujoco envi- ronments. Plots for other estimators can be found in App. F We also show trends with these estima- tors (with error bars) on individual environments in App Increases in Kurtosis implies an increase in heavy-tailedness. Dotted line represents the Kurtosis value for Gaussian distribution. Note that the analysis is done with gradients taken on a fixed batch of data within a single iteration. As off- policyness increases, the actor gradients get substantially heavy-tailed. This trend is corroborated by the increase of heavy-tailedness in ratios, Moreover, consistently we observe that the heavy- tailedness in "actor/ratios" stays constant. While initially during training, the heavy-tailedness in the ratio's 's increases substantially, during later stages the increase tapers off. The overall increase across training iterations is explained by the induced heavy-tailedness in the advantage estimates (cf. Sec. 3.1.
similar magnitude, the heavy-tailed nature escalates at a higher rate in PPO This observation may lead us to ask: What is the cause of heightened heavy-tailedness in PPO (when compared with A2CY? Next, we demonstrate that off- off-policy training can exacerbate the heavy-tailed behavior.
3.2 OFFPOLICYNESS ESCALTE HEAVYTAILNESS GRADIENTS
To analyze the gradients off-policy steps, perform the following experiment: At various stages of training (i.e., at initialization, 50% of maximum reward, and maximum reward), we fix the actor and the critic network each gradient step during off-policy training and analyze the collected gra- dients (see App. D for details). First, in the early stages of training, as the off off-policyness increases, the heavy-tailedness in gradients (both actor and critic) increases. However, unlike with on on-policy steps, actor gradients are the major contributing factor to the overall heavy-tailedness of the gradient distribution. In other words, the increase heavy-tailedness for actor gradients due to off-policy training is substantially greater than for critic gradients (Fig-E). Furthermore, this increase lessens in later stages of training as the agent approaches its maximum performance.
Now we turn attention to explaining the possible causes for such a profound increase. The strong increase in heavy-tailedness the actor gradients during off-policy training coincides with a increase of -tayldtass in the distribution of likelihood ratios p, given by To(as, To)/ st)...)). The corresponding increase in heavy- tailedeess in ratios can be explained theoretically. In contin- control RL tasks, the actor-network often implements the policy with Gaussian distribution where the policy parameters estimate the mean and the (diagonal) covariance. With simple exam- ple, we highlight the heavy-tailed behavior of such likelihood-ratio of Gaussian density function. This example highlights how even a minor increase in the standard deviation of the distribution of the current policy (as compared to behavior policy) can induce heavy-tails.
Example (Wagg et al. 2018). Assume Ti (x) = N (a; (a;0, of) and T²(2) = N (z;0,oz) Let = Ti (z)) (2))) at a sample W ~ T2- If σ. A d2, then likelihood ratio p is bounded and its distribution is not heavy-tailed. However, when 01 02, then has heavy-tailed distribution with the tail-index (Definition 1 a" =f/(o? )
In Appendix
F.2 we show corresponding trend in the heavy-tailedness of advantage estimates.
5

---

Under review as a conference paper at ICLR 2021
2.1
2.1
actor
critc
actor-clpp
critic-clip
actor-gradclip
1.4
critic-grad
Kurtos
Kurtosis
1.8
1.7
1.4
1.6
1.5
144
1.
300
Off-policy steps
Off policy steps
Figure 3: Heavy-tailedness PPO-NOCLIP with PPO-heuristics applied progressively during off- off-policy steps, with kurtosis aggregated across 8 MuJoCo environments. For other estimators, see App. [F] Dotted line represents the Kurtosis value for a Gaussian distribution. "-clip" denotes loss clipping corresponding networks. "-gradclip" denotes both gradient clipping and loss clip- ping. Increases in Kurtosis implies an increase in heavy-tailedness. As training progresses during off-policy steps, the increased heavy-tailedness in actor and critic gradients is mitigated by PPO- heuristics.
During off-policy training, to understand the heavy-tailednees of actor gradients beyond the contri- butions from likelihood ratios, we inspect the actor gradients normalized by likelihood-ratios, i.e.,
V Vono st) ///// 8t) A (8t, ae) = Ve log (TTo (a)) Aro (St, Tolar, 82) /o (0) 8t)
(5)
Note that the gradient expression in Eq. Slis similar to on-policy actor gradients. Since we observe an increasing trend in heavy-tailedness the actor gradients even during on-policy training, one might ask: does these gradients' heavy-taileddness increase during off-policy gradient updates? Recall that in PPO, we fix the value function at the beginning of off- off-policy training and pre-compute advantage estimates that will later be used throughout the training. Since the advantages were the primary fac- tor dictating the increase during on-policy training, ideally, we should not observe any increase the heavy-tailed tailed behavior. Confirming this hypothesis, we show that the heavy-tailedness, in this quan- tity indeed stays constant during the off-policy training (Fig. 2}. i.e. Vo log (Ty (a,, st)) Aro (St, ae) doesn't 't cause the increased heavy-tailed nature as long as un fixed.
Our findings from off- off-policy analysis strongly suggest that when the behavioral policy is held fixed, -eily-tail in the importance ratios p is the fundamental cause. In addition, in Sec. 3.1] showed that when importance-ratio's are (i.c., the data on which the gradient step is taken is on-policy) advantages induce heavy-tailedness. With these two observations, we conelude that the scalars (either the likelihood-ratios or the advantage estimates) in the loss objective are the primary causes to the underlying heavy-tailedness in the gradients. Having analyzed key components dic- tating the heavy-tailed behavior, in App. ! we present two ablation experiments to test how heavy- tailedness likelihood-ratios and advantage estimates individually contribute to the optimization issues in PPO leading to poor performance. Next, we illustrate how PPO clipping heuristics allevi- ate heavy-tailedness issues.
3.3 EXPLAINING ROLES OF VARIOUS PPO OBJECTIVE OPTIMIZATIONS
Motivated from our results from the previous sections, we now take deeper look at how the core idea of likelihood-ratio clipping and auxiliary optimizations implemented in PPO and understand how they affect the heavy-tailedness during training. First, we make key observation. Note that the PPO-clipping heuristics don't 1 get triggered for the first gradient step taken (when a new batch of data sampled). But rather these heuristics may alter the loss only when behavior policy is different from the policy that is being optimized. Hence, in order to understand the effects clipping heuristics, perform the following analysis on the off- off-policy gradients of the PPO-Not -O-NOLIPPP: At each update step on the agent trained with PPO-NOCLIP, we compute the gradients with progressively including optimizations from the standard PPO objective.

---

Under review as a conference paper at ICLR 2021
Our results demonstrate that both the likelihood-ratio clipping and value-function clipping in loss during training offset the enormous heavy-tailedness induced due to off-policy training (Fig. 3 Recall that by clipping the likelihood ratios and the value function, the PPO objective is discarding samples (i.e., replacing them with zero when) used for gradient aggregation. Since heavy-tailedness in the distribution of likelihood ratios is the central contributing factor during off-policy training, by truncating likelihood-ratios Pt which lie outside (1 e, 1.1++) +e) interval, PPO is primarily mitigating heavy-tailedness in actor gradients. Similarly, by rejecting samples from the value function loss which lie outside an boundary of a fixed targer estimate, the heuristics alleviate the slight heavy- tailed nature induced with off- aff-po training in the critic network.
While these PPO heuristics alleviate the tailedesis induced with off off-policy training, the ef- fects of PPO clipping optimizations on mitigating heavy-tailedness induced during on-policy up- dates are far less clear. Since none of these heuristics directly target the outliers present in the advantage-estimates (the primary cause of increasing heavy-tailedness throughout training), we be- lieve that our findings can guide a development of fundamentally stable RL algorithms. In App. I.I. [.I
we present a preliminary result in this direction demonstrate how fixing heavy-tailedness advan- tage estimates improve agent's performance.
4 MITIGATING HEAVY-TAILEDNESS WITH ROBUST GRADIENT ESTIMATION
Motivated by our analysis showing that the gradients in PPO-NOCLIP exhibit heavy-tailedness that increases during off off-policy training, we propose an alternate method of gradient aggregation- using the gradient estimation framework from Prasad et al.] (2018) is better suited to the heavy- tailed estimation paradigm than the sample mean. To support our hypothesis that addressing the primary benefit of PPO's various clipping heuristics lies in mitigating this heavy-tailedness, we aim to show that equipped with our robust estimator, oftte- PPO implementations, even with the clipping heuristics turned off.
can achieve comparable results to
We now consider robustifying PPO-NOCLIP (policy gradient with importance sampling but without any trust-region enforcing steps PPO clipping tricks). Informally, for gradi- ent distributions which do not enjoy Gaussian-like concentration, the empirical-exppecation based estimates of the gradient do not necessarily point in the right descent direction, lead- ing to bad solutions. To this end, we leverage a robust mean aggregation technique called Geometric Ofddian-Of-Maans (GMOM) due to Minsker et al. (2015). In short, we first split the samples into non- non-overlapping subsamples and estimate the sample mean of each. The GMOM estimator is then given by the ge- ometric median-of-means of the subsamples. Formally, let { E R be n i.i.d. random variables sampled from distribution D. Then the GMOM estimator for estimating the mean can be described as follows: Parti- tion the n samples into b blocks BI...., B.. each of size [n/b]. Compute sample means in each block, i.e., (fu,....,bh }b).
Algorithm 1 BLOCK-GMOM
input Samples S fæ1..... .n). ) number of blocks b. Model optimizer Oc. block opti- mizers OB. network fe. loss é
1: Partition S into b blocks B B, of equal size.
where i = Ex,EB, 2// [&|l- |. Then the GMOM estima- tor j.GMOM is given by the geometric median of (ii,...., [b defined as follows: Á.GMOM
2: for in 1... 1...bdu. do
3: A := =(() EZ Vol(so, \B.))
4: end for
5: PoMMOM OG (WEISZFELD((1... ... ..o)).
argmin, Eim |l Å.ll2- Algorithm in Ap- pendix C presents the algorithm formally along
output Gradient estimate ÁАMMо
with the Weiszfeld's algorithm used for computing the approximate geometric median.
GMOM has been shown to have several favorable properties when used for statistical estimation in heavy-tailed settings. Intuitively, GMOM reduces the effect of outliers on mean estimate by taking a intermediate mean of blocks of samples and then computing the geometric median of those block means. The robustness comes from the additional geometric median step where small number of samples with large norms would not affect a GMOM estimate much as they would sample mean. More formally, given n samples from a heavy-tailed distribution, the GMOM estimate concentrates better around the true mean than the sample mean which satisfies the following:
7

---

Under review as a conference paper at ICLR 2021
Theorem 1
Minsker al. (2015), ) Suppose are given samples {z,);- from distribution with mean i and covariance E. Assume 0. Choose the number of blocks b = 1+ 3.5 l.ggo((//)) Then, with probability at least 1- 6,
(race({)) log(1 and
70 3
trace (E) nd
|NGMOM 112 S
2
n
When applying stochastic gradient descent or its variants in deep learning, one typically backprop- agates the mean loss, avoiding computing per-sample gradients. However, computing GMOM re- quires per-sample gradients. To this end, propose simple (but novel) variant of GMOM called BLOCK-GMOM which avoids the extra sample-size dependent computational penalty of calculating sample-wise gradients. Notice that in Theorem | the number of blocks required to obtain the guar- antee with high probability is independent of the sample size, i.e., we just need constant (dependent on 8) number of blocks to compute GMOM. To achieve this, instead of calculating sample-wing wise gra- dients, we compute block-wise gradients by backpropagating on sample-mean aggregated loss for each block. Moreover, such an implementation not only increases efficiency but also allows incorpo- rating adaptive optimizers for individual blocks. Algorithm 1 presents the overall BL.CKKGMMON
4.1 RESULTS MUJoCo ENVIRONMENT
We perform experiments on 8 MuJoCo Todorov
Normalized Rewards
ct al.] 2012) continuous control tasks. To use B1.0CK- aggregation with PPO-NOCL.IP,
1.0
we extract actor-network and critic-network gra-
dients at each step and separately run the Al- gorithm [ on both the networks. For our ex- periments, use SGD Og and Adam OG and refer to this variant of PPO-NOCLIP BRAUUST-PPONNCL..
0.4 0.2
PPO-NoClip
We compare the performances of РPO, PPO-NOCLIP, and Ro- BUST-PPO-NOCL.P using hyperparameters that are tuned individually for each method but held fixed across all tasks (Table DT For 7 tasks, we observe significant improvements with Ro- BUST-PPO-NOCLIP over PPO-NOCL.P and per- formance close to that achieved by PPO (with all clipping heuristics enabled) (Fig- 4. Although we do not observe improvements over PPO, we believe that this result corroborates our conjec- ture that PPO heuristics primarily aim to offset the haileetailedness induced with training.
Robust-PPO-NoClin
HarChmntativz
Art-12
Humanold- H2
Weinersd-i
Reacher-d
Interte Panttuaannd
CariPeli vl
Hopperss2
Figure 4: Normalized rewards for ROBUST- PPO-NOCLIP and PPO-NOCLIP. Normal- ized w.r.t. the reward obtained with PPO (with all heuristics enabled) and performance of random agent. (See App G for reward curves on individual environment.)
5 RELATED WORK
Studying the behavior of SGD, Simsekli et al. (2019) questioned the Gaussianity of SGD noise, high- lighting its heavy-tailed nature. Subsequently, there has been growing interest in understanding the nature of SGD noise. More recently, other works (Simşekli et al. 2020 Zhang et al. 2019b) explore the heavy-tailed behavior of SGD noise, with emphasis on tasks that require adaptive methods. In particular, Zhang et al. (2019b) studied the nature of gradients in natural language processing (e.g., BERT DFRTTppetraining). Later work (Panigrahi et al., 2019) studied results through Gaussianity tests on random projections. They showed that at least carly on in training, gradients remain near Gaussian for larger batch sizes. Some recent work has also made progress towards understanding the effee- tiveness of gradient clipping in convergence (Zhang al., 2019b a Şimşekli al. 2020). However, its consequences modulo the bias- vs variance trade-off are not completely understood.
On the RL side, large-scale study of PPO presented in (Ilyas et al. 2018). examining the extent that the PPO gradients align to the true underlying gradient. Likewise, Engstrom et al. (2019) provide thorough study of the code-level heuristies used in trust region methods and indicate the
8

---

Under review as a conference paper at ICLR 2021
necessity of such heuristies in obtaining strong model performance. Chung al. (2020) highlighted the impacts of stochasticity on the optimization process in policy gradients. In simple MDPs, authors showed that larger higher moments with fixed variance lead to improved exploration. This aligns in supervised learning where Simsekli et al. (2019) conjectured
with one view of that heavy-tailedness in gradients improve generalization.
However, we hypothesize that in deep RL where the optimization process is known to be brittle (Henderson al. 2018: [017 [Engstrom et al. 2019: Tyyas et al. 2018), heavy-tailedness can cause heightened instability than help in efficient exploration. This perspective aligns with another line of work (Zhagg et al. 2019b al where authors demonstrate that heavy-tailednee can cause instability in the learning process in deep models. Indeed with ablation experiments in Appendix [ increasing heavy-tailedness in likelihood ratios hurt the agent's performance, and mitigating heavy- tailedness in advantage estimates improves learning dynamics and hence the agent's performance. Chung et al. (2020) further pointed out the importance of careful analysis of stochasticity in updates to understand the optimization process of policy gradient algorithms. We consider that our work is a stepping stone towards analyzing stochasticity beyond variance.
we show that
Bubeck et al. (2013) studied the stochastic multi-armed bandit problem when the reward distribution is heavy-tailed. The authors designed a robust version of the classical Upper Confidence Bound algorithm by replacing the empirical average of observed rewards with robust estimates obtained via the univariate median-of-means estimator (Nemirovski & Yudin 1983) on the observed sequence of rewards. Medina & Yang (2016) extended this approach to the problem of linear bandits under heavy-tailed noise.
CONCLUSION
In this paper, we empirically characterized PPO's gradients, demonstrating that they become more heavy-tailed training proceeds. Our detailed analysis showed that at on-policy steps, the heavy- tailed nature of the gradients is primarily attributable to the multiplicative advantage estimates. On the other hand, we observed that during off-policy training, the heavy-tailedness of the likelihood ratios of the surrogate reward function exacerbates the observed heavy-tailedness.
Subsequently, we examined PPO's s clipping heuristics, showing that they serve primarily to offset the -tiledness induced by off-policy training. Thus motivated, showed that a robust estimation technique could effectively replace all three of PPO's clipping hcuristics: likelihood-rath, clipping, value loss clipping, and gradient clipping.
In future work, we plan to conduct similar analysis on gradients for other RL algorithms such as deep Q-learning. We believe that progress in this direction significantly impact algorithm devel- opment for reinforcement learning.
REFERENCES
Theodore W Anderson and Donald A Darling. A test of goodness of fit. Journal of the American statistical association, 49(268):765-766 1954.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Dkebiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 19/2.96620,... 2019.
Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Trans- actions on Information Theory, 59(11)7711-7717,22 2013.
Wesley Chung. Valentin Thomas, Marlos C Machado, and Nicolas Le Roux. Beyond variance reduction: Understanding the true impact of baselines on policy optimization. arXiv preprint arXiv:2008. 13773, 2020.
Jon Danielsson, Lerby Murat Ergun, Laurens de Haan, and Casper de Vries. Tail index estimation: Quantile driven threshold selection. Available at SSRN 27/7478, 2016.

---

Under review as a conference paper at ICLR 2021
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras. Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Implementation matters in deep rl: A case study on ppo and trpo. In International Conference Learning Representations, 2019.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Jain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. arXiv preprint 1802.01 2018.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. arXiv preprint (xiiv110090066000 2017.
Peter Henderson, Joshua Romoff, and Joelle Pineau. Where did my optimum go?: An em- pirical analysis of gradient descent optimization in policy gradient methods. arXiv preprint 1rX1v:1810.02525, 2018.
Bruce Hill. simple general approach to inference about the tail of distribution. The annals of statistics, pp. 1174-1174, 1975.
Andrew Ilyas, Logan Engstrom, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry. A closer look at deep policy gradients. arXiv preprint arXiv: 181 I. 1.05533, 2018.
Riashat Islam, Peter Henderson, Maziar Gomrokchi, and Doina Precup. Reproducibility of benchmarked deep reinforcement learning tasks for continuous control. arXiv preprint arXiv: /701:1770..00 131, 2017.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, pp. 1531-1538, 2002.
Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed linear bandits. In International Conference on Machine Learning, pp. 1642-1650, 2016.
Stanislav Minsker et al. Geometric median and robust estimation in banach spaces. Bernoulli, 21 (4):2308-233) 2015.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 518(7540):529 533, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp.
2016.
Mohammad Mohammadi, Adel Mohammadpour, and Hiroaki Ogata. On estimating the tail index and the spectral measure multivariate a-stable distributions. Metrika, 78(5))549-561, 2015.
A.S. Nemirovski and D.B. Yudin. Problem Complexity and Method Efficiency in Optimization. A Wiley-Interscience publication. Wiley, 1983.
Abhishek Panigrahi, Raghav Somani, Navin Goyal, and Praneeth Netrapalli. Non-gaussianity of stochastic gradient noise. arXiv preprint
2019.
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust esti- mation via robust gradient estimation. arXiv preprint arXiv: 1802.0680006488 2018.
Sidney I Resnick. Heavy-tail phenomena: probabilistic and statistical modeling. Springer Science & Business Media, 2007.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference machine learning, pp. 1889-1897, 2015a.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint 1oXiv:/506.0244 2015b.
10

---

Under review as a conference paper at ICLR 2021
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
David Silver. Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):35-339) 2017.
Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise deep neural networks. arXiv preprint arXiv:/901.0000 2019.
Umut Şimşekli, Lingjiong Zhu, Yee Whye Tch, and Mert Gürbüzbalaban. Fractional underdamped langevin dynamics: Retargeting sgd with momentum under heavy-tailed gradient noise. arXiv preprint arXiv:2002.05688, 2020.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural informa- tion processing systems, 1057-1063, 2000.
Emanuel Todorov, Tom Frez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEF/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012.
Dilin Wang, Hao Liu, and Qiang Liu. Variational inference with tail-adaptive f-divergence. In Advances in Neural Information Processing Systems, pp. 5737-5747, 2018.
Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Mach. Learn., 8(3 4):229 256, May 1992. ISSN 0885-6125. BF00992696. htth:tt::: /doi..i..///// /tc/ 11..1....0000000000 1007 /F0////FF0996666
doi: 10.1007/
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint
2019a.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why adam beats sgd for attention models. arXiv preprint 19200:191, 2019b.

---

Under review as a conference paper at ICLR 2021
A DETAILED BACKGROUD
We define a Markov Decision Process (MDP) as a tuple (S, 7, P). where S represent the set of environments states, A represent the of agent actions, R: A the reward function, is the discount factor, and P S x A x S - R is the state transition probability distribution. The goal in reinforcement learning is learn policy we S that the expected cumulative discounted reward (known as returns) is maximized. Formally,
[0, 1], parameterized by A, such
arginxx Baias( (10))
Σ 7' R(sss a.)
(6)
Policy gradient methods directly optimize a paraterized policy function (also known as actor net- work). The central idea behind policy gradient methods to perform stochastic gradient ascent on expected return (Eq. (6) to learn parameters A. Under mild conditions (Sutton et al. 2000), the
gradient of the Eq. c be written as
8 Σ y R(ss, at) Vo
VoJ(O) ETTTT
where T ~ my are trajectories sampled according to (T(T) and J(O) is the objective maximised
in Eq. 6 With the observation that action d, only affects the reward from time / onwards, we re- we-write the objective J()). replacing returns using the Q-function, i.c., the expected discounted
reward after taking an action a at state and following wa afterwards. Mathematically. Qn (s, Ey ->== 7* [[ dc+x) a, 8t = s]. Using the Q-function, can write the gradient
of the objective function as
o Σ 1=0
VoJ(O) Ey
(To at Vo Vogo((o((a)ss))
However, the variance in the above expectation can be large, which raises difficulties for estimating
the expectation empirically. To reduce the variance of this estimate, baseline is subtracted from cotetioooooonnnnnnne the Q-function often the value function or expected cumulative discounted reward starting
certain state and following a given policy i.e., V (s) Er [_ [*[[++4,, 0x44)18; s]. The network that estimates the value function is often referred to critic. Define Ano ($t, a.) =
Qr (St, at) Vr (st) as the advantage of performing action a, state st. Incorporating an advan- tage function, the gradient of the objective function can be written:
VoJ EYNTA
Ana (st, at Vo log(To((asssss)
Eq. 7 is the näive actor-critic objective and is used by A2C.
Trust region methods and PPO. Since directly optimizing the cumulative rewards can be challeng- ing, modern policy gradient optimization algorithms often optimize a surrogate reward function in place of the true reward. Most commonly, the surrogate reward objective includes a likelihood ratio to allow importance sampling from behavior policy To while optimizing policy such as the surrogate reward used by Schulman al. (2015a):
(o(a,, 8t) Anp (Se, av)
max E (ssaa)))
To(a,, st)
a(A,) (we refer to this as the normalized advantages). However, the surrogate is indicative of the true reward function only when To and mo are close in distribution. Different policy gradient methods (Schulman al.] [2015a] 2017: Kakade 2002) attempt enforce the closeness in different ways. Natural Policy Gradients (Kakade (002) and Trust Region Policy Optimization (TRPO) (Schulman et al. 2015a), authors utilize conservation policy iteration with an explicit divergence constraint which provides provable lower bounds guarantee on the improvements of the parameterized policy. On the other hand, PPO (Schulman al. 2017) implements clipping
where A, A- Ax-H(A.)
12

---

Under review as a conference paper at ICLR 2021
heuristic the likelihood ratio of the surrogate reward function to avoid excessively large policy updates. Specifically, PPO optimizes the following objective:
max ( min (clip(pt, e, + e) +,
(s), (e
(9)
[o( where Pe: [as,se)) We refer to Pt as likelihood-ratios Due minimum with the unclipped surrogate reward, the PPO objective acts as a pessimistic bound on the true surrogate reward. As in standard PPO implementation, use Generalized Advantage Estimation (GAE) (Schulman et al. 2015b). Moreover, instead of fitting the value network via regression to target values:
LV (Vo. Vtarg)²
(10)
standard implementations fit the value network with PPO-like objective:
L max (Vo, - Viarg) (clip (Vo., Vo, -
-, Vo, + + Vharg) )
(11)
where e the same value used clip probability raitos in PPO's loss function (Eq. ??). PPO uses the following training procedure: At any iteration t, the agent creates clone of the current policy To, which interacts with the environment to collects rollouts S (i.e., state-action pair {(s;, (.s,aa)]: { Then the algorithm optimizes the policy To and value function for fixed K gradient steps on the sampled data S. Since at every iteration the first gradient step is taken on the same policy from which the data was sampled, we refer to these gradient updates on-policy steps. And for the remaining K - 1 steps, the sampling policy differs from the current agent, we refer to these updates off off-policy steps.
Throughout the paper, we consider a stripped-dows variant of PPO (denoted PPO-NOCLIP) that consists of policy gradient with importance weighting (Eq. & but has been simplified follows: i) no likelihood-ratio clipping, i.e., no objective function clipping; ii) value network optimized via regression to target values (Eq. 10p without value function clipping; and iii) gradient clipping- Overall PPO-NOCLIP uses the following objective:
Te (e(ar, St) Ar, (8), c(Vo. Vtarg)
max E (s
Tu(ae, st)
where c is a coefficient of the value function loss (tune hyperparameter), Moreover, gradient clipping is incorporated in PPO-NOCLIP. One may argue that since PPO-NOCLIP removes the clipping heuristic from PPO, the unconstrained maximization of Eq. I may lead excessively large policy updates. In App. we empirically justify the use of Eq. by showing that with the small learning rate used in our experiments (optimal hyperparameters in Table PPO-NOCLIP maintains a KL based trust-region like PPO throughout the training. We elaborate this in App.
B DETAILS ON ESTIMATORS
We now formalize our setup for studying the distribution of gradients. Throughout the paper, the following definition of the heavy-tailed property:
Definition 2 (Resnick (2007)) )) A non-negative random variable w is called heavy-tailed if its tail probability (t): =P(w 2 1) is asymptotically equivalent to t t-a as 1 > oo for some positive number a". Here a determines the heavy-tailedness and a is called tail index of w.
For heavy-tailed distribution with index ox", its a-th moment exist only if < a", i.e., E|w < oo iff a < a*. A value of a² = 1.0 corresponds a Cauchy distribution and oo (i.e., all moments exist) corresponds to Gaussian distribution. Intuitively, a decreases, the central peak of the distribution gets higher, the valley before the central peak gets deeper, and the tails get heavier. In other words, the lower the tail-index, the more heavy-tailed the distribution. However, in the finite sample setting, estimating the tail index is notoriously challenging (Simsekli et al. 2019 Danielsson
et al. 2016 Hill 1975).
In this study, we explore three estimators as heuristic measures to understand heavy tails and non- Gaussianity of gradients.
13

---

Under review as a conference paper at ICLR 2021
(a paretaoalpha-z100 22)=2) normal
pareto normal
kurtosis" (114)
purtos's" "irtosis"(11 (1/4)
107
101
10*
10a
10t
10
Num samples
Shape Pareto
(b)
Figure 5: Kurtosis plots. Analysis norms of 100-dimensional vectors such that each coordinate is sampled iid from Pareto distribution or normal distribution. (a) Variation in kurtosis (x. /// as the sample size is varied for samples from normal distribution and Pareto with tail index 2 (i.e, 2). (b) Variation in kurtosis (x:/4) as the shape of Pareto varied fix sample size.
Alpha-inder estimator. This estimator was proposed in Mohammadi et al. (2015) for sym- meteric a-stable distributions and was used by Simsselll al. (2019) understand the noise behavior of SGD. This estimator is derived under the (strong) assumption that the stochas- tic Gradient Noise (GN) vectors are coordinate-wiss independent and follow a symmetric alpha-stable distribution. Formally, let { be collection of N mn (centered) random variables. Define Y, Σn X x+((1-1)) 1)m for i E [n]. Then, the estimator given by
1
1 Σ Nog (X, |x.]
log |Y]
log
Instead of treating each co-ordinate of gradient noise independent scalar, we these estimators on gradient norms. With alpha-index estimator, smaller alpha-index value signify higher degree of heavy-tailednne
test (Anderson & Darling 1954) on random projections of GN to per- form Gaussianity testing. Panigraai et al. (2019) proposed the Gaussianity test on the pro- jections of GN along 1000 random directions. Their estimate is then the fraction of direc- tions accepted by the Anderson Darling test. While this estimator is informative about Gaussian behavior, it is not useful to quantify and understand the trends of heavy-tailednnes if the predictor nature is non- non-Gaussian.
To our knowledge, the deep learning literature has only exploredthese two estimators for analyzing the heavy-tailed nature of gradients. (iii) Finally, in our work, we propose us- ing kurtosis Kurtosis. To quantify the heavy-tailedness relative to a normal distribution, we measure kurtosis (fourth standardized moment) of the gradient norms. Given samples [X the kurtosis x is given by
ΣN -X,-8)1//
K
(X. X)P/N)
where X is the empirical mean of the samples.
B. SYNTHETIC STUDY
In Figure 5 we show the trends with varying tail index and sample sizes. Clearly as the tail-index increases, Le.,, the shape parameter increases, the kurtosis decreases (signifying its correlation to capture tail-index). Although for tail-index smaller than the kurtosis is not defined, we plot empir- ical kurtosis and show its increasing trend sample size. We fix the tail index of Pareto 2 and plot
14

---

Under review as a conference paper at ICLR 2021
finite sample kurtosis and observe that it increases almost exponentially with the sample size. These two observations together hint that kurtosis is neat surrogate measure for
C GMOM ALGORITHM
Algorithm 3 WEISZFELD
Algorithm 2 GMOM
input Samples S = . ,b), number of blocks b
input Samples S = {II, En number of blocks b
1: Initialize arbitrarily.
1: In/b].
2: for iteration I,..., do
2: for 11..... b...brr do
3: dy: 1n-1;12 for in ,
3: Nı L5== I--iom! m.
4: end for
4: j:: E () / (E)=1 d3)
5: ÍGMMM= = WEISZFELD((A,... ...)
5: end for
output Estimate ÅGMом
output Estimate
D EXPERIMENTAL SETUP FOR GRADIENT DISTRIBUTION STUDY
Recall that PPO uses the following training procedure: At any iteration the agent creates clone of the current policy To, which interacts with the environment to collects rollouts S (i.e., state-action pair {(, ) Then the algorithm optimizes the policy Th and value function for fixed K gradient steps on the sampled data S. Since at every iteration the first gradient step is taken on the same policy from which the data was sampled, we refer to these gradient updates as on-policy steps. And as for the remaining K - steps, the sampling policy differs from the current agent, we refer to these updates as off-policy steps. For all experiments, we aggregate our estimators across 30 seeds and 8 environments. We do this by first computing the estimators for individual experiments and then taking the sample mean across runs. now describe the exact experimental details.
In all of our experiments, for each gradient update, we have a batch size of 64. Hence for an individ- ual estimate, we aggregate over 64 samples (batch size in experiments) to compute our estimators. For Anderson Darling test, we use 100 random directions to understand the behavior of stochastic gradient noise.
On-policy heavy-tailed estimation. At every on-policy gradient step (i.e. first step on newly sam- pled data), we freeze the policy and value network, and save the sample-wist gradients of the actor and critic objective. The estimators calculated every tenth on-policy update throughout the training.
Off-policy heavy-tailed estimation At every off-policy gradient step (i.e. the gradient updates made on fixed batch of data when the sampling policy differs from the policy being optimized), freeze the policy and value network, and save the sample-wise gradients of the actor and critic objective. Then at various stages of training, i.c., initialization, 50% max reward and max reward (which corresponds different batches of sampled data), we fix the collected trajectories and collect sample-wise gradients for the 320 steps taken. We now elaborate the exact setup with one instance, 50% of the maximum reward. First, we find the training iteration where the agent achieves approximately 50% of the maximum reward individually for each environment. Then at this training iteration, we freeze the policy and value network and save the sample-wise gradients of the actor and critic objective for off- off-policy steps.
Analysis PPO-NOCLIP with progressively applying PPO heuristics. We compute the gra- dients for the off- off-policy steps taken with the PPO-NOCLIP objective explained above. Then each gradient step. we progressively add heuristics from PPO and re-compute the gradients for anal- ysis. Note that we still always update the value and policy network with PPO-NOCLIP objective gradients.
15

---

Under review as a conference paper at ICLR 2021
E TRENDS WITH ADVANTAGES
E.1 KURTOSIS FOR RETURNS, VALUE ESTIMATE AND ADVANTAGES GROUPED WITH SIGN
2.1
Ag +
1.8
1.5
0 103
200
300
400
500
On-policy steps
Figure 6: Heavy-tailedness in advantages grouped by their sign, rewards and value estimates. Clearly, as the training progresses the negative advantages become heavy-tailed. For returns, we observe an initial slight increase in the heavy-tailedness which quickly plateaus to small magni- tude of heavytailedness. The heavytailedness the value estimates and positive advantages remain almost constant throughout the training.
E.2 HEAVY-SAILEDNESS IN A2C AND PPO IN ONPOLICY ITERATIONS
A2C-A,
PPO-A.,
1.8
Kurtost
1.7
166
1.3
On-policy steps
Figure 7: Heavy-tailedness in advantages for A2C and PPO during on-policy iterates. Clearly, as the training progresses heavy-tailedness in PPO advantages increases rapidly when compared with A2C advantages. The observed behavior arises to the off- off-policy training of the agent in PPO. This explains why we observe heightened tailedness in PPO during onpolicy iterations in Fig Ta).
16

---

Under review as a conference paper at ICLR 2021
E.3
HISTOGRAMS OF ADVANTAGES ON HALFCHEETAH OVER TRAINING ITERATIONS
Env Steps #102400
Env Steps #204800
Env Steps #307200
66
66
26
24
24
>-8
<0
63
03
333
23
60
66
3.
Env Steps #409600
Env Steps #512000
Env Steps # #614400
36
05
01
02
80
38
Env Steps #716800
Env Steps #819200
Env Steps #921600
65
02
35
62
62
33
-22
Figure 8: Distribution of log( (0g( 1) over training grouped by sign of 1o,(1A...)) for HalfCheetah- v2. To elaborate, we collect the advantages and separately plot the grouped advantages with their sign, i.e., we draw histograms separately for negative and positive advantages. As training proceeds, we clearly observe the increasing heavy-tailed behavior in negative advatanges as captured by the higher fraction of log((A,,,)) with large magnitude. Moreover, the histograms for positive advan- tages (which resembel Gaussain pdf) stay almost the same throughout training. This highlights the particular heavy-tailed (outlier-rich) nature of negative advantages corroborating our experiments with kurtosis and tail index estimators.
17

---

Under review as a conference paper at ICLR 2021
F ANALYSIS WITH OTHER ESTIMATORS
F.1 ON-POLICY GRADIENT ANALYSIS
Alpha Index
2.0
Alpha Index
2.0
2.0
1.
1.
3.
PPO
Av
166
300
306
400
548
166
200
204
400
568
108
230
206
400
548
On-policy steps
On-policy steps
On-policy steps
(b)
(c)
Figure 9: Heavy-tailedness in PPO during on-policy iterations. All plots show mean alpha index aggregated over 8 MuloCo environments. A decrease in alpha-index implies increase in heavy- tailedness. (a) Alpha index vs on-policy iterations for A2C and PPO. Evidently, as training pro- ceeds, the gradients become more heavy-tailed for both the methods. (b) Alpha index on-policy iterations for actor networks PPO. (c) Alpha index vs on on-policy iterations for critic networks in PPO. Both critic and actor gradients become more heavy-tailed on-policy steps the agent is trained. Note that as the gradients become more heavy-tailed, we observe a corresponding increase of heavy-tailedness in the advantage estimates (Ar, ) However, "actor/ A and "critic/A Am " (i.e., actor or critic gradient norm divided by GAE estimates) remain light-tailed throughout the training.
actor actoriA
0.8
Fraction Accepted
Fraction Accepted
0.6
0.5
0.5
0.4
critic/Á.
0.2
0.3
0.0
0.9
200
500
130
200
300 400
500
On-policy steps
On-policy steps
(b)
Figure 10: Heavy-tailedness in PPO during on-policy iterations. All plots show mean fraction of directions accepted by Anderon-Darling test over MuJoCo environments. A higher accepted frac- tion indicates Gaussian behavior. (b) Fraction accepted on-policy iterations for actor networks in PPO. (c) Fraction accepted vs on-policy iterations for critic networks in PPO. Both critic and actor gradients remain non-Gaussian as the agent is trained. However, "actor/ À and "critic/A,g (i.e.. actor or critic gradient norm divided by GAE estimates) have fairly high fraction of directions accepted, hinting their Gaussian nature.
18

---

Under review as a conference paper at ICLR 2021
F.2
OOLICY GRADIENT ANALYSIS
Initiallzation
50% of Max Reward
Max Reward
0.80
2.00
Alpha index
Alpha index
ratios
aloo
1.4
139
Aupha
1.7
actor
actor trbcc
onbic
ratlos
ratios Sctoriratio
1.50 actoniratio
120
222
Off-policy steps
Off-policy steps
Off-policy steps
Figure 11: Heavy-tailedness in PPO-NOCLIP during off-policy steps various stages of train- ing iterations in MuloCo environments. All plots show mean alpha index aggregated over 8 Mujoco environments. A decrease in alpha index implies increase heavy-tailedness. As off-policyness increases, the actor gradients get substantially heavy-tailed. This trend is corroborated by the in- crease of heavy-tailedness in ratios. Moreover, consistently we observe that the heavy-tailedness in "actor/ratios" stays constant. While initially during training, the heavy-tailedness in the ratio's 's in- creases substantially, during later stages the increase tapers off. The overall increase across training iterations is explained by the induced heavy-tailen seavdesailedness in the advantage estimates (cf. Sec. 3.1)
19

---

Under review as a conference paper at ICLR 2021
G HYPERPARAMETER SETTINGS AND REWARDS CURVES ON INDIVIDUAL ENVIORNMENTS
Hyperparameter
Values
Steps per PPO iteration
2048
Number of minibatches
32
PPO learning rate
0.0003
ROBUST-PPO-NOCLL learning rate
0,00008
PPO-NOCLIP learning rate
0.00008
Discount factor ?
0.99
GAE parameter X
0.95
Entropy loss coefficient
0.0
PPO value loss coefficient
2.0
PPOUS-T-PP-NOLPPPP value loss coefficient
2.0
PPO-NOCLIP value loss coefficient
2.0
Max global L2 gradient norm (only for PPO)
0.5
Clipping coefficient (only for PPO)
0.2
Policy epochs
10
Value epochs
10
GMOM number of blocks
8
GMOM Weiszfeld iterations
100
Table 1: Hyperparameter settings. Sweeps run over learning rates 0.000025, 0.00005, 0.000075, 0.00008, 0.00009 0.0001, 0.0003, 0.0004 and value loss coefficient { (.1,, 0.5, 1.0, 2.0, 10.0) with 30 random seeds per learning rate.
X2
AVC-V2
Humansidu2
Rewardss
Rowards
N Number of Timesteps
Number of Timesteps
Bo0 1900
Number of Timestpss
Numbhr of Timeetpss
Cortooeev
Hopper +2
Reachar-v2 v2
InvertedPendalum-
Rewerrss
Rowards
Druddo
Number limestipa
Number "imeddess
Timeslaps
Numbar Timessopa
Figure 12: Reward curves training progresses in different Mujuco Environments aggre- gated across 30 random seeds and for hyperparameter setting tabulated in Table I The shaded region denotes the standard deviation across seeds. We observe that except in Hopper-v2 en- vironment, the mean reward with RORUST-PPO-NOCL.PP is significantly better than PPO-NOCLIP and close that achieved by PPO with optimal hyperparameters. Aggregated results shown in Fig.
20

---

Under review as a conference paper at ICLR 2021
H ANALYSIS ON INDIVIDUAL ENVIORNMENTS.
Overall, in the figures below, we show that the trends observed in aggregated plots in Section 3 with Kurtosis hold true on individual environments. While the degree of heavy-tailedness varies in different environments, the trend of increase in heavy-tailedness remains the same.
Hoppor
HaPChoctah V2
On policy
Onpeliyy stops
On policy
CartPolo
Reacher
Walker2d
InvertedPendalum v2
eclond.
On policy stops
On On-policy stops
On colicolcy Saps
On-policy stops
Figure 13: Heavy-tailedness in actor gradients for PPO during on-policy steps for MuJoCo environments. All plots show mean and std of kurtosis aggregated over 30 random seeds. As the agent is trained, actor gradients become more heavy-tailed. Note that as the gradients become more heavy-tailed, we observe corresponding increase of heavy-tailedness in the advantage estimates (A However, A (i.e., actor gradient norm divided by advantage) remain light-taibe tailed throughout the training.
Art-v2
Hoppor-v2
HalCChottah-22
Humansidiv2
city
city
ericol_
On-policy staps
Onipolicy staps
Onseliiy stops
On-pelicy staps
CartPoleol
Reacher-22
Walker
Irvertedferddkam-22
citc
Onepolicy
200 40
323
CC-policy
Onspoliy Mleps
po
35.
300
300
60
30
Figure 14: Haavy-tailedness in critic gradients for PPO during on-policy steps for MuJoCo environments. All plots show mean and std of kurtosis aggregated over 30 random seeds. As the agent is trained, critic gradients become more heavy-tailed. Note that the gradients become more heavy-tailed, we observe a corresponding increase of heavy-tailednes in the advantage estimates (A However, "critic/ " (i.e., critic gradient norm divided by advantage) remain light-tailed throughout the training.
21

---

Under review as a conference paper at ICLR 2021
Art--2
Hopper-22
Haiftheetah-w22
Hu mumrriid-22
pff-policy stops
Offipolicy Steps
off-poicy Staps
Ofliplicy Steps
CartPole-v1
Reacher-
Walkerd6-22
InvertedPend dlum '2
12
city
off-policy stops
Off-policy staps
Cffpplicy Staps
Of.policy staps
Figure 15: Heavy-tailedness in PPO-NOCLIP during off-policy steps at Initialization for 8 Mu- JoCo environments. All plots show mean and std of kurtosis aggregated over 30 random seeds. As off-policyness increases, the actor gradients get substantially heavy-tailed. This trend is cor- roborated by the increase of heavy-tailedness in ratios. Moreover, consistently we observe that the heavy-tailedness in "actor/ratios" stays constant. The trend in heavy-tailedness at later training it- eration follow similar trends but the increase in heavy-tailedness tapers off. The overall increase across training iterations is explained by the induced heavy- tealy-sailesnnss in the advantage estimates (cf. Sec.
Hopper-12
HallCheethh-22
Humanoid-22
PFO PPG-NoxCIp
PPO
PPO Noo
PPG-NaCip
0
Borations
Karations
Itorations
4 Iborrtions
CartFole vi
Beachero22
Wi kerler2d-22
Truvs hanleaaaann
3.50
PPO PrO-Xecip
PPD PPDD-Ncilo
IPG
PPO-Nocip
PRD PPO NoC
<0001
5000
Figure 16: KL divergence between current and previous policies with the optimal hyperparam- eters (parameters in Table We measure the mcan empirical KL divergence between the policy obtained at the end of off- polliol training (after every 320 gradient steps) and the sampling policy at the beginning of every training iteration. The quantities are measured over the state-action pairs collected in the training step (Engstrom al. (2019) observed similar results with both unseen data and training data). We observe that both the algorithms maintain a KL based trust region. The trend with KL divergence in PPO matches with the observations made in Engstrom al. 20119 where they also observed that it peeks in halfway in training.
I MEAN KL DIVERGENCE BETWEEN CURRENT AND PREVIOUS POLICY
Enforcing a trust region is a core algorithmic property of PPO and TRPO. While the trust-region enforcement is not directly clear from the reward curves or heavy-tailed analysis, inspired by En- gstrom et al. (2019), crty varies with PPO and our variant PPO-NOCLIP with optimal hyperparameters. In Fig [6 we measure mean KI. divergence between successive policies of the agent while training with PPO
perform additional experiment to understand how this algorithmic prop-
22

---

Under review as a conference paper at ICLR 2021
HalCheetah-222
per
Ant-22
Rewards
Rowurds
480487.300
Number of Timassttp
Namber of Timastaps
Number of Timentaps
Number Timendeps
D000
CartPo evr
IneeredPendullumi
Humanoli-v22
Reecher-u2
Bowards
ROMSOS
Rowords
Number Tip
Number of Timessaps
Numbbrr Timmelaps
Number of Timestaps
Figure 17: Reward curves with vdvattege clipping in 8 different Mujoco Environments aggre- gated across 30 random seeds. The shaded region denotes the one standard deviation across seeds. The clipping threshold is tuned per environment. We observe that by clipping outlier advantages, we substantially improve the mean rewards for 5 environments. While for the remaining three envi- ronments, we didn't 't observe any differences the agent performance.
and PPO-NOCLIP. Recall that while PPO implements a clipping heuristics in the likelihood ratios (as a surrogate to approximate the KL constraint of TRPO), we remove that clipping heuristics in PPO-NOCI.IP.
Engstrom et al. (2119 pointed out that trust-region enforced in PPO is heavily dependent on the method with which the clipped PPO objective is optimized, rather than on the objective itself. Cor- roborating their findings, we indeed observe that with optimal parameters (namely small learning rate used in our experiments), PPO-NOCLIP indeed manages to maintain trust region with mean KL metric (Fig I6) on all 8 MuJoCo environments. This highlights that instead of the core algo- rithmic objective used for training, the size of the step taken determines the underlying objective landscape, and its constraints. On a related note, [[yas et al. (2018) also highlighted that the ob- jective landscape of PPO algorithm in the typical sample-regime in which they operate be very different from the true reward landscape.
J HOW HEALY-TAILEDNESS AFFECT TRAINING?
To understand the effects of heavy we perform two ablation experiments: First, we study the effects of haave-tailedness in negative advantages. By clipping the outlier negative advantages used in the PPO loss, we show that the induced heavy-tailedness in advantages gets reduced and the performance of the agent improves. Second, we seek to understand the effects of heavy-tailedne, taileddesss induced in the likelihood ratios during off-policy training. We vary the number of off-policy gra- dient steps (a hyperparameter otherwise fixed 10) taken by agent trained with PPO-NOCI.IP and show that the additional off-policy learning exacerbates heavy-tailednes in ratios and directly affects the agent performance even while maintaining trust-region with mean KL metric.
Next, we detail these experiments and highlight how the heavy-tailedness induced hurts the learning of agent with the mean reward metric.
J.1 EFFECT OF HEAVY- TAILEDNESS IN ADVANTAGES
Recall that analysis in Section 3.1 shows that multiplicative advantage estimate in the PPO loss is a significant contributing factor to the observed heavy-tailedness. While PPO clipping mech- anisms ameliorate the observed heavy-tailedness some extent, the heuristics majorly offset the
We tried using PPO loss for this experiment. However, while training with PPO, the successive policies diverge in mean KI. metric when we increase the number of offline epochs used for training.
23

---

Under review as a conference paper at ICLR 2021
heavy- talylttaisdness induced during off off-policy gradient steps and doesn't t seem to handle the induced heavy-taile heavy-tailedness in advantages. Motivated by this connection, we aim to study the effects of clip- ping advantages to understand its impact the agent's 's behavior. In particular, we clip negative advantages which are the primary contributors to the induced heavy-tailedness.
Depending the individual environment and the ob- served heavy-tailedness, we tune an environment depen- dent clipping threshold for advantages to maximize the
21
A,
2.0
1.9
performance of the agent trained with PPO. Intuitively, we expect that clipping should improve optimization and
Kurtosis
2.6
3.7
hence should lead to improved agents' performance. Cor- roborating the intuition, we observe significant improve- ments (Figure 17). Moreover, to understand the nature of clipped advantages, we plot the trend of heavy-tailednee in advantage estimates during training. Confirming our hypothesis, as we clip negative advantages below the obtained threshold, observe that the induced heavy- tailedness stays constant throughout training (Figure (8].
1.6
1.5
1.4
1.3
100
200
On-policy steps
Figure 18: Heavy-tailedness in PPO advantages with per-environment tuned clipping threshold in MuJoCo environments. All plots show mean kurtosis aggregated over 8 Mujoco environments. With clipping advan- tages appropriate thresholds (tuned per environment), we observe that the heavy-tailedness in advantages remains almost constant with training.
Our experiment unearths a previously unknown fact. Since the advantage estimates significantly contribute to the observed heavy-tailed behavior, we show that clipping outlier advantages stabilizes the training and improves agents' performance on 5 out of 8 MuJoCo tasks. While tuning clipping threshold per environment may not be practical, the primary purpose of this study is to illustrate that heavy-tailedness in advantages can actually hurt the optimization process, and clipping advan- tages lead to improvements in the performance of agent. We believe that this opens a door for future research to develop more principled (and environment agnostic) methods to handle the induced haaly-tailedness in advantages which is not handled by PPO.
J.2 EFFECT OF HEAVY-TAILEDNESS IN LIKELHHOOD-RATU
we demonstrated the heavy-tailed behavior of gradients during off-policy training which increases with off-policy gradient steps in PPO-NOCLIP. Moreover, we observe corresponding increase in the heavy-tailedness of likeliihood ratios. Motivated by this connection, we train agents with increased off- off-policy gradient steps to understand the effect of the likelihood ratios induced heavy-tailednes, on the performance of the agent. With PPO-NOCLIP, we train agents for 20 and 30 offline epochs (instead of 10 in Table [ and analyse its performance in terms of mean reward. Note that even with 20 and 30 offline epochs the agent maintains a KL based trust-region throughout training (Bottom row in Figure 21
Recall, in Section 3.2
First, as expected, we observe an increase in heavy-tailedness in the likelihood ratios with escalated offline training (Figure 20). Moreover, the heavy-tailedie an increase in the number of offline epochs (Figure 19 confirming that the observed behavior is pri- marily due to heightened heavy-tailedness in likelihood ratios. We hypothesize that induced heavy- tailedness can make the optimization process harder. Corroborating this hypothesis, observe that as the number of offline epochs increases, the performance of agent trained with PPO-NOCLIP deteriorates, and the training becomes unstable (Top row in Figure 21
in advantages remains unaffected with
The findings from this experiment clearly highlight the issues due to induced heavy-tailedness in likelihood ratios hindering efficient policy optimization. While offline training enables sample effi- cient training, restricting the number of off-policy epochs allows effective tackling of optimization issues induced due to the heavy-tailed nature (which are beyond just trust-region enforcement). In the future, we believe that these insights can be used to develop better algorithms for efficient offline training.
Beyond 30 offline steps, successive policies often diverge-failing maintain a KL. based trust region.
24

---

Under review as a conference paper at ICLR 2021
Initialization
20
1. epochs
10 epochs
2,2
20 epochs
10 epochs
apochs
Kurtosis
2.0
epochs
1.8
1.6
15
14
1.4
0.0
02 64 0.6 5. 1.0
On-policy steps
Fraction of off-policy steps
Figure 19: Heavy-tailedness in PPO-NOCLIP advantages throughout the training the de- gree of off-policyness is varied in MuJoCo en- vironments. Kurtosis is aggregated over Mu- joco environments. We plot kurtosis vs on- policy iterates. As the number of off-policy epochs increases, the heavy-tailedness. in advan- tages remains the same showing an increase the number of offline epochs has minor effect on the induced heavy-tailedness the advan- tage estimates.
Figure 20: Heavy-tailedness in PPO-NOCLIP likelihond-ratios as the degree of off- policyness is varied. at initialization in MuJoCo environments. Kurtosis is aggregated over Mujoco environments. We plot kurtosis the fraction of off-policy steps (i.e. number steps taken normalized by the total number of gradients steps in one epoch). As the number of off off-policy epochs increase, the heavy-tailedness in ratios increases substantially. The same trend holds at other training iterations, however, the degree of increase tappers off.
25

---

Under review as a conference paper at ICLR 2021
LalCCheeeh--
A12-2
Haaannidde
24
FRO-REC 120
Number of Timestapa
Number of Timesteps
Number of Timmstppa
Number of Timmssaapa
Hopperrv2 V2
Carthllos
Reacher V2
InoerteePeendalumm
SC2
bactly (982
2000
Timestoss
Namoor of Timestops
Timestops
Timesstipo
PPO
NaClip (30)
Walcor26-12
(201
303
PPQ
PRG-Naclin (0)
PPG Aodip (20)
PC---CCip (10)
HaTChealt
FPG-NeCIp (1E)
PPG-Nocip
PPO NoClp (20)
PPQ
Ant-v2
NoClpp
Humanoid
NoCip
Itorationa
301
leertioos
lterations
Iterations
tronpe-122
CartPole-vL
Reach
Inverta@Pendddum-2
PPQ
IPD
CH
PPO
3250
PPQ NoCCip (30)
PPO NoClpp (20)
1:01
PPO NoCilp (10)
NoClip (20)
PPO NoC 1201v
PPG- PPG-NcCiip (30)
PPG Nucipp (30)
sGx
3300
Zerodons
Iterations
Eerations
Figure 21: (Top two rows) Reward curves with the varying number of offline epochs in different Mujoco Environments aggregated across 10 random seeds. Bracketed quantity in the legend denotes the number of offline epochs used for PPO-NOCLIP training. Clearly. as the number of offline epochs increases, the performance of the agent drops (consistent behavior across all environments). Furthermore, at 30 epochs the training also gets unstable. We also show the PPO performance curve for comparison. (Bottom two rows) KL divergence between current and previous policies with the optimal hy tyerparraeetess (parameters in Table I for PPO and PPO-NOCLIP with varying number of offline epochs. We measure mean empirical KL divergence between the policy obtained at the end of off-policy training and the sampling policy at the beginning of every training iteration. The quantities are measured over the state-action pairs collected in the training step. We observe that till 30 offline epochs PPO-NOCLIP maintains a trust-region with mean KL metric.
26


Reviews:
[{"review_id": "x0owSVgqPH2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "**Update Post Rebuttal:** The revised manuscript addresses my main concerns, and is stronger than the original, so I am raising my score to accept. For the final manuscript, I urge the authors to better integrate the added content from this discussion period into the main text, instead of relegating it to the Appendix. \n \n**Summary**: This paper hypothesizes that the policy gradient in RL has heavy tails, and conducts a thorough empirical investigation of the heavy-tailed properties of PPO and it's critic estimation. The paper finds that advantages and the sampling ratio have the heaviest tails. Based on this insight, the authors propose a robust version of the PPO gradient estimator that avoids clipping and heuristics, but which still generally matches performance with PPO.\n\n**Assessment:** The paper tests a simple, important, and previously un-studied hypothesis, and provides a convincing empirical analysis. It provides a potential step towards designing better RL algorithms without the heuristics and sensitivity of current RL algorithms, and as such, would be of great interest to the reinforcement learning community at ICLR. Nevertheless, there are some major concerns detailed below, primarily relating to the validity of the PPO-NoClip objective. Conditional on these concerns being addressed, I would recommend acceptance.\n\n**Major Comments:**\n\nWhile the likelihood clipping term in PPO is certainly heuristic, it serves a purpose that is not properly discussed in the paper: to prevent $\\pi_\\theta$ from deviating from $\\pi_0$. More precisely, when function approximation is used for the policy, the surrogate objective $E_{s \\sim \\pi_0, a\\sim \\pi_\\theta}[A_{\\pi_0}(s, a)]$ is not necessarily a good surrogate when $\\pi_\\theta$ is far from $\\pi_0$ **even with infinite samples**. This is not an issue with finite sampling as is mentioned in the preliminaries, and remains a problem even with access to the true expectation (that is, even when heavy-tailed behavior is not a problem). See the TRPO paper [1] for more discussion. This point needs to be made more explicit in the main paper.\n\nAs a result, it is my understanding PPO-NoClip is simply not an appropriate gradient / objective to be analyzing when $\\pi_\\theta$ is very far from $\\pi_0$. This is a problem for the off-policy analysis, since the PPO-NoClip objective and its gradient do not relate to the original expected return objective, and so may not be meaningful quantities to measure or analyze. My initial assessment is that this highly reduces the value of the off-policy experiments for me.\n\n**Clarity**: The paper is generally well-written and easy to follow. However, the paper could greatly benefit from a discussion why heavy-tailed gradients are bad in reinforcement learning. The paper does a very good job of arguing that heavy-tailed gradients exist in PPO, but has little discussion or empirical evidence to suggest that this is necessarily a problem. \n\n\n**Minor Comments:**\n\n- Some recent work [2] also studies a similar phenomenon more generally in stochastic PG methods, and find that second-order moments are insufficient to describe learning phenomena, and would be worth citing.\n- It would be useful to write the exact equation / objective used for `PPO-NoClip` in the main paper\n- In Section 2.1, it is only stated that Pareto distributions (with lower $\\alpha$) also have higher kurtosis. Does some statement to this effect hold for arbitrary distributions (not Pareto)?\n- Why are results different for PPO and A2C in the On-Policy iterations? If only on-policy iterations are conducted, aren't the PPO and A2C updates the same (both equivalent to standard policy gradients).\n- I found the x labels for Figure 1 and Figure 2 confusing. From what I understood, Figure 1 is taken across iterations (different data collection policies for each step) but Figure 2 is taken within a single iteration? This could be more clear.\n- I found the obervation that the negative advantages are the ones with heavy tails to be interesting. However, given the fact that the PPO objective is to minimize the probability of highly negative advantages, aren't heavy tails to be expected? The discussion also didn't make it clear to me why having heavy tails for negative advantages is necessarily a bad thing.\n- In the Preliminaries, the policy in general doesn't map to [0,1] but in the continuous setting, more generally to $\\mathbb{R}_+$.\n\n[1] Schulman et al. Trust Region Policy Optimization, ICML 2015\n\n[2] Chung et al. Beyond variance reduction: Understanding the true impact of baselines on policy optimization. 2020. ArXiv", "extra_scores": {}, "extra_text": {}}, {"review_id": "nIlbpBF6j-S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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**: This paper performs an empirical analysis of the heavy-tailedness of the PPO gradients across MuJoCo environments. They find that PPO gradients are heavy-tailed, which means that they are sensitive to outliers, which means computing the expected gradient is hard. The paper studies two causes of this issue -- advantage estimation errors and the harm caused by optimizing density ratios in a sampled setting, and shows that removing either of them with the other issue controlled for helps PPO. They then propose to use a standard robust mean estimation technique to obtain a robust gradient mean estimator that is plugged into PPO, and performs sort of somewhat worse than vanilla PPO. \n\nI like the paper, but I do think the paper misses some comparison to prior work and alternate views of looking at the same phenomenon which I will discuss next. I am not sure if heavy-tailedess of gradients is the best way of looking at it. Very similar phenomena have been studied in the form of using regularization to prevent overfitting to the density ratios in off-policy bandits (see Swaminathan et al. 2015), and also the impact of variance reduction techniques such as the use of baselines in policy optimization (several papers). What these papers show is that (1) optimizing against importance weighting in the presence of samples may not lead to an improvement in the overall objective, which is bad -- and some on-policy regularization is employed (2) baselines help because they make it possible to reduce variance, however, their form also impacts learning dynamics and exploration (see Chung et al., Beyond variance reduction: Understanding the true impact of baselines on policy optimization) and just looking at variance may not be enough to talk about the efficacy of a baseline. So baselines affect optimization issues even in an expected sense, and just variance is not the best way of looking at the efficacy of a baseline. Translated to PPO, this means that some advantage estimators that lead to higher variance gradients or heavy-tailed gradients might actually be better because the learning dynamics and exploration is better here. Therefore, these are alternate ways of explaining the same issue that the paper points out. So, why is heavy-tailedness interesting, and why should we not look at these other interpretations?\n\nIn particular, is heavy-tailedness always bad? I suspect not -- in some cases, I might want to have more heavy-tailed gradients just because they can either help to navigate the optimization landscape (see Mei et al. On the Global Convergence of Softmax Policy Gradient Methods, or Schaul et al. Ray Interference: a Source of Plateaus in Deep Reinforcement Learning or Chen et al. Surrogate Objectives for Batch Policy Optimization in One-step Decision Making, for a discussion of how the true expected policy gradient can have many saddle points and can have slow convergence based on initialization) by avoiding getting stuck at saddle points. So maybe it is not always that bad? Perhaps some analysis in settings where optimization challenges exist and a comparison of the impact of heavy-tailedness in scenarios where optimization challenges don't exist is a possible way to answer this question.\n\nAlso what happens if I compute the true advantages? Heavy tailedness based on your presented analysis would decrease but would it be better to still do robust gradient estimation? I suspect there will still be some sort of overfitting due to finite sample reuse in the off-policy updates in PPO, but it is interesting to see how much the performance improves in that case. And what would happen in methods that actually derive policy updates from a closed-form objective such as REPS, RWR/AWR, SIL, MPO, etc? \n\nFinally, the method seems like fixing an effect and not the cause -- if the end goal is to obtain better advantage estimates and do better optimization with density ratios, why not fix that directly, rather than using robust mean estimation, which seems like a complex procedure? One way of fixing advantages, for instance, is to just utilize a monotonic function of advantages such as the indicator function in Self-imitation learning and exponentiation function in AWR. Or for instance, centering the advantages which PPO uses can also help (see https://openreview.net/pdf?id=SJaP_-xAb) and maybe even using self-normalization on the importance weights which are optimized in PPO. How would these solutions compare to the proposed estimator?\n\nI think that the paper will benefit from a more concrete discussion of these aspects, especially contrasting and clearly stating the benefits of the proposed view of understanding PPO in comparison with prior explanations and by doing a more extensive evaluation of simpler alternatives to fixing this issue. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "PokwCTFNfw", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "**Positives**\n\nThe claims of the paper are clear and the evidence to support the claims is clearly presented. \n\nThe question of heavy-tailedness is well-motivated and important. There has been growing interest in characterizing the tails of gradient norms, especially in light of assumptions in optimization theory that may be invalidated by heavy tails (e.g., second moment bound). Characterization of the heavy tail property permits further understanding of why our algorithms might fail, and how we might improve them.\n\nThe central claims are well-substantiated with experiments (subject to statistical significance concerns below). Sections 3.1-3.2 show that heavy-tailed gradient norms occur both in the on-policy and off-policy parts of PPO. I especially liked the care in determining the source of the heavy-tailedness: the advantage in the on-policy case and the IS ratio in the off-policy case. Section 3.3 shows that the clipping of the PPO objective reduces the heavy-tailedness of the gradients, which is further support for the relevance of heavy-tailedness.\n\nI appreciated the promising connection made to the field of robust statistics. In section 4, the paper modifies a robust gradient estimation technique to apply in PPO. The fact that Robust-PPO-NoClip does either as well (again, subject to statistical significance concerns below) as or better than PPO or its NoClip variant is evidence that not accounting for heavy-tailed gradients can impede performance. \n\n**Negatives**\n\nThe main problem with this work is the relative lack of statistical significance analysis (figs 1-4). I would have liked to see error bars on figs 1-4. For the individual learning curves (fig 11) in the appendix, it seems that more runs are necessary given the noisiness of the curves. Are there more disaggregated plots of the kurtoses over the environments (in addition to the three in the appendix)? I'm not totally sure what to make of averaging over environments whose dynamics could be quite different. For each environment, it also seems that only 10 seeds were run. Given that prior work (Henderson et al., 2017) suggests that RL algorithms are extremely sensitive to the random seed, I would have liked to see more seeds (minimum 20, preferably 30+).\n\nThe work needs some further discussion on why Robust-PPO-NoClip only seemed to beat PPO-NoClip in some environments, but not others.\n\n**Summary**\n\nI'm leaning towards a marginal accept for the paper: I do think the contribution of the paper is valuable, despite the concerns I have outlined above about statistical significance. I think these concerns are strongest for the control experiments (a relatively smaller part of the paper) given that they are per-environment and utilize fewer samples to estimate the return, as opposed to the gradient estimation experiments for which a batch size of 64 was used for the gradient norm estimation. I think this paper otherwise provides much value in characterizing an important property of PPO, opening the way for future RL algorithms that can better deal with heavy-tailedness. \n\n**Things which didn't affect my decision**\n\n1. Uniform axes for fig 7 would be helpful, to permit comparison of plots\n\n\n** Edit after author response **\nThe authors have addressed the concerns I had so I've increased the score accordingly. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "MUSJqwUZ5qZ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "### Strengths\n\nThis paper presents an intriguing analysis of the gradient distributions over the course of training for popular RL algorithms in common mujoco benchmarks.  The observation that negative advantages are a bigger contributor to the kurtosis than positive advantages seems interesting and if true as a general phenomenon, deserving of more understanding. The authors also propose a new alternative (inspired by robust statistic) to the simple PPO clipping heuristic that does reasonably well even if it doesn't deliver any clear improvements over PPO.\n\n### Weaknesses\n\nThe paper is well motivated, and has a collection of interesting observations but I am not sure if these empirical observations lead to something beyond that, in terms of a more general claim/conjecture. The algorithmic contribution, while novel, is neither particularly strong in terms of performance nor simpler compared to the PPO clipping heuristic.  \n\n### Comments\n\n* By the heavy tailedness in \"advantage divided gradients\", can the authors refer to exactly what 1-dimensional projection is being referred to? This is something ambiguous in the legend in Figure 1 (b) and (c) as well.\n\n* Figure 6 in Appendix E is used to support the claim that the kurtosis increases over time only for negative advantages, but in the figure this isn't clear to me. e..g. for returns there seems to be an increase over time. Also, nit: typo in the legend for $\\hat{V}$.\n\n* \"This observation highlights that at least in Mujoco ...., there is a positive bias of ....value estimate....for actions with negative returns\" <-- this seems a little ambiguous, are you referring to negative advantages?\n\n* In the off-policy case, Figure 2 suggests that the heavy tailedness is coming only from the importance weight ratios. What happened to the heavy tailedness of the (negative)advantages being another source? It seems a bit mysterious that this is only present in the on-policy case and disappears when off-policy. In particular why would the heavy tailedness in the importance ratios and the heavy tailedness from advantages be mutually exclusive?\n\n* The setup for Sec 3.2 is not clear even with appendix D. What does the iteration in the learning curve refer to when considering a particular snapshot like 50% of the max reward?\n\n* Nit/typo: The notation for the GMOM description in the text is missing the \\hat for $\\mu_b$.\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,

As you can see, reviewers agree on the importance of the analysis present in the paper but two reviewers feel like it misses important comparisons.

That said, PPO is a popular algorithm and I also welcome any attempt as improving our understanding of its dynamics. With this paper, information about PPO would be more complete but also more spread out across multiple papers.

At the same time, I am sympathetic to the reviewers' arguments and also feel that the paper would have had a much clearer message had some additional ablation studies been performed, for instance on tabular settings where this is easily done.

The overall assessment is that the paper is not yet ready for publication.
Decision: Reject