Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper discusses the effect of baselines in stochastic policy gradient optimization, i.e., the subtracted term in the advantage function. Previous approaches have demonstrated that by subtracting a state value baseline would stabilize the learning of RL empirically, however, few researches focus on explaining this theoretically. Considering natural policy gradient (NPS), the paper demonstrated that using a state value baseline can prevent the probability of the optimal action from vanishing almost for sure, and the NPG can converge to a globally optimal policy at rate of O(1/t). The paper further discusses more on the variance reduction effect of using baselines for stochastic gradients. Results show that the PG estimator is unbounded neither with nor without a baseline, and the key effect of baseline is ensuring convergence and reduce the aggressiveness of updates. Some simulation results in simple one-state MDP toy example are provided to support the proposed theories.
strengths_and_weaknesses: Pros:
The proposed discussion and analyses indeed provide me new insights for the effect of baselines in stochastic PG. I think the used techniques in analyzing the global optimality convergence for stochastic PG is informative for future research. Moreover, the relationship between using value baselines and variance reduction is discussed and the results tell that there might not exist directly.


Cons:
The experimental results are far insufficient and general MDPs are not studied for Algorithm 1, which, I think, is the most critical part for RL applications. The only concern I have is the practical performance that whether on-policy stochastic NPG matches the theoretical convergence results.

questions: Are there any connections between the theories in this paper and existing variance reducation baselines, e.g., the input-dependent baseline [1]? Could the used techniques to applied to explain such baselines in the effect of variance reduction and global convergence?

[1] Mao H, Venkatakrishnan S B, Schwarzkopf M, et al. Variance reduction for reinforcement learning in input-driven environments[J]. arXiv preprint arXiv:1807.02264, 2018.

limitations: Insufficient empirical studies of stochastic NPG with baseline.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work studies the role of baselines in natural policy gradients (NPG). Earlier it has been argued that baselines are effective for reducing variance of the updates. They first study the one-state MDP. They argue theoretically that NPG updates without baseline might converge to sub-optimal action and it is not so with the baseline. More importantly they provide results on a.s. global convergence rates for the baseline case. They then extend these results to general MDP. They argue that the variance maybe unbounded in the NPG with baseline case and therefore it is unfair to draw conclusions from a variance reduction perspective alone. The explain the vicious and virtuous cycle of update aggressiveness. Finally, they provide experiments in a simplified setting to evaluate their theoretical results.
strengths_and_weaknesses: **Strengths**:
1. The paper is very well written and goes through various concepts very carefully despite it being dealing with topics that are very complicated.
2. The new perspective on update aggressiveness is both intuitive and technically sound from what I understand. The clear dichotomy between the "vicious circle" and "virtuous circle" of updates is deeply insightful and very well presented!
3. Their experiment on convergence rate illustrates the practical outcome of Theorem 1 very clearly.

**Weaknesses**:
1. My primary concern is that the authors have not very well positioned their work in light of past work, to the best of my knowledge. This hinders my understanding of how exactly their analysis is novel and stands apart from previous work. For example, Lemma 2 by Bhatnagar et al [1] is a well known result on how the value function is the minimum variance baseline (to the best of my knowledge) which is also for the more general linear setting. How is this different from your results or how is the setting different? My best guess is that lines 237-239 hint at this but I am unsure how this works in light of previous results. Also, the difference is that your work considers on-policy NPG? Also please see other citations [2,3].

2. My second concern is the lack of explanation of the constants in the convergence rate results. The constants $C$ in Theorems 1 and 2 are not explained. Are they the same or similar? I see that the constant does not depend on $t$ but as a reader I would like to know what this constant does depend on? What properties of the MDP effect these constants? Therefore, in my opinion, a corresponding empirical study of how this convergence rate changes with the MDP would also be warranted for a complete understanding of the theoretical results in addition to the explanations.

**Overall**: I am currently reluctant to reject the paper and would recommend an accept if my concerns above and below are addressed. This is primarily because the results formalise "committal behavior" and open up avenues for future research which could impact the practice of RL.

[1] Natural actor-critic algorithms, Shalabh Bhatnagar and Richard S. Sutton and Mohammad Ghavamzadeh and Mark Lee, 2009

[2] Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning, Evan Greensmith and Peter L. Bartlett and Jonathan Baxter, 2004

[3] Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines, Cathy Wu and Aravind Rajeswaran and Yan Duan and Vikash Kumar and Alexandre M. Bayen and Sham M. Kakade and Igor Mordatch and P. Abbeel, 2018
questions: **Questions and suggestions for the authors**:
1. I think "the variance is unbounded" and therefore "Baselines Do Not Control Update Variance" is a leap I am still not convinced of after reading the main body of the paper. I was wondering if the authors could comment on how the two values of interest in Proposition 3 ($\frac{r(a)^2}{\pi_{\theta}(a)}$ and $\frac{(r(a) - \pi_{\theta_t}^Tr)^2}{\pi_{\theta}(a)}$) evolve through time $t$ (and not only the convergence)? Please point me to the result if it already dealt with in the paper or previous work. This might give us an idea of how baselines effect the variance through time.

2.  In the abstract you claim that for the NPG setting "finite variance is not necessary" (line 15)  and in Section 3.1 you claim "there exists at least one action such that $\frac{r(a)^2}{\pi_{\theta}(a)}$ and $\frac{(r(a) - \pi_{\theta_t}^Tr)^2}{\pi_{\theta}(a)}$ become unbounded" (line 244). Can you please explain in what case the variance is finite? My reading is that this necessitates variance being unbounded. 

3. I am curious why the optima is stuck in a plateau in Fig 2(a)? Kakade [4] had asserted that NPG overcomes the plateau phenomena, in principle, effectively. I hope the authors can comment on this.

