PaperlayerView exact revision on arXiv

Source-linked AI summary

A Concentration Bound for Two-Timescale Actor-Critic Algorithm

Prashansa Panda, Shalabh Bhatnagar

arXiv:2609.29117v1cs.LG

TL;DR

Finite-time high-probability guarantees are an active line of work for two-timescale actor–critic algorithms. This paper derives an all-time concentration bound for the actor parameter with linear critic approximation in a long-run average-reward setting. The bound keeps the actor in a safe region after a specified time with high probability.

  • Problem

    Finite-time, high-probability convergence guarantees for two-timescale actor–critic algorithms are a focus beyond their asymptotic convergence analyses.

    Source: §1 · p. 1

  • Method

    The paper analyzes a two-timescale actor–critic algorithm with a linear critic approximation for finite-state, finite-action MDPs in the long-run average-reward setting.

    Source: §1 · p. 2, §3.1 · p. 2, §3.2 · p. 3

  • Results

    After a specified time, the actor parameter enters a safe region and remains there with high probability under the paper’s all-time bound.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The bound characterizes actor-parameter behavior uniformly over time after the specified time instant.

    Source: §7 · p. 9

    The analysis assumes uniform ergodicity of the policy-generated Markov chain.

    Source: §4.1 · p. 4

Abstract

from arXiv · show

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 high probability. Specifically, with probability at least $1-\epsilon_1-\epsilon_2$, the actor error $\Vert \theta_k-\theta^{*}\Vert$ is $O\left(\frac{n_0^{3/4}}{k}\frac{1}{\sqrt{\epsilon_2}}+\left(\frac{1}{n_0}\right)^{1/4}\log^{1/4}\left(\frac{1}{\epsilon_1}\right)+\left(\frac{1}{n_0}\right)^{1/4}\right)$ for all $k\geq n_0$ and sufficiently large $n_0$. We also present experimental results demonstrating that the aforementioned actor error diminishes with the number of actor-parameter updates.

1 INTRODUCTION

Actor–critic methods combine policy and value learning, with the actor slower than the critic. This paper establishes an all-time, high-probability bound for the actor parameter in a linear-function-approximation, long-run average-reward setting.

1 INTRODUCTION

  • Actor–critic methods combine policy-based actor learning with value-based critic feedback, while separating their learning timescales to support stability.The actor learns a policy; the critic estimates the value function for the current policy.Source: §1 · p. 1
  • Finite-time analyses provide sample-complexity guarantees and optimal learning rates, while concentration bounds provide high-probability convergence bounds.Source: §1 · p. 2
  • The paper derives a high-probability actor-parameter bound that holds uniformly after a specified time, so entry into a safe region is followed by remaining there with high probability.The analysis concerns a two-timescale actor–critic algorithm with linear critic approximation in the long-run average-reward setting.Source: §1 · p. 2

2 RELATED WORKS

Prior work established asymptotic analyses for actor–critic algorithms and expanded finite-time results across several settings. The paper situates its contribution alongside this work and concentration bounds for temporal-difference learning.

2 RELATED WORKS

  • Lookup-table actor–critic methods and their first asymptotic convergence analysis were introduced by Konda & Borkar (1999), followed by function-approximation analysis by Konda & Tsitsiklis (2003).Source: §2 · p. 2
  • Finite-time analyses cover two-timescale actor–critic under Markovian sampling, single-timescale methods, natural policy gradients, and decentralized actor–critic methods.Reported sample complexities include ˜O(ϵ−2.5) for Wu et al. (2022) and ˜O(ϵ−2) for Chen & Zhao (2023) and Luo & Li (2023).Source: §2 · p. 2
  • Non-asymptotic work also studied two-timescale natural actor–critic with a ˜O(ϵ−6) sample-complexity bound and three-timescale constrained variants under Markovian sampling.Source: §2 · p. 2
  • Concentration bounds have been developed for TD(0) with linear function approximation, including a stochastic-approximation bound applicable when step sizes are not square-summable.The cited TD(0) bounds include work by Korda & La (2015), Thoppe & Borkar (2019), and Chandak & Borkar (2026).Source: §2 · p. 2

3 BACKGROUND

The paper formulates a finite-state, finite-action average-reward MDP and uses a linear critic within a two-timescale actor–critic algorithm. The critic and average-reward updates run faster than the actor updates.

3.1 MARKOV DECISION PROCESS

  • The setting is a finite-state, finite-action MDP with bounded single-stage rewards, stationary randomized policies, and a long-run average-reward objective.Source: §3.1 · p. 2

