Research map / Optimization / Nonconvex and smooth optimization
Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes the bias of constant-step stochastic approximation with state-dependent Markovian noise via infinitesimal generator comparison, showing O(α) bias and that Polyak-Ruppert averaging gives bias αV + O(α²), enabling Richardson-Romberg extrapolation.
Problem
Characterizing the bias of constant-step-size stochastic approximation when the Markovian noise transition kernel depends on the iterate (e.g., epsilon-greedy Q-learning), where the iterates do not converge to the ODE equilibrium.
Approach
Compares the expectation of the stochastic recursion with its deterministic Euler discretization via a hybrid system z_{n,k}, reducing the bias to a comparison of infinitesimal generators; uses Poisson equation to handle Markovian averaging, yielding a Lyapunov-equation constant V for the bias of the Polyak-Ruppert average.
Key results
- The bias of the constant-step SA iterates is shown to be O(alpha) under smoothness conditions, with the time-averaged bias equal to alpha V + O(alpha^2), where V is characterized by a Lyapunov equation.
- The Polyak-Ruppert average converges in high probability to theta* + alpha V with deviation O(alpha^2).
- Richardson-Romberg extrapolation 2*theta^(alpha) - theta^(2alpha) yields bias of order O(alpha^2), validated on a synthetic one-dimensional example with theta*=1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Average the constant-step iterates with Polyak-Ruppert averaging | Constant-step stochastic approximation · Markovian-noise stochastic approximation | variance: \lim_{n\to\infty}\var{\bar{\theta}_n}=0 | Helped |
| Average the constant-step iterates with Polyak-Ruppert averaging | Constant-step stochastic approximation · Markovian-noise stochastic approximation | bias order: \alpha V + O(\alpha^2) | No clear effect |
| Combine Polyak-Ruppert averages from step-sizes \alpha and 2\alpha | Polyak-Ruppert averaging · Synthetic example | bias order: O(\alpha) -> O(\alpha^2) | Helped |
| Use tail averaging instead of the unaveraged iterate | Constant-step stochastic approximation · Synthetic example | distance to \theta^*=1 | Helped |
| Use half-window averaging \bar{\theta}_{n/2:n} instead of full averaging \bar{\theta}_n | Polyak-Ruppert averaging · Synthetic example with small step-sizes | convergence rate | Helped |
| Average the iterates over time | Constant-step stochastic approximation with periodic Markov noise · Periodic-noise example | stability of the scaled bias | Helped |
Surprising findings
- Without averaging, the O(alpha) bias term of the raw iterates may be periodic rather than converge to a constant when the Markov chain is periodic.
Limitations
- Requires the parameter space Theta to be compact and the ODE to have a unique globally exponentially stable equilibrium.
- Requires four times differentiability of f, K, Q, R in theta; non-differentiable settings would give O(sqrt(alpha)) bias.
- Results are asymptotic in n and only validated on a synthetic example.
Experimental setup
Metrics: bias distance to theta*
Baselines: theta_n without averaging Polyak-Ruppert averaged iterates
Builds on: Polyak-Ruppert averaging Richardson-Romberg extrapolation Stein's method
Closest papers by meaning
- The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize (NeurIPS 2024 · similarity 0.90)
- Statistical inference for Linear Stochastic Approximation with Markovian Noise (NeurIPS 2025 · similarity 0.86)
- Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference (AAAI 2024 · similarity 0.86)
- Convergence Rate in a Nonlinear Two-Time-Scale Stochastic Approximation with State (Time)-Dependence (AAAI 2025 · similarity 0.86)
- Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift (NeurIPS 2026 · similarity 0.85)
- Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.