cs.LGOct 7, 2026

Stationary Bias and Extrapolation in Nonlinear Two-Timescale Stochastic Approximation

Authors: A. Ch. Madhusudanarao, Rahul Singh

Organizations: Department of Computer Science and Automation Indian Institute of Science, Bengaluru, India · Laboratoire de Recherche de l’EPITA, Paris, France

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Constant-step stochastic approximation generally has a nonzero stationary mean error that persists under time averaging. This paper studies that error for nonlinear two-timescale recursions driven by an exogenous finite-state Markov chain. Under stated smoothness assumptions and conditions on the stationary distribution, we derive a first-order bias expansion whose error bound remains uniform as the slow step size becomes much smaller than the fast step size. Fast-manifold coordinates keep the associated covariance equation regular in this limit. For fast step ηη and slow step ε\varepsilon, the expansion reveals a mixed contribution ε2/η\varepsilon^2/η alongside terms linear in each step size. This dependence matters for bias reduction: along power-law step-size paths, the bias exponents need not be integers, so Richardson--Romberg extrapolation requires weights matched to the path. An exactly solvable nonlinear Markov example verifies the coefficients. We verify localization for temporal-difference learning and compare finite-run extrapolation at equal update budgets. For finite runs, we bound the initialization error of tail averages on both timescales under an additional coupling assumption. In the special case of additive independent noise, signed third-moment cancellation yields a sharper remainder.

Figures & tables

Figure 1: Empirical bias and variability of TDC estimates of θ⋆\theta^{\star} . Top: empirical bias divided by η\eta at fixed ratios ρ=0.1\rho=0.1 and ρ=0.25\rho=0.25 , for Markov sampling and independent transition-pair sampling. Dashed lines show the theoretical leading coefficient b0θ+ρb1θb_{0}^{\theta}+\rho b_{1}^{\theta} ; the dotted line marks the zero stationary bias of the independent-pair control. Bottom: empirical signed bias and standard deviation at equal total update budgets, including burn-in, along ε=ηp\varepsilon=\eta^{p} with p=6/5p=6/5 and base step h=0.05h=0.05 . All estimates use 256 independent replications. Error bars are pointwise 95% intervals: Student- tt intervals for bias and replication-bootstrap intervals for standard deviation. Solid segments connect empirical points. RR labels specify the cancelled powers.
Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: TDC estimation error at equal total update budgets. Points show empirical RMSE relative to θ⋆\theta^{\star} for ordinary averaging and three extrapolation rules. The step sizes are ηj=h2−j\eta_{j}=h2^{-j} and εj=ηjp\varepsilon_{j}=\eta_{j}^{p} , with h=0.05h=0.05 and p=6/5p=6/5 . Each budget includes burn-in and all updates across levels. Error bars are pointwise 95% bootstrap intervals based on 256 independent replications and 2,000 bootstrap resamples. Solid segments connect empirical points. RR labels specify the cancelled powers.
Figure 3: Empirical bias of the nonlinear toy model at ρ=ε/η=0.25\rho=\varepsilon/\eta=0.25 , for q=0q=0 and q=0.5q=0.5 . Points show estimated bias relative to Z⋆=0Z^{\star}=0 , divided by η\eta . Dashed lines show the theoretical leading coefficient cq(1/2+ρ/(1+ρ))c_{q}\bigl(1/2+\rho/(1+\rho)\bigr) , where cq=(1+q)/(1−q)c_{q}=(1+q)/(1-q) . Error bars are pointwise 95% bootstrap intervals based on 256 independent replications and 2,000 bootstrap resamples. Each replication uses 240,000 updates, including burn-in.
Figure 4: Empirical extrapolation results for the nonlinear toy model along ε=η6/5\varepsilon=\eta^{6/5} . Columns correspond to q=0q=0 and q=0.5q=0.5 . Top: estimated signed bias from runs using 2,400,000 updates per level, including burn-in. The vertical scale is logarithmic away from zero and linear for ∣bias∣≤10−5|\mathrm{bias}|\leq 10^{-5} . Bottom: empirical RMSE at a total budget of 240,000 updates per method, including burn-in across all levels. The top and bottom rows therefore represent distinct experiments with different averaging lengths. All error bars are pointwise 95% bootstrap intervals based on 256 independent replications and 2,000 bootstrap resamples. Solid segments connect empirical points. RR labels specify the cancelled powers, with p=6/5p=6/5 .

Explore similar work

CardsList

  1. The Bias of Nonlinear Two-Time-scale Stochastic Approximation under Constant Step-Sizes

    Sep 17, 2026Djamel Rassem Lamouri, Dorian Baudry, Nicolas GastStochastic ApproximationTwo-Timescale Stochastic Approximation

    Univ. Grenoble Alpes, CNRS, Inria Grenoble INP, LIG, 38000 Grenoble France

  2. Nonlinear Two-Time-Scale Stochastic Approximation: A Sharp Phase Transition and How to Beat It

    Jun 12, 2026Dhruv Sarkar, Vaneet AggarwalStochastic ApproximationTwo-Timescale Stochastic Approximation

    1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Purdue University

  3. Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration

    Jul 15, 2026Dhruv Sarkar, Vaneet AggarwalLast-Iterate ConvergenceStochastic Approximation

    Indian Institute of Technology Kharagpur · Mohamed bin Zayed University of Artificial Intelligence · Purdue University