Finite-time analysis of single-timescale actor-critic

Summary

The paper studies finding the optimal policy in an infinite-horizon average-reward MDP with an online, sample-based algorithm. The state-of-the-art algorithm in this setting uses two different timescales and is known to have a sample complexity of $\widetilde{\mathcal{O}}(\epsilon^{-2.5})$. This paper shows that a single-timescale version of the actor-critic algorithm enjoys an improved complexity of $\widetilde{\mathcal{O}}(\epsilon^{-2})$, up to a logarithm factor. If we were always able to sample according to the stationary distribution under the current policy, the logarithm factor can be removed.

Strengths

Being able to improve the convergence rate from $\widetilde{\mathcal{O}}(\epsilon^{-2.5})$ to $\widetilde{\mathcal{O}}(\epsilon^{-2})$ is a pretty significant contribution. As the authors noted, this rate already matches the rate of standard SGD for non-convex functions. The paper is also well-written.

Weaknesses

While the presentation of the paper is mostly clear, more discussion how exactly the authors improved the convergence rate and why previous works failed to do that is needed for the audience to appreciate the technical contribution. In fact, many existing works on two-timescale AC do not start off trying to the make updates two-timescale. Making the step sizes for the actor and critic decay at the same rate is allowed, but doing so hurts their convergence rates. Do the authors take advantage of any other structure of the MDP beyond general non-convexity to make a single timescale more favorable?

Questions

- Related work section is somewhat limited. The connection of the paper to existing works on single-loop AC algorithms including the following ones should be discussed. Hong, M., Wai, H.T., Wang, Z. and Yang, Z., 2023. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1), pp.147-180. Zeng, S., Doan, T.T. and Romberg, J., 2021. A two-time-scale stochastic optimization framework with applications in control and reinforcement learning. arXiv preprint arXiv:2109.14756. Khodadadian, S., Doan, T.T., Romberg, J. and Maguluri, S.T., 2022. Finite sample analysis of two-time-scale natural actor-critic algorithm. IEEE Transactions on Automatic Control. Zhou, M. and Lu, J., 2022. Single Time-scale Actor-critic Method to Solve the Linear Quadratic Regulator with Convergence Guarantees. arXiv preprint arXiv:2202.00048. - I do not feel that the discussion of i.i.d. sampling case and the theorem adds much to the paper. The claimed contribution on Markovian sampling also seems a bit oversold. Many existing works have shown how Markovian samples can be handled at the cost of introducing a log factor, which does not appear if the samples are i.i.d.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

The work studies the actor-critic algorithm’s convergence under the single-timescale update where the step-size of actor and critic variables are only proportional by a constant. Authors suggest the epsilon-optimal solution with a sample complexity $\tilde{O}(\epsilon^{-2})$ under standard assumptions and $O(\epsilon^{-2})$ under i.i.d. sampling.

Strengths

This paper tries to analyze the sample complexity of the AC method under more practical Markovian sampling, where the transition tuples are generated from a single trajectory. The theoretical problem is well-motivated. The paper proposes a new analysis framework for the algorithm and establishes the sample complexity of $O(\epsilon^{-2})$ which matches the best existing sample complexity for the single-timescale AC algorithm, and a sample complexity of $\tilde{O}(\epsilon^{-2})$ without i.i.d. assumption.

Weaknesses

After removing the assumption of independence and identically distributed (i.i.d.) data, the author introduces a new assumption, namely that the Markov chain is geometrically mixing and the rollout state distribution rapidly approximates the stationary distribution (assumption 3.2). I am curious whether this assumption, although slightly weaker than the i.i.d. assumption, can still be considered strong, as it may not be commonly applicable in practical scenarios. Furthermore, this assumption appears to conflict with the statement "the transition tuples are generated from a single trajectory." In the final results, the author requires a condition of $T>2\tau$ to ensure that the obtained samples are sufficiently close to samples from an i.i.d. stationary distribution. Numerous studies have already examined actor-critic methods and achieved the same sample complexity of $O(\epsilon^{-2})$. The author claimed that their proposed methods can be utilized without relying on the i.i.d. assumption and achieve a slightly inferior complexity of $\tilde{O}(\epsilon^{-2})$ under alternative assumptions. It is hard to judge the contribution in this situation since it is natural to obtain a worse result under milder assumptions.

Questions

