Poisson Equation Decomposition for Markovian Noise

15 concepts15 papers

Stochastic approximation (SA) algorithms underpin modern machine learning, from training neural networks with SGD to evaluating policies via Temporal Difference (TD) learning. Traditional convergence proofs rely heavily on a convenient assumption: the noise introduced by data sampling must be independent and identically distributed (i.i.d.), or at least form a martingale difference sequence. Under these conditions, errors cancel out on average, and tail bounds are straightforward to compute.

However, in real-world applications like reinforcement learning or Markov Chain Monte Carlo (MCMC), data is collected sequentially along a trajectory. The next sample depends intimately on the current state. This temporal correlation introduces Markovian noise. Because the noise carries memory, standard martingale tools break down. The bias accumulates, making it notoriously difficult to guarantee finite-time convergence or derive exact error bounds.

The Core Intuition: Splitting the Noise

To analyze algorithms under Markovian noise, researchers need a way to isolate the memoryless, zero-mean component of the noise from its systematic, history-dependent drift. The breakthrough tool for this task is the Poisson equation.

Imagine an iterative algorithm tracking a state $X_k$ governed by a Markov chain. The noisy update function we observe is $g(X_k)$, whose expected value under the chain's stationary distribution is $\bar{g}$. The Markovian noise at step $k$ is the deviation from this stationary mean:

$$\xi_k = g(X_k) - \bar{g}$$

Because $X_k$ is Markovian, $\xi_k$ is biased and correlated with $\xi_{k-1}$. The Poisson equation solves this by introducing a "potential function" $V(X)$ that satisfies:

$$V(X) - P V(X) = g(X) - \bar{g}$$

where $P$ is the transition operator of the Markov chain, meaning $P V(X_k) = \mathbb{E}[V(X_{k+1}) \mid X_k]$.

By substituting this relation into our noise term, we can rewrite the noise at step $k$ as the difference between the current potential and the expected next potential:

$$\xi_k = V(X_k) - \mathbb{E}[V(X_{k+1}) \mid X_k]$$

Now, we perform a clever algebraic rearrangement by adding and subtracting the actual next-state potential $V(X_{k+1})$:

$$\xi_k = \underbrace{\left( V(X_{k+1}) - \mathbb{E}[V(X_{k+1}) \mid X_k] \right)}_{M_{k+1}} + \underbrace{\left( V(X_k) - V(X_{k+1}) \right)}_{R_k}$$

This is the Poisson noise decomposition. It splits the correlated noise $\xi_k$ into two distinct parts:

  1. A Martingale Difference Term ($M_{k+1}$): By construction, the expectation of $M_{k+1}$ given the current state $X_k$ is exactly zero. It represents the pure, unpredictable random shock of the transition.
  2. A Telescoping Residual ($R_k$): This term represents the change in the potential function between steps.

Why It Works: The Power of Telescoping

Why does this split make convergence proofs possible? The magic happens when we aggregate the noise over time.

When analyzing the cumulative error of an algorithm over $T$ steps, we sum the noise terms. The martingale difference terms $M_k$ can be bounded using standard probabilistic tools (like the Azuma-Hoeffding inequality or martingale central limit theorems) because they lack temporal correlation.

Meanwhile, the residual terms $R_k$ form a telescoping sum:

$$\sum_{k=1}^T R_k = \sum_{k=1}^T (V(X_k) - V(X_{k+1})) = V(X_1) - V(X_{T+1})$$

Instead of growing with $T$, the entire history of systematic bias collapses into just two boundary terms: the initial potential and the final potential. As long as the potential function $V$ is bounded or well-behaved, this residual term becomes negligible when divided by $T$ or scaled by a decaying step size.

By decoupling the memory of the Markov chain into a harmless telescoping remainder, the Poisson equation allows researchers to treat the primary driving force of the noise as an unbiased martingale.

Applications Across Stochastic Approximation

This decomposition strategy has become a foundational framework for proving the stability and efficiency of complex iterative systems where data dependencies cannot be ignored.

Temporal Difference Learning and Multi-Timescale Systems

In reinforcement learning, algorithms often update multiple parameters simultaneously at different rates. Kaledin et al. utilized the Poisson equation to establish tight, finite-time analysis for linear two-timescale stochastic approximations without requiring artificial projection steps. Similarly, Hu et al. derived a Central Limit Theorem for two-timescale architectures, proving that more efficient Markovian sampling directly minimizes asymptotic variance.

More recently, Chandak et al. extended these finite-time bounds to non-Euclidean norms, expanding the theory to arbitrary norm contractions. For single-timescale setups, Zhang and Blaser leveraged this decomposition to provide the first proof of almost sure convergence for tabular average reward TD learning.

Handling Unbounded and State-Dependent Environments

Early iterations of noise analysis required strict assumptions, such as bounded noise or uniform mixing times. To bypass these limitations, Ul Haque and Maguluri introduced a general-purpose theorem for non-linear SA that handles unbounded Markovian noise and periodic chains by isolating the noise characteristics from the algorithm's internal logic.

When the underlying Markov chain is influenced by the algorithm's parameters themselves—a scenario known as state-dependent noise—the problem compounds. Karimi et al. provided non-asymptotic convergence rates for biased SA under state-dependent Markovian noise, while Roy et al. applied the telescoping decomposition to constrained nonconvex optimization driven by state-dependent data.

Distributed Systems and Performative Prediction

The framework also generalizes to multi-agent and strategic settings. Wai applied Poisson bounding to decentralized consensus algorithms, matching the convergence rates of centralized methods despite localized Markovian data streams. In distributed optimization, Hu et al. used the decomposition to demonstrate that improving the sampling efficiency of a fraction of agents lifts the performance of the entire network.

Furthermore, in performative prediction—where deploying a model alters the future data distribution—Li et al. used the Poisson equation to split gradient errors caused by agents' historical memory, proving stable convergence.

Quantifying Uncertainty and Exact Bounds

Beyond merely proving that an algorithm converges, the Poisson decomposition enables researchers to quantify how fast and with what confidence. Chen et al. demonstrated that while traditional exponential bounds often fail for Markovian noise, decomposing the noise via the Poisson equation yields explicit Mean-Square Error (MSE) bounds with exact constants matching the Central Limit Theorem.

For statistical inference, Samsonov et al. used the decomposition to establish non-asymptotic guarantees for uncertainty quantification, allowing the construction of reliable confidence intervals via bootstrap methods. Finally, Wang et al. leveraged this approach to map out the steady-state behavior and tail bounds of constant-stepsize SA, providing a rigorous mathematical bridge to real-world deployment scenarios.

Key Foundational Work

Non-asymptotic Analysis of Biased Stochastic Approximation Scheme (2019) — contributed 1 concept elements to this direction.
The Schrödinger equation with spatial white noise: the average wave function (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_markovian_noise_decomposition_58576f7e,
  title = {Markovian noise decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/markovian-noise-decomposition/rdr_58576f7e9cd349f391cd36ecf25c7e6b},
  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_markovian_noise_decomposition_58576f7e_v1,
  title = {Markovian noise decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/markovian-noise-decomposition/rdr_58576f7e9cd349f391cd36ecf25c7e6b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake