Traditional machine learning theory relies heavily on a comfortable assumption: that data points are independent and identically distributed (i.i.d.). This assumption allows us to use classical concentration inequalities—like Hoeffding’s or Chernoff’s bounds—to guarantee that a model's performance on a training set will generalize to unseen data.
But in the real world, data is rarely i.i.d. Consider an autoregressive large language model predicting the next token, a contextual bandit algorithm selecting ads based on user clicks, or a reinforcement learning agent navigating a physical environment. In all these scenarios, the next data point depends heavily on past states and actions. When data points are tightly coupled over time, classical generalization bounds collapse, often yielding vacuous or mathematically invalid guarantees.
To bridge this gap, a powerful body of research replaces the strict i.i.d. assumption with martingale structures and Markovian dynamics. By analyzing how information accumulates sequentially, these frameworks provide rigorous, data-dependent generalization guarantees for inherently dependent data streams.
The Core Intuition: Martingales and Innovations
How can we guarantee concentration when data points are correlated? The key is to shift our focus from the raw data points to their innovations—the unexpected information introduced at each step.
Mathematically, this is achieved by framing the sequence of learning errors or parameter updates as a martingale or a martingale difference sequence. Intuitively, a martingale models a fair game: given the entire history of a process up to time $t$, the expected value of the next step is exactly equal to the current value. For a martingale difference sequence $X_t$, the conditional expectation of the next step given the past is zero:
$$\mathbb{E}[X_t \mid X_1, X_2, \dots, X_{t-1}] = 0$$
Even though $X_t$ depends on the history, its deviation from its conditional mean is unbiased. This single property is incredibly powerful: it unlocks generalized concentration inequalities, such as the Azuma-Hoeffding inequality and martingale Bernstein inequalities. Instead of requiring absolute independence, we only require that the conditional expectations remain stable over time.
i.i.d. Assumption: [Data 1] ──(Independent)──> [Data 2] ──(Independent)──> [Data 3]
Martingale Assumption: [History] ──(Determines)──> [Conditional Mean] ──(Unbiased Innovation)──> [Next Step]
This perspective allows researchers to analyze highly adaptive systems. For example, Haoyu Chen et al. frame parameter updates in online decision-making as a martingale. This allows them to apply central limit theorems to non-i.i.d. data, proving asymptotic normality for estimators in contextual bandits.
In a completely different domain, Sanae Lotfi et al. use Azuma's inequality to treat individual tokens in a text stream as dependent data points rather than treating entire documents as single i.i.d. samples. This martingale-based approach yields the first non-vacuous generalization bounds for massive autoregressive language models like LLaMA2.
Sequential PAC-Bayesian Analysis
The PAC-Bayesian framework is one of the most flexible tools in learning theory. It provides generalization bounds for a distribution over models (a posterior $Q$) relative to an initial distribution (a prior $P$), typically penalizing complexity using the Kullback-Leibler (KL) divergence.
To adapt PAC-Bayes to sequential, non-i.i.d. settings, pioneering work by Yevgeny Seldin et al. integrated martingale concentration directly into the bound derivations. Instead of partitioning data into independent blocks, the authors bounded the moment-generating function of evolving processes. This foundational step enabled the first PAC-Bayesian regret bounds for multiarmed bandits (Yevgeny Seldin et al.) and contextual bandits (Yevgeny Seldin et al.), where the performance guarantees scale naturally with the mutual information between states and actions.
To make these bounds tighter and more adaptive, subsequent work has focused on two key improvements:
- Variance Awareness: By developing a PAC-Bayes-Bernstein inequality for martingales, Yevgeny Seldin et al. incorporated variance information into the bound. This allows the guarantee to adapt to the specific difficulty of the sequential task, which is crucial for balancing exploration and exploitation.
- Time-Uniform Validity: Traditional bounds hold only for a fixed, pre-specified number of samples $n$. However, Ben Chugg et al. introduced a unified recipe for time-uniform PAC-Bayes bounds. By leveraging martingale structures, these bounds are anytime-valid, meaning they remain mathematically sound even if an experimenter continuously monitors the data stream or stops early based on intermediate results. This mathematical foundation also enables tracking high-dimensional sequential data streams over time via confidence spheres (Ben Chugg et al.).
Handling Heavy Tails and Non-Stationarity
Martingale theory also provides elegant solutions to two other common failure modes of classical learning theory: heavy-tailed distributions and non-stationary environments.
Heavy Tails via Supermartingales
Standard concentration inequalities assume light-tailed losses (e.g., bounded or sub-Gaussian errors). When data streams exhibit heavy tails (where variance is bounded but higher moments are not), standard exponential bounds fail.
Maxime Haddouche et al. resolved this by replacing Markov's inequality with Ville's inequality for supermartingales. This shift allows for the derivation of robust generalization bounds for non-i.i.d. streaming data with heavy-tailed losses, providing a theoretical foundation for online learning algorithms that operate in volatile environments (Maxime Haddouche et al.).
Algorithmic Robustness in Markov Chains
An alternative way to guarantee generalization without relying on PAC-Bayes complexity measures is algorithmic robustness. An algorithm is robust if similar training inputs lead to similar performance errors.
Huan Xu et al. and Shie Mannor et al. demonstrated that this geometric framework can be extended to non-i.i.d. data by analyzing processes driven by Markov chains. By partitioning the state space of a Markovian process into robust sets, the authors proved that an algorithm can achieve uniform convergence even when subsequent data points are inherently dependent on previous states. Similarly, Fei Tian et al. showed that modeling strategic sequential interactions as higher-dimensional stationary Markov chains provides rigorous generalization guarantees for predicting agent behavior in dynamic environments like digital auctions.
Applications Across Interactive Domains
By relaxing the i.i.d. requirement, these theoretical tools provide concrete performance guarantees across several interactive machine learning paradigms:
- Reinforcement Learning under Abstraction: In model-based RL, agents often use state abstractions to simplify complex environments. However, abstraction can destroy the Markov property, making the agent's observed history highly dependent and non-Markovian. Rolf A. N. Starre et al. applied the Azuma-Hoeffding inequality to these dependent samples, establishing the first formal concentration bounds and performance guarantees for RL from abstracted observations.
- Lifelong Learning: When an agent faces a sequence of distinct but related multiarmed bandit tasks, Hamish Flynn et al. utilized martingale Bernstein inequalities to safely transfer knowledge from past tasks to new ones, accelerating reward accumulation without violating safety bounds.
- Active Learning and Optimization: In active learning and Bayesian optimization, the data collection process is explicitly biased because the algorithm chooses its next sample based on past observations. Frameworks developed by Hideaki Ishibashi et al. and Rafael Oliveira et al. leverage sequential bounds to determine exact convergence guarantees and stopping criteria, eliminating the need for independent hold-out validation sets.
Key Foundational Work
PAC-Bayesian Analysis of Martingales and Multiarmed Bandits (2011) — contributed 2 concept elements to this direction.
Robustness and Generalization (2010) — contributed 2 concept elements to this direction.
PAC-Bayesian Inequalities for Martingales (2011) — contributed 1 concept elements to this direction.