In the textbook version of stochastic optimization, we imagine an agent picking samples from a hat. Each sample is independent of the last, and every draw provides an unbiased glimpse of the true gradient. This "independent and identically distributed" (i.i.d.) assumption is the bedrock of most convergence proofs for Stochastic Gradient Descent (SGD).
But in the real world—especially in Reinforcement Learning (RL), finance, and control systems—data doesn't come from a hat; it comes from a trajectory. If a robot is in the kitchen at time $t$, it is almost certainly still in or near the kitchen at time $t+1$. This temporal dependency is known as Markovian noise. Because the next sample depends on the current state, the "noise" in our updates is correlated over time, violating the core assumptions of standard optimization theory.
The Challenge of Temporal Correlation
When samples are Markovian, the algorithm suffers from two main issues: bias and memory. Because the agent is stuck in a specific part of the state space for a while, its local gradient estimates are biased toward that region. We cannot simply wait for these biases to cancel out as we do in i.i.d. settings.
To prove that an algorithm still works under these conditions, researchers like Aymeric Dieuleveut, Eric Moulines, and Gersende Fort leverage mixing times. The mixing time of a Markov chain is essentially the "memory" of the system—how long you have to wait before a new sample becomes roughly independent of the starting state. In Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning, the authors show that by accounting for this mixing time, we can establish stability using Lyapunov functions, even when the update directions aren't true gradients.
Finite-Time Guarantees
For a long time, theory only guaranteed that these algorithms would converge "eventually" (asymptotically). Recent work has shifted toward finite-time analysis, which tells us exactly how many samples we need to reach a certain accuracy.
Surprisingly, Markovian sampling doesn't necessarily slow things down as much as one might fear. Thinh T. Doan and Justin Romberg demonstrated in Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness that SGD under Markovian noise achieves nearly the same $O(1/\sqrt{T})$ convergence rate as i.i.d. SGD. The primary penalty is a logarithmic factor related to the mixing time of the underlying chain. This suggests that as long as the environment "mixes" reasonably fast, trajectory-based learning is almost as efficient as random sampling.
Smoothing the Path with Averaging
One of the most effective tools for handling the "jitter" of Markovian noise is Polyak-Ruppert (PR) averaging. Instead of looking only at the last iterate of the algorithm, we take the average of all previous iterates.
Sajad Khodadadian and Martin Zubeldia recently provided high-probability bounds for this technique in A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging. Averaging acts as a low-pass filter, smoothing out the correlated noise and allowing the algorithm to achieve "instance-optimal" performance—meaning it performs as well as the best possible algorithm for that specific noise structure.
Scaling to Multiple Agents
This framework is particularly vital for Federated Reinforcement Learning, where multiple agents collect data in their own environments and periodically sync their findings. In this setting, the noise is not only Markovian but also heterogeneous (each agent's environment might mix at a different rate).
In Federated Reinforcement Learning: Linear Speedup Under Markovian Sampling, Siva Theja Maguluri and colleagues proved that federated versions of TD-learning can achieve a linear speedup. This means that if you have $N$ agents, you reach your target $N$ times faster, even though every single agent is dealing with its own biased, temporally correlated data stream.
Beyond Euclidean Geometry
While much of the early work focused on standard gradient descent, the field is expanding to more complex geometries and problem types:
- Non-Euclidean Geometry: Vladimir Solodkin and Aleksandr Beznosikov have extended these results to Mirror Descent and Variational Inequalities, which are crucial for solving games and constrained optimization problems under Markovian noise (Methods for Optimization Problems with Markovian Stochasticity and Non-Euclidean Geometry).
- Two-Timescale Systems: Many RL algorithms (like Actor-Critic) involve two coupled processes running at different speeds. Yue Wu and Quanquan Gu provided the first finite-time analysis for these complex interactions under Markovian sampling (A Finite-Time Analysis of Two Time-Scale Actor-Critic Methods).
By treating temporal correlation as a feature to be modeled (via mixing times and Lyapunov stability) rather than a bug to be ignored, this research direction provides the mathematical foundation for why reinforcement learning works in practice, even when its data violates every rule of classical statistics.