Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: **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. 

I 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?

In 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.

Also 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? 

Finally, 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?

I 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. 
review_title: Interesting analysis but needs more work

final_score: rating: 5: Marginally below acceptance threshold
review_content: ### Strengths

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.

### Weaknesses

The 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.  

### Comments

* 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.

* 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}$.

* "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?

* 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?

* 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?

* Nit/typo: The notation for the GMOM description in the text is missing the \hat for $\mu_b$.




review_title: A interesting empirical analysis of some RL gradient statistics, but unclear takeaways

final_score: rating: 7: Good paper, accept
review_content: **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. 
 
**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.

**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.

**Major Comments:**

While 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.

As 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.

**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. 


**Minor Comments:**

- 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.
- It would be useful to write the exact equation / objective used for `PPO-NoClip` in the main paper
- 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)?
- 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).
- 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.
- 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.
- In the Preliminaries, the policy in general doesn't map to [0,1] but in the continuous setting, more generally to $\mathbb{R}_+$.

[1] Schulman et al. Trust Region Policy Optimization, ICML 2015

[2] Chung et al. Beyond variance reduction: Understanding the true impact of baselines on policy optimization. 2020. ArXiv
review_title: Interesting empirical analysis

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: **Positives**

The claims of the paper are clear and the evidence to support the claims is clearly presented. 

The 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.

The 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.

I 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. 

**Negatives**

The 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+).

The work needs some further discussion on why Robust-PPO-NoClip only seemed to beat PPO-NoClip in some environments, but not others.

**Summary**

I'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. 

**Things which didn't affect my decision**

1. Uniform axes for fig 7 would be helpful, to permit comparison of plots


** Edit after author response **
The authors have addressed the concerns I had so I've increased the score accordingly. 
review_title: Important advance into understanding of PPO, with some caveats about statistical significance 

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