Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors analyse a mean-field limit of an actor-critic algorithm for which the critic is parametrized with a single-hidden-layer neural network, and the policy is tabular. The analysis is carried out in continuous time, and in the limit of infinite network width.
main_review: The analysis of reinforcement learning algorithms under non-linear function approximation is an important direction for better understanding the behavior of deep reinforcement learning agents. As such, the topic the authors study is likely to be of interest to the (theoretical side of) the NeurIPS RL community.

The mean-field limit considered here is interesting and elegant, and broadly the mathematical presentation is precise. A wide variety of related work is presented. However, at the moment I think the paper is currently lacking a broader discussion of the context of these results. This is the primary reason for the current rating for the paper, and I would be open to revising the authors if the authors can address these concerns.

At present, a lot of space is given to detailing aspects of the convergence proof, at the expense of e.g. a conclusion at the end of the main paper, and more discussion/motivation of the various limits described in Section 3, and what these results have to say about Q-learning with neural networks. In particular, I was left with several questions about the motivation and utility of the main results:
 * To obtain the mean-field limit Eqns (3.5) and (3.7), several limits are taken (infinite width, and stepsizes/continuous-time updates). I was unsure whether the order in which these limits are taken affects the analysis, and how closely we should expect the analysis of these systems to relate to finite-width networks updated in discrete-time, and what the analysis can tell us about these systems. Some additional discussion of these connections would be useful, and small-scale experiments to understand when the limit is likely to "kick in" may also be useful.
 * There are some seemingly strong assumptions made in the course of the analysis, such as a tabular policy, bounded output weights for the neural network in Eqn (4.2), structure assumptions on the MDP (Assumption 4.3), and an algorithmic restarting mechanism, presumably to avoid divergence. I would expect these to limit the applicability of the main theoretical result, but there is not much discussion of the practical implication of these assumptions in the paper.

Minor technical comments

Why can we assume (s, a) has uniformly bounded norm without loss of generality? It seems this induces some topological assumptions on S x A (precompactness, for example) - can the authors make clear why their arguments would still apply to state-action spaces which aren't precompact? Is the argument at Equation (4.4) affected by this?

Under the general assumptions on the structure of state-action space, I don't think it holds that Q^pi is the unique minimizer of MSBE - some kind of qualification allowing  \tilde{\Phi}-almost sure equality is required (i.e. consider modifying Q^pi at a single state-action pair that has zero probability under \tilde\{Phi}^pi).

Line 245: Is there a typo here? Should (-B_beta, B_beta) be [-B_beta, B_beta]?

Line 248: "Such over-representation appears to be essential for our analysis". Can more be said about this?

---

AFTER REBUTTAL:

I thank the authors for their clarifications on many of the questions I mentioned in the original review, and have increased my rating for the paper. There are several points of discussion (for example, the boundedness of state-action features) here that would benefit the paper to be included in later versions.
limitations_and_societal_impact: As mentioned above, more discussions of the assumptions made for the main theoretical results (including their limitations) would be useful.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies actor-critic (AC) algorithms with neural networks from a theoretical perspective. 

The authors consider an AC algorithm variant that updates its actor with PPO with a small stepsize, and its critic updated via TD and a larger stepsize. Under certain conditions, the authors prove that this AC reaches the optimal policy with sublinear rate. The authors additionally show that the feature representations learned by the critic can move further away from the initialization. 
main_review: - Originality: authors approached the neural AC problem from very interesting angles and the approach as well as the results seem to be novel
- Quality: The theoretical results in the paper seem interesting and important
- Clarity: the paper is clearly written
- Significance: significant results that improves understanding of how actor-critic methods learn with neural networks

Questions/comments for the authors:
- Why would we want to update the critic much faster than the actor? In many recent paper on deep reinforcement learning (for example, TD3, SAC), the actor and critic have similar or same learning rates. And if the two are updated at the same rate, how would that affect the results proven in the paper? 
- The results on representation can evolve into a larger neighborhood seems to be very interesting, but why is this significant? What does it tell us about how actual neural networks should be treated differently from NTK? In my opinion it would be great if the authors can provide some more discussion here. 
- The paper mentions many times the close relationship to replicator dynamics, but it seems to me the paper does not have a good background introduction to exactly what this relationship is, and this might be a bit confusing for readers who are not that familiar with replicator dynamics. 

Minor comments:
- there is a typo at line 178 "the the critic"

==================

