Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the convergence of various policy gradient methods. The authors introduce a novel conception, the committal rate, to characterize the convergence speed and convergence quality of policy gradient methods, which is defined as the speed of the policy on a particular action converges to 1. For a simple MDP with 1 state, the authors show that the committal rate can explain the phenomenon that faster convergent algorithms using true policy gradients can be dominated by slower ones in the stochastic setting.   

main_review: In general, the paper is well written and easy to understand. The insight on the committal rate is also novel and very helpful for researchers to understand the connections and differences among different policy gradient methods. One drawback is the paper did not provide the discussion on the generalization to more common MDPs with more than one state. Another point that could be potentially more interesting as stated in the conclusion part is to identify the sufficient conditions and necessary conditions for such type of methods to converge using the committal rate theory. 

Why do we need the importance sampling estimator since the action is chosen from the same policy we want to evaluate?

In Definition 2, is it correct that you need to specify that kappa (or equivalently alpha) is a constant that does not depend on t? Otherwise, it is easy to construct counter examples by setting $\kappa(A,a)$ to be a function of t, where the examples presented in Line 233-236 are not true. Moreover, in Line 235, it should be “if $1-\pi_{\theta_t}(a) \in O(1)$, then $\kappa(A,a)=0$”, since $\pi_{\theta_t}(a)$ itself can be O(1), just like in the previous two examples you mentioned. 

In the proof of Theorem 5, at the last line, how do you guarantee that $\pi_{\theta_t}(a)>0$ for all t? Does this mean the general algorithm A here should not have any truncation procedures? 

Theorem 6 claims that $\kappa(A,a)=\infty$ for all actions. By the definition of kappa, does this mean $\pi_{\theta_t}(a)$ converges to 1 for all actions? However, this obviously seems wrong.

Typos:
Line 60: “the a variant ...”
Line 129: “can *be* lower bounded”

limitations_and_societal_impact: One drawback is the lack of discussion of how the proofs of Section 3 can be generalized to more common MDPs, which have more than 1 state. It is unclear whether the conclusions made in Section 3 about the committal rates of PG and NPG hold in more general cases. 

I do not see any potential negative societal impact directly related to this work
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper aims to answer a fundamental question: what is the key factor that ensures the convergence of stochastic policy gradient (PG) methods? This question is built on the fact that bounded variance appears to be only a sufficient condition for convergence of the PG methods. To begin with, the paper starts by summarizing the existing convergence results of three PG methods, namely Softmax PG, Natural PG (NPG), and Geometry-aware Normalized PG (GNPG), in both the exact and stochastic gradient settings. Then, the paper proposes the notion of “committal rate” as an indicator for characterizing the convergence behavior of the PG methods. Accordingly, for one-state MDPs, the authors show that $\kappa\leq 1$ for all sub-optimal actions serves as a necessary condition for ensuring convergence as well as provide the committal rates of the three PG methods.

main_review: The problem studied in this paper is important and interesting, but I find the overall contribution of this paper quite limited due to the following issues with the theoretical results and presentation:

- The theoretical results are not strong: Most of the main theoretical contributions are established only for one-state MDPs (Theorems 5-8 and 10). While it is okay to present the results in the main text using one-state MDPs for didactic purposes, these results are quite limited as the PG methods are typically used in the context of general MDPs. It remains unknown whether the results of the committal rate and their proof techniques can be extended to the case of general MDPs. On the other hand, the convergence results of Theorems 2-4 are mostly adapted from [12] (with some direct extensions).

- The definition of committal rate in (6) seems problematic: Since $\kappa$ involves $\pi_{\theta_t}(a)$ which is itself a random quantity and could vary with the sample path, then $\kappa$ shall also depend on the underlying sample path. However, throughout the paper, $\kappa$ is viewed as a deterministic value that depends only on the arm and the update scheme. Moreover, in Line 228, it is stated that “Let $t$ denote the number of times action $a$ is sampled after initialization.” This appears inconsistent with the notation of $\pi_{\theta_t}$, where $t$ is the total number of samples. Could the authors comment on this?

- While the committal rate might provide some high-level intuition, it is unclear whether it offers any new insight into the characterization of the convergence behavior. Based on the definition in (6), the committal rate seems a bit tautological when being used to state “convergence to a sub-optimal policy”.

- Regarding the presentation, I find Sections 4.2 and 4.3 not very informative. For example, Theorem 9 follows directly from the definition of the committal rate. Similarly, Theorem 10 also appears quite straightforward and provides very little new insight. As a result, this part can be greatly simplified for clarity.

- In Section 2, it is mentioned that “The main results below extend to general finite MDPs, but for clarity of exposition we move details for general cases to the appendix.” This is a bit misleading as that a large portion of the theoretical results (cf. Theorems 5-8) are established only for one-state MDPs.

- In Section 4.1, two examples are provided to show that $\kappa$ does not serve as a necessary condition, but the examples are a bit artificial. Built on this, another interesting question is: Under which (non-trivial) class of algorithms does $\kappa$ offer a necessary and sufficient condition for convergence? 

Other minor comments:
- Line 178: Theorem 2 is adapted from [12]. It would be good to clearly mention this in the main text.
- Line 813: It would be nice to directly provide the proof of Lemma 8 here for completeness. 

----- Post-rebuttal updates -----

I’d like to thank the authors for the response. I have raised my score because the authors addressed my main concerns by:

- Clarifying the definition of the committal rate for one-state MDPs

