Provable Convergence of Single-Timescale Neural Actor-Critic in Continuous Spaces

(W1: on the choice of $c$)

For THM 3.9 to hold, it is sufficient to set $c$ smaller than a problem-dependent constant, as specified in Eq. (34) of our revised manuscript (Eq. (30) of the original submission). The complex constant is only an upper bound of $c$, and can be easily satisfied by choosing $c$ a sufficiently small positive number, as is commonly done in practice. Intuitively, it indicates that a small stepsize will be conducive to stable learning. In our experiment, we set $c=1$, which produced satisfactory simulation results.

(W2: on the dependence of $m$)

Indeed, the neural network approximation error, denoted by $\epsilon_{\rm app}$, also depends on the neural network width $m$. If $m$ is too large, the neural network's approximation ability will deteriorate. However, deriving a more analytical bound for $\epsilon_{\rm app}$ in terms of $m$ remains an open problem. Our results are better interpreted as characterizing the analytical convergence rate within the range where the increase of $m$ does not significantly increase $\epsilon_{\rm app}$. Moreover, we empirically show the impact of $m$ through a newly added inverted pendulum example (see Section 5). It demonstrates that the initial increase of $m$ (for $m\le 300$) reduces the learning error, but worsens the performance when $m$ is too large ($m > 300$).

(W3: on the novelty of the proof)

Thank you for your advice. We provided a proof sketch in our updated manuscript in Appendix. We highlight the new techniques developed in detail and labeled in bold for your reference. We would like to summarize our novelty in the following: (1) we formulate a general condition in Assumption 4.7(c) and show that it is satisfied by a broad class of neural network policies in continuous spaces, as detailed in Proposition 4.8, which plays a crucial role in the proof. (2) We developed new operators to efficiently handle the complexities of continuous settings. (3) To address Markovian noise in continuous settings, we proved a sharp bound on the distance between stationary distributions, as characterized by Lemma C.1. These techniques have never been developed in the single-timescale actor-critic framework. They are the enablers for the analysis of the continuous state and action spaces.

(W4: on the experiment)

Thanks for your suggestion. As already mentioned in the above, we experimented with the classic "Pendulum" benchmark environment to validate our theoretical findings (Section 5). This environment features continuous state and action spaces. Both the critic and actor are parameterized using the neural network structure defined in Eq. (5) of our paper. We adopt a step size of $5 \times 10^{-6}$ for both the critic and actor, which is a single-timescale setting. The results demonstrate the convergence of this single-timescale neural actor-critic algorithm in continuous spaces when the neural network width $m$ is sufficiently large ($m\ge 200$). We hope this experiment is illustrative.

Thanks for your response. Note that this rate is only an upper bound. The actual convergence rate in terms of $m$ can be faster. Meanwhile, the convergence rate is also strongly affected by various randomness in the learning process, such as the sampling of the actions. Therefore, experiments show exactly match of the order is difficult, if not impossible. Nevertheless, we are able to demonstrate that the learning error decreases as m increases (for $m \in (10, 400)$) . This relationship is well captured by our theorectical results.

(Q3: on Assumption 4.6)

Assumption 4.6 states that the induced Markov chain is geometrically mixing, which holds for both finite and continuous cases. To justify this assumption in the continuous space, we note that all the distributions specified by the Ornstein–Uhlenbeck process satisfy this property. The OU process can be defined as follows

$

dX_{t}=\theta_{\pi}(\mu_{\pi}-X_t)dt+\sigma d W_t,

$

where $\theta_{\pi}>0$ and the drift $\mu_{\pi}$ are induced by the policy $\pi$. This process converges to a Gaussian distribution with the exponential mixing time. Moreover, it can also be shown that this property holds for more general diffusion processes[1].

(Q4: on Assumption 4.5)

This assumption was first introduced by us for the continuous setting with general function approximation classes. To demonstrate its connection to exploration, we show that if exploration is insufficient, the assumption fails to hold. Consequently, when the assumption holds, it implies sufficient exploration. First note that the operator $D_{\theta}$ essentially multiplies the stationary distribution $\mu_{\theta}$ to the function on its right (see the definition in Eq. (1) in the manuscript). If the policy $\pi_{\theta}$ does not sufficiently explore, there exists a subset of the state space $U \subset \mathcal{S}$ such that $\mu_{\theta}(U)=0$. Furthermore, we can choose $\widehat{V}(\omega)$ such that $\widehat{V}(\omega;s) = 0, \forall s \in \mathcal{S}\setminus U$ and $\widehat{V}(\omega;s) \ge 0, \forall s \in U$. With this choice, the left-hand side of the inequality evaluates to 0, while the right-hand side becomes positive. This violates the condition stated in Assumption 4.5. Thus, the contrapositive holds: if Assumption 4.5 is satisfied, it ensures sufficient exploration of the state space under the policy $\pi_\theta$.

Note that sufficient exploration assumption is standard in the literature of analyzing the convergence of on-policy RL algorithms. We can also drop this condition by analyzing the off-policy version of the algorithm under some sufficiently-exploring behavior policy that can be arbitrarily specified, and relates to the target policy by importance sampling. However, this is not the core focus of the problem. Therefore, we adopt Assumption 4.5 directly and concentrate on the primary challenge of analyzing the algorithm in the continuous state-action space.

Thanks for taking your time to review our paper. We are looking forward to your reply and we would be delighted to address any further concerns during the remaining discussion time.

[1] Pierre Del Moral and Denis Villemonais. Exponential mixing properties for time inhomogeneous diffusion processes with killing. 2018

