Exact solution clarifies best advice strategy for five experts
An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB
Computer Science and Game TheoryMachine Learning
Summary
The paper solves a complex problem about predicting the best choice when given advice from five experts. The authors found a precise formula that works in different scenarios and showed which advice directions are best. They also disproved a previous guess about the best strategy, called COMB, showing it only works in specific cases. Their work involves detailed mathematical proof, some of which was checked by computer.
What this means in practice
- •For algorithm design teams: Use the exact solution to test and improve algorithms that aggregate advice from multiple experts in decision-making systems.
- •For machine learning engineers: Understand limits of existing prediction strategies like COMB when combining multiple model predictions for better ensemble methods.
A theory result. No direct application yet.
Authors
Jeff Calder, Nadejda Drenska
Abstract
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 hyperbolic products whose coefficients are determined by one scalar quadrature. Our formula establishes that the direction $(1,0,1,0,0)$ is optimal throughout the ordered sector, and that the COMB strategy $(1,0,1,0,1)$ is optimal only on a lower dimensional subset of the sector (where $x_1=x_2$ and $x_3=x_4$). This disproves the COMB optimality conjecture of Gravin, Peres and Sivan (2016). The verification of the Hamiltonian inequalities is a tedious task, part of which is completed with a computer assisted proof. The verification reduces to 21 scalar inequalities, which we prove using 147 exact rational Bernstein polynomial certificates. The exact certificates and their independent arithmetic checks are included in a supplement to this paper.