The authors extend information-theoretic generalization bounds—a tool for understanding when learning algorithms will generalize from training to test data—to sequential decision-making settings like online learning and bandits. Previous bounds assumed data arrived all at once in a fixed batch, but here the learner sees data one piece at a time and adapts its strategy along the way. They show that under a "row-wise exchangeability" assumption (a technical condition meaning you can shuffle certain groups of data), the gap between training and test performance is controlled by a sum of information terms measuring how much each round's selection rule reveals about the loss.
Main takeaways:
- Existing generalization theory assumed batch i.i.d. data; this work handles sequential, adaptive settings (online learning, bandits, streaming active learning).
- The key technical move is a "sequential supersample" framework that separates the learner's own evolving data from a proof-side construction used for analysis.
- Generalization error is bounded by "sequential conditional mutual information"—roughly, a sum over rounds of how much information the selection rule leaks about the loss.
- They also derive a Bernstein-type bound that gives faster convergence rates when the variance is low.
- The framework applies to online learning, importance-weighted streaming active learning, and stochastic multi-armed bandits.