3.2 FUNCTION APPROXIMATION

  • The critic approximates the state-value function linearly as ϕ(s)^T v, using a known feature map to represent values without solving for exact values.Source: §3.2 · p. 3

3.3 TWO-TIMESCALE ACTOR-CRITIC ALGORITHM

  • The algorithm uses Robbins–Monro step sizes with β_t = o(α_t) and γ_t = Kα_t, placing the actor on the slower timescale than the critic and average-reward updates.The critic estimate is projected onto a compact convex set to ensure boundedness.Source: §3.3 · p. 3

4 ASSUMPTIONS AND MAIN RESULT

The analysis uses assumptions on features, critic stability, approximation error, ergodicity, and performance-function concavity. It establishes a concentration-bound result and a corollary under specified learning-rate and time conditions.

4.1 ASSUMPTIONS

  • The assumptions include bounded state features, a negative-definite critic matrix that supports existence and uniqueness of v*(θ), and bounded linear-approximation error.The performance function is also assumed to be strongly concave.Source: §4.1 · p. 4
  • The analysis assumes uniform ergodicity of the Markov chain generated by the policy and transitions.Source: §4.1 · p. 4

4.2 CONCENTRATION BOUND RESULTS

  • The learning rates use α_t and γ_t proportional to (1+t)^−ν and β_t proportional to (1+t)^−σ, with 0 < ν < σ ≤ 1.Source: §4.2 · p. 4
  • Theorem 1 asserts the existence of finite positive constants C1, C2, C3, C4, C5, and D under conditions 0 < δ ≤ 1, ε > 0, and sufficiently large n0 satisfying 2mβn0 < 1.Source: §4.2 · p. 5
  • The actor-error analysis depends on critic error and average-reward estimation error, which the paper also analyzes to establish Theorem 1.Source: §4.2 · p. 5
  • Corollary 1 specializes the result to σ = 1 and ν = 0.5, with ε ≥ 1 and sufficiently large n0 satisfying 2mβ_n0 < 1.Source: §4.2 · p. 5
  • The proof sketch formulates the actor update as a stochastic-approximation iteration, bounds deviations from an auxiliary sequence and from θ*, then combines those bounds.Source: §4.2 · p. 5

5 PROOF SKETCH OF MAIN RESULT AND COROLLARY

The proof treats the actor update as a stochastic-approximation iteration, separates noise sources, and uses an auxiliary sequence to establish a bound that holds after n0.

5 PROOF SKETCH OF MAIN RESULT AND COROLLARY

  • The actor update is formulated as a stochastic-approximation iteration, with a filtration defined so the noise sequence is a martingale difference sequence.Source: §5 · p. 6
  • The proof distinguishes error from martingale noise from error due to Markov noise.Source: §5 · p. 6
  • It bounds actor error by splitting it into deviation from an auxiliary sequence and that sequence’s distance from θ*, whose contraction factor is α.Source: §5 · p. 6
  • For sufficiently large n0, the proof concludes that its actor-error bound holds for every k ≥ n0, ignoring approximation error.The passage does not include the bound’s expression.Source: §5 · p. 9

6 EXPERIMENTAL RESULTS

The experiments evaluate actor-parameter convergence in three continuing average-reward environments. Across the environments, the estimated actor error decreases smoothly with iteration.

6 EXPERIMENTAL RESULTS

  • The three environments are reformulated as continuing average-reward tasks by restarting at a randomly chosen non-terminal state when an episode ends.Source: §6 · p. 9
  • Across CartPole-v1, FrozenLake-v1, and Blackjack-v1, the actor-parameter error shows a smooth, monotonically decreasing trend over iterations.The plotted error uses an estimate of θ* obtained by running the algorithm for many iterations across independent seeds and averaging the resulting parameters; Figure 2 averages ten training runs and shows one standard deviation.Source: §6 · p. 9

7 CONCLUSIONS AND FUTURE WORK

The paper reports a first finite-time, high-probability convergence bound for two-timescale actor-critic and says it holds uniformly after a specified time. It identifies extensions to other actor-critic variants as future work.

7 CONCLUSIONS AND FUTURE WORK

  • The authors report the first finite-time, high-probability convergence bound for two-timescale actor-critic, holding uniformly after a specified time.Source: §7 · p. 9
  • Future work could establish analogous concentration bounds for two-timescale natural actor-critic and three-timescale constrained actor-critic algorithms.Source: §7 · p. 9
  • Such bounds could clarify how learning rates, constraints, and natural gradients affect concentration.Source: §7 · p. 9

