ON PROXIMAL POLICY OPTIMIZATION’S HEAVY-TAILED GRADIENTS
Year: 2020

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 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 in gradients. Motivated by these connections, we propose incorporating GMOM, a high-dimensional robust estimator, into PPO as a substitute for three clipping tricks. Our method achieves comparable performance to that of PPO with all heuristics enabled on a battery of MuJoCo continuous control tasks.

heading: 1 INTRODUCTION
text: As Deep Reinforcement Learning (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., 2015), policy gradient methods (Williams, 1992; Sutton et al., 2000; Mnih et al., 2016) have emerged as a popular alternative to dynamic programming approaches. Since the breakthrough results of Mnih et al. (2016) demonstrated the applicability of policy gradients in DRL, a 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—introduced 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., 2018), 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 et al., 2017; 2018; Islam et al., 2017). The ubiquity of these issues raises a broader concern about our understanding of policy gradient methods.
In this work, we take a 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 a rigorous empirical study to understand the causes of heavy-tailedness in PPO gradients. Furthermore, we provide a 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 to analyze the role played by each component of the PPO objective in the heavy-tailedness of the gradients. We observe that as the training proceeds, gradients of both the actor 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 off-policyness increases (i.e. as the behavioral policy and actor policy diverge) dur-
ing training, the likelihood-ratios that appear in the surrogate objective exacerbates the heavy-tailed behavior. Subsequently, we demonstrate that the clipping heuristics present in standard PPO implementations (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, we present an algorithm that uses Geometric Median-of-Means (GMOM), a high-dimensional robust aggregation method adapted from the statistics literature. Without using any of the objective clipping and gradient clipping heuristics implemented in PPO, the GMOM algorithm nearly matches PPO’s performance on MuJoCo (Todorov et al., 2012) continuous control tasks.

heading: 2 PRELIMINARIES
text: We define a Markov Decision Process (MDP) as a tuple (S,A, R, γ, P ), where S represent the set of environments states, A represent the set of agent actions, R : S ×A → R is the reward function, γ is the discount factor, and P : S × A × S → R is the state transition probability distribution. The goal in reinforcement learning is to learn a policy πθ : S × A → R+, parameterized by θ, such that the expected cumulative discounted reward (known as returns) is maximized. Formally, π∗ : = argmaxπ Eat∼π(·|st),st+1∼P (·|st,at) [ ∑∞ t=0 γ tR(st, at)].
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 a surrogate reward function. Often the surrogate objective includes a likelihood ratio to allow importance sampling from a behavior policy π0 while optimizing policy πθ. For example, Schulman et al. (2015a) optimize:
max θ E(st,at)∼π0
[ πθ(at, st)
π0(at, st) Aπ0(st, at)
] , (1)
where Aπθ = Qπθ (st, at) − Vπθ (st). Here, Q-function , i.e. Qπθ (s, a), is the expected discounted reward after taking an action a at state s and following πθ afterwards and Vπθ (s) is the value estimate (implemented with a critic network).
However, the surrogate is indicative of the true reward function only when πθ and π0 are close in distribution. Different policy gradient methods (Schulman et al., 2015a; 2017; Kakade, 2002) attempt 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 a 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 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 θ
E(st,at)∼π0 [ min ( clip(ρt, 1− , 1 + )Âπ0(st, at), ρtÂπ0(st, at) )] , (2)
where ρt : = πθ(at,st) π0(at,st) . We refer to ρt as likelihood-ratios. Due to a minimum with the unclipped surrogate reward, the PPO objective acts as a 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 = (Vθt − Vtarg)2, (3)
standard implementations fit the value network with a PPO-like objective: LV = max { (Vθt − Vtarg) 2 , ( clip ( Vθt , Vθt−1 − ε, Vθt−1 + ε ) − Vtarg )2} , , (4)
where 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 t, the agent creates a clone of the current policy πθt which interacts with the environment to collect rollouts B (i.e., state-action pairs {(si, ai)}Ni=1). Then the algorithm optimizes the policy πθ and value function Vθ for a fixed K gradient steps on the sampled data B. 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 − 1 steps, the sampling policy differs from the current agent, we refer to these updates as off-policy steps.
Throughout the paper, we consider a stripped-down variant of PPO (denoted PPO-NOCLIP) that consists of policy gradient with importance weighting (Eq. 1), but has been simplified as follows: i) no likelihood-ratio clipping, i.e., no objective function clipping; ii) value network optimized via regression to target values (Eq. 3) without value function clipping; and iii) no gradient clipping. Overall PPO-NOCLIP uses the objective summarized in App. A. One may argue that since PPONOCLIP removes the clipping heuristic from PPO, the unconstrained maximization of Eq. 1 may lead to excessively large policy updates. In App. I, we empirically justify the use of Eq. 1 by showing that with the small learning rate used in our experiments (tuned hyperparameters in Table 1), PPONOCLIP maintains a KL based trust-region like PPO throughout the training. We elaborate this in App. I.

