On the Convergence of Continuous Single-timescale Actor-critic

(Claim 1: on new operator-based analysis.)

Operator-based analysis is employed not only to handle the lemmas in Appendix B but also to accommodate the continuous distribution throughout the proof. For instance, it is used in establishing Propositions 3.1 and 3.2.

Prior to our work, it remained unclear how to extend single-timescale actor-critic methods to continuous action spaces. This is precisely why (Chen et al, 2021) and (Chen & Zhao, 2024) consider continuous state spaces but restrict the action space to be finite—an uncommon and limiting assumption.

In analyzing the most challenging case of single-timescale actor-critic methods, one must rely on several previously established lemmas (see Appendix B) that state the regularity of the problem. However, these lemmas are derived for finite action space assume Lipschitz constants that scale with the number of actions ($|\mathcal{A}|$), which, however, becomes meaningless in the case of the uncountable continuous space. We observe that the dependence on $|\mathcal{A}|$ stems from the need to bound the evolution of the stochastic processes defined in Eq. (12) and Eq. (13) over the action space. This evolution is mainly governed by the policy $\pi_{\theta}$. We demonstrate (formally established in Proposition 4.4) that if the total variation distance between two policies is Lipschitz continuous, then the evolution of the stochastic process in the action space can be effectively controlled without assuming the finiteness of the action set. This novel insight and development allow us to extend several foundational lemmas (Appendix B) to the continuous action setting. Such extension is further enabled by the proposed operator-based analysis, which conveniently handles the continuous distribution throughout the proof, including in the verification of Propositions 3.1 and 3.2.

(Claim 2: on Markovian sampling in the discounted setting.)

We acknowledge that Markovian sampling in the discounted setting has been analyzed in [1]. Nonetheless, this does not weaken our contribution.

First, several key propositions essential for our analysis are not presented in [1]. For instance, Proposition 3.1 plays a central role in our framework, yet it is not established in [1]. Even Proposition 3.2, while stated in [1], is assumed without proof. In contrast, we rigorously establish these results within a continuous setting.

Furthermore, our work addresses Markovian sampling under a single-timescale formulation, whereas [1] considers the two-timescale case. As a result, the treatment of Markovian noise in our analysis is fundamentally different from those in [1]. In fact, our considered setting is significantly more challenging than the two-timescale case and requires the development of new analysis techniques.

We acknowledge that [1] is a valuable contribution. As emphasized in the Introduction, the analyses of single-timescale and two-timescale actor-critic methods are fundamentally different. Since Table 1 is intended to compare only single-timescale methods, we did not include [1] in the comparison.

(Claim 3: on Lyapunov function.)

We respectfully disagree with the claim that our use of a Lyapunov function is akin to the interconnected system approach. In our analysis, we sum the critic and actor errors into a unified loss function $\mathcal{L}$ and convert all error terms into a single inequality involving $\mathcal{L}$, as shown in Eq. (33). In contrast, (Chen & Zhao, 2024) track three distinct error terms and construct an interconnected system of three coupled inequalities. It remains unclear whether the latter case admits a Lyapunov-like formulation that combines the three errors into a single function and establishes a unified inequality.

That said, we agree that from a more abstract mathematical standpoint, all such approaches can be interpreted as sequences of intricate inequality manipulations.

(Q1: challenges in dealing with continuous action space.)

Previous results derived for finite action space assume Lipschitz constants that scale with the number of actions ($|\mathcal{A}|$), which, however, becomes meaningless in the case of the uncountable continuous space. We observe that the dependence on $|\mathcal{A}|$ stems from the need to bound the evolution of the stochastic processes defined in Eq. (12) and Eq. (13) over the action space. This evolution is mainly governed by the policy $\pi_{\theta}$. We demonstrate (formally established in Proposition 4.4) that if the total variation distance between two policies is Lipschitz continuous, then the evolution of the stochastic process in the action space can be effectively controlled without assuming the finiteness of the action set. This novel insight and development allow us to extend several foundational lemmas (Appendix B) to the continuous action setting. Such extension is further enabled by the proposed operator-based analysis, which conveniently handles the continuous distribution throughout the proof, including in the verification of Propositions 3.1 and 3.2.

(Q2: requirement to have i.i.d. samples from $\eta$.)

Thank you for your question. Note that existing analysis requires i.i.d. samples from the discounted state visitation distribution for updating the actor, not from the initial distribution. The former is unknown. It is difficult to directly sample it, even approximately, in a simulator given its form. The initial distribution is a predefined distribution over states, and its i.i.d sampling is easy. The key challenge here is how to sample from the unknown discounted state visitation distribution approximately. The assumption of a known initial distribution is standard in the discounted setting. As shown in Eq. (3), the objective function is defined as the integral of the value function $V_\theta(s)$, weighted by the initial state distribution $\eta$, over the state space. Accordingly, we assume access to $\eta$, which allows i.i.d. sampling from this distribution. This requirement might be removed by identifying a class of behavior policies for state sampling that are guaranteed to provide a good approximation to the true value functions and policy gradient estimate. The existing Markov chain $(\pi_\theta, \widehat{P})$ may serve as a special example to examine the desired characteristics that such distributions should satisfy. It will be our future research.

(Q3: on Assumption 4.3.)

