Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studied the convergence rate of the asynchronous actor-critic algorithm (with linear value function approximation)  for RL. This paper showed A3C-TD(0) has O(\epsilon^{-2.5}/N)  sample complexity per worker where N is the number of workers., which means the per-worker sample complexity can be reduced linearly with respect to # of worker. 

In general, this paper is well written and easy to follow. The sample complexity results are insightful.  Could the authors address my following comments/questions?

(1)$w_\theta^\ast$ or $w_{\theta_k}^\ast$ are never formally defined. Please clarify the notations properly. 
(2)Unlike "linear-speedup" in setting such as convergence rates for SGD,  the linear speedup is not so "idea". The gradient norm has a constant error floor term $O(\epsilon_{app})$, which eventually dominates the error as K increases.   To my understanding, an error term is unavoidable because the valuation is approximated by a linear function.  I wonder if the results in the current paper can be easily extended to cover the situation where no linear approximation is used, in which case I expect the error terms disappears totally. 
(3)  This is also related to (2). It is reasonable that the critic-convergence (Theorem 1) uses  a drifting $\theta_k$. But if we look at the actor and critic together, our goal is to converge to a fixed policy, am I right? If so, is it necessary to define $\epsilon_{app}$ in (13) as the error regarding to the worst \theta? (In other words, can we remove $max_{\theta\in R^d}$ in (13) and define $\epsilon_{app}$ using a single $\theta$? By doing that, $\epsilon_{app}$ can be much smaller)
review_title: Well written paper with sound results

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper revisits the A3C algorithm with TD(0) for the critic update to provide better theoretical analysis of A3C. A3C-TD(0) achieves linear speedup and it also matches our intuition. To show the empirical results, the authors provide convergence results of A3C-TD(0) with Markovian sampling in synthetic environments and speedup of A3C-TD(0) in CartPole and Seaquest.
In this paper, the theoretical and experimental results show that using multiple workers in parallel improves learning speed without loss of sample efficiency. I think it is a valuable research direction. 
However, A3C-TD(0) is limited compared to A3C because A3C-TD(0) does not use multi-step TD or TD(\lambda). Moreover, the authors use only two gym environments, which seems insufficient.

review_title: Theoretical analysis for A3C with 1-step TD

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studied the two time scale A3C in discounted MDP based on recent development in the finite sample analysis of A2C. The sample complexity result in this paper matches previous result in two time-scale A2C in terms of the dependence of \epsilon, and this paper further shows the benefit of "linear speed up" brough by the structure of A3C. Given the practical usefulness of A3C, the result established in this paper is meaninful.

Although most of the technical proof seem correct to me, the algorithm studied in this paper has the following issues.

(1) In the policy evaluation part (critic), samples are generated according to the the "hybrid" transition kernel \tilde{P}, which is not reasonable. The purpose of the policy evaluation is to evalue the value function, thus the samples used by the critic need to follow the transition kernel P not \tilde{P}. Otherwise, the value function learned by the critic would be different from the pure TD(0). I understand that the the author adopt this sampling method because the author want to make a "two time-scale" algorithm to study here. However, under such a sampling startegy only the actor can obtain appropriate samples. In fact, it is very difficult to design a two time-scale algorithm for a discount MDP, as the transition kernel required by actor and critic are different. I suggest the author to study "averaged MDP" instead. In the averaged MDP, both the actor and critic can share the same transition kernel, which make designing a two time-scale algorithm possible.

(2) Another problem is the projection used in the critic. The projection in linear SA is a practical problem, as we do not have prior knowledge of the radius before we run the algorithm. The projection issue has been criticized by many researchers' in the RL community in the last few years thus should not be ignored here. In fact, the projection issue can be avoid if the author adopts a nested-loop structure, and I think the sample complexity result can even be  improved in the nested-loop setting. Thus I suggest the author to used nested-loop structure to avoide this projection issue.

Overall I think the paper is well written. However, considering the two problems that I mentioned above, I think the current version is not ready to be published.
review_title: The result is reasonable but the sampling has some issues

Meta-review: Although the reviewers found the paper well-written that analyzes a relatively popular algorithm (TD(0) version of A3C), there are concerns regarding the novelty of the convergence results given those for A2C, the comparison of the results with those for A2C, and the sufficiency of the experiments. Although the authors addressed some of these issues/comments during the rebuttals, it seems none of the reviewers is excited about the paper and there still exist concerns regarding the novelty of the results and how they are compared with those in the literature. I would suggest that the authors take the reviewers' comments into account, have a more comprehensive discussion about the relation of their results with those in the literature (two-time scale algorithms), and prepare their work for future conferences. 
Decision: Reject