On the Convergence of Single-Timescale Actor-Critic

We sincerely thank the reviewer for their thorough and insightful feedback. We are encouraged that they find our results and analysis both significant and of interest to the reinforcement learning theory community. We also greatly appreciate the constructive criticism and thoughtful suggestions, which will help us improve the final version of the paper.

Q1) The weakness in the analysis from Chen and Zhao [2024] is that they treat the policy optimization objective as a general smooth non-convex function without using the gradient domination structure (or one may plug in the inequality at the end). In my understanding, the core innovation of the current paper is to exploit this structure when bounding the iteration-wise drift of the actor. A more thorough discussion of this aspect should be the actual focus of the presentation.

We thank the reviewer for this insightful observation. The comment is indeed correct in noting that our analysis leverages the Gradient Domination Lemma (GDL) structure from the outset, using it as a foundation to derive and solve the core recursion. We will emphasize this point more clearly in the final version.

This approach stands in contrast to that of Chen and Zhao [2024], who rely on standard smooth optimization techniques and employ a telescoping sum to upper bound the gradient norm. In their analysis, the GDL is applied only at the end, yielding a best-iterate guarantee but leading to a weaker overall convergence rate.

We will incorporate this comparison into the introduction, main text, and discussion sections of the final version.

Q2) Can the authors clarify if I correctly understand the innovation of the paper in my comments above (in Strengths & Weaknesses)? Specifically, the limitation in prior works like Chen and Zhao [2024] .... more emphasis on Lemma 4.1 and its analysis in the main paper.

Yes, the reviewer is correct in understanding both the novelty and the techniques used in the paper. Indeed, Lemma 4.2 is derived using standard techniques that are well-established in the literature. We appreciate the suggestion to emphasize Lemma 4.1 more prominently, and we will incorporate this in the final version.

Q3) The authors state "Additionally, when this ODE tracking method is applied to the recursion for the exact gradient case, it produces better results compared to existing bounds, such as those in Mei et al. (2022)." in line 52-54, but never establish anything along this line.

We apologize for this omission. By applying our techniques, we can improve the iteration complexity by a factor of $\frac{1}{(1 - \gamma)^3}$ compared to Mei et al. (2022), along with better dependence on the initial sub-optimality. A brief explanation follows:

In the exact gradient case, from the sufficient increase lemma and using a step size $\eta_k = \frac{1}{L}$, where $L = \frac{8}{(1 - \gamma)^3}$ is the smoothness coefficient, we have: $a_{k+1} - a_k \geq \frac{\lVert \nabla J^{\pi_{\theta_k}} \rVert_2^2}{2L}.$ From the Gradient Domination Lemma (GDL), we also have: $a_k \leq \frac{\sqrt{S} C_{PL}}{c} \lVert \nabla J^{\pi_{\theta_k}} \rVert_2.$ Combining the two gives the recursion: $a_{k+1} - a_k \geq \frac{c^2}{2 L S C_{PL}^2} a_k^2.$ Using ODE tracking, it follows that:

We thank the reviewer for the prompt response. We are glad to know that the reviewer is satisfied with the answers to most questions, except Q1 and Q2, which we now address below.

Novelty of the Paper

First, we apologize for any confusion caused by our previous response. To clarify: Lemmas 4.1, 4.2, and 4.3 are supporting results that help derive the interdependent recursions summarized in Equation (3). The main technical novelty lies in our method for solving these coupled recursions, culminating in Lemma 4.4.

Creative Step In prior work, notably by Chen and Zhao [2024], the analysis leverages the possibility of a telescoping sum in the actor update recursion ($a_{k+1} - a_k$). In contrast, our approach introduces a novel Lyapunov function of the form $a_k + z_k^2$, which leads to a significantly more elegant and well-behaved recursion. Identifying this Lyapunov structure was far from straightforward—it required substantial insight and effort. Once identified, it allowed us to bypass the major bottleneck in solving the coupled recursions.

Why Solving Equation (3) Is Difficult Without the Lyapunov Term: Equation (3) consists of coupled recursions for the actor and critic. To bound the actor term ($a_k$), we require a lower bound on $y_k$, which we obtain via the GDL (Lemma 4.3). However, to control the critic error ($z_k^2$), the critic recursion requires an upper bound on $y_k$, which is not available. This introduces a major hurdle in analyzing the recursion. By summing the actor and critic recursions and carefully constructing the Lyapunov term $a_k + z_k^2$, we eliminate $y_k$ entirely from the recursion without its upper bound—achieving a breakthrough that would not be possible otherwise (see Line 279).