A.1 PROOF OF MAIN RESULT

The proof rewrites the actor update as a stochastic approximation and bounds its deviation from an auxiliary sequence under a sufficiently large starting index.

A.1 PROOF OF MAIN RESULT

  • The actor update is formulated as a stochastic-approximation iteration with a mean update term and a martingale-noise term.Source: §A.1 · pp. 12–13
  • It defines a filtration from the actor parameters, states, and actions, and identifies the noise sequence as a martingale difference sequence.Source: §A.1 · p. 13
  • The proof separates martingale-noise error from Markov-noise error when bounding the actor’s deviation from the auxiliary sequence.Source: §A.1 · pp. 13–14
  • The proof assumes 2mβ_n0 < 1 and splits actor error into deviation from z_n and the distance from z_n to θ*.Source: §A.1 · p. 14

A.2 PROOF OF COROLLARY

This appendix section assembles the corollary and supporting lemmas through intermediate inequalities and term-by-term arguments. The supplied passages state the corollary’s condition on n0 but do not include its full bound.

A.2 PROOF OF COROLLARY

  • The corollary’s final inequality is stated for k ≥ n0 and sufficiently large n0 satisfying 2mβ_n0 < 1, while ignoring approximation error.The displayed inequality itself is not included in the supplied passage.Source: §A.2 · p. 29

A.3.1 PROOF OF LEMMA 1

  • Lemma 1’s proof sets γ1 = 1, ϵ = 1, and C = exp(2UvB), then invokes a result of Chandak & Borkar (2026).The supplied passages identify constants D1 through D4 and define D as their minimum, but omit the associated inequalities.Source: §A.3.1 · pp. 29–31

A.3.2 PROOF OF LEMMA 2

  • Lemma 2’s proof expands the actor-error recursion and bounds terms involving reward estimation, critic error, approximation error, and a centered fluctuation.The displayed inequality includes a contraction factor (1 − 2mβt) on the squared actor error.Source: §A.3.2 · p. 32

A.3.3 PROOF OF LEMMA 3

  • Lemma 3’s proof is organized around terms Ia, Ib, and Ic, followed by a combined result.The supplied passages do not include the term bounds or the final expression.Source: §A.3.3 · p. 38

A.3.4 PROOF OF LEMMA 4

  • Lemma 4’s proof invokes Wu et al. (2022) for its first inequality and cites assumption 3(c) for its third.It also discusses differentiability and boundedness of the stationary distribution and average reward for finite MDPs under stated policy conditions.Source: §A.3.4 · p. 39

A.3.5 PROOF OF LEMMA 5

  • Lemma 5’s proof defines the policy-averaged reward r̄θ(s) and analyzes several terms, including comparisons with earlier terms and Wu et al. (2022).The supplied excerpts do not show the resulting bounds.Source: §A.3.5 · pp. 40–41

A.3.6 PROOF OF LEMMA 6

The supplied excerpts show the critic update rule and fragments of a term-by-term proof for Lemma 6. They do not state the lemma’s conclusion.

A.3.6 PROOF OF LEMMA 6

  • The critic update rule is introduced, and one displayed term combines an expected temporal-difference expression with the average-reward estimation error.The expression includes the feature vector ϕ(st) and the difference L(θt) − Lt.Source: §A.3.6 · pp. 41–42
  • The cited passages report putting Lemma 5 results into an inequality, gathering all terms, and rearranging the terms, without showing the resulting expression in the supplied excerpts.Source: §A.3.6 · pp. 42, 44, 45

A.3.7 PROOF OF LEMMA 7

This section identifies the actor and critic architectures and learning-rate schedules used in the experiments. Feature representations vary across CartPole, FrozenLake, and Blackjack.

A.3.7 PROOF OF LEMMA 7

  • Table 1 reports the actor and critic architectures and learning-rate schedules used in each experimental environment.The supplied passages give the table’s scope but not its individual entries.Source: Table 1 · p. 47, §A.4 · p. 47

A.4 HYPERPARAMETERS

  • CartPole uses a shared 11-dimensional actor–critic feature map, while FrozenLake uses 16-dimensional one-hot state features for the critic.The CartPole map includes a bias, normalized state variables, their squares, and two selected interactions; FrozenLake has one critic parameter per state.Source: §A.4 · p. 47
  • Blackjack uses a shared 7-dimensional actor–critic feature map built from player and dealer variables, an ace indicator, squared variables, and one interaction.Source: §A.4 · p. 47
Loading 2609.29117v1…