Introduction
In the field of online learning, a forecaster aims to predict a sequence of outcomes sequentially, minimizing the cumulative regret. Regret is defined as the difference between the forecaster's total loss and the loss of the best fixed model (expert) chosen in hindsight. Under logarithmic loss, the theoretically perfect strategy is the Normalized Maximum Likelihood (NML).
However, NML suffers from two significant practical limitations that often make it a "deal-breaker" for real-world applications:
- The Horizon Problem: The forecaster must know the exact length of the data sequence ($n$) in advance.
- Computational Complexity: It requires calculating a massive integral over all possible future sequences, which is often mathematically or computationally intractable.
Practical Alternatives: SNML and Bayesian Prediction
To circumvent the limitations of NML, researchers and practitioners often turn to two alternatives: Sequential Normalized Maximum Likelihood (SNML) and Bayesian prediction. SNML operates greedily, applying the NML logic at each individual step as if it were the final one, thereby removing the horizon problem. Bayesian prediction uses a prior distribution to weight models. While these methods are known to be effective, this paper addresses a fundamental theoretical gap: When are these practical shortcuts actually optimal?
The Role of Exchangeability
The central contribution of this work is identifying exchangeability as the necessary and sufficient condition for SNML's optimality. A sequence is exchangeable if its joint probability distribution remains invariant regardless of how the data points are shuffled.
The authors prove that this simple symmetry property is the "missing link" binding SNML, NML, and Bayesian methods together. Specifically, Theorem 3.1 establishes that SNML is equivalent to NML (and thus minimax optimal) if and only if the joint distribution defined by SNML is exchangeable.
The Grand Equivalence in Exponential Families
The paper focuses its analysis on canonical maximal exponential families, a broad class of distributions that includes the Gaussian, Poisson, and Gamma distributions. For these models, the authors establish a "Grand Equivalence" (Theorem 3.3), proving that the following conditions are equivalent:
- The SNML strategy is exchangeable.
- The SNML strategy is identical to the NML strategy.
- The strategy is equivalent to a Bayesian prediction using the Jeffreys prior.
This result provides a deep theoretical justification for the Jeffreys prior in objective Bayesian statistics, showing it to be the gold standard for minimizing regret when exchangeability holds.
Illustrative Cases
As a theoretical study, the authors evaluate their theorems using classic mathematical models as test cases:
- Exponential Distribution: In this case, the theory holds perfectly. SNML, NML, and Bayesian prediction with a Jeffreys prior all converge to the same optimal strategy, demonstrating that the horizon problem vanishes when exchangeability is present.
- Bernoulli Distribution: Conversely, for the Bernoulli distribution, SNML is shown to be not exchangeable. This explains why SNML and NML differ in this common case and why SNML remains slightly sub-optimal for binary sequences.
Conclusion and Limitations
This research clarifies the relationship between sequential prediction and batch-optimal strategies by characterizing optimality through the lens of exchangeability. While these results offer a powerful litmus test for model optimality, they are currently limited to parametric constant experts and canonical exponential families. Future work is needed to explore the "non-exchangeable gap" in models like the Bernoulli distribution and to extend these findings to more complex, non-stationary, or non-parametric models.
Summary updated