acceptodds
Withdrawn from ICLR 2027

A Concentration Bound for Two-Timescale Actor-Critic Algorithm

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Significant research effort has been directed in recent years towards establishing both asymptotic and non-asymptotic convergence guarantees for two-timescale actor–critic algorithms, where the actor recursion is run on a slower timescale than the critic recursion. This work derives a uniform all-time concentration bound for the actor-critic algorithm with function approximation in the long-run average-reward setting. This bound helps us analyze the behavior of the actor parameter with high probability. We show that, after some finite time, the actor parameter enters a safe region and remains within it thereafter with a high probability. Specifically, with probability at least , the actor error is for all and sufficiently large . We also present experimental results demonstrating that the aforementioned actor error diminishes with the number of actor-parameter updates.

Primary area:
reinforcement learning
Keywords:
Actor-critic algorithm, linear function approximation, concentration bound

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 2 reviews, above 0% of the others.
Reviewer_BEYqOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper establishes the concentration of two time scale actor critic algorithm.

Critical strengths

I do not see any strengths.

Critical weaknesses

The result does not make much theoretical sense. The lower bound on probability in Theorem 1 has a fixed constant, which is not clear what it means theoretically. Corollary 1 establishes a high probability bound that is polynomial in 1/\sqrt{\epsilon_2}. This result is not interesting, as we would like to get a poly log(1/\sqrt{\epsilon_2}). Otherwise, this result can be created by the combination of mean square bound and Markov inequality. Also, the result in Corollary 1 has a fixed constant proportional to (1/n_0)^{0.25} which does not make sense.

Questions for authors

Could the authors derive a much stronger concentration bound for actor critic? Could they extend their result to natural actor critic?

Reviewer_SozKOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies the convergence of a two-timescale actor-critic algorithm in the average-reward setting with linear function approximation for the critic. Its main contribution is a high-probability concentration bound on the actor parameters, which is uniform over all iterations after a sufficiently large initial time. Under several assumptions, including strong concavity of the performance objective, the authors establish that the actor iterates remain within a neighborhood of an optimal parameter with high probability. The paper also presents experiments on three Gym environments to illustrate the convergence of the actor parameters.

Critical strengths
  • Establishing uniform-in-time concentration guarantees for actor-critic algorithms is an interesting theoretical problem.

  • The analysis considers Markovian sampling and accounts for errors arising from the critic and average-reward estimation.

Critical weaknesses
  • My main concern is Assumption 5, which requires the performance objective L(θ)L(\theta) to be globally mm-strongly concave over $ \mathbb{R}^d$. This assumption is not satisfied by standard policy optimization problems. Even in the simpler discounted setting, the policy optimization objective is generally non-concave with respect to the policy parameters. More importantly, the assumption appears to be mathematically inconsistent with the setting considered in the paper. Since rewards are bounded by UrU_r, the average-reward objective satisfies ∣L(θ)∣≤Ur,∀θ∈Rd.|L(\theta)| \leq U_r, \forall \theta \in \mathbb{R}^d. However, global strong concavity implies L(θ)≤L(θ0)+⟨∇L(θ0),θ−θ0⟩−m2∥θ−θ0∥2.L(\theta) \leq L(\theta_0) + \langle \nabla L(\theta_0),\theta-\theta_0\rangle -\frac{m}{2}\|\theta-\theta_0\|^2. The right-hand side tends to −∞-\infty as ∥θ∥→∞\|\theta\|\to\infty, contradicting the boundedness of LL. Thus, Assumptions 5 and the bounded-reward setting cannot simultaneously hold as stated. This is not a minor technical restriction: the main convergence result critically relies on this assumption. Consequently, I do not see a nontrivial class of MDPs satisfying the complete set of assumptions under which the theorem can be applied.

  • Without the strong concavity assumption, the main technical ingredients do not appear to substantially advance the existing finite-time analysis of actor-critic algorithms, particularly the work of |1]. The proof relies on a decomposition of the actor error into martingale noise, Markovian sampling error, critic estimation error, and average-reward estimation error. Such decompositions and the control of coupled actor-critic recursions are already well established in the literature. The principal distinction is the conversion of these error estimates into an all-time parameter-distance guarantee. However, this step relies crucially on the problematic strong concavity assumption. The paper should identify more precisely which technical arguments are genuinely new relative to existing analyses.

  • The presentation is particularly difficult to follow. Several constants and technical conditions appear immediately before the main theorem without sufficient explanation of their roles. The proof sketch contains lengthy expressions involving multiple error terms and auxiliary martingale sequences, but provides little intuition about the key analytical difficulties or how they are resolved. The relationship between the different lemmas, the choice of learning rates, and the resulting concentration bound is not explained clearly. The main text is dominated by technical manipulations rather than an accessible account of the proof strategy. In its current form, I found it unnecessarily difficult to identify the actual mathematical contribution.

  • Theorem 1 contains residual terms depending on the critic approximation error and the mixing parameters. However, the simplified rate emphasized in the abstract and Corollary 1 omits these contributions. The authors should clarify precisely under which additional conditions these terms can be neglected. In particular, the assumption b≤ϵappb\leq\epsilon_{\mathrm{app}} is unusual, since it connects the mixing constant to the approximation error without a clear justification. It is also unclear how the exact-representation case is intended to fit this assumption when b>0b>0.

  • The discussion overlooks several important recent developments in actor-critic theory. In particular, the papers [2] and [3] should be discussed. Although these works study different settings, they provide important context for assessing the assumptions, convergence guarantees, and novelty of the present paper.

[1] Chen, Xuyang and Zhao, Finite-Time Analysis of Single-Timescale Actor-Critic, NeurIPS 2023

[2] Kumar et al, On the Convergence of Single-Timescale Actor-Critic, NeurIPS 2025

[3] Labbi et al. Refined Analysis of Entropy-Regularized Actor-Critic, ICML 2026

Questions for authors
  • Can the authors provide a concrete nontrivial example of a class of bounded-reward MDPs whose average-reward objective satisfies Assumption 5 globally over Rd\mathbb{R}^d? How do they reconcile this assumption with the boundedness of the objective?

  • Is it possible to obtain a meaningful concentration guarantee without assuming strong concavity?

  • What is the main technical novelty compared with the finite-time actor-critic analysis of |1]?

  • Under which precise conditions do the approximation-error terms vanish in the simplified bound presented in Corollary 1?

[1] Chen, Xuyang and Zhao, Finite-Time Analysis of Single-Timescale Actor-Critic, NeurIPS 2023

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.