Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:

The paper studies global convergence of actor-critic methods in the single-timescale setting, where in each iteration, the critic is update using the Bellman operator only once. The authors consider a setting where both the actor and critic are represented with either a linear model or a deep neural network. For this, the paper shows a sublinear rate of convergence of O(1/\sqrt{K}) to the optimal policy.

Comments:

- I think the analysis in the single timescale setting is an interesting question and probably more challenging than the two-timescale setting where the critic is assumed to be trained to (near) optimality. However, I am not sure how useful the result itself is - it matches the results for two-timescale settings. Why is such a result interesting? The authors don't show any lower bounds. Intuitively, one might expect the single timescale setting to converge faster than a double loop kind of algorithm. In some ways the paper leaves me more confused. 

- The authors claim the one advantage of the single timescale setting is the fact that it is amenable to the off-policy setting. I seem to be missing something here. Why can't the same argument be made for the two timescale setting? It might be useful to have a discussion on this in the paper. 

- Another confusion I have is that the paper nowhere assumes that the optimal policy is contained in the policy class. How does one get a global optimality result without this? In the function approximation setting, with the class of energy based policies, is there a characterization of the best policy in the policy class and the approximation error it incurs? Intuitively, I was expecting a residual error term in the bound.

- Lastly, and this is one of my main complaints, I tried very hard to follow the proofs in the Appendix and despite my best efforts over a couple of days, I still don't have any intuition why this result holds - specifically, why only a single application of the Bellman operator to update the critic is enough. What do the authors mean by 'double contraction', a term often used in the paper. Clearing out Section D in the Appendix would be helpful - currently there are a bunch of equations, some with proofs in Appendix E etc. I am unable to verify these easily and hence not sure how the authors got the results. The main text only spells out the setting along with a rather long section on related works etc. but gives no intuition.
review_title: Single Timescale Actor Critic Provably Finds Globally Optimal Policy

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This is a theoretical paper. The paper studies convergence and optimality of the actor-critic with the function approximation in a single-timescale setting. The proposed single-timescale AC applies PPO for the actor and updates the critic by applying the Bellman operator to the critic one time. Despite the actor-critic coupling, the paper establishes global convergence with sublinear rates for the proposed AC method in both linear and neural network function approximation.  

Strong points:

(1) The paper is well-written, and the motivation is easy to follow. The paper also provides detailed literature on related works. 

(2) The studied AC is practical in the sense that both the actor and the critic can take function approximation and their updates work in the one-timescale. The proposed scheme could complement the previous study of the AC methods in the two-timescale.

(3) The provided convergence theory could be some new insights into dealing with the coupling of the actor and the critic. The provided intuition makes sense to me although I didn’t get time checking proof details. 

Weak points and comments:

(1) Although the paper provides a general setup for the one-timescale AC method, it is worth providing some generic examples to explain the theory, e.g., the energy-based policy with direct parametrization. 

(2) The theory seems to be specific to the energy-based policy. Are there any other types of policies that can also be considered? If not, it would be helpful to comment on the importance of the energy-based policy in practice or from the theoretical point of view? 

(3) The proposed AC methods rely on the population quantity, e.g., expectation over state-action visitation probability. How practical are they? Or how is the proposed AC related to practical one-timescale AC methods mentioned in the Introduction? 

(4) In (2.7), the critic depends on the current policy at k+1. What do you mean by they are updated simultaneously in the Abstract?

(5) It would be helpful to make a table comparing the proposed AC with others in terms of sampling assumptions, policy classes, and convergence. 

I believe my concerns can be addressed during reviewing. For me, the development of this paper is new, and I am more inclined to agree with the acceptance.


review_title: Theory for an one-timescale AC 

final_score: rating: 7: Good paper, accept
review_content: This paper studies the finite time performance of actor-critic algorithm with PPO-type update. Global convergence  is provided by exploring the convex-like property of the objective function in the distributional space. Different from previous studies that focus either on two time-scale update or nested-loop update, this paper studies the single time-scale update scheme. Thus the result in this paper is somehow meaningful.