Technical Contribution: Once the Lyapunov recursion is derived (Line 280), solving it remains challenging due to the time-varying learning rate $\eta_k$. While classical intuition suggests that such a difference equation should follow its corresponding ODE under small step sizes, Lemma 4.4 formalizes this intuition in a rigorous and general way. The ODE tracking lemma (Lemma 4.4) is a core technical contribution of this work. Both the result itself and the proof technique used to derive it are, in our view, elegant and novel.

Supporting Results

Lemma 4.1 (Actor Recursion): Derived from the smoothness of the return function, this lemma ensures monotonic improvement under sufficiently small step sizes. It is a noisy-biased variant of the standard sufficient increase lemma, and similar results have appeared in various forms in the literature.

Lemma 4.2 (Critic Recursion): This follows standard techniques for convergence of the critic using sample-based updates. It relies on the contraction property of the Bellman operator for policy evaluation.

Lemma 4.3 (GDL Recursion): This lemma applies a gradient domination argument in expectation, using standard tools such as Jensen’s inequality.

Summary

To avoid confusion, we are considering relabeling Lemmas 4.1, 4.2, and 4.3 as propositions and making it explicit that these results are derived using standard techniques. This would help highlight that:

The key insight lies in identifying the Lyapunov function that bypasses the need for an upper bound on $\|y_k\|$.

The main technical novelty lies in Lemma 4.4, which solves the Lyapunov recursion via a general ODE tracking argument.

We hope this clarifies the core contributions and addresses the remaining concerns in Q1 and Q2. Thank you again for the thoughtful feedback. We are glad to answer any further questions, if any.

We thank the reviewer for the encouraging reviews. We are glad that the reviewer finds key ideas and analysis to be novel, fairly simple, and insightful. We're also happy to hear that the presentation of the setting and positioning within prior work were clear.

Q1) The sample-complexity does not match the lower-bound whose dependence in $O(\varepsilon^{-2}).$

The reviewer is correct in noting that our $O(\epsilon^{-3})$ complexity does not match the lower bound of $O(\epsilon^{-2})$. However, our result significantly improves upon the existing complexity of $O(\epsilon^{-4})$, thereby narrowing the gap. To the best of our knowledge, this represents the current state-of-the-art for single-time-scale actor-critic algorithms.

Q2) The dependence on quantities other than $\varepsilon$ are ignored. In particular, the dependence on the effective horizon $1/(1-\gamma)$ and the size of the state-action space $SA$, which are hidden within constants, appears like it could be quite poor.

All prior works report complexity only in terms of $\epsilon$, and we followed the same for consistency and clarity. Nonetheless, the sample complexity for our actor-critic algorithm is:

$$O\left(\frac{S^{4/3} A^{2/3} C_{PL}^{4/3}}{\lambda^{2/3} (1 - \gamma)^{16/3} \, k^{1/3}}\right).$$

For comparison, the iteration complexity for the exact gradient case is:

$$O\left(\frac{S \, C_{PL}^2}{c^2 (1 - \gamma)^6 \, k}\right),$$

as shown in Theorem 4 of Mei et al. (2022). We outline the high-level computation below:

From Lemma C.1, we have:

a_k \leq C \cdot \frac{S^{4/3} A^{2/3} C_{PL}^{4/3}}{\lambda^{2/3} (1 - \gamma)^{16/3} , k^{1/3}},

We thank the reviewer for the positive and thoughtful feedback.

We are glad that the reviewer finds our focus on the single-timescale actor-critic setting both practical and meaningful. We appreciate the recognition of our improved sample complexity and the Lyapunov-based analysis technique. We agree with the reviewer that this approach can inspire further work in similar settings.

Q1) The 2nd and 3rd row of Table 1 looks the same.

Thank you for pointing this out. We will merge the two in the final version.

Q2) In equation (3), the $z_k$ at the end of the first line seems redundant.

Thank you for noticing this. It is indeed a typo, and we will correct it in the final version.

Q3) The dimension of variables is obscure. Something like $A^k \in \mathbb{R}^{|S||A|}$ might make it clearer.

Thank you for the suggestion. We will include the dimensions of all variables in the final version.

Q4) Some references looks ill-formated. For example, it looks like that line 342-347 are referring to the same paper.

Thank you for pointing this out. We will fix it in the final version.

Q5) How does the analysis techniques compared to the analysis in previous works and why previous analysis cannot achieve the rate obtained in this paper?

The main limitation of the previous analysis by Chen and Zhao [2024] is that they treat the policy optimization objective as a general smooth non-convex function. Moreover, they follow the standard approach of bounding the average squared norm of the gradient. Their analysis does not leverage the gradient domination structure, or if used, it is only plugged in at the end—leading to a suboptimal convergence rate.

In contrast, the core innovation of our work is to exploit this structure directly when analyzing the iteration-wise drift of the actor.

