# Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension

arXiv: https://arxiv.org/abs/2302.13849 · HTML: https://mlsanity.com/paper/2302.13849/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 61 references that are in the map.
- First posted on arXiv 27 Feb 2023.

## Builds on (most cited first, 15 of 15)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [Sample Complexity Bounds on Differentially Private Learning via Communication Complexity](https://mlsanity.com/paper/1402.6278/) (2014)
- [A General Characterization of the Statistical Query Complexity](https://mlsanity.com/paper/1608.02198/) (2016)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [Towards Optimal Algorithms for Prediction with Expert Advice](https://mlsanity.com/paper/1409.3040/) (2014)
- [Towards Minimax Online Learning with Unknown Time Horizon](https://mlsanity.com/paper/1307.8187/) (2013)
- [A Drifting-Games Analysis for Online Learning and Applications to Boosting](https://mlsanity.com/paper/1406.1856/) (2014)
- [Online Learning with an Almost Perfect Expert](https://mlsanity.com/paper/1807.11169/) (2018)

## Built on by (most cited first, 18 of 18)

- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024)
- [Multiclass Online Learnability under Bandit Feedback](https://mlsanity.com/paper/2308.04620/) (2023)
- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)
- [Online Learning of Neural Networks](https://mlsanity.com/paper/2505.09167/) (2025)
- [Bounds on the price of feedback for mistake-bounded online learning](https://mlsanity.com/paper/2401.05794/) (2024)
- [Deterministic Apple Tasting](https://mlsanity.com/paper/2410.10404/) (2024)
- [Mistake-bounded online learning with operation caps](https://mlsanity.com/paper/2509.03892/) (2025)
- [Partial Feedback Online Learning](https://mlsanity.com/paper/2601.21462/) (2026)
- [An Optimal Agnostic PAC Algorithm](https://mlsanity.com/paper/2608.06363/) (2026)
- [Worst-case Error Bounds for Online Learning of Smooth Functions](https://mlsanity.com/paper/2502.16388/) (2025)
- [Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings](https://mlsanity.com/paper/2510.00574/) (2025)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [A Combinatorial Characterization of Supervised Online Learnability](https://mlsanity.com/paper/2307.03816/) (2023)
- [Ambiguous Online Learning](https://mlsanity.com/paper/2506.19810/) (2025)
- [Discriminative Feature Feedback with General Teacher Classes](https://mlsanity.com/paper/2510.07245/) (2025)
- [Thompson Sampling Is 2-Competitive for Mistakes](https://mlsanity.com/paper/2607.12389/) (2026)

## Abstract (arXiv)

A classical result in online learning characterizes the optimal mistake bound achievable by deterministic learners using the Littlestone dimension (Littlestone '88). We prove an analogous result for randomized learners: we show that the optimal expected mistake bound in learning a class H equals its randomized Littlestone dimension, which is the largest d for which there exists a tree shattered by H whose average depth is 2d. We further study optimal mistake bounds in the agnostic case, as a function of the number of mistakes made by the best function in H, denoted by k. We show that the optimal randomized mistake bound for learning a class with Littlestone dimension d is k + Theta (√k d + d ). This also implies an optimal deterministic mistake bound of 2k + Theta(d) + O(√k d), thus resolving an open question which was studied by Auer and Long ['99]. As an application of our theory, we revisit the classical problem of prediction using expert advice: about 30 years ago Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire and Warmuth studied prediction using expert advice, provided that the best among the n experts makes at most k mistakes, and asked what are the optimal mistake bounds. Cesa-Bianchi, Freund, Helmbold, and Warmuth ['93, '96] provided a nearly optimal bound for deterministic learners, and left the randomized case as an open problem. We resolve this question by providing an optimal learning rule in the randomized case, and showing that its expected mistake bound equals half of the deterministic bound of Cesa-Bianchi et al. ['93,'96], up to negligible additive terms. In contrast with previous works by Abernethy, Langford, and Warmuth ['06], and by Branzei and Peres ['19], our result applies to all pairs n,k.