heading: 2.1 FRAMEWORK FOR ESTIMATING HEAVY-TAILEDNESS
text: We now formalize our setup for studying the distribution of gradients. Throughout the paper, we use the following definition of the heavy-tailed property: Definition 1 (Resnick (2007)). A non-negative random variable w is called heavy-tailed if its tail probability Fw(t) : =P (w ≥ t) is asymptotically equivalent to t−α ∗ as t → ∞ for some positive number α∗. Here α∗ determines the heavy-tailedness and α∗ is called tail index of w.
For a heavy-tailed distribution with index α∗, its α-th moment exists only if α < α∗, i.e., E[wα] < ∞ iff α < α∗. A value of α∗ = 1.0 corresponds to a Cauchy distribution and α∗ = ∞ (i.e., all moments exist) corresponds to a Gaussian distribution. Intuitively, as α∗ 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 nonGaussianity of gradients (refer to App. B for details). (i) Alpha-index estimator which measures alpha-index for symmeteric α-stable distributions. This estimator is derived under the (strong) assumption that the stochastic Gradient Noise (GN) vectors are coordinate-wise independent and follow a symmetric alpha-stable distribution. (ii) Anderson-Darling test (Anderson & Darling, 1954) on random projections of GN to perform Gaussianity testing (Panigrahi et al., 2019). To our knowledge, the deep learning literature has only explored these two estimators for analyzing the heavytailed nature of gradients. (iii) Finally, in our work, we propose using Kurtosis. To quantify the heavy-tailedness relative to a normal distribution, we measure kurtosis (fourth standardized moment) of the gradient norms. Given samples {Xi}Ni=1, the kurtosis κ is given by:
κ = ∑N i=1(Xi − X̄)4/N(∑N i=1(Xi − X̄)2/N
)2 , where X̄ is the empirical mean of the samples. With a slight breach of notation, we use kurtosis to denote κ1/4. It is well known that for a Pareto distribution with shape α ≥ 4, the lower the tail-index (shape parameter α) the higher the kurtosis. For α < 4, since the fourth moment is 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.

