Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper studies policy gradient where the policy is parameterized by an extremely wide neural network. The authors assume that the number of nodes ($m$) in the network is extremely large ($T^{8}R^{18}$, $T$ is the total runtime and $R$ is the radius of the function class that the network falls into), and they restrict their convergence analysis of the policy gradient algorithm in a particular function class and claims that the approximation error between the true network and the function class goes to zero when $m$ is large. The paper is written in a rigorous way and the presentation is mostly clear. I have some concerns about many of the assumptions made across the paper that are not explained or verified. This may potentially further decrease the usefulness of the analysis in this paper though the theoretical result with $m=T^8$ is already very impractical. Another major issue with this paper is that the theoretical analysis is not novel in terms of bringing new insights and results to the field given many other papers including global convergence of policy gradient (Agarwal et al., 2019;), convergence of neural TD learning (Cai et el., 2019), theory for overparameterized neural networks (Jacot et al., 2018; Allen-Zhu et al., 2018a;b; Du et al., 2018a;b; Zou et al., 2018; Chizat and Bach, 2018; Jacot et al., 2018, etc.) and other very similar papers. 

There is a prior work by Agarwal et al. (2019) that proves the global convergence of both vanilla policy gradient and natural policy gradient methods. In the related work, the authors distinguish their paper from that of Agarwal et al. (2019) by claiming that they are studying the non-tabular setting and they use the actor-critic scheme. However, the first claim is incorrect because Agarwal et al. (2019) also studied the non-tabular setting (see Section 6 in Agarwal et al. (2019)) and proved an O(1/\sqrt{T}) convergence rate. Moreover, the actor-critic scheme in this paper is just a trivial modification of the nonlinear policy gradient method by calling existing result for TD learning in Cai et al. (2019). Therefore, the contribution of this paper is not so clear given existing papers.

In Algorithm 1, the policy gradient estimator $\widehat{\nabla} J(\pi_{\theta_i})$ also depends on the critic parameter $\omega_i$. It is better to show this dependency in the notation as well.

In Algorithm 1, the temperature parameter $\tau_i$ is updated in natural policy gradient but not in vanilla policy gradient. It seems that $\tau_i$ increases linearly with $i$, which makes the policy defined in eq (3.1) close to a uniform distribution when the time horizon goes to infinity. This seems to offset the update of parameter $\theta_i$.

In the update of natural policy gradient, solving eq (3.8) is really expensive in computation, especially in the setting of this paper where $m$ is chosen as $T^{8}$. It seems impossible to obtain a reasonable solution within the claimed $O(1/T^{1/4})$ runtime.

What is the function $\iota(w)$ in Assumption 4.1?

It would be better for the authors to discuss more about Assumption 4.1. It is unknown why the action-value function $Q^{\pi}$ for all policy can fall into this class. 

The equation in Assumption 4.2 is exceeding the paper margin. Please make sure the paper follows the format guidelines.

Assumption 4.2 seems to be very strong. The remark after the assumption says that this condition is made on the Markov transition kernel. However, this may not be true since the assumption needs to hold for any two arbitrary policies. It is not known what kind of transition kernel $\mathcal{P}$ will satisfy this.

In each step of the neural policy gradient (Algorithm 1), the authors need to call a TD learning (Algorithm 2) to approximate the unknown action-value function $Q_{\omega_i}$ associated with the policy $\pi_{\theta_i}$ at the $i$-th step. It seems that in the learning process of ALgorithm 2, at each iteration, it samples independent data from the stationary state-action distribution which is unknown.  

In the proof of Theorem 4.8, it seems that eq (D.14) and (D.15) are the same. Why it needs to be proved twice? In addition, why the equation after (D.14) holds?

The authors should provide more details about the function $u_{\hat \theta}$ defined in eq (4.4), which seems to approximate the critic function. Specifically, why are there the derivative terms instead of just the inner product term in eq (4.4).

Other comments:
In the last sentence of Section 3.1, “... approximate aompatible function approximation ...”

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 
[Summary]
This paper studies the convergence of actor-critic algorithms with two-layer neural networks under iid assumption. Theoretical results show that, in the aforementioned setting, policy gradient and natural policy gradient converge to a stationary point at a sublinear rate and natural policy gradient's solution is globally optimal. 

[Decision]
I recommend accepting this paper. While these results may not have immediate practical interest, the analysis is an important step in understanding the behavior of actor-critic algorithms with neural networks. The final revision needs to be more clear on the limiting assumptions and include a conclusion section that assembles the results.

[Comments]
The first important assumption is the architecture of the neural network. The results in the paper consider two-layer neural networks but the abstract implies that the analysis applies to general neural networks.

The second assumption is that the state-action pairs are sampled iid from the policy's stationary distribution. In reality, these samples are either gathered online (and are therefore temporally correlated), or from a buffer that is also affected by previous policies. The description of results in the abstract and introduction should clarify this setting.

Section G in the appendix shows the analysis for the projection-free method. The projection radius (R) does not seem to play a role in the new algorithm, but the convergence rate still depends on R. Does R have a different definition in this context?

Subsection 3.1 says "without loss of generality, we keep b_r fixed at the initial parameter throughout training and only update W." Whether this modification affects the optimization of the neural network and its convergence rate is not obvious to me.

The paragraph above Theorem 4.7 defines the stationary point. Is this point guaranteed to, or assumed to, exist?
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: This paper provides theoretical studies for neural policy gradient descents for reinforcement learning problems. The authors prove global optimality and rates of convergence of neural natural/vanilla policy gradient. Their results rely on the key factor for "compatibility" between the actor and critic. This is ensured by sharing neural architectures and random initializations across the actor and critic. 

The paper is well written with clear derivations. I suggest the publication of this paper. 
review_title: Official Blind Review #1

Meta-review: The paper makes a solid contribution to understanding the convergence properties of policy gradient methods with over-parameterized neural network function approximators.  This work is concurrent with and not subsumed by other strong work by Agarwal et al. on the same topic.  There is sufficient novelty in this contribution to merit acceptance.  The authors should nevertheless clarify the relationship between their work and the related work noted by AnonReviewer2, in addition to addressing the other comments of the reviewers.
Decision: Accept (Poster)