On prediction from expert advice with more than five experts

Jeff Calder; Nadejda Drenska

math.APOct 4, 2026

On prediction from expert advice with more than five experts

Authors: Jeff Calder, Nadejda Drenska

Organizations: School of Mathematics, University of Minnesota · Department of Mathematics, Louisiana State University

Abstract

We prove that no single rank ordered adversary strategy is globally optimal for the prediction with expert advice problem with six or more experts, in both the geometric stopping and finite time horizon settings. The proof is based on establishing a leading order correction when one expert moves far ahead of the others. This allows us to connect optimal strategies between $n$ and $j<n$ experts and utilize recent results on the exact optimality set for the five expert problem.

Explore similar work

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
Sep 23, 2026Yang Cai, Vineet Gupta, Yanchen Jiang +4\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Regret
Google Research · Yale University · Google DeepMind
An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB
Sep 14, 2026Jeff Calder, Nadejda DrenskaOptimality Exact
School of Mathematics, University of Minnesota · Department of Mathematics, Louisiana State University
A Mathematical Optimization Approach for Expert-Informed Bayesian Best Subset Selection
Jun 28, 2026Nolan Alexander, Henning MortveitModel Selection Probability
Systems and Information Engineering University of Virginia

Sep 23, 2026, stat.MLJ/K move · Enter open · S save

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw+3

Google Research · Yale University · Google DeepMind

\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Regret Weight Decay

Open paper AskPDF arXiv

Prediction with expert advice is a fundamental problem in online learning. When the time horizon

T

is known in advance, the minimax cumulative regret over

n

experts is asymptotically

\sqrt{\frac{T \ln n}{2}}

. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to

T

, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time

t

, the best known guarantee has been

\sqrt{t \ln n}

---a factor of

\sqrt{2}

worse---and it has remained unknown whether this factor of

\sqrt{2}

is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies

R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2}

simultaneously for every

t \ge 1

Abstract

Explore similar work

Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB

A Mathematical Optimization Approach for Expert-Informed Bayesian Best Subset Selection