# Optimal Tracking in Prediction with Expert Advice

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

## Key facts

- Cited by 1 papers in the map (data through 7 Oct 2026).
- Builds on 10 of its 41 references that are in the map.
- First posted on arXiv 7 Aug 2022.

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

- [Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient](https://mlsanity.com/paper/1605.04638/) (2016)
- [Optimally Efficient Sequential Calibration of Binary Classifiers to Minimize Classification Error](https://mlsanity.com/paper/2108.08780/) (2021)
- [Prediction with Expert Advice: a PDE Perspective](https://mlsanity.com/paper/1904.11401/) (2019)
- [New Potential-Based Bounds for Prediction with Expert Advice](https://mlsanity.com/paper/1911.01641/) (2019)
- [Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environments](https://mlsanity.com/paper/2009.09249/) (2020)
- [Towards Optimal Algorithms for Prediction with Expert Advice](https://mlsanity.com/paper/1409.3040/) (2014)
- [Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1911.11122/) (2019)
- [Online Second Price Auction with Semi-bandit Feedback Under the Non-Stationary Setting](https://mlsanity.com/paper/1911.05949/) (2019)
- [Learning Latent Features with Pairwise Penalties in Low-Rank Matrix Completion](https://mlsanity.com/paper/1802.05821/) (2018)
- [Universal Online Convex Optimization with Minimax Optimal Second-Order Dynamic Regret](https://mlsanity.com/paper/1907.00497/) (2019)

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

- [When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses](https://mlsanity.com/paper/2506.01722/) (2025)

## Abstract (arXiv)

We study the prediction with expert advice setting, where the aim is to produce a decision by combining the decisions generated by a set of experts, e.g., independently running algorithms. We achieve the min-max optimal dynamic regret under the prediction with expert advice setting, i.e., we can compete against time-varying (not necessarily fixed) combinations of expert decisions in an optimal manner. Our end-algorithm is truly online with no prior information, such as the time horizon or loss ranges, which are commonly used by different algorithms in the literature. Both our regret guarantees and the min-max lower bounds are derived with the general consideration that the expert losses can have time-varying properties and are possibly unbounded. Our algorithm can be adapted for restrictive scenarios regarding both loss feedback and decision making. Our guarantees are universal, i.e., our end-algorithm can provide regret guarantee against any competitor sequence in a min-max optimal manner with logarithmic complexity. Note that, to our knowledge, for the prediction with expert advice problem, our algorithms are the first to produce such universally optimal, adaptive and truly online guarantees with no prior knowledge.