# Online Learning with an Almost Perfect Expert

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2018.

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

- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [Online Learning of Neural Networks](https://mlsanity.com/paper/2505.09167/) (2025)
- [Deterministic Apple Tasting](https://mlsanity.com/paper/2410.10404/) (2024)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)

## Abstract (arXiv)

We study the multiclass online learning problem where a forecaster makes a sequence of predictions using the advice of n experts. Our main contribution is to analyze the regime where the best expert makes at most b mistakes and to show that when b = o(log4n), the expected number of mistakes made by the optimal forecaster is at most log4n + o(log4n). We also describe an adversary strategy showing that this bound is tight and that the worst case is attained for binary prediction.