4. Can you present empirical results for a more general MDP case as well? That would make the argument stronger although I wouldn't reject the paper for this reason since the results for single state example serve as a good example.

5. Some additional background on NPG in section 2 and how it differs from vanilla PG would be helpful for the reader. Update 2 being NPG and where it comes from might not be apparent to most readers in the community.

6. How is committal behavior different from the standard exploration exploitation problem? I am curious if some of the effects of the baseline are similar to that of adding noise (or policy gradient version of $\epsilon$-greedy exploration) to the policy? 

Minor: Title mismatch between the submission and paper.

[4] A Natural Policy Gradient, Sham M. Kakade, NIPS.
limitations: Apart from the limitations mentioned above I don't see any limitations in terms of addressing the ethical guidelines.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: *The Role of Baselines in Policy Gradient Optimization* is a submission that studies the impact of substracting baselines in the natural policy gradient updates. While in expectation (or with exact gradients), both updates are equivalent, the authors show that their stochastic updates behave differently, in particular with respect to the aggressivity of convergence.
strengths_and_weaknesses: This is a well rounded study on a phenomenon that has not been investigated before. While I think that the paper deserves to be published, I am bothered by several points (this explains my low recommendation):
* The claims made in the abstract and the introduction are too strong: the convergence to global optimality relies on Assumption 2 in MDPs in order to ensure exploration of all states. This is true even with exact gradients, when the updates are online PG [Laroche2021].
* Aggressiveness of updates is not a well defined concept and the reader has not a good grasp of what the authors mean before Section 3. I would rather call it speed of convergence that prevent a proper exploration of actions (exploration of states being handled by Assumption 2).
* Update 2 relies on the knowledge of $r$? Same for the learning rate? How is it a practical algorithm? 
* I don't like the learning rate to be dependent on $\theta_t$. I don't feel that the update should be called NPG anymore. (this was already something that bothered me in the escort paper [Mei2020]) Could you justify your choice to keep calling it NPG?
* Lemma 1 would hold with $\eta$ being defined lesser than the right hand side of eq (4), wouldn't it?
* Converging faster than $O(1/t)$ in a stochastic setting is not possible, otherwise MAB could be solved with regret in $O(1)$. The authors spend more than 1 page and 4 lemmas on it. Could you please help me understand better why your arguments in 3.2-3.5 are necessary?
* I find it very surprising that introducing a baseline (basically IS on the advantage rather than the value) allows to obtain this dampening of the convergence as the authors claim. Isn't it rather granted by the adaptive learning rate? Wouldn't the same result be obtainable without baseline? (I don't really buy the explanation in Section 3.5)
questions: Please address my questions in the previous section.
limitations: No potential negative societal impact.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors consider the well-known policy gradient algorithm (PG) of reinforcement learning
and study the effect of the baselines, which is frequently used in practice with PG to improve the sample efficiency and the stability.
To this end, the authors study the asymptotic behavior of the exemplary algorithm, namely
the softmax policy + on-policy importance sampling + the natural policy gradient (NPG), with and without the baseline.
As a result, it is shown that NPG + baseline is sufficient to achieve the convergence to global optimum, which is not possible with the NPG only.
Moreover, the authors show that the convergence rate achieved with the baseline is O(1/t) in expectation, which is not improvable without compromising the global convergence property.
They also give intuitive explanation why baselines lead to global convergence while pointing out a flaw of the conventional explanation via variance reduction.
Finally, these theoretical results (the global convergence and the convergence rate) are confirmed with numerical simulations.

strengths_and_weaknesses: The strength of this work is that it gives one clear explanation on the effectiveness of the commonly-used baseline technique and thus promotes our understanding of reinforcement learning.
However, there are some concerns with the clarity of the technical details and the presentation style:

- In the stochastic NL inequalities, a variable learning rate (eq. 4) is used and its dependency on $\pi\_{\theta\_t}(a\_t)$ seems important there to reduce agressiveness of the updates. How can it be adopted by the fixed-learning-rate regime of Update 2?
- In Theorem 1 and 2, there seems no assumption on the learning rate $\eta$, but at least it should satisfy $\eta>0$. Is that all?
- With regard to Remark 1, it reads for me that Theorem 1 and 2 are only valid with the noiseless bandit feedback model. Is it true? If so, it should be clarified in the statement of the theorems.
- The problematic agressiveness of Update 1 seems to be largely attributed to the computation of the natural gradient rather than the absence of baseline. Could you discuss the benefits of baseline compared to just computing the naive softmax policy gradient?
- What exactly is your assumption on the distribution of $\hat{Q}$ in Algorithm 1? How can we estimate the Q function to satisfy it?
- The explanation with Section 3 focuses too much on narrative intuitions and seems to be disconnected with the theoretical results presented in Section 2. Organizing these explanations in a form of more structured proof sketch would be very helpful to make the paper more coherent as a whole. Specifically, how are those lemmas in Section 3 connected with the proof of Theorem 1 and 2?

questions: Please address the above questions.
limitations: I think some aspects of the limitation are further addressed by answering the above questions.
review_title: null

Meta-review: metareview: The paper studies the effect of subtracting baselines in natural policy gradient methods for reinforcement learning. The authors offer a new perspective on update aggressiveness that is both intuitive and technically sound. All the reviewers appreciated the exposition around "vicious circle" and "virtuous circle" of updates, and how this is different from variance reduction. There were concerns that the empirical evaluations are limited, but the authors pointed to experiments in depth-4 tree MDPs to provide additional evidence.

There were several clarifying questions from the reviews that the authors addressed comprehensively during the feedback phase. Please include these clarifications in a paper revision to strengthen the current exposition.
confidence: Less certain
Decision: Accept