# Optimal anytime regret with two experts

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

## Key facts

- Cited by 16 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 20 Feb 2020.

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

- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [Discounted Adaptive Online Learning: Towards Better Regularization](https://mlsanity.com/paper/2402.02720/) (2024)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers](https://mlsanity.com/paper/2110.14804/) (2021)
- [Improving Adaptive Online Learning Using Refined Discretization](https://mlsanity.com/paper/2309.16044/) (2023)
- [Continuous Prediction with Experts' Advice](https://mlsanity.com/paper/2206.00236/) (2022)
- [Efficient and Optimal Fixed-Time Regret with Two Experts](https://mlsanity.com/paper/2203.07577/) (2022)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit](https://mlsanity.com/paper/2202.05767/) (2022)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [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)
- [Reasoning without Regret](https://mlsanity.com/paper/2504.09777/) (2025)
- [Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs](https://mlsanity.com/paper/2602.06545/) (2026)
- [Cogentic: Multi-Agent Orchestration for Automated Proof Discovery](https://mlsanity.com/paper/2609.40324/) (2026)

## Abstract (arXiv)

We consider the classical problem of prediction with expert advice. In the fixed-time setting, where the time horizon is known in advance, algorithms that achieve the optimal regret are known when there are two, three, or four experts or when the number of experts is large. Much less is known about the problem in the anytime setting, where the time horizon is not known in advance. No minimax optimal algorithm was previously known in the anytime setting, regardless of the number of experts. Even for the case of two experts, Luo and Schapire have left open the problem of determining the optimal algorithm. We design the first minimax optimal algorithm for minimizing regret in the anytime setting. We consider the case of two experts, and prove that the optimal regret is γ √t / 2 at all time steps t, where γ is a natural constant that arose 35 years ago in studying fundamental properties of Brownian motion. The algorithm is designed by considering a continuous analogue of the regret problem, which is solved using ideas from stochastic calculus.