Stochastic approximation in non-markovian environments revisited

Vivek Shripad Borkar

stat.MLMar 22, 2026

Stochastic approximation in non-markovian environments revisited

Authors: Vivek Shripad Borkar

Organizations: Department of Electrical Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400076, INDIA.

Abstract

Based on some recent work of the author on stochastic approximation in non-markovian environments, the situation when the driving random process is non-ergodic in addition to being non-markovian is considered. Using this, we propose an analytic framework for understanding transformer based learning, specifically, the `attention' mechanism, and continual learning, both of which depend on the entire past in principle.

Stochastic Approximation

Stochastic approximation studies iterative algorithms that solve optimization, root-finding, and fixed-point problems using noisy data.

See all 76 papers

Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift
May 8, 2026Xinyu Liu, Zixuan Xie, Shangtong ZhangReinforcement Learning Stochastic Approximation
University of Virginia
Learning to Adapt: In-Context Learning Beyond Stationarity
Apr 13, 2026Zhen Qin, Jiachen Jiang, Zhihui ZhuIn-Context Learning Gated Attention
Michigan Institute for Computational Discovery and Engineering, Department of Electrical Engineering and Computer Science, Department of Statistics, University of Michigan · Department of Computer Science and Engineering, The Ohio State University
Incremental Learning of Sparse Attention Patterns in Transformers
Feb 22, 2026Oğuz Kaan Yüksel, Rodrigo Alvarez Lucendo, Nicolas FlammarionSelf-Attention Transformer Training Dynamics
TML Lab, EPFL

May 8, 2026J/K move · Enter open · S save

Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

Xinyu Liu, Zixuan Xie, Shangtong Zhang

University of Virginia

Reinforcement Learning Stochastic Approximation Convergence Analysis

Open paper AskPDF arXiv

Establishing almost sure convergence rates for stochastic approximation and reinforcement learning under Markovian noise is a fundamental theoretical challenge. We make progress towards this challenge for a class of stochastic approximation algorithms whose expected updates are contractive, a setting that arises in many reinforcement learning algorithms such as

Q

-learning and linear temporal difference learning. Specifically, for a power-law learning rate

O(n^{-η})

with

η\in (1/2, 1)

, we obtain an almost sure convergence rate arbitrarily close to

o(n^{1 - 2η})

. For a harmonic learning rate

O(n^{-1})

, we obtain an almost sure convergence rate arbitrarily close to

o(n^{-1})

, which we argue is a strong result because it is close to the optimal rate

O(n^{-1}\log\log n)

given by the law of the iterated logarithm (for a special case of i.i.d. noise). Key to our analysis is a novel Lyapunov drift construction that applies a Poisson-equation based correction for Markovian noise to the well-established Moreau-envelope smoothing for the contractive mapping.

Abstract

Stochastic Approximation

Explore similar work

Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

Learning to Adapt: In-Context Learning Beyond Stationarity

Incremental Learning of Sparse Attention Patterns in Transformers