Log-linear policies satisfy this assumption under the condition that the feature map $\phi(s,a)$ is bounded and the action space is finite. Moreover, as noted in our manuscript, certain continuous policy classes—such as the uniform distribution, truncated Gaussian distribution, and Beta distribution—can also satisfy this assumption.

(On other suggestions.)

Thanks for your advice. We will mention the use of linear function approximation to address large state-action spaces earlier. We will fix the time index of the policy parameter $\theta$, which is $\theta_t$.

Thank you for highlighting this interesting problem. Establishing optimality guarantees for AC or NAC methods typically requires the underlying optimization problem to be convex or to satisfy properties such as gradient domination. We view the convergence of AC and NAC to an optimal policy in continuous action spaces as an important direction for future work.

(On removing linear function assumption)

Thank you for your suggestion regarding the removal of the linear function approximation assumption for the value function. We are aware of recent works (e.g., Tian et al., 2023; Ke et al., 2024) that employ deep neural networks for value function approximation. However, these approaches often rely on additional assumptions (e.g., Tian et al., 2023) to ensure theoretical tractability. We plan to further investigate these results and explore how to extend our analysis to broader classes of function approximators under milder assumptions.

(Weakness & Q4: on single-simple)

1. The terminology ''single-sample" follows the seminal work [Olshevsky & Gharesifard, 2023], where they directly assume sampling from visitation distribution and stationary distribution for updating actor and critic, respectively. It refers to the fact that at each iteration, the critic and the actor are each updated using a single sample.
2. Our analysis can accommodate the case where ''a single sample generated from the same stochastic process is used to update both the actor and the critic'', as suggested by the reviewer. To achieve this, we can modify the sampling scheme so that the critic is also updated using the same samples from the Markov chain $(\pi_\theta, \hat{P})$ as the actor. We would like to highlight that our theoretical analysis would still apply under this alternative sampling scheme. The current presentation of sampling from $(\pi_\theta, P)$ for the critic update simply follows the existing setup in the literature of on-policy actor-critic analysis. The proposed modification can be viewed as an extension to analyze a special off-policy version.
3. Sampling from two Markov processes does not force the decoupling or simplify the analysis. In fact, our analysis directly copes with the coupling between the actor and critic, which can be seen in the Proof Sketch. In particular, the term $I_5$ in the critic error analysis is coupled with the actor error and is ultimately bounded by $\mathcal{O}(\mathbb{E}[\\|\Delta_t\\| \\|\nabla J(\theta_t)\\|])$ in Eq.(26). Conversely, $I_4$ in the actor error analysis is coupled with the critic error and simplifies to $\mathcal{O}(\mathbb{E}[\\|\nabla J(\theta_t)\\| \\|\Delta_t\\|])$ in Eq.(30). Due to this mutual dependence, we define a novel Lyapunov function that captures both the actor and the critic errors, enabling a unified analysis of their convergence.
4. Our work is by far the most practical analysis, in the sense that we address the most widely used single-timescale discounted reward formulation, and our analysis does not require sampling from unknown distributions (i.e., the stationary distribution and the discounted state visitation distribution). Moreover, as mentioned in Point 2, our analysis still holds with minor modifications to accommodate the case of using the same samples for updating both critic and actor.

(Q1: Key innovations for extending previous results to continuous space)

Previous results derived for finite action space assume Lipschitz constants that scale with the number of actions ($|\mathcal{A}|$), which, however, becomes meaningless in the case of the uncountable continuous space. We observe that the dependence on $|\mathcal{A}|$ stems from the need to bound the evolution of the stochastic processes defined in Eq. (12) and Eq. (13) over the action space. This evolution is mainly governed by the policy $\pi_{\theta}$. We demonstrate (formally established in Proposition 4.4) that if the total variation distance between two policies is Lipschitz continuous, then the evolution of the stochastic process in the action space can be effectively controlled without assuming the finiteness of the action set. This novel insight and development allow us to extend several foundation lemmas (Appendix B) to the continuous action setting. Such extension is further enabled by the proposed operator-based analysis, which conveniently handles the continuous distribution throughout the proof, including in the verification of Propositions 3.1 and 3.2.

(Q2: on the notation)

Thanks for pointing out the typo. It should be $\hat{P}(\cdot | \hat{s}_t, \hat{a}_t)$.

(Q3: Relation to existing actor-critic analyzed in the literature)

Yes, it is correct. This is the same sampling scheme also employed in [Shen et al. 2023]. However, their analysis only handles the two-timescale AC algorithm on finite state-action space. In Konda's thesis, this artificial MDP is only constructed to utilize its property that its average reward equals the original MDP's discounted reward induced by $(\pi_\theta, P)$. It's not analyzed for convergence. In addition, [Zhang et al. 2020a] employ a different sampling scheme to approximate the discounted occupancy measure. However, their approach relies on a multi-sample procedure. Moreover, they also require a simulator with a state-reset function.

Existing literature on analyzing AC requires samples from the unknown visitation distribution for updating actor, which requires a simulator as well. [Shen et al. 2023] needs to assume the same simulator as ours. For i.i.d. sampling [Chen et al., 2021; Olshevsky & Gharesifard (2023)], one has to run the simulator for sufficiently many steps under the current policy $\pi_{\theta_t}$ to approximate the visitation distribution. This inevitably takes a very long time and requires significant modification of the simulator as well. But our setting only requires a reset, which is much simpler and more time-efficient.