# Efficient and Optimal Fixed-Time Regret with Two Experts

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 24 references that are in the map.
- First posted on arXiv 15 Mar 2022.

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

- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [New Potential-Based Bounds for Prediction with Expert Advice](https://mlsanity.com/paper/1911.01641/) (2019)
- [Optimal anytime regret with two experts](https://mlsanity.com/paper/2002.08994/) (2020)
- [Finite-Time 4-Expert Prediction Problem](https://mlsanity.com/paper/1911.10936/) (2019)
- [Towards Optimal Algorithms for Prediction with Expert Advice](https://mlsanity.com/paper/1409.3040/) (2014)
- [Tight Lower Bounds for Multiplicative Weights Algorithmic Families](https://mlsanity.com/paper/1607.02834/) (2016)
- [Experimental Evidence for Asymptotic Non-Optimality of Comb Adversary Strategy](https://mlsanity.com/paper/1912.01548/) (2019)

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

- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [Improving Adaptive Online Learning Using Refined Discretization](https://mlsanity.com/paper/2309.16044/) (2023)
- [Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant](https://mlsanity.com/paper/2609.27206/) (2026)
- [A PDE approach for regret bounds under partial monitoring](https://mlsanity.com/paper/2209.01256/) (2022)
- [Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs](https://mlsanity.com/paper/2602.06545/) (2026)

## Abstract (arXiv)

Prediction with expert advice is a foundational problem in online learning. In instances with T rounds and n experts, the classical Multiplicative Weights Update method suffers at most √(T/2)ln n regret when T is known beforehand. Moreover, this is asymptotically optimal when both T and n grow to infinity. However, when the number of experts n is small/fixed, algorithms with better regret guarantees exist. Cover showed in 1967 a dynamic programming algorithm for the two-experts problem restricted to 0,1 costs that suffers at most √T/2π + O(1) regret with O(T2) pre-processing time. In this work, we propose an optimal algorithm for prediction with two experts' advice that works even for costs in [0,1] and with O(1) processing time per turn. Our algorithm builds up on recent work on the experts problem based on techniques and tools from stochastic calculus.