Skip to content

The finite-horizon five-expert prediction problem

Sep 2026 · 1 citation
Mathematics Computer Science

TL;DR

The solution formula establishes that the adversary's rank strategy $(1,0,1,0,0,0) is globally optimal, and the COMB strategy $(1,0,1,0,1) is optimal exactly on the set where $x_1=x_2$ and $x_3=x_4$.

Abstract

We give an explicit solution to the five expert prediction with expert advice partial differential equation (PDE) in the finite-time horizon setting. The solution formula establishes that the adversary's rank strategy $(1,0,1,0,0)$ is globally optimal, and the COMB strategy $(1,0,1,0,1)$ is optimal exactly on the set where $x_1=x_2$ and $x_3=x_4$. The formula is derived from the solution of the geometric-stopping problem given in our companion paper through the transform principle of Bayraktar, Ekren and Zhang, which links the two problems by a Laplace transform. Inverting the transform term by term expresses the solution through a series of Gaussian and complementary error function kernels. The optimality of $(1,0,1,0,0)$ is reduced to the signs of $41$ one-variable Gaussian series, which are certified with computer assistance by Poisson summation, first-mode domination and interval arithmetic on $1616$ rational cells. The proofs of our main theorems, certificates included, are also formalized in the Lean proof assistant.

View source

Similar papers

#machine learning Preprint Sep 2026

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

In this paper, we derive an explicit solution of the stationary prediction with expert advice PDE for five experts. The formula is given in three regions. In the first two regions, it is the four-expert solution plus a single integral with an elementary positive density. In the third region, it is a finite sum of hyper...

Jeff Calder, Nadejda Drenska · 2 citations
Preprint Sep 2026

Prediction with Five Experts and Geometric Stopping: A Probabilistic Construction and Analytic Verification

We present a solution of the limiting five-expert prediction problem with geometric stopping, based on stochastic calculus and partial differential equations. If $\delta$ is the stopping probability, the minimax expected regret from tied initial scores is $45\pi^2/(512\sqrt{2\delta})+o(\delta^{-1/2})$ as $\delta\downar...

Erhan Bayraktar, Ibrahim Ekren, N. Kolliopoulos · 3 citations
Preprint Oct 2026

Shifted-Chart Composition for Horizon-Optimal Time-Varying LQR

Horizon optimization in finite-horizon LQR treats the horizon $T$ as a decision variable and adds a penalty $wT$ to the cost. Recent composition-based methods evaluate all candidate horizons in $O(Nn^3)$, instead of the $O(N^2n^3)$ of one Riccati recursion per horizon, but they track the inverse cost-to-go $P^{-1}$ and...

Viswas Dinesh, Spandan Roy · 0 citations
Open access Nov 2026

Exact variational cost for small-noise exit time in a two-slope autoregressive model

We determine the quadratic variational cost that yields the large-deviation upper bound for the mean exit time from $(-1,1)$ in the small-noise regime for an autoregressive process driven by a continuous two-slope map f lying strictly below the diagonal on $(0,1)$. The Klebaner–Liptser reduction expresses this constant...

A. Aliev, A. Dzhalilov · 0 citations
Preprint Oct 2026

Low Residuals, Wrong Value: Learning the Viscosity Solution of Hamilton-Jacobi-Isaacs Equations with PINNs

This work uses the semiconcavity of the viscosity solution to build a mesh-free finite-difference test that needs only forward network evaluations and detects the folded solutions and the harmful min-of-charts failures without access to the exact value function.

Raúl Jiménez, Pablo Tejerina-Pérez, Leonid Sarieddine et al. · 0 citations
Preprint Oct 2026

Dynamical low-rank approximations for the optimal control of matrix ODEs

We consider the open-loop optimal control of a dynamical system whose state is described by a time-dependent matrix $X(t)\in\mathbb{R}^{m\times n}$. Gradient-based optimization methods may incur substantial computational and memory costs, particularly for large-scale systems and fine temporal discretizations. To allevi...

Benjamin Carrel, Tommaso Vanzan · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.