AI Research Portal

This paper investigates the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. The core idea is to propose a novel decomposition of the bias using a linearization technique, revealing that the leading-order term is linear in the step size and cannot be eliminated by PR averaging alone. To address this, the Richardson-Romberg (RR) extrapolation procedure is applied to effectively cancel this leading bias term. The paper derives high-order moment bounds for the RR iterates, demonstrating that the leading error term aligns with the asymptotically optimal covariance matrix of the vanilla averaged LSA iterates. The applicability of these findings is validated for the temporal difference algorithm in reinforcement learning.

The paper addresses several bottlenecks in the analysis of LSA algorithms:

Inevitable Bias with Constant Step Size: LSA problems with constant step sizes suffer from an inevitable bias, particularly when the noise variables form a Markov chain, which cannot be fully mitigated by standard Polyak-Ruppert averaging.

The main contributions of this paper are:

A novel technique to quantify the asymptotic bias of θ(α), which considers the limiting distribution of the joint Markov chain {(θ(α), Zk+1)}k∈N and analyzes the bias Π_α(θ₀) – θ*.
Application of the linearization method for θ(α) from Aguech, Moulines, and Priouret (2000) to study the limiting distribution of components whose average values are ordered by powers of α.
Establishment of high-order moment error bounds for the Richardson-Romberg method, where the leading term aligns with the asymptotically optimal covariance Σ_∞.
Analysis of the dependence of the error bounds on the number of steps n, step size α, and the mixing time t_mix.

The paper studies Linear Stochastic Approximation (LSA) algorithms, which aim to estimate a solution θ* of the linear system Aθ* = b.

LSA and Polyak-Ruppert Averaging: The sequence of estimates {θk}k∈N and {η_n}n>no+1 are given by: θκ = θk−1 - ακ{A(Zk)θk−1 – b(Zk)}, k≥ 1 η_n = (η - πο)⁻¹ Σk=no^(n-1) θκ, n≥no +1 Here, {Zk}k∈N is a Markov chain, and η_n is the Polyak-Ruppert averaged estimator.

Bias Decomposition: The bias of θ(α) is decomposed using a linearization technique. The leading-order term is shown to be linear in the step size α and cannot be eliminated by PR averaging alone.

Richardson-Romberg Extrapolation: To mitigate the bias, the Richardson-Romberg (RR) extrapolation procedure is applied. The LSA iterations with a constant step size α are denoted as θ(α), and the corresponding Polyak-Ruppert averaged iterates as θ(α). θ(α) = θ(α) - α{A(Zk)θ(α) - b(Zk)}, k≥ 1 θ(α) = (η - πο)⁻¹ Σk=no^(n-1) θ(α), n≥no +1 The RR extrapolated iterate θ(α,RR) is then defined using two sequences of averaged iterates, one with step size α and another with 2α: θ(α,RR) = 2θ(α) – θ(2α) This procedure effectively cancels the leading bias term, which is linear in α.

High-Order Moment Bounds: The paper derives high-order moment error bounds for the RR iterates. It shows that the leading error term for the RR estimator aligns with the asymptotically optimal covariance matrix Σ_∞ of the vanilla averaged LSA iterates. The analysis involves studying the limiting distribution of a joint Markov chain {(θ(α), Zk+1)}k∈N and applying perturbation-expansion frameworks.

