AI Research Portal

This paper establishes non-asymptotic bounds for the accuracy of normal approximation for linear two-timescale stochastic approximation (TTSA) algorithms. It considers both martingale difference and Markov noise settings, analyzing both the last iterate and Polyak-Ruppert averaged regimes. The core idea involves decomposing the statistics into a linear part and a small perturbation, then bounding the convex distance to a Gaussian distribution. The main empirical claim is that the normal approximation rate for the last iterate improves with increased timescale separation, while it decreases in the Polyak-Ruppert averaged setting, achieving rates up to n⁻¹/⁴ (martingale noise) and n⁻¹/⁶ (Markov noise) up to logarithmic factors. The theoretical results are demonstrated to be applicable to reinforcement learning algorithms like GTD and TDC.

The paper addresses several bottlenecks in the analysis of stochastic approximation (SA) algorithms:

Asymptotic nature of existing Gaussian approximation results: Classical results on Gaussian approximation (GAR) for SA algorithms are asymptotic and do not provide convergence rates, which limits their utility for statistical inference and constructing confidence intervals.

Derivation of non-asymptotic bounds for the accuracy of normal approximation for Polyak-Ruppert-averaged TTSA (√(θn – θ*)) and last iterate (βn¹/²(θn – θ*)) under martingale-difference noise assumptions, in terms of convex distance.
Demonstration that the normal approximation for the last iterate improves as timescale separation increases, achieving a convergence rate of order up to n⁻¹/⁴, up to log n factors.
Demonstration that Polyak-Ruppert averaged TTSA iterates achieve the same rate of normal approximation (n⁻¹/⁴ up to log n factors), but require timescales βk and γk to coincide up to a constant factor.
Generalization of the obtained results for normal approximation for averaged TTSA and the last iterate to the setting of Markov noise, showing a convergence rate of order up to n⁻¹/⁶, up to logarithmic factors, with the same conclusion regarding timescale separation. This is reported as the first result on the normal approximation rate for TTSA with Markov noise.
Provision of high-order moment bounds for the error of linear TTSA algorithms.

The method for establishing Gaussian approximation (GAR) for Two-Timescale Linear Stochastic Approximation (TTSA) algorithms involves a general scheme for proving normal approximation by decomposing the statistic of interest into a linear part and a small perturbation.

General Scheme for Gaussian Approximation: The paper considers vector-valued nonlinear statistics T(X1,..., Xn) ∈ Rd, which can be represented as: T = W + D where W is a linear statistic of the random variables X1,..., Xn, and D is a small perturbation. The approximation quality is measured using the convex distance ρConv(μ, ν) = supB∈Conv(Rd) |μ(B) – ν(B)|. The problem of estimating ρConv(W + D, N(0, I)) is reduced to:

Estimating ρConv(W, N(0, I)).
Estimating moments E[||D||P] for some p > 1.

TTSA Algorithm Formulation: The linear two-timescale SA problem aims to find a solution (θ*, w*) to the system of linear equations: A11θ + A12w = b1 A21θ + A22w = b2 The underlying matrices Aij and vectors bi are not accessible, and instead, stochastic estimates b_i(X_k) and A_ij(X_k) are used. The corresponding recurrence runs as: θk+1 = θk + βk{b_k+1¹ – A_k+1¹¹θk – A_k+1¹²wk} Wk+1 = Wk + γk{b_k+1² – A_k+1²¹θk – A_k+1²²wk} where θk ∈ Rdo, wk ∈ Rdw, and b_k, A_k are shorthand for b_i(X_k) and A_ij(X_k). The step sizes βk, γk > 0 satisfy limk→∞ βk/γk < 1, meaning wk is updated at a faster timescale.

Decoupled TTSA Updates: The original TTSA equations are reformulated into a decoupled form using changed variables θk := θk - θ* and ῶk = wk - w* + Dk-1θk. This leads to equivalent recursions: θk+1 = (I - βkB1)θk – βkA12ῶk – βkVk+1 Wk+1 = (I − γkB22)Ŵk – βkDkVk+1 - γkWk+1 where Vk+1 and Wk+1 are noise terms.

Gaussian Approximation for Polyak-Ruppert Averaged TTSA: For averaged iterates, the key decomposition is: Δ(θk – θ*) = (θk - θk+1)/βk - A12A22(Wk – Wk+1)/γk + (Vk+1 - A12A22Wk+1) Summing this from k=1 to n and using definitions, the averaged iterate term is expressed as: √nΔ(θn – θ*) = Σk=1n Ψk+1 + Rpr,m where Ψk+1 = ε_k+1^v – A12A22ε_k+1^w and Rpr,m is a residual term.

Gaussian Approximation for Last Iterate: For the last iterate, a similar decomposition is used: βn¹/²θn+1 = – Σj=0n βjG_j+1:n^(1)ε_j+1 + Rlast where Rlast is a remainder term.