- Clarifying the main results (i.e., Theorems 5, 9, and 10)

- Extending the main result (i.e., Theorems 5) from one-state MDPs to general MDPs

limitations_and_societal_impact: In the checklist, this paper mentions that it has described the limitations, but I did not see this part mentioned in any section.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: Summary

The authors show how the convergence rates of stochastic policy gradient algorithms can differ from the full-information/expected case. Even before diving into the stochastic case they prove a linear convergence rate for NPG in the expected setting. Then for the stochastic setting they show convergence of vanilla PG with probability 1. For NPG (and GNPG) they show that there is a strictly positive probability of converging to a suboptimal solution. To do so they introduce the notion of committal rate, a useful tool, not without some limitations that they discuss.
More generally they explicit the tradeoff between geometry and noise for RL which is a very important topic.
Finally they propose a method using ensembles to show how we can still find the optimal policy for committal algoritms in high probabablity.



main_review: Clarity
---
I found the paper clear and well written.

Significance
---
I think this is a very important topic as we are seeing more and more convergence results in RL theory, mostly limited to
the expected case. This paper stresses how the stochastic case can be fundamentally different, and how convergence of the expectation does not translate to convergence in probability.

Main review
---

Here are some thoughts and questions I would like the authors to discuss.

1) I think I am missing something about the proof of Thm 7. You show in the appendix that kappa = 1 by showing it is both bigger and smaller than 1. 
Thm5 only informs you that if kappa > 1, then probability of sampling any suboptimal action an infinity of times is > 0.
(i) Where is the proof that this is 0 for the case kappa = 1?
(ii) And once this is proven, how do you get to the result that the optimal action will be taken an
infinite number of times? 

2) Do you think the 1/t lower bound, was, in some way very unsurprising? For instance, we know that for bandit the regret is Omega(log(t)).
Let us assume that V* - V_t = o(1/t) (small o notation), then we would have by
summation that regret = o(log t) which contradicts the lower bound on regret,
hence V* - V_t = Omega(1/t).
This is a pretty handwavy proof (for bandits), but I suspect it might easy to
formalize and extend to MDPs (as you ust need to extract a bandit problem from
the MDP to show the impossibility).

Under that light, could you then discuss the link between your lower bound result and the one on
regret in bandits?

3) In RL, contrary to supervised learning, the data distribution changes after each action taken, and this introduces new dependencies.
The variance of the parameter theta_t, will be composed of the variance of the gradients, but also of the different covariances between the gradients. 
Intuitively, the results of Chung and Thomas et al. even if not formalized that way, could be understood that choosing some baselines can guarantee convergence by ensuring this variance/spread is small (negative correlations) while some other baselines (including potentially the one that minimizes the variance of the gradient) cannot. 
I don't think committal rates in their current form can capture this accurately, this difference, do you have any idea how it could be extended to capture these effects?

4) Could you clarify the following point: In the setting where we have a 2-arm bandit with deterministic rewards -1 and 1, then natural policy gradient will be guaranteed to increase the probability of the right action at each time step, and the convergence will be exponential. Therefore are your results about the O(1/t) rate for all MDPs?

I will change my score accordingly depending on how these questions are answered.

limitations_and_societal_impact: Theoretical work, no societal impact to foresee.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studied how stochasticity of on-policy evaluation affects the convergence speed of various policy optimization methods. The paper demonstrated an inherent trade-off between fast convergence versus achieving optimality almost surely.
main_review: This paper studied how stochasticity of on-policy evaluation affects the convergence speed of various policy optimization methods and demonstrated an inherent trade-off between fast convergence versus achieving optimality almost surely.

In particular, the authors proposed "committal rate" to characterize how fast the probability $\pi(a|s)$ converges to 1 under some algorithm. When a sub-optimal state action pair has a committal rate greater than 1, the sub-optimal may be sampled forever and hence leads to sub-optimality. On the other hand, the convergence speed to the optimal policy is also characterized by the committal rate of the best state-action pairs. Therefore, any algorithm that fails to give highest committal rate to best actions must face the trade-off between fast convergence versus achieving optimality almost surely.

However, the reviewer has some doubts when verifying some Theorems and the proofs:
1. Theorem 3 says "there is a positive probability that $\pi_{\theta_t}(a) \to 1$, $\forall a\in [K]$". Does it mean to say "$\forall a\in [K]$, there is a positive probability that $\pi_{\theta_t}(a) \to 1$"?

2. At the first glance, the proof of Theorem 3 seems to be saying "When $a$ is always sampled, then with a positive probability $a$ is always sampled". Reorganizing the proofs would fix the issue.

3. The lower bound of the probability of "$a$ is always sampled" (173) is roughly at the order $O(\exp(-|A|/\eta))$. Is it reasonable to say that the event is negligible when $|A|$ is large or $\eta$ is small? If so, the discussion in section 5.1 can be misleading, since the "positive probability" can be fairly small.

Typos:
Line 60, "the a";
limitations_and_societal_impact: See main review.
review_title: null

Meta-review: The paper studies the effect of stochastic on policy optimization in Reinforcement Learning, i.e., the impact of not having the true gradient. The paper argues that there are significant differences between the case of true gradient and a stochastic version. While this is not surprising, the reviewers agree that the paper makes a good contribution to the literature by pointing out the differences. There was some concern that many of the results are for a one-state MDP, but the reviewers felt that the paper makes some interesting points which can  potentially stimulate further work.  
Decision: Accept (Poster)