I have the following questions for the author:

(1) The algorithm proposed and stuided in this paper can be implemented in a "single time-scale" way only at a cost of high computational cost at each iteration, making the motivation of using this algorithm in practice less clear. The AC algorithm in this paper need a near-optimal solution in both policy optimization (actor) and policy evluation (critic) at each iteration, thus requires the critic to perform LSTD instead of TD(0). However LSTD requires computation cost of O(d^2) and TD(0) only requires O(d), thus TD(0)-typer critic is more favored in practice, especially when the dimension d is very large. Since this paper is a pure theoretical paper so let's forget about the practical concern first. Can the author highlight the technique challenging of using LSTD-critic instead of TD(0)-critic compared with previous work Liu et al. (2019)?

Boyi Liu, Qi Cai, Zhuoran Yang, Zhaoran Wang, (2019) "Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy"

(2) The critic stuided in this paper adopts projection to enable the whole proof go through. The projection is a practical issue which has been criticized by many researchers in the RL community. Can the author provide an upper bound for the projection radius so that the algorithm can be at least implemented in practice.

(3) It seems that the neural network parameterization studied in the appendix is still a nested-loop algorithm, not a single-timescale algorithm that highlighted in the title and the story of this paper. I agree that it is meaningful to study the DNN in AC for the first time, but can the author compare the overall sample complexity in this paper with the sample complexity in Liu et al. (2019)? Does the LSTD-critic help to improve the overall sample complexity comparied with the TD(0)-type critic in Liu et at. (2019)?

(4) It seems that the global convergence guarantee is highly depend on the soft-max parameterization, which has limited practical applications. Can the author still establish a similar result in the infinite-action space case by using a similar proof in this paper?

I will keep my score if the author can answer the above questions.

=== post rebuttal ===

I am satisfied with the response and i will keep my score.

review_title: Meaningful Result for AC algorithm

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

This paper proves that the proposed single-timescale actor-critic algorithm with KL regularization converges to a globally optimal policy when appropriate function approximation is used. The authors define a specific form of actor/critic updates, which are PPO update for the actor and the single application of Bellman evaluation operator for the critic. Given such an algorithm, the authors provide an upper bound of the regret for linear and deep neural network function approximation (although there are some strong assumptions, e.g. no approximation error). 

Reasons for score:

Overall, I vote for strong acceptance. While I am not capable of fully checking the proofs, I understand the importance of the result. Based on the mathematical rigorousness of the main text and the proof sketch, I assume that the paper is technically correct. Given that the paper is technically correct, it is the first convergence result for a single-timescale actor-critic algorithm as far as I know (and the paper claims so). This work will be very significant as it theoretically grounds the single-timescale actor-critic algorithms, where the state-of-the-art deep RL algorithms are mostly single-timescale actor-critic algorithms.

PROS:
* The paper (at least the main text and the proof sketch) is well written.
* First result on convergence rate and global optimality of single-timescale actor-critic, which is very significant.

CONS:
* No further discussions based on the results for better design of an actor-critic algorithm. It would be helpful if there are more discussions about the algorithm choice, i.e. being off-policy, broken assumption, etc.

Questions:
* I still do not understand how this result can be applied to off-policy results, where we have $\mathbb{P}^{\pi_{\theta_{k+1}}}$ in e.g. equation 3.4 and 3.7. How can the samples be reused if $(s,a)$ are not from $\rho_{k+1}$ but from previous $\rho$s?

Typo:
* Specifically, after K + 1 actor updates, we are interest -> we are interested? : before eq (4.1).






review_title: First convergence result for single-timescale actor-critic

Meta-review: Most reviewers agree that the paper makes valuable contribution in analyzing single-timescale actor-critic algorithms. There were some doubts on the theoretical advantage over two-timescale algorithms and the realizability assumptions, but the authors made satisfactory clarifications. 

Therefore, acceptance is recommended, though I strongly suggest the authors to explicitly state key assumptions required to ensure global optimality in the abstract and introduction to avoid confusion. 

Decision: Accept (Poster)