heading: 3 HEAVY-TAILEDNESS IN POLICY-GRADIENTS: A CASE STUDY ON PPO
text: 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. D for details). As the training proceeds, the gradients clearly become more heavy-tailed (Fig. 1(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.
Alongside, we also perform ablations to understand how PPO heuristics affect the heavy-tailed nature of the gradient distribution. To decouple the behavior of naı̈ve policy gradients from PPO optimizations, we consider a variant of PPO which we call PPO-NOCLIP as described in Section 2. Recall that in a nutshell PPO-NOCLIP implements policy gradient with just importance sampling. In what follows, we perform a fine-grained analysis of PPO at on-policy iterations.

heading: 3.1 HEAVY-TAILEDNESS IN ON-POLICY TRAINING
text: Given the trend of increasing heavy-tailedness in on-policy gradients, we 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. 1). Note that during on-policy steps, since the likelihood-ratios are just 1, the gradient of actor network is given by ∇θ log (πθ(at, st)) Âπ0(st, at) and the gradient of the critic network is given by ∇θVθÂπ0(st, at) where π0 is the behavioral policy. To explain the rising heavy-tailed behavior, we separately plot the advantages Âπ0 and the advantage divided gradients ( i.e, ∇ log(πθ(at|st)) and ∇θVθ). Strikingly, we observe that while the advantage divided gradients are not heavy-tailed for both value and policy network, the heavy-tailedness in advantage estimates increases as 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 a slight increase in returns. However, remarkably, we notice a very similar course of an increase in heavytailedness with negative advantages (whereas positive advantages remained light-tailed) as training proceeds. In App. E.3, we also provide evidence to this observation by showing the trends of increasing heavy-tailed behavior with the histograms of log(|Aπθ |) grouped by their sign as training proceeds for one MuJoCo environment (HalfCheetah-v2). This observation highlights that, at 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-tailed behavior in the actor and critic gradients.
We also analyse the gradients of A2C (Mnih et al., 2016)—an on-policy RL algorithm—and observe similar trends (Fig. 1(a)), but at a relatively smaller degree of heavy-tailedness. Although they start
at a similar magnitude, the heavy-tailed nature escalates at a higher rate in PPO1. This observation may lead us to ask: What is the cause of heightened heavy-tailedness in PPO (when compared with A2C)? Next, we demonstrate that off-policy training can exacerbate the heavy-tailed behavior.

heading: 3.2 OFFPOLICYNESS ESCALTE HEAVYTAILNESS IN GRADIENTS
text: To analyze the gradients at off-policy steps, we 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 at each gradient step during off-policy training and analyze the collected gradients (see App. D for details). First, in the early stages of training, as the off-policyness increases, the heavy-tailedness in gradients (both actor and critic) increases. However, unlike with on-policy steps, actor gradients are the major contributing factor to the overall heavy-tailedness of the gradient distribution. In other words, the increase in heavy-tailedness for actor gradients due to off-policy training is substantially greater than for critic gradients (Fig. 2). Furthermore, this increase lessens in later stages of training as the agent approaches its maximum performance.
Now we turn our attention to explaining the possible causes for such a profound increase. The strong increase in heavy-tailedness of the actor gradients during off-policy training coincides with a increase of heavy-tailedness in the distribution of likelihood ratios ρ, given by πθ(at, st)/π0(at, st). The corresponding increase in heavy-tailedness in ratios can be explained theoretically. In continuous control RL tasks, the actor-network often implements the policy with a Gaussian distribution where the policy parameters estimate the mean and the (diagonal) covariance. With a simple example, we highlight the heavy-tailed behavior of such likelihood-ratios 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 1 (Wang et al., 2018). Assume π1(x) = N ( x; 0, σ21 ) and π2(x) = N ( x; 0, σ22 ) . Let ρ = π1(x)/π2(x) at a sample x ∼ π2. If σ1 ≤ σ2, then likelihood ratio ρ is bounded and its distribution is not heavy-tailed. However, when σ1 > σ2, then w has a heavy-tailed distribution with the tail-index (Definition 1) α∗ = σ21/(σ 2 1 − σ22).
1In Appendix E.2, we show a corresponding trend in the heavy-tailedness of advantage estimates.
During off-policy training, to understand the heavy-tailedness of actor gradients beyond the contributions from likelihood ratios, we inspect the actor gradients normalized by likelihood-ratios, i.e.,
∇θπθ(at, st)/π0(at, st) πθ(at, st)/π0(at, st) Âπ0(st, at) = ∇θ log (πθ(at, st)) Âπ0(st, at) . (5)
Note that the gradient expression in Eq. 5 is similar to on-policy actor gradients. Since we observe an increasing trend in heavy-tailedness of the actor gradients even during on-policy training, one might ask: does these gradients’ heavy-tailedness increase during off-policy gradient updates? Recall that in PPO, we fix the value function at the beginning of off-policy training and pre-compute advantage estimates that will later be used throughout the training. Since the advantages were the primary factor dictating the increase during on-policy training, ideally, we should not observe any increase in the heavy-tailed behavior. Confirming this hypothesis, we show that the heavy-tailedness in this quantity indeed stays constant during the off-policy training (Fig. 2), i.e.,∇θ log (πθ(at, st))Aπ0(st, at) doesn’t cause the increased heavy-tailed nature as long as π0 is fixed.
Our findings from off-policy analysis strongly suggest that when the behavioral policy is held fixed, heavy-tailedness in the importance ratios ρ is the fundamental cause. In addition, in Sec. 3.1, we showed that when importance-ratio’s are 1 (i.e., the data on which the gradient step is taken is on-policy) advantages induce heavy-tailedness. With these two observations, we conclude 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 dictating the heavy-tailed behavior, in App. J, we present two ablation experiments to test how heavytailedness in likelihood-ratios and advantage estimates individually contribute to the optimization issues in PPO leading to poor performance. Next, we illustrate how PPO clipping heuristics alleviate heavy-tailedness issues.

heading: 3.3 EXPLAINING ROLES OF VARIOUS PPO OBJECTIVE OPTIMIZATIONS
text: Motivated from our results from the previous sections, we now take a 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 a key observation. Note that the PPO-clipping heuristics don’t get triggered for the first gradient step taken (when a new batch of data is 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 of clipping heuristics, we perform the following analysis on the off-policy gradients of the PPO-NOCLIP: At each update step on the agent trained with PPO-NOCLIP, we compute the gradients with progressively including optimizations from the standard PPO objective.
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 ρt which lie outside (1− , 1 + ) 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 target estimate, the heuristics alleviate the slight heavytailed nature induced with off-policy training in the critic network.
While these PPO heuristics alleviate the heavy-tailedness induced with off-policy training, the effects of PPO clipping optimizations on mitigating heavy-tailedness induced during on-policy updates 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 believe that our findings can guide a development of fundamentally stable RL algorithms. In App. J.1, we present a preliminary result in this direction demonstrate how fixing heavy-tailedness in advantage estimates can improve an agent’s performance.

heading: 4 MITIGATING HEAVY-TAILEDNESS WITH ROBUST GRADIENT ESTIMATION
text: Motivated by our analysis showing that the gradients in PPO-NOCLIP exhibit heavy-tailedness that increases during off-policy training, we propose an alternate method of gradient aggregation—using the gradient estimation framework from Prasad et al. (2018)—that is better suited to the heavytailed 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, PPO-NOCLIP can achieve comparable results to state-of-the-art PPO implementations, even with the clipping heuristics turned off.
We now consider robustifying PPO-NOCLIP (policy gradient with importance sampling but without any trust-region enforcing steps or PPO clipping tricks). Informally, for gradient distributions which do not enjoy Gaussian-like concentration, the empirical-expectationbased estimates of the gradient do not necessarily point in the right descent direction, leading to bad solutions. To this end, we leverage a robust mean aggregation technique called Geometric Median-Of-Means (GMOM) due to Minsker et al. (2015). In short, we first split the samples into non-overlapping subsamples and estimate the sample mean of each.
Algorithm 1 BLOCK-GMOM input : Samples S = {x1, . . . , xn}, number of
blocks b, Model optimizer OG, b block optimizers OB , network fθ, loss ` 1: Partition S into b blocks B1, . . . Bb of equal size. 2: for i in 1 . . . b do 3: µ̂i = O(i)B (∑ xj∈Bi ∇θ`(fθ, xj)/ |Bi|
) 4: end for 5: µ̂GMOM = OG (WEISZFELD(µ̂1, . . . , µ̂b)).
output : Gradient estimate µ̂GMOM
The GMOM estimator is then given by the geometric median-of-means of the subsamples. Formally, let {x1, . . . , xn} ∈ R be n i.i.d. random variables sampled from a distribution D. Then the GMOM estimator for estimating the mean can be described as follows: Partition the n samples into b blocks B1, . . . , Bb, each of size bn/bc. Compute sample means in each block, i.e., {µ̂1, . . . , µb}, where µ̂i =∑ xj∈Bi xj/ |Bi|. Then the GMOM estimator µ̂GMOM is given by the geometric median of {µ̂1, . . . , µb} defined as follows: µ̂GMOM = argminµ ∑b i=1 ||µ− µ̂i||2. Algorithm 2 in Appendix C presents the algorithm formally along 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 a 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 a small number of samples with large norms would not affect a GMOM estimate as much as they would a 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:
Theorem 1 (Minsker et al. (2015)). Suppose we are given n samples {xi}ni=1 from a distribution with mean µ and covariance Σ. Assume δ > 0. Choose the number of blocks b = 1+b3.5 log(1/δ)c. Then, with probability at least 1− δ,
||µGMOM − µ||2 . √ trace(Σ) log(1/δ) n and ∣∣∣∣∣ ∣∣∣∣∣ 1n n∑ i=1 xi − µ ∣∣∣∣∣ ∣∣∣∣∣ 2 & √ trace(Σ) nδ .
When applying stochastic gradient descent or its variants in deep learning, one typically backpropagates the mean loss, avoiding computing per-sample gradients. However, computing GMOM requires per-sample gradients. To this end, we propose a 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 1, the number of blocks required to obtain the guarantee with high probability is independent of the sample size, i.e., we just need a constant (dependent on δ) number of blocks to compute GMOM. To achieve this, instead of calculating sample-wise gradients, 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 incorporating adaptive optimizers for individual blocks. Algorithm 1 presents the overall BLOCK-GMOM.

heading: 4.1 RESULTS ON MUJOCO ENVIRONMENT
text: We perform experiments on 8 MuJoCo (Todorov et al., 2012) continuous control tasks. To use BLOCK-GMOM aggregation with PPO-NOCLIP, we extract actor-network and critic-network gradients at each step and separately run the Algorithm 1 on both the networks. For our experiments, we use SGD as OB and Adam as OG and refer to this variant of PPO-NOCLIP as ROBUST-PPO-NOCLIP. We compare the performances of PPO, PPO-NOCLIP, and ROBUST-PPO-NOCLIP, using hyperparameters that are tuned individually for each method but held fixed across all tasks (Table 1). For 7 tasks, we observe significant improvements with ROBUST-PPO-NOCLIP over PPO-NOCLIP and performance 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 conjecture that PPO heuristics primarily aim to offset the heavy-tailedness induced with training.

heading: 5 RELATED WORK
text: Studying the behavior of SGD, Simsekli et al. (2019) questioned the Gaussianity of SGD noise, highlighting its heavy-tailed nature. Subsequently, there has been a growing interest in understanding the nature of SGD noise. More recently, other works (Şimş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-pretraining). Later work (Panigrahi et al., 2019) studied results through Gaussianity tests on random projections. They showed that at least early on in training, gradients remain near Gaussian for larger batch sizes. Some recent work has also made progress towards understanding the effectiveness of gradient clipping in convergence (Zhang et al., 2019b;a; Şimşekli et al., 2020). However, its consequences modulo the bias- vs variance trade-off are not completely understood.
On the RL side, a large-scale study of PPO was 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 a thorough study of the code-level heuristics used in trust region methods and indicate the
necessity of such heuristics in obtaining strong model performance. Chung et 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 with one view of heavy-tailedness in supervised learning where Simsekli et al. (2019) conjectured that heavy-tailedness in gradients can improve generalization.
However, we hypothesize that in deep RL where the optimization process is known to be brittle (Henderson et al., 2018; 2017; Engstrom et al., 2019; Ilyas et al., 2018), heavy-tailedness can cause heightened instability than help in efficient exploration. This perspective aligns with another line of work (Zhang et al., 2019b;a) where authors demonstrate that heavy-tailedness can cause instability in the learning process in deep models. Indeed with ablation experiments in Appendix J, we show that increasing heavy-tailedness in likelihood ratios hurt the agent’s performance, and mitigating heavytailedness in advantage estimates improves learning dynamics and hence the agent’s performance. Chung et al. (2020) further pointed out the importance of a 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.
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.

heading: 6 CONCLUSION
text: In this paper, we empirically characterized PPO’s gradients, demonstrating that they become more heavy-tailed as training proceeds. Our detailed analysis showed that at on-policy steps, the heavytailed 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 clipping heuristics, showing that they serve primarily to offset the heavy-tailedness induced by off-policy training. Thus motivated, we showed that a robust estimation technique could effectively replace all three of PPO’s clipping heuristics: likelihood-ratio 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 can significantly impact algorithm development for reinforcement learning.

heading: A DETAILED BACKGROUD
text: We define a Markov Decision Process (MDP) as a tuple (S,A, R, γ, P ), where S represent the set of environments states, A represent the set of agent actions, R : S ×A → R is the reward function, γ is the discount factor, and P : S ×A×S → R is the state transition probability distribution. The goal in reinforcement learning is to learn a policy πθ : S × A → [0, 1], parameterized by θ, such that the expected cumulative discounted reward (known as returns) is maximized. Formally,
π∗ = argmax π Eat∼π(·|st),st+1∼P (·|st,at) [ ∞∑ t=0 γtR(st, at) ] . (6)
Policy gradient methods directly optimize a paraterized policy function (also known as actor network). The central idea behind policy gradient methods is to perform stochastic gradient ascent on expected return (Eq. 6) to learn parameters θ. Under mild conditions (Sutton et al., 2000), the gradient of the Eq. 6 can be written as
∇θJ(θ) = Eτ∼πθ [ ∞∑ t=0 γtR(st, at)∇θ log(πθ(at|st)) ] ,
where τ ∼ πθ are trajectories sampled according to πθ(τ) and J(θ) is the objective maximised in Eq. 6. With the observation that action at only affects the reward from time t onwards, we re-write the objective J(θ), replacing returns using the Q-function, i.e., the expected discounted reward after taking an action a at state s and following πθ afterwards. Mathematically, Qπθ (s, a) = Eτ∼πθ [∑∞ k=0 γ kR(st+k, at+k)|at = a, st = s ] . Using the Q-function, we can write the gradient of the objective function as
∇θJ(θ) = Eτ∼πθ [ ∞∑ t=0 Qπθ (st, at)∇θ log(πθ(at|st)) ] .
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, a baseline is subtracted from the Q-function—often the value function or expected cumulative discounted reward starting at a certain state and following a given policy i.e., Vπθ (s) = Eτ∼πθ [∑∞ k=0 γ kR(st+k, at+k)|st = s ] . The network that estimates the value function is often referred to as critic. Define Aπθ (st, at) = Qπθ (st, at)− Vπθ (st) as the advantage of performing action at at state st. Incorporating an advantage function, the gradient of the objective function can be written:
∇θJ(θ) = Eτ∼πθ [ ∞∑ t=0 Aπθ (st, at)∇θ log(πθ(at|st)) ] . (7)
Eq. 7 is the näive actor-critic objective and is used by A2C.
Trust region methods and PPO. Since directly optimizing the cumulative rewards can be challenging, 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 a behavior policy π0 while optimizing policy πθ, such as the surrogate reward used by Schulman et al. (2015a):
max θ E(st,at)∼π0
[ πθ(at, st)
π0(at, st) Âπ0(st, at)
] , (8)
where Âπ = Aπ−µ(Aπ) σ(Aπ)
(we refer to this as the normalized advantages). However, the surrogate is indicative of the true reward function only when πθ and π0 are close in distribution. Different policy gradient methods (Schulman et al., 2015a; 2017; Kakade, 2002) attempt 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 a 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 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 θ
E(st,at)∼π0 [ min ( clip(ρt, 1− , 1 + )Âπ0(st, at), ρtÂπ0(st, at) )] , (9)
where ρt : = πθ(at,st) π0(at,st) . We refer to ρt as likelihood-ratios. Due to a minimum with the unclipped surrogate reward, the PPO objective acts as a 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 = (Vθt − Vtarg)2, (10)
standard implementations fit the value network with a PPO-like objective: LV = max [ (Vθt − Vtarg) 2 , ( clip ( Vθt , Vθt−1 − ε, Vθt−1 + ε ) − Vtarg )2] , (11)
where is the same value used to clip probability raitos in PPO’s loss function (Eq. ??). PPO uses the following training procedure: At any iteration t, the agent creates a clone of the current policy πθt which interacts with the environment to collects rollouts S (i.e., state-action pair {(si, ai)}Ni=1). Then the algorithm optimizes the policy πθ and value function for a 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 − 1 steps, the sampling policy differs from the current agent, we refer to these updates as off-policy steps.
Throughout the paper, we consider a stripped-down variant of PPO (denoted PPO-NOCLIP) that consists of policy gradient with importance weighting (Eq. 8), but has been simplified as follows: i) no likelihood-ratio clipping, i.e., no objective function clipping; ii) value network optimized via regression to target values (Eq. 10) without value function clipping; and iii) no gradient clipping. Overall PPO-NOCLIP uses the following objective:
max θ E(st,at)∼π0
[ πθ(at, st)
π0(at, st) Âπ0(st, at)− c(Vθt − Vtarg)2
] .
where c is a coefficient of the value function loss (tune as a hyperparameter). Moreover, no 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. 1 may lead to excessively large policy updates. In App. I, we empirically justify the use of Eq. 1 by showing that with the small learning rate used in our experiments (optimal hyperparameters in Table 1), PPO-NOCLIP maintains a KL based trust-region like PPO throughout the training. We elaborate this in App. I.

