📊 statistics

Information-Theoretic Generalization Bounds for Sequential Decision Making

This paper introduces a sequential supersample framework that extends information-theoretic generalization bounds to adaptive sequential decision-making problems by separating the learner's filtration from a proof-side enlargement, thereby enabling the control of generalization gaps via sequential conditional mutual information for tasks like online learning and bandits.

Original authors: Futoshi Futami, Masahiro Fujisawa

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Futoshi Futami, Masahiro Fujisawa

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to play a video game. In a simple game, you show the robot a thousand random levels all at once, let it study them, and then test it on a new level. This is like the "batch" learning the paper talks about.

But in the real world, learning is often a sequential adventure. The robot plays a level, learns from it, changes its strategy, and then the game generates the next level based on what the robot just did. The robot is walking a path, and every step it takes changes the scenery ahead. This is "sequential decision making" (like online learning, active learning, or bandits).

The problem is: How do we know if the robot is actually learning the game, or just memorizing the specific path it walked?

The Old Tool: The "Ghost" Mirror

In the simple "batch" world, researchers use a clever trick called Supersample Construction. Imagine you give the robot two identical copies of a level, but you hide one behind a curtain (a "ghost" level). You tell the robot, "Pick one to study."

If the robot picks the left one, it studies the left.
The researchers then peek at the right one (the ghost) to see how the robot would have done if it had picked that instead.

By comparing the robot's performance on the chosen path vs. the ghost path, they can measure how much the robot "overfitted" (memorized) the specific choice it made. This measurement is called Conditional Mutual Information (CMI).

The Problem: The Robot is Moving Too Fast

The old trick works great when the levels are static. But in a sequential game, the robot's choice today changes the levels tomorrow.

If you try to use the old "ghost mirror" at the very end of the game, you can't tell when the robot started memorizing the path. Did it memorize step 1? Step 50? Or step 100?
The old method treats the whole game as one big block, but the robot is walking a causal chain where every step depends on the last.

The New Solution: The "Causal" Ghost

This paper introduces a new framework called Sequential CMI (SCMI). Think of it as upgrading the ghost mirror to a live, round-by-round camera.

Instead of waiting until the end of the game to check the ghost, the researchers set up a special "proof-side" room.

The Learner's Room: The robot sees only the level it chose. It updates its brain.
The Proof Room: A researcher stands in a separate room. They see both the chosen level and the ghost level for that specific round.
The Swap: Before the robot moves to the next round, the researcher swaps the levels in their mind. They ask: "If the robot had picked the ghost level right now, how would its brain look different?"

By doing this at every single step, they can measure exactly how much information the robot "leaked" about its choice at that specific moment. They sum up these tiny leaks to get a total "overfitting budget."

The Three Games They Tested

The authors tested this new "live camera" method on three types of sequential games:

Online Learning (The Infinite Stream): Imagine a news feed that never ends. The robot reads an article, predicts the next one, and the feed changes based on that.
- The Result: They showed that this new method connects to a concept called "Littlestone dimension," which is like counting how many different "storylines" the robot could possibly get stuck in. It proves the robot isn't just memorizing the news feed but actually understanding the pattern.
Streaming Active Learning (The Curious Student): Imagine a student who can ask a teacher for the answer to some questions but not others (to save time). The student decides which questions to ask based on what they already know.
- The Result: The method handles the "importance weighting" (giving more credit to the questions the student actually asked). It proves that even though the student is picky about what they learn, they aren't cheating by memorizing the answers they didn't ask for.
Stochastic Bandits (The Slot Machine): Imagine a row of slot machines. You pull one lever, get a reward, and decide which one to pull next. You don't know the odds of the others.
- The Result: This is the big win. Previous methods gave a "slow" guarantee (like saying the robot will get better, but maybe very slowly). This new method, combined with a variance trick (like checking how "jumpy" the rewards are), gives a "fast-rate" guarantee. It proves the robot learns much faster, with a regret (mistakes made) that grows with the square root of time, rather than a slower, messier rate.

The "Fast" Secret: The Variance Trick

The paper also mentions a "Bernstein-type refinement."

The Slow Way: Imagine guessing the average height of people in a room. If you just say "everyone is between 4 and 8 feet," your guess is safe but vague.
The Fast Way: If you notice that everyone is actually between 5'6" and 5'10", you can make a much sharper, more accurate guess.
In the bandit game, the researchers realized that if the rewards aren't too "jumpy" (low variance), they can tighten their bound significantly. This turns a "safe but slow" prediction into a "sharp and fast" one.

Summary

In simple terms, this paper built a time-traveling audit tool for learning algorithms.

Old Tool: Looked at the whole journey at the end and guessed where the mistakes happened.
New Tool (SCMI): Checks the learner's "memory leak" at every single step of the journey, comparing the real path with a ghost path in real-time.

This allows researchers to prove that learning algorithms for sequential tasks (like self-driving cars, stock trading bots, or medical trial selectors) are actually learning the rules of the game, rather than just memorizing the specific path they took.

Technical Summary: Information-Theoretic Generalization Bounds for Sequential Decision Making

