# New Potential-Based Bounds for Prediction with Expert Advice

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2019.

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

- [Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications](https://mlsanity.com/paper/2108.03837/) (2021)
- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [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)
- [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)
- [A PDE-Based Analysis of the Symmetric Two-Armed Bernoulli Bandit](https://mlsanity.com/paper/2202.05767/) (2022)
- [Numerical solution of a PDE arising from prediction with expert advice](https://mlsanity.com/paper/2406.05754/) (2024)
- [An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB](https://mlsanity.com/paper/2609.14892/) (2026)
- [A New Approach to Drifting Games, Based on Asymptotically Optimal Potentials](https://mlsanity.com/paper/2207.11405/) (2022)
- [Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant](https://mlsanity.com/paper/2609.27206/) (2026)
- [Optimal Tracking in Prediction with Expert Advice](https://mlsanity.com/paper/2208.03708/) (2022)
- [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)
- [On prediction from expert advice with more than five experts](https://mlsanity.com/paper/2610.05186/) (2026)

## Abstract (arXiv)

This work addresses the classic machine learning problem of online prediction with expert advice. We consider the finite-horizon version of this zero-sum, two-person game. Using verification arguments from optimal control theory, we view the task of finding better lower and upper bounds on the value of the game (regret) as the problem of finding better sub- and supersolutions of certain partial differential equations (PDEs). These sub- and supersolutions serve as the potentials for player and adversary strategies, which lead to the corresponding bounds. To get explicit bounds, we use closed-form solutions of specific PDEs. Our bounds hold for any given number of experts and horizon; in certain regimes (which we identify) they improve upon the previous state of the art. For two and three experts, our bounds provide the optimal leading order term.