heading: B DETAILS ON ESTIMATORS
text: We now formalize our setup for studying the distribution of gradients. Throughout the paper, we use 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 Fw(t) : =P (w ≥ t) is asymptotically equivalent to t−α ∗ as t → ∞ for some positive number α∗. Here α∗ determines the heavy-tailedness and α∗ is called tail index of w.
For a heavy-tailed distribution with index α∗, its α-th moment exist only if α < α∗, i.e., E[wα] <∞ iff α < α∗. A value of α∗ = 1.0 corresponds to a Cauchy distribution and α∗ =∞ (i.e., all moments exist) corresponds to a Gaussian distribution. Intuitively, as α∗ 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 nonGaussianity of gradients.
102 103 104 105
Num samples
2
4
6
8
10
12
ku rto
sis ^{
1/ 4}
pareto(alpha=2) normal
(a)
100 101
Shape of Pareto
2
3
4
5
ku rto
sis ^{
1/ 4}
pareto normal
(b)
B.1 SYNTHETIC STUDY
In Figure 5, we show the trends with varying tail index and sample sizes. Clearly as the tail-index increases, i.e., the shape parameter increases, the kurtosis decreases (signifying its correlation to capture tail-index). Although for tail-index smaller than 4 the kurtosis is not defined, we plot empirical kurtosis and show its increasing trend sample size. We fix the tail index of Pareto at 2 and plot
finite sample kurtosis and observe that it increases almost exponentially with the sample size. These two observations together hint that kurtosis is a neat surrogate measure for heavy-tailedness.