Problem Statement
Information-theoretic (IT) generalization bounds, particularly those based on Conditional Mutual Information (CMI) and supersample constructions, have become a standard tool for algorithm-dependent analysis in the batch, independent and identically distributed (i.i.d.) setting. These methods measure how strongly a learning algorithm couples the training data to its output by comparing selected training coordinates against "ghost" (unselected) coordinates within a paired supersample. However, existing CMI frameworks rely on the symmetry of paired i.i.d. supersamples, a property that does not directly extend to sequential decision-making problems such as online learning, streaming active learning, and stochastic bandits. In these adaptive settings, data are revealed through history-dependent interactions, and the learner evolves along a causal trajectory. A terminal CMI term measuring dependence on the entire selector vector fails to reveal how information enters the trajectory at specific rounds, making it difficult to control the generalization gap in adaptive environments.

Methodology: The Sequential Supersample Framework
To address the limitations of batch CMI in adaptive settings, the authors propose a sequential supersample framework that separates the learner's filtration from a proof-side enlargement.

Causal Construction: The framework introduces a round-by-round construction where, at each time step $t$ , the environment generates a paired latent row $\tilde{Z}_t = (Z_{t,0}, Z_{t,1})$ . A fair selector $U_t \in \{0, 1\}$ chooses one coordinate ( $Z_t = Z_{t, U_t}$ ) for the learner to observe and update upon. The unselected coordinate ( $Z'_{t} = Z_{t, 1-U_t}$ ) remains unobserved by the learner but is retained for proof-side analysis as a "ghost" coordinate.
Filtration Separation:
- Learner History ( $H_t$ ): Contains only the information retained along the selected path (past observations, states, and selected actions).
- Proof-Side Enlargement ( $G_{t-1}$ ): A local sigma-field defined as $G_{t-1} = H_{t-1} \vee \sigma(\tilde{Z}_t)$ . This field exposes the full current paired row $(Z_{t,0}, Z_{t,1})$ only for the purpose of the proof, allowing a comparison between the selected and ghost coordinates while keeping the learner's state $W_t$ generated solely from the selected coordinate.
Sequential CMI (SCMI): The authors define Sequential CMI as the mutual information between the learner-induced loss (or state) and the current selector, conditioned on the proof-side enlargement: $I(L^+_t; U_t \mid G_{t-1})$ . This measures the information about the current selector revealed at the specific round where the comparison occurs, rather than aggregating information at the terminal time.
Assumptions: The framework relies on a selected-coordinate update condition (the learner updates only using the selected coordinate) and row-wise exchangeability (the joint distribution of the pair $(Z_{t,0}, Z_{t,1})$ is invariant under swapping, conditioned on the past).

Key Contributions and Results

General SCMI Bounds (Theorem 2):
The authors establish that the sequential generalization gap (train-holdout difference) is bounded by the sum of roundwise SCMI terms. Specifically, the gap is controlled by the square root of the sum of $I(L^+_t; U_t \mid G_{t-1})$ . This result generalizes the batch CMI identity to sequential settings, decomposing the generalization error into causal increments of selector information.
Bernstein-Type Refinement (Theorem 3):
Under a Bernstein condition (a bound on the conditional second moment of the excess loss), the authors derive a "fast-rate" bound where the information term enters linearly rather than via a square root. This yields tighter bounds when the variance of the loss is small.
Applications to Specific Sequential Problems:
- Online Learning (Section 3.3): The framework is applied to online learning, connecting SCMI to sequential Rademacher complexity and the Littlestone dimension. Under pathwise realizability, the SCMI sum is bounded by the logarithm of the sequential pattern growth, providing a combinatorial interpretation of the information bound.
- Streaming Active Learning (Section 4): The framework handles importance-weighted active learning where query decisions are adaptive. The proof-side enlargement includes query coins and label masks. The authors derive a bound for the terminal predictor's population risk, showing that the generalization gap is controlled by the SCMI of the importance-weighted losses.
- Stochastic Multi-Armed Bandits (Section 5): The authors apply the framework to bandits with smoothing (exponential weights). A key technical contribution here is a selector-comparison correction (Lemma 12) required because the terminal posterior depends on the entire selected trajectory. By using a past-retaining proof context and a variance calculation specific to the bandit gap, they derive a regret bound with a $\sqrt{KT}$ horizon dependence (up to logarithmic and gap-dependent factors). This improves upon existing PAC-Bayes bandit bounds which typically exhibit $O(K^{1/3}T^{2/3})$ dependence.

Significance and Claims
The paper claims that the primary contribution is the development of a causal supersample framework that transforms batch CMI analysis into a sum of roundwise selector-information increments. This approach:

Preserves the "ghost-sample" comparison essential for CMI bounds while respecting the causality of sequential decision-making.
Provides a unified template for analyzing generalization in online learning, active learning, and bandits.
Demonstrates that SCMI serves as the sequential analogue to batch CMI, maintaining the connection to combinatorial complexity measures like the Littlestone dimension.
Offers improved horizon dependence in bandit settings through the integration of SCMI with variance-aware Bernstein bounds and a novel selector-comparison correction.

The authors note that their bounds are currently expectation bounds for bounded losses. They identify high-probability guarantees, heavy-tailed losses, dynamic regret, and extensions to contextual bandits and reinforcement learning as open directions for future work. The framework is presented as a tool for algorithm-dependent analysis, bridging the gap between information-theoretic measures and the causal structure of adaptive learning processes.