Leveraging this additional structure required us to develop a novel methodology for solving the interdependent recursions, which in turn led to stronger results.

In summary, our analysis is more tailored to reinforcement learning, as it effectively incorporates the gradient domination structure—unlike the standard smooth optimization techniques used in the prior work.

Q6) Is there a sample-complexity lower bound for this kind of actor-critic algorithm?

The sample complexity lower bound for reinforcement learning is $O(\epsilon^{-2})$, as shown by Auer et al. (2008). However, to the best of our knowledge, there is no known lower bound specifically for single-time-scale actor-critic algorithms. Nonetheless, it is widely believed that the same lower bound applies in this setting as well.

We thank the reviewer for the encouranging feedback. We appreciate the time and effort spent on reviewing this paper. We are glad that the reviewer finds that the paper provides state-of-the-art complexity result to a challenging and more practical single-time scale algorithm.

We answer the questions below.

Q1) The paper is restricted to tabular setups. This means not applicable to environments such as robotics.

The reviewer is correct in noting that the current setting is not directly applicable to large-state problems such as those in robotics. The main limitation lies in the square-root state dependence of Gradient Dominant Lemma (GDL) 2.1. However, we agree that extending this lemma to continuous state spaces—potentially through embedding or an approximate version—is a promising direction for future research. Such an extension would also facilitate a non-tabular generalization of the exact gradient convergence results in Xiao et al. (2022) and Mei et al. (2022). As a result, our actor-critic complexity bounds could be extended to the non-tabular setting, with minor modifications to account for function approximation errors and other approximations. We thank the reviewer for this insightful question, which we intend to pursue in future work.

Q2) In certain situations, using multiple samples to estimate the critic can be beneficial such as DDPG. A discussion of these would be good.

We thank the reviewer for this insightful question. While many existing works on double-loop actor-critic methods rely on using a large number of critic updates per actor update, our work lies at the other extreme—using a single critic update per actor update. It is quite possible that the optimal balance lies somewhere between these two extremes, either generally or in specific contexts such as DDPG. We will include a discussion of this point in the final version and explore it further as part of our future work.

Q3) The authors claim that the analysis may be extended to bilvel RL setup. More discussion on that would be good.

Our work proposes a high-level approach for tackling bi-level problems such as min-max optimization, robust MDPs, and two- (or multi-) agent reinforcement learning:

Step 1: Formulate the interdependent recursions, as illustrated in Equation (3), for the relevant quantities.
Step 2: Identify a suitable Lyapunov function, as demonstrated in Line 274 — often the most creative and critical part of the analysis.
Step 3: Solve the Lyapunov recursion, as done in Lemma 4.4, to obtain the desired bound.

Lemma 4.4 can be extended to handle more general recursion structures , which we chose to omit for clarity. Additionally, we uncovered several useful insights during this process — for example, that such recursions often track the behavior of the corresponding ODE, and that appropriate learning rates can be chosen using a power-matching technique.

We will be glad to include a dedicated section in the appendix (along with a more general ODE-tracking lemma) in the final version.

Q4) Is there any path to extend the analyses to infinite state/action spaces?

As discussed in Q1, the key step in extending the analysis to infinite state-action spaces is to establish a Gradient Domination Lemma (either exact or approximate), since this is the only component that exhibits state dependence.

The rest of the analysis—such as applying a sufficient increase lemma under function approximation—is standard in the literature. One can derive the corresponding recursion and solve it with minor modifications to the existing framework.

Loosely speaking, the $\sqrt{S}$ term in GDL Lemma 2.1 corresponds to the diameter of the policy space, i.e., $\max_{\pi, \pi' \in \Pi} \lVert \pi - \pi' \rVert_2$. In the function approximation setting, it may be possible to replace this with the diameter of the parameter space, i.e., $\max_{\theta, \theta' \in \Theta} \lVert \theta - \theta' \rVert_2$. However, this substitution requires careful investigation, which we leave for future work.

Q5) What challenges do you anticipate if any in extending your analysis to bilevel RL setup?

We briefly outlined a possible approach for bi-level problems in Q3. We believe the first step—deriving the recursions—is likely to be straightforward, though potentially laborious. Identifying a suitable Lyapunov function, however, is likely the most challenging part. Once obtained, the recursion can be solved using techniques similar to our ODE tracking lemma.

That said, finding a Lyapunov function may not always be feasible or straightforward. Fortunately, it is possible to bypass this step by directly solving multiple recursions using an extended ODE tracking lemma. This would require applying the same methodology multiple times—essentially the same arguments used to prove the Lyapunov recursion. In fact, this was our original approach before we discovered the elegant Lyapunov function presented here.

We will gladly include a detailed section on this alternative route, along with the extended ODE tracking lemma, in the appendix of the final version.