In classical optimization and supervised machine learning, we almost always assume that data samples are independent and identically distributed (i.e., i.i.d.). This assumption is the bedrock of standard Stochastic Gradient Descent (SGD) proofs: at any given step, the stochastic gradient is an unbiased estimator of the true gradient.
But when an agent learns from real-world experiences—such as navigating a physical environment, playing a game, or running a Markov Chain Monte Carlo (MCMC) sampler—the i.i.d. assumption completely breaks down. Instead, data is collected sequentially along a continuous trajectory. The next state the agent encounters depends entirely on its current state. This sequential dependency is known as Markovian sampling, and the resulting noise that corrupts our updates is called Markovian noise.
Understanding why algorithms like Temporal Difference (TD) learning and Q-learning still converge despite this continuous stream of correlated data requires shifting our perspective from single-step optimization to the long-term dynamics of Markov chains.
The Core Challenge: The Conditional Bias
To see why Markovian sampling complicates optimization, let us look at a standard stochastic approximation update rule for updating a parameter vector $\theta$:
$$\theta_{t+1} = \theta_t + \alpha_t \cdot g(\theta_t, z_t)$$
Here, $\alpha_t$ is the step size, and $g(\theta_t, z_t)$ is an update operator driven by the data sample $z_t$.
If $z_t$ were drawn independently from a stationary distribution $\mu$, taking the conditional expectation given the current parameter $\theta_t$ would yield the true, unbiased update direction $\bar{g}(\theta_t)$:
$$\mathbb{E}[g(\theta_t, z_t) \mid \theta_t] = \bar{g}(\theta_t)$$
Under Markovian sampling, however, $z_t$ is not independent; it depends on the previous sample $z_{t-1}$. If the agent is currently stuck in a suboptimal or unrepresentative corner of the state space, the sample $z_t$ will reflect that local bias. Consequently, the conditional expectation is biased away from the true target:
$$\mathbb{E}[g(\theta_t, z_t) \mid \theta_t, z_{t-1}] \neq \bar{g}(\theta_t)$$
This discrepancy introduces a gradient bias. As noted by Hoi To Wai in On the Convergence of Consensus Algorithms with Markovian noise and Gradient Bias, this bias propagates through the learning process over time, meaning standard concentration bounds (like Hoeffding's inequality) cannot be applied directly to the underlying stochastic process.
The Intuition: Time-Scale Separation and Mixing Times
Why do these algorithms converge at all if every single step is biased? The answer lies in a concept called time-scale separation, which is governed by the mixing time ($\tau_{mix}$) of the underlying Markov chain.
The mixing time is the number of steps required for a Markov chain's distribution to get close to its stationary distribution $\mu$, regardless of where it started. If the chain is ergodic and fast-mixing, it forgets its initial state exponentially fast.
Markovian Trajectory: [z_0] -> [z_1] -> [z_2] ... -> [z_τ]
\_________________________________/
Highly Correlated Steps
|
v
Distribution approaches stationarity (μ)
When we choose a sufficiently small step size $\alpha_t$, the parameter vector $\theta_t$ changes very slowly—like a heavy fluid moving through a pipe. Meanwhile, the state transitions $z_t$ change rapidly—like gas molecules bouncing around. By the time $\theta_t$ moves a significant distance, the Markov chain has already had enough time to "mix" and sample from its true stationary distribution $\mu$.
As a result, the local biases cancel each other out over a long enough horizon. As Xuyang Chen and Lin Zhao demonstrate in Finite-Time Analysis of Single-Timescale Actor-Critic, accounting for this mixing time introduces a logarithmic or polynomial overhead in sample complexity compared to the i.i.d. setting, which represents the mathematical cost of navigating temporal dependencies.
Proving Convergence: The Multistep Lyapunov Look-Ahead
To translate this intuition into rigorous finite-time bounds, researchers have had to move away from traditional single-step Lyapunov analyses. In standard optimization, you prove that the distance to the optimal solution decreases at every single step. Under Markovian sampling, this is no longer guaranteed because a string of highly correlated, biased steps can temporarily push the parameters away from the optimum.
To overcome this, Bingcong Li et al. developed a multistep Lyapunov approach in A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximation. Instead of analyzing the progress made in one step, the framework "looks ahead" across a block of future updates of length $K$, where $K$ is chosen to be larger than the mixing time $\tau_{mix}$.
Standard Analysis: [θ_t] -> [θ_{t+1}] (Must decrease error at every step)
Multistep Look-Ahead: [θ_t] --------------> [θ_{t+K}] (Error decreases over a window K > τ_mix)
\__ Mixed Window __/
Over this window of $K$ steps, the accumulated conditional bias averages out toward zero because the Markov chain spends most of its time close to the stationary distribution. This allows the authors to prove strict contraction properties over intervals of steps, establishing finite-time convergence rates for standard reinforcement learning algorithms without needing artificial modifications like projection steps.
Scaling to Complex Architectures
The interplay between Markovian sampling and optimization becomes even more intricate when moving beyond simple linear models to multi-agent or multi-timescale systems.
Two-Timescale Systems
Algorithms like Actor-Critic or Temporal Difference with Gradient Correction (TDC) use two coupled stochastic approximation loops running at different speeds (with different step sizes). In Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms, Tengyu Xu and Yingbin Liang show how to decouple these interacting variables under Markovian noise. The fast loop treats the slow loop's parameters as static, while the slow loop sees the fast loop as having already converged to its quasi-stationary equilibrium, allowing both to stabilize despite tracking moving targets over correlated trajectories.
Decentralized and Federated Learning
In distributed settings, multiple agents collect data along their own local Markovian trajectories while communicating over a network. The challenge here is a double-coupling: the noise is coupled temporally within each agent's trajectory, and the agents' parameters are coupled spatially through consensus requirements.
A streamlined proof strategy for this setting is detailed by Aritra Mitra in A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation, which isolates how compression errors and network consensus delays interact with the underlying mixing time of the data stream.
By modeling the data sampling process directly as a geometric mixing process, modern theoretical frameworks have successfully bridged the gap between i.i.d. theory and sequential reality, proving that stochastic approximation remains robust even when its inputs are deeply intertwined over time.