post rebuttal: I have read the responses from the authors, I feel my questions are addressed and my evaluation remains the same
limitations_and_societal_impact: Since the authors are analyzing neural AC algorithms, it might be really interesting to have some numerical experiments, especially on the relative learning rate of actor and critic. And it would be interesting to have analysis on how this relates to other problems in RL such as bias accumulation. However, the theoretical results in this paper seem to be already quite important.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper analyzes the optimality and convergence of the two-scale update for an actor-critic algorithm where the actor and critic are parameterized by two layer NNs (which is a generalization of traditional linear function approximation guarantees in RL). The authors analyze for the PPO as actor and minimizer of the the MSBE as the critic. Considering the actor-critic updates as gradient flow differential equations in the L_2 Wasserstein space, in following steps, the authors show: (1) optimality and convergence rate of policy error proportional to inverse of time and the critic error (2) bounding the critic error based on the Wasserstein error of the distribution of NN weights (3) applying (1) and (2) with Restarting mechanism (resampling the critic weights from an initial distribution when they are sufficiently close to the initial distribution), they prove the global optimality and convergence rate of AC method .
main_review: The paper is clear and enjoyable to read. The idea of the paper is interesting and the convergence analysis of an actor critic algorithm with two layer neural networks potentially helps strengthening RL theoretical foundation.

My main concern about this paper is the update 3.2 that is a based on minimizing MSBE which suffers from double sampling and I couldn’t find it being incorporated/or discussed in the analysis of the paper. I am interested in knowing if and how much this affects the convergence analysis in this paper?

Line 276: does not lose…
limitations_and_societal_impact: They discussed potential analytical limitations in the conclusion in the appendix
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies convergence of an Actor-Critic algorithm for an MDP problem with infinite one-hidden layer neural network approximation of Q function in the regime mean-field  (Theorem 4.5) and lazy type regime (Theorem 4.6).    By bringing (heavy) machinery from gradient flows literature, the authors perform a similar analysis to the one performed by a group of A. Montanari or Chizat/Bach in the context of supervised learning problem with one-hidden layer approximation which more recently has been adapted by Agazzi an Lu to study popular Policy Gradient algorithm. 

main_review: Originality:  The results seem to be new, and the main contribution is the study of actor-critic algorithm represented by gradient flow equations (3.5) MF-TD and (3.7) MF-PPO. However, the dynamics of 3.7 is very simple and one can see from the error in Theorem 3.7 that the crux of the matter is the estimate on Q functions (where grad flow  3.7 plays a small role).  At that point, it would be very helpful if authors presented a thorough comparison to the work [69] of Zhang et al. and possibly [1] Agazzi et al. Especially result from [69] seems very relevant (see their Section 4), though I only had a chance to skim through that other paper.   

Quality: This is theoretical work and as already pointed the results stated in section 4 follow from a heavy analysis of gradient flow. In my opinion, authors did not make sufficient effort to help readers follow the proofs. Even though I'm rather well familiar with the analysis of this type I found reading the paper difficult.   

There are a number of things that would require further comments. Let me give a few examples (impossible to list them all here):
- Heuristics in section 3 are helpful, but there isn't any comments on which of these approximation errors would be easy to quantify and which not.
- in 3.3, entropy regularisation appears without any comments.  This doesn't correspond to classical an actor-critic algorithm. Is this needed? How does this help?
-  [top page 7] when giving a reference to technical results, please specify chapter, section, concrete results. Giving a reference to a whole book is useless. 
- I have some issues with assumptions 4.2: why the activation function need to be odd? And Lipschtnes in [-2/3,2/3] seems too prescriptive.  
- In 4.3: why it is sensible to assume that both reward and transition functions need to admit one-hidden layer representation and with the same activation function? This seems cooked up and little effort has been made to explain why these are sensible assumptions. 
- Theorem 4.5 and a discussion that follows: One would expect the bound to decay with t, but instead authors stated results that says that one need to send \eta and \alpha  to \infty. Now \eta in 3.5 corresponds to the time change and \alpha dictates scaling of the neural network approximation. Hence, if I'm reading this correctly, this means that in effect, authors study lazy regime in the end... This is somehow also implied by 'restoring mechanism.'
- Authors mention replicator dynamics and even put this in the title, but there isn't anything in the paper saying why this is relevant.

Clarity: As already stated, I would appreciate more discussion around assumptions and main results and how they relate to what's in the literature. The analysis in the appendix is hard to read, and significantly more effort is needed to make it accessible to NIPS community. 

Significance: While I appreciate the importance of this type of work to shed more light on why neural networks based algorithms work, I don't feel this work adds significantly in comparison to what already has been done in the study of on-hidden layer neural networks in mean-field or lazy regimes.
limitations_and_societal_impact: n/a
review_title: null

Meta-review: All reviewers thought this paper made useful contributions around strengthening the theoretical foundations of RL through an analysis of an AC algorithm with neural networks. AC is a very popular approach in RL and this will likely be of interest to the large body of researchers interested in RL. The authors are encouraged to address the reviewers' feedback in their camera ready paper. 
Decision: Accept (Poster)