The author asserts that their methods are capable of addressing continuous state situations, even when the state space is infinite. However, it is unclear whether the analyses can also be extended to infinite action spaces. Could the author provide some clarification and analyses on this aspect? Since the paper obtain the same results of $O(\epsilon^{-2})$ with previous works, could the author discuss and compare their results more specifically? (e.g., the constant comparison or simple control experiments)

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The paper still needs many strong assumptions to analyze the problem and it is very understandable due to the theoretical nature of the work.

Summary

This paper studies the actor-critic algorithm with linear function approximation. The authors provide a single-time-scale analysis for the AC and achieve $\epsilon^{-2}$ sample complexity.

Strengths

- The paper is overall well written and easy to follow - The single-time-scale analysis with markovian noise for actor-critic is new in the literature, to my best knowledge. - The policy gradient norm error analysis is interesting

Weaknesses

- I'm confused about Assumption 3.4, I wonder how $L_\mu$ contributes to the final results. - Assumption 3.1, though the authors mentioned a few paper using the same assumption, sounds pretty strong for me. It basically requires even the optimal policy should visit all state-action pairs, which is quite uncommon in practice.

Questions

My concerns are listed in the weakness part.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA

Summary

This paper provides a finite-time analysis of single-timescale, single-sample, average-reward actor-critic with a linear critic under Markovian sampling. It is established that the standard scheme achieves $\epsilon$-approximate stationarity with $\widetilde{O}(\epsilon^{-2})$ sample complexity. The analysis is achieved by extending the small-gain analysis of [A. Oleshevsky & B. Gharesifard, _A small-gain analysis of single-timescale actor-critic_. SICON 2023], which was for the discounted setting, to the average reward setting. This is accomplished by leveraging a uniform ergodicity assumption (Assumption 3.2, line 202) and associated analysis (like, e.g., that of [Y. F. Wu, W. Zhang, P. Xu, Q. Gu, _A finite-time analysis of two time-scale actor-critic methods_. NeurIPS, 2020]) to handle the Markovian sampling that becomes particularly important in the average-reward setting. It is furthermore claimed that the results apply to problems with continuous state spaces. The sample complexity achieved matches the state of the art for finite-time analyses of actor-critic methods, yet applies to the single-timescale, single-sample, average-reward, Markovian sampling setting, which was previously an open question.

Strengths

As stated in the summary, this work establishes that single-timescale, single-sample, average-reward actor-critic under Markovian sampling achieves $\epsilon$-stationarity with $\widetilde{O}(\epsilon^{-2})$ sample complexity. This shows that this version of actor-critic matches the state of the art, resolving what was a previously an open question. Despite the analysis presented in the appendix being notation-heavy and somewhat difficult to follow, and though there are issues in the exposition and assumptions that need to be addressed (see weaknesses and questions below), the main steps in the theoretical results appear to be sound. The analysis appears to build off of the small-gain analysis of [Oleshevsky & Gharesifard, 2023], combined with elements of previous two-timescale analyses for average-reward actor-critic with the uniform ergodicity assumption such as [Wu et al., 2020], as well as some algebraic manipulations of inequalities. Though of uncertain practical utility, this contribution is definitely of interest to the theoretical reinforcement learning community.

Weaknesses

