Information-Theoretic Generalization Bounds for Sequential Decision Making
Provides a theoretical foundation for algorithm-dependent generalization analysis in adaptive sequential settings, addressing a known gap in existing CMI bounds.
This work extends information-theoretic generalization bounds from batch i.i.d. settings to sequential decision-making problems (online learning, streaming active learning, bandits) by introducing a sequential supersample framework. The resulting sequential CMI bound controls the generalization gap, with a Bernstein-type refinement providing faster rates under variance conditions.
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.