Information-Theoretic Generalization Bounds for Sequential Decision Making

Authors: Futoshi Futami, Masahiro Fujisawa

arXiv · PDF

Summary

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.

Relevance

Not directly related to my persona/midtraining or behavioral installation work—this is theoretical generalization analysis for sequential decision-making. Could be tangentially useful if I ever need rigorous generalization guarantees for adaptive fine-tuning schedules or active data selection during training.

Threat model

Potential threat/caveat for clean result "Fine-tuning one persona on a two-marker chunk and another on the start marker plants the end marker at every donor answer's end, not chained to the start (LOW confidence)": this item discusses limitation.

Abstract

arXiv:2605.12190v1 Announce Type: new Abstract: Information-theoretic generalization bounds based on the supersample construction are a central tool for algorithm-dependent generalization analysis in the batch i.i.d.~setting. However, existing supersample conditional mutual information (CMI) bounds do not directly apply to sequential decision-making problems such as online learning, streaming active learning, and bandits, where data are revealed adaptively and the learner evolves along a causal trajectory. To address this limitation, we develop a sequential supersample framework that separates the learner filtration from a proof-side enlargement used for ghost-coordinate comparisons. Under a row-wise exchangeability assumption, the sequential generalization gap is controlled by sequential CMI, a sum of roundwise selector--loss information terms. We also establish a Bernstein-type refinement that yields faster rates under suitable variance conditions. The selector-SCMI proof strategy applies to online learning, streaming active learning with importance weighting, and stochastic multi-armed bandits.