heading: C GMOM ALGORITHM
text: Algorithm 2 GMOM input : Samples S = {x1, . . . , xn}, number of
blocks b 1: m = bn/bc. 2: for i in 1 . . . b do 3: µ̂i = ∑m j=0 xj+i∗m/ m. 4: end for 5: µ̂GMOM = WEISZFELD(µ̂1, . . . , µ̂b).
output : Estimate µ̂GMOM
Algorithm 3 WEISZFELD input : Samples S = {µ1, . . . , µb}, number of
blocks b 1: Initialize µ arbitrarily. 2: for iteration← 1, . . . , n do 3: dj : =
1 ||µ−µj ||2 for j in 1, . . . , b. 4: µ : = (∑b
j=1 µjdj
) / (∑b
j=1 dj ) 5: end for
output : Estimate µ

heading: D EXPERIMENTAL SETUP FOR GRADIENT DISTRIBUTION STUDY
text: Recall that PPO uses the following training procedure: At any iteration t, the agent creates a clone of the current policy πθt which interacts with the environment to collects rollouts S (i.e., state-action pair {(si, ai)}Ni=1). Then the algorithm optimizes the policy πθ and value function for a 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 remainingK−1 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 all runs. We 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 individual 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 sampled data), we freeze the policy and value network, and save the sample-wise gradients of the actor and critic objective. The estimators are calculated at 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 a fixed batch of data when the sampling policy differs from the policy being optimized), we 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.e., initialization, 50% max reward and max reward (which corresponds to 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, at 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-policy steps.
Analysis of PPO-NOCLIP with progressively applying PPO heuristics. We compute the gradients for the off-policy steps taken with the PPO-NOCLIP objective as explained above. Then at each gradient step, we progressively add heuristics from PPO and re-compute the gradients for analysis. Note that we still always update the value and policy network with PPO-NOCLIP objective gradients.

heading: E TRENDS WITH ADVANTAGES
text: E.1 KURTOSIS FOR RETURNS, VALUE ESTIMATE AND ADVANTAGES GROUPED WITH SIGN
E.2 HEAVY-TAILEDNESS IN A2C AND PPO IN ONPOLICY ITERATIONS
E.3 HISTOGRAMS OF ADVANTAGES ON HALFCHEETAH OVER TRAINING ITERATIONS

heading: F ANALYSIS WITH OTHER ESTIMATORS
text: F.1 ON-POLICY GRADIENT ANALYSIS
F.2 OFF-POLICY GRADIENT ANALYSIS

heading: G HYPERPARAMETER SETTINGS AND REWARDS CURVES ON INDIVIDUAL ENVIORNMENTS

heading: H ANALYSIS ON INDIVIDUAL ENVIORNMENTS.
text: 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.

heading: I MEAN KL DIVERGENCE BETWEEN CURRENT AND PREVIOUS POLICY
text: 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 Engstrom et al. (2019), we perform an additional experiment to understand how this algorithmic property varies with PPO and our variant PPO-NOCLIP with optimal hyperparameters. In Fig 16, we measure mean KL divergence between successive policies of the agent while training with PPO
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-NOCLIP.
Engstrom et al. (2019) 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. Corroborating their findings, we indeed observe that with optimal parameters (namely small learning rate used in our experiments), PPO-NOCLIP indeed manages to maintain a trust region with mean KL metric (Fig 16) on all 8 MuJoCo environments. This highlights that instead of the core algorithmic objective used for training, the size of the step taken determines the underlying objective landscape, and its constraints. On a related note, Ilyas et al. (2018) also highlighted that the objective landscape of PPO algorithm in the typical sample-regime in which they operate can be very different from the true reward landscape.

heading: J HOW HEAVY-TAILEDNESS AFFECT TRAINING?
text: To understand the effects of heavy-tailedness, we perform two ablation experiments: First, we study the effects of heavy-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-tailedness induced in the likelihood ratios during off-policy training. We vary the number of off-policy gradient steps (a hyperparameter otherwise fixed to 10) taken by an agent trained with PPO-NOCLIP2 and show that the additional off-policy learning exacerbates heavy-tailedness 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 mechanisms ameliorate the observed heavy-tailedness to some extent, the heuristics majorly offset the
2We tried using PPO loss for this experiment. However, while training with PPO, the successive policies diverge in mean KL metric when we increase the number of offline epochs used for training.
heavy-tailedness induced during off-policy gradient steps and doesn’t seem to handle the induced heavy-tailedness in advantages. Motivated by this connection, we aim to study the effects of clipping advantages to understand its impact on the agent’s behavior. In particular, we clip negative advantages which are the primary contributors to the induced heavy-tailedness.
Depending on the individual environment and the observed heavy-tailedness, we tune an environment dependent clipping threshold for advantages to maximize the performance of the agent trained with PPO. Intuitively, we expect that clipping should improve optimization and hence should lead to improved agents’ performance. Corroborating the intuition, we observe significant improvements (Figure 17). Moreover, to understand the nature of clipped advantages, we plot the trend of heavy-tailedness in advantage estimates during training. Confirming our hypothesis, as we clip negative advantages below the obtained threshold, we observe that the induced heavytailedness stays constant throughout training (Figure 18).
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 a 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 advantages 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 heavy-tailedness in advantages which is not handled by PPO.
J.2 EFFECT OF HEAVY-TAILEDNESS IN LIKELIHOOD-RATIOS
Recall, in Section 3.2, 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 a corresponding increase in the heavy-tailedness of likelihood ratios. Motivated by this connection, we train agents with increased off-policy gradient steps to understand the effect of the likelihood-ratios induced heavy-tailedness on the performance of the agent. With PPO-NOCLIP, we train agents for 20 and 30 offline epochs (instead of 10 in Table 1) 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)3.
First, as expected, we observe an increase in heavy-tailedness in the likelihood ratios with escalated offline training (Figure 20). Moreover, the heavy-tailedness in advantages remains unaffected with an increase in the number of offline epochs (Figure 19) confirming that the observed behavior is primarily due to heightened heavy-tailedness in likelihood ratios. We hypothesize that induced heavytailedness can make the optimization process harder. Corroborating this hypothesis, we 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).
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 efficient 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.
3Beyond 30 offline steps, successive policies often diverge—failing to maintain a KL based trust region.

Review summaries:
This 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.

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.