(Q1: on Assumption 4.7)

Thank you for seeking clarification. Compared to the standard tabular case, we proposed a more general condition in Condition (c) to handle continuous policies. It holds for a broad class of policy functions as proved in Proposition 4.8. Conditions (a) and (b) can be easily verified through direct computation. For example, Assumption 4.7 can be satisfied by truncated Gaussian distributions with bounded mean values parameterized by MLPs or Transformers, and we adopt this parameterization for the policy in our newly added experiment section. Moreover, a uniform distribution with an interval length $\theta > 0$ also fulfills Assumption 4.7.

(Q2: on the novelty of the analysis)

Our novelty lies in the following: (1) we formulate a general condition in Assumption 4.7(c) and show that it is satisfied by a broad class of neural network policies in continuous spaces, as detailed in Proposition 4.8, which plays a crucial role in the proof. (2) We developed new operators to efficiently handle the complexities of continuous settings. (3) To address Markovian noise in continuous settings, we proved a sharp bound on the distance between stationary distributions, as characterized by Lemma C.1. These techniques have never been developed in the single-timescale actor-critic framework. They are the enablers for the analysis of the continuous state and action spaces.

We would like to highlight that our work extends beyond simply combining existing methods. In fact, (Chen&Zhao, 2024) only considers the learning with the linear function approximation. This strong assumption greatly simplifies the assumptions and transfers the dynamic analysis of the actor and critic to the corresponding simple matrix analysis. (Tian et al., 2024) focuses on the neural network learning problem in the discounted case and i.i.d. sampling of the actor. We note that the discounted problem greatly relieves the rate analysis of the critic analysis due to the well-defined Bellman equation in this case. In contrast, our work considers the most general setting. The convergence analysis of the neural network is coupled with the non-i.i.d. sampling and the additional reward estimation error from the Bellman equation of the time-average MDPs. We are the first to integrate neural network estimation analysis into the coupling relationship between three error sources, including the reward estimation error, critic error, and actor error defined in Eq. (12). Moreover, we established sufficient conditions for convergence over an infinite action space, a result not previously achieved. Our work bridges the gap between theoretical analysis and practical applications.

(W1: add experiment)

Thanks for your suggestion. We added an experiment using the classic "Pendulum" benchmark to validate our theoretical findings (Section 5). This environment features continuous state and action spaces, aligning well with the focus of our study. Both the critic and actor are parameterized using the neural network structure defined in Eq. (5) of our paper. We adopt step sizes of $5 \times 10^{-6}$ for both the critic and actor, resulting in a single-timescale setting. The results demonstrate the convergence of the considered single-timescale neural actor-critic algorithm in continuous spaces when the neural network width $m$ is sufficiently large ($m\ge 200$). This experiment aims to illustrate the practical efficacy of the algorithm and support our theoretical results.

(W2: on the global convergence)

Thanks for pointing out the two relevant works. The provided reference [1] additionally assumes strong conditions on the objective function -- the well-known gradient domination lemma, which directly guarantees global convergence when the gradient approaches zero and simplifies the analysis. However, this property does not hold in general. For instance, one prerequisite for the gradient domination lemma is that the initial distribution must be strictly positive across all states---a condition that is unmet in our continuous setting. The provided reference [2] only considers the vanilla policy gradient algorithm, which is not of the actor-critic structure and does not parameterize and estimate the critic. Therefore, their optimization landscapes are significantly different from our considered problem.

(W3: on the activation function)

Thanks for your advice. To illustrate the practicality, we experiment with the tanh activation function which is nonlinear and satisfies the smoothness assumption.

(W4: on Assumption 4.3)

Assumption 4.3 does not require the original value functions to be smooth with respect to the underlying parameter. Meanwhile, we would like to clarify that Assumption 4.3 only assumes the Lipschitz continuity and Lipschitz continuous gradient of the optimal critic parameter with respect to the actor parameter, and does not require uniform boundedness of the optimal parameters.

(W5: on Assumption 4.4) Thank you for your careful reading. This was a typo. Our proof does not require this condition to hold for all individual states; it only requires the norm defined over the state space to hold (that is, independent of any individual state). We have corrected this in the manuscript.

(Q1: on the measure $d(a \times s')$)

In Eq. (1), the measure $d(a \times s')$ represents the joint measure defined on the space of actions $a$ and subsequent states $s'$. It is used exchangeably with $dads'$.

(Q2: on the type value of $c$)

In the theoretical analysis, $c$ is set to be smaller than a problem-dependent constant, as specified in Eq. (34) of our revised manuscript (Eq. (30) of the original submission). In our experiment, we set $c=1$, which produced satisfactory simulation results.

(Q1: on the term $\pi_{\theta}-1$)

Thank you for the careful reading. It is indeed a typo, which should be $1-\pi_\theta$ as can be seen from our proof in Line 1178. We have updated Assumption 4.5 and labeled it with red color for your reference in the newly submitted revised manuscript. Sorry for the confusion caused and thanks for pointing out the issue.

(Q2: on the term $\widetilde{\mathcal{O}}(\frac{1}{\sqrt{m}})$)

Thanks for seeking clarification. The term $\widetilde{\mathcal{O}}(\frac{1}{\sqrt{m}})$ comes from the $H_v$-Lipschitz continuous gradient $H_v=\widetilde{\mathcal{O}}(\frac{1}{\sqrt{m}})$ of the critic neural network parameterization (see Lemma C.5, Page 16 of the revised manuscript). We have provided additional explanation of this derivation on Page 26 of the revised manuscript to enhance readability.