I have some concerns about: (i) clarity about the innovation required in the analysis; (ii) the satisfiability of the assumptions made; and (iii) the dependence of the main result presented in Step 4 in lines 331-339 on having access to potentially unknown problem-specific constants when designing stepsizes. Addressing these issues or being clear about any limitations will likely strengthen the paper. (i) As stated above, the analysis appears to build off of [Oleshevsky & Gharesifard, 2023] to handle the interconnectedness of the single-timescale analysis, elements of two-timescale analyses like [Wu et al., 2020] to handle Markovian sampling, as well as algebraic manipulations of inequalities to combine it all together. However, it is unclear from the main body whether the analysis is a straightforward (albeit complicated) combination of these existing methods, or if some critical new insight and innovation are required. If the former, the significance of the contribution is weakened. If the latter, it should be stated more clearly. Also, the abstract claims that the analysis applies to continuous state spaces, and on lines 73-74 it is stated that achieving this requires "significantly non-trivial effort in the analysis". It is not clear where in the analysis this non-trivial effort takes place, however. If serious additional effort was required, it should be clearly stated exactly where it occurs. (ii) Two of the assumptions call into doubt the applicability of the result to continuous state spaces. On lines 198-199, it is stated that Assumption 3.1 holds under certain conditions in the tabular case, but applicability to the continuous state space case is not mentioned. The reader wonders: does Assumption 3.1 hold when $|S| = \infty$? In addition, lines 220-221 state that Assumption 3.4 holds for the finite state-action space setting. Again: what about when $|S| = \infty$? Since the analysis relies on these assumptions, it must be shown that they hold in the continuous state space setting for the corresponding claims in the abstract and introduction to be true. Finally, though uniform ergodicity (Assumption 3.2) is commonly assumed in average-reward analyses, the recent two-timescale analysis of [W. A. Suttle, A. S. Bedi, B. Patel, B. M. Sadler, A. Koppel, D. Manocha, _Beyond exponentially fast mixing in average-reward reinforcement learning via multi-level monte carlo actor-critic_. ICML 2023] removes the need for this assumption. It would be helpful to see a discussion of why Assumption 3.2 is still required in the single-timescale analysis or how it might be eliminated. (iii) On lines 334-337, it is pointed out that, for Step 4 (cf. lines 331-339) to work, a certain set of inequalities (line 335) needs to be satisfied. It is stated that this condition can be satisfied by choosing the stepsize ratio $c$ to be smaller than some threshold. On line 556 in the appendix, this threshold is given, but it involves the problem-specific constants $\lambda, L_*, G, B$. It thus appears necessary that we have oracle knowledge or that an additional estimation procedure is required for the specific stepsize scheme to be operable.

Questions

* What is the key innovation required in the analysis? * What is the effort required in accommodating continuous state spaces? * Under what conditions do Assumptions 3.1 and 3.4 hold for continuous state spaces? * Why is Assumption 3.2 necessary? Or can it be eliminated? * How do we choose the stepsize ratio $c$ in practice?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Aside from the weaknesses and questions described above, the authors have adequately addressed the limitations of the work.

Summary

This works provides finite sample analysis for single timescale actor critic.

Strengths

A finite sample analysis for single timescale actor critic under Markovian noise and infinite state space is definitely a notable contribution to the community.

Weaknesses

My biggest concern is the correctness of this work. This work is a resubmission from ICML 2023. In the ICML round, all reviewers agree that this is a good paper until one expert reviewer that seems to really be in the field pointed out one critical technical error in the proof, leading to the rejection. But I unfortunately do not have access to the ICML reviews now so I will recommend "rejection" for now. If the authors provide the following information in the rebuttal, I am more than happy to evaluate the work again. 1. What errors did the reviewer pointed out in the ICML round (it would help a lot if a copy of the original review can be provided, assuming the authors still have access to it)? 2. Was the reviewer wrong or the authors were wrong? 3. If the authors were wrong, how is the bug fixed in this version? If the reviewer was wrong, what mistake did the reviewer make? It would help a lot if the authors could answer the above questions in details and in a self-contained way.

Questions

See above

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See above

Assumption too strong

I am afraid Assumption 3.4 is way too strong. [8] does have such an assumption. But I quote from [8] > Assumption 11 is the counterpart of Assumption 10 that is made for the stationary distribution μθ(a|s). Note that the existence of ∇μθ(s) has been shown in [2]. In this case, under Assumption 10, i) and iii) of Assumption 11 can be obtained from the sensitivity analysis of Markov chain; see e.g., [32, Theorem 3.1]. While we cannot provide a justification of (ii), we found it necessary to ensure the smoothness of the lower-level critic solution y∗(θ). [8] does **NOT** provide a justification for the smoothness of the stationary distribution. The argument the authors make is "This assumption holds for the finite state-action space setting". I would like to see a proof, since [8] does not prove this. I think it's ok for [8] to use this assumption because RL is merely 1 of their 4 applications of a more general result, but RL is all of this work.

Clarification request: continuous spaces

Thanks very much for the responses. In the abstract on line 6 and contributions on lines 73-74, you mention that you target the continuous spaces setting. In your response to (Q2) above, you have nicely outlined the **challenges** inherent in the continuous space setting, but I still don't understand how you **overcame** those challenges. Two questions: 1. Does your analysis handle the continuous spaces setting? 2. Can you point out specific locations (e.g., with sections or line numbers) in the analysis where you made "significantly non-trivial effort" to handle this setting? Also, can you explain how these efforts are completely different from previously used techniques?