Martingale Decomposition for Markovian Stochastic Approximation

This direction is split into other directions: Markovian noise decomposition. Its last version stays readable and citable here.

Version 1 of 176 papers82 conceptsfrozen 2026-10-04

In the standard theory of machine learning, we often assume that data arrives as a sequence of independent and identically distributed (i.i.d.) samples. Under this assumption, the "noise" in our gradients is well-behaved: it is zero-mean and doesn't remember the past. However, in reinforcement learning (RL) and adaptive control, data is collected along a trajectory. The next state depends on the current one, creating Markovian noise.

This temporal correlation breaks traditional convergence proofs. If the noise at time $t$ depends on the state at time $t$, how can we guarantee the algorithm won't drift into instability? The research direction across these papers focuses on a powerful mathematical "bridge": using the Poisson equation to decompose dependent Markovian noise into a martingale difference sequence and a vanishing remainder.

The Problem of Noise Memory

Stochastic Approximation (SA) is the mathematical engine behind algorithms like SGD, Q-learning, and Temporal Difference (TD) learning. The general form is $x_{k+1} = x_k + \alpha_k [h(x_k) + \xi_{k+1}]$, where $h(x)$ is the desired update and $\xi$ is the noise.

When $\xi$ is i.i.d., we can use Law of Large Numbers-style arguments to show the noise cancels out. But as Prasenjit Karmakar, Arunselvan Ramaswamy, and Vivek S. Borkar explore in Asymptotic and non-asymptotic convergence properties of stochastic approximation with controlled Markov noise without ensuring stability, real-world noise is often "controlled" or "iterate-dependent." The noise distribution shifts as the algorithm updates its parameters. This creates a "chicken-and-egg" problem: to prove the algorithm converges, you need the noise to be stable, but the noise only stabilizes if the algorithm converges.

The Poisson Equation as a Decorrelator

The core intuition shared by this research is that Markovian noise can be "unwrapped" into a form that looks like i.i.d. noise. The primary tool for this is the Poisson equation.

In simple terms, if you have a function $f$ of a Markov chain, the Poisson equation helps you find a "corrector" function. By applying this corrector, you can decompose the noise term into two parts:

  1. A Martingale Difference: A sequence of random variables that, while not independent, are "fair" in expectation given the past.
  2. A Telescoping Remainder: A term that represents the transient "memory" of the Markov chain, which vanishes as the number of iterations grows.

Maxim Kaledin, Eric Moulines, and colleagues demonstrate in Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise that this decomposition allows researchers to apply martingale concentration inequalities—tools originally designed for independent variables—to complex, correlated data streams.

From Asymptotic to Finite-Time Bounds

Historically, theory focused on "almost sure" convergence—the idea that the algorithm will eventually reach the right answer. However, modern practitioners need to know how many samples are required to reach a certain accuracy.

By using the Poisson decomposition, researchers like Siva Theja Maguluri and Shaan Ul Haque have moved toward "black-box" theorems for finite-time analysis. In Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem, they show that this approach yields tighter bounds than traditional "mixing-time" arguments. While mixing-time methods assume the Markov chain forgets its past exponentially fast, the Poisson approach handles periodic or slower-mixing chains more gracefully, eliminating unnecessary logarithmic factors in sample complexity.

Stability and "Lock-in" Probabilities

A recurring challenge in this field is that many algorithms are not globally stable; if they start too far from the solution, they might diverge. Prasenjit Karmakar addresses this by developing the concept of lock-in probability.

In Dynamics of stochastic approximation with Markov iterate-dependent noise with the stability of the iterates not ensured, the goal is to calculate the probability that an algorithm, once it enters a certain "attractor" region, will stay there and converge. The Poisson decomposition is again the hero here: it allows the authors to bound the "shocks" from the Markovian noise, ensuring they aren't strong enough to kick the algorithm out of its stable path.

Applications in Reinforcement Learning

This theoretical framework has immediate consequences for the reliability of RL. For instance, Shangtong Zhang has used these techniques to provide the first formal verification of RL algorithms. In Towards Formalizing Reinforcement Learning Theory, the "skeleton iterates" technique is used to transform trajectory-based Markovian noise into martingale noise, allowing the convergence of Q-learning to be proved within the Lean 4 theorem prover.

Similarly, Han-Dong Lim and Donghwan Lee 0002 apply these decompositions to Experience Replay in Temporal Difference Learning with Experience Replay. They split the error into "concentration error" (from the mini-batch) and "Markovian noise" (from the buffer's correlation), providing a mathematical explanation for why larger buffers stabilize training.

By treating dependent noise as a slightly messy version of a martingale, this research direction provides the tools to treat RL and online optimization with the same statistical rigor as classical i.i.d. machine learning.

Papers in this version

Showing 60 of 76 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_martingale_decomposition_for_markovian_s_4c7f7ad6,
  title = {Martingale Decomposition for Markovian Stochastic Approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/martingale-decomposition-for-markovian-stochastic-approximation/rdr_4c7f7ad6a9d44c92831f72bb687fd8bf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_martingale_decomposition_for_markovian_s_4c7f7ad6_v1,
  title = {Martingale Decomposition for Markovian Stochastic Approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/martingale-decomposition-for-markovian-stochastic-approximation/rdr_4c7f7ad6a9d44c92831f72bb687fd8bf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}