Problem Formulation: Find (θ*, w*) solving A11θ + A12w = b1 and A21θ + A22w = b2.
Step Sizes: βk = co,β(k + ko)⁻ᵇ and γk = co,γ(k + ko)⁻ᵃ.
Exponents: 1/2 < a < b < 1.
Assumptions (Martingale Noise):
- A1 (Zero-mean noise): EFk [Vk+1] = 0, EFk [Wk+1] = 0.
- A2(p) (Moment bound): For p ≥ 2, E¹/P[||Vk+1||P] ≤ mv (1 + E¹/P[||θk - θ*||P] + E¹/P[||Wk - w*||P]) and E¹/P[||Wk+1||P] ≤ mw (1 + E¹/P[||θk - θ*||P] + E¹/P[||Wk - w*||P]).
- A3 (Quadratic characteristic): EFk [ε_k+1^v(ε_k+1^v)T] = Σv, EFk [ε_k+1^w(ε_k+1^w)T] = Σw, EFk [ε_k+1^v(ε_k+1^w)T] = Σvw.
- A4 (Hurwitz matrices): Matrices –A22 and –Δ = – (A11 – A12A22⁻¹A21) are Hurwitz.
- A5(p) (Step sizes): βk, γk are non-increasing, co,β/co,γ is small enough, and ko > Ca5p⁴/b.
- A6 (Boundedness): supx∈X ||Aij(x)|| ∨ ||Aij(x) – Aij|| ≤ CA, supx∈X ||bi(x)|| ∨ ||bi(x) – bi|| ≤ Cb.
- A7 (Last iterate step size exponents): 2b > 1 + a, and n satisfies nb > CA7.
Assumptions (Markov Noise):
- B1 (Markov chain properties): {Xk}k∈N is a Markov chain on a Polish space (X, X) with kernel P, admits a unique invariant distribution π, and is uniformly geometrically ergodic (dtv(Pk(x, ·), Pk(x', ·)) ≤ (1/4)⌊k/tmix⌋). Also, Eπ[Aij] = Aij and Eπ[bi] = bi.
- B2(p) (Step sizes): Same form as A5(p), but ko > CB2p⁴/b.
- B3 (Last iterate step size exponents): Same as A7, but n satisfies nb > CB3.
Distance Metric: Convex distance ρConv(μ, ν) = supB∈Conv(Rd) |μ(B) – ν(B)|.

Polyak-Ruppert Averaged TTSA (Martingale Noise):
- Convergence Rate: ρConv(√n(θn – θ*), N(0, Σθ)) ≤ log n n⁻¹/⁴ + n^(1-b)/2.
- Optimized Rate: Setting a = 1/2 + 1/log n and b = a + 1/log n yields a final rate of ρConv(√n(θn – θ*), N(0, Σθ)) ≤ log n n⁻¹/⁴.
Last Iterate TTSA (Martingale Noise):
- Convergence Rate: ρConv(βn¹/²θn+1, N(0, Σlast)) ≤ log n n^(b/2) Πj=0n (1 - αΔβj/8)⁻¹ + n^-(3b-a-2)/2.
- Optimized Rate: Setting a = 1/2 + 1/log n and b = 1 - 1/log n yields a final rate of ρConv(βn¹/²θn+1, N(0, Σlast)) ≤ log n n⁻¹/⁴.
Polyak-Ruppert Averaged TTSA (Markov Noise):
- Convergence Rate: ρConv(√nΔ(θn – θ*), N(0, Σmark)) ≤ log n n⁻¹/⁴ + n^(1-b)/2 + n^(a-1) + √n Πj=0n (1 - αΔβj/16).
- Optimized Rate: Setting a = 2/3 and b = 2/3 + 1/(log n) yields a final rate of ρConv(√n(θn – θ*), N(0, Σmark)) ≤ log n n⁻¹/⁶.
Last Iterate TTSA (Markov Noise):
- Convergence Rate: ρConv(βn¹/²θn+1, N(0, Σlast,m)) ≤ log n Πj=0n (1 - αΔβj/8)⁻¹ + n^-(2b-1)/4 + n^-(2a-b)/2 + n^-(3b-a-2)/2.
- Optimized Rate: Setting a = 2/3 and b = 1 - 1/(log n) yields a final rate of ρConv(βn¹/²θn+1, N(0, Σlast,m)) ≤ log n n⁻¹/⁶.
Applicability: The results are directly applicable to reinforcement learning algorithms such as GTD(0) and TDC.

Step size exponent b=1: The results in their current form do not apply directly if the step size exponent b = 1. The authors expect the result to hold in this case, possibly with additional logarithmic factors.
Dependence on initial errors: The coefficients before the terms in the bounds depend on the initial errors ||θ0-θ*||, ||w0-w*||, and factors 1/(1-a) and 1/(1-b).
Parameter p dependence on n: The parameter p is set to order log(n), which means the constant ko in the step size definition will depend on the total number of iterations n. This effect is unavoidable in constant step size algorithms.
Technical difficulties in moment bounds: Improving the dependence of the moment bounds on p (equations 12 and 13) by applying Pinelis's Rosenthal inequality instead of Burkholder's inequality introduces additional technical difficulties.
Constraint for last iterate analysis: Bounding the moments of the residual term Rlast for the last iterate requires an additional constraint 2b > 1 + a.

Method evidence: "In this paper, we establish non-asymptotic bounds for accuracy of normal approximation for linear two-timescale stochastic approximation (TTSA) algorithms driven by martingale difference or Markov noise." (section: Abstract)
Result evidence: "The normal approximation rate for the last iterate improves as the timescale separation increases and achieves a convergence rate of order up to n-1/4, up to log n factors." (section: Abstract)
Limitation evidence: "In the theorem above, the coefficients before the terms depend upon the initial errors ||θ0-θ*||, ||w0-w*||, and upon the factors 1/(1 – a) and 1/(1 – b). That is why the result in its current form does not apply directly if b = 1." (section: 3.2 GAR for Polyak-Ruppert Averaged TTSA)

Gaussian Approximation for Two-Timescale Linear Stochastic Approximation

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence