Online universal learning from information-theoretic perspective

Online learning is a foundational paradigm underlying applications from recommendation systems to the continual learning of modern AI models. Yet much of its theory centers on either fully adversarial or purely stochastic settings. However, real-world environments typically fall between these extremes, making classical models inadequate for describing practical behavior. This monograph develops a unified perspective for analyzing online learning under more nuanced and realistic environments. The authors approach the problem through the lens of universality from information theory and extend tools such as the Shtarkov sum, covering numbers and packing arguments to the online setting, revealing deeper structural connections between these two fields. Building on this viewpoint, they characterize minimax regret for logarithmic and Lipschitz losses, analyze expected regret under i.i.d. and more general stochastic processes and study hybrid adversarial–stochastic scenarios. The authors further develop constructive algorithms that achieve near-optimal regret guarantees, yielding a coherent and fine-grained information-theoretic framework of online universal learning.