LSA Problem: Estimates a solution θ* of the linear system Aθ* = b.
Noise Variables: {Zk}k∈N is a Markov chain taking values in a measurable space (Z, Z). A(Zk) and b(Zk) are stochastic estimates of A and b.
Assumptions:
- A1: CA = supzez ||A(z)|| ∨ supzez ||A(z)|| < ∞, and the matrix -Ā is Hurwitz.
- A2: ∫z A(z)dπ(z) = Ā and ∫z b(z)dπ(z) = b. Also, ||ε||∞ = supzez ||ε(z)|| < +∞.
- UGE1: {Zk}k∈N is a Markov chain with Markov kernel Q, admitting π as an invariant distribution and being uniformly geometrically ergodic. This implies there exists t_mix ∈ N* such that for all k ∈ N*, Δ(Qk) ≤ (1/4)[k/tmix], where Δ(Qk) is the Dobrushin coefficient.
Noise Covariance Matrix: Σ(M) = E_π[ε(Z₀)ε(Z₀)T] + 2Σl=1^∞ E_π[ε(Z₀)ε(Zl)].
Asymptotically Optimal Covariance Matrix: Σ_∞ = (Ā)⁻¹Σ(M)(Ā)⁻T.
Step Size Choice: For high-probability bounds, the step size α is chosen as α(n, d, t_mix, p) = α(b) n⁻¹⁄².
Experimental Setup:
- Markovian Noise: {Zk, k ≥ 1} on space Z = {0, 1} with transition matrix P = [[1-a, a], [a, 1-a]].
- Noisy Observations: A(z) = z · A(1) + (1 − z) · A(0), b(z) = z · b(1) + (1 − z) · b(0).
- Specific Parameters:
  - A(0) = [[-2, 1], [1, -2]], b(0) = [[0], [0]].
  - A(1) = [[-2, -1], [-1, -2]], b(1) = [[2], [1]].
  - This leads to Ā = I and b = (1/2)b(1).
  - α = 0.3.
  - N_traj = 400 trajectories from θ₀ = θ*.

Bias Reduction: The Richardson-Romberg scheme significantly reduces bias compared to Polyak-Ruppert averaging. Figure 1d illustrates that E[||θ(α,RR) – θ*||²] decreases faster than E[||θ(α) – θ*||²] after a few iterations.
Error Scaling: The resulting dependence on α and n in the bounds (25) is shown to be tight. For step sizes of the form α = n⁻β with β ∈ [1/2, 1), the term R(fl)n,p,α scales as n^(β-2).
Optimal Step Size: Numerical verification shows that the step size α = n⁻¹⁄² yields the smallest error for Richardson-Romberg iterations. For Polyak-Ruppert averaging, this choice of step size introduces a large bias.
High-Order Moment Bound (Theorem 2): For n ≥ t_mix, α ∈ (0, α(b)), and initial probability measure ξ on (Z, Z), the p-th moment of the error for RR iterations is bounded: E¹⁄p[||Ā(θ(α,RR) – θ*)||p] ≤ 2 C_rm,1{TrΣ(M)}¹⁄²p¹⁄²n⁻¹⁄² + R(fl)n,p,α + R(tr)n,p,α|θ₀ - θ*|| exp{-aαn/24}.
High-Probability Bound (Corollary 3): With probability at least 1 - δ, for α = α(b) n⁻¹⁄², the error is bounded: ||Ā(θ(α,RR) – θ*)|| ≤ √TrΣ(M) log (1/δ)n⁻¹⁄² + (1+log³⁄² (n) log⁵⁄² (1/δ)) log (1/δ)n⁻³⁄⁴ + n⁻¹⁄² log (1/δ)||θ₀ - θ*|| exp {-αlog d₀αn¹⁄²}.

Complexity of Remainder Term Analysis: The paper notes that the remainder term O(α³/2) in Theorem 2 could potentially be improved to O(α²), but this would necessitate a "technically complicated analysis of J(3,α)."
Scope of Generalization: The current work is limited to linear Markovian SA. The authors state that "further work, we consider the generalization of the obtained results to the setting of non-linear Markovian SA and SA with state-dependent noise," implying these are current limitations.

Method evidence: "To address this, we apply the Richardson-Romberg (RR) extrapolation procedure, which effectively cancels the leading bias term." (section: Abstract)
Result evidence: "Figure 1d illustrates the significant reduction in bias achieved by the Richardson-Romberg scheme, estimating E[||θ(α) – θ*||²] and E[||θ(α,RR) – θ*||²]. These results justify that, after a few iterations, the error of the RR procedure starts to decrease faster than for PR averaging." (section: 6 Experiments)
Limitation evidence: "Moreover, the leading term in (24) scales with {TrΣ(M)}¹⁄², which is known to be locally asymptotically minimax optimal for the Polyak-Ruppert iterates (Mou et al. 2024) and aligns with the CLT covariance matrix Σ∞(see (7))." (section: 6 Experiments)

High-Order Error Bounds for Markovian LSA with Richardson–Romberg Extrapolation

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures