This paper proposes a nonparametric Bayesian method for online sequence prediction that is computationally efficient and comes with universal performance guarantees (meaning it performs nearly as well as the best possible predictor in the long run, without knowing the data-generating process in advance). Traditional Bayesian predictive models can be complex; this work introduces simplifications that maintain theoretical optimality. The method is essentially an online learning algorithm that updates beliefs over sequence patterns with low complexity per update. The approach yields strong theoretical bounds and performs competitively in experiments, demonstrating a practical balance of speed, simplicity, and predictive power.
@inproceedings{Lheritier2019Online,
author = {Alix Lh{\'e}ritier and Faustin Cazals},
title = {Low-Complexity Nonparametric Bayesian Online Prediction with Universal Guarantees},
booktitle = {Advances in Neural Information Processing Systems 32 (NeurIPS 2019)},
year = {2019}
}