The exact finite-horizon minimax regret of prediction with three and four experts, and the exact deficit of the comb adversary
Abstract
In the classical game of prediction with expert advice — k experts, T rounds, binary gains, full information, an adaptive adversary — the minimax expected regret V_T(k) is a rational number, but to our knowledge only the case k = 2 (Cover, 1965) is in print exactly: for k ≥ 3 the literature gives asymptotics, the geometric-horizon variant, or a continuum limit. We determine V_T(3) for every 1 ≤ T ≤ 12 and V_T(4) for every 1 ≤ T ≤ 10. For three experts the values obey the closed form V_T(3) = frac((4⌈ T/2⌉ + [T even])C(T, ⌊ T/2⌋))3 · 2^(T) = (2 E|S_T| + ℙ(S_T = 0))/(3), S a simple random walk — the three-expert companion of Cover's V_T(2) = E|S_T|/2 — and the approximating expression published by Abbasi-Yadkori, Bartlett and Gabillon for even T exceeds the exact value by exactly ℙ(S_T = 0)/3. We also compute exactly what the comb adversary of Gravin, Peres and Sivan — conjectured by them to be asymptotically optimal for every k — inflicts at finite horizon: for k = 3 it is strictly suboptimal at every 1 ≤ T ≤ 12, with deficit 1/6, 1/12, 1/8, 1/16, …, 191/4096; for k = 4 it is strictly suboptimal at T = 1 and at every 3 ≤ T ≤ 10, and exactly optimal at T = 2. The bound holds for the whole class of "two teams by rank, fair coin" adversaries, of which the comb adversary is the best member. Every value is certified on both sides by an explicit per-state certificate (a player mixed strategy and a balanced adversary distribution), glued by weak duality, and machine-checked in Lean 4; Section [sec:verif] says exactly what is and what is not formalised.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
26230cf8bb430821af78cedc2149c1a60f285d3027ea12b964401e5dc1bb842c
Claim ledger
Stated results
EK1candidate2026-09-03
V_T(3) = (4*ceil(T/2) + [T even]) * C(T, floor(T/2)) / (3 * 2^T) for every 1 <= T <= 12: the exact minimax regret of the T-round, 3-expert, binary-gain, full-information game, certified on both sides (a player mixed strategy per state and a balanced adversary vertex per state, glued by weak duality proved with no minimax theorem). Equivalently V_T(3) = (2*E|S_T| + P(S_T = 0))/3 for a simple random walk S – the three-expert companion of Cover's V_T(2) = E|S_T|/2
EK2candidate2026-09-03
The expression of Abbasi-Yadkori-Bartlett-Gabillon (NIPS 2017, Theorem 2), C(T+2, T/2+1)*(T/2+1)/(3*2^T), exceeds the exact value V_T(3) by exactly C(T, T/2)/(3*2^T) = P(S_T = 0)/3, at every even 1 <= T <= 12
EK3candidate2026-09-03
For three experts and every 1 <= T <= 12: the exact value of the best 'two teams by rank, one team gains, fair coin' adversary – the class containing the COMB adversary of Gravin-Peres-Sivan with every tie-breaking and every mixture – is c_T = 1/2, 3/4, 7/8, 17/16, 37/32, 83/64, 177/128, 383/256, 807/512, 1713/1024, 3579/2048, 7509/4096, and c_T < V_T(3) with the exact gaps 1/6, 1/12, 1/8, 1/16, 3/32, 11/192, 29/384, 41/768, 33/512, 51/1024, 117/2048, 191/4096. So no COMB adversary is minimax optimal at any of these horizons
EK4candidate2026-09-03
The exact minimax regret of the T-round, 4-expert, binary-gain, full-information game for every 1 <= T <= 10: V_T(4) = 3/4, 1, 23/20, 4/3, 29/20, 8/5, 1283/750, 329/180, 15433/8000, 21923/10800
EK5candidate2026-09-03
For four experts: the exact value of the best 'two teams by rank, fair coin' (COMB-class) adversary is c_T = 1/2, 1, 1, 5/4, 11/8, 3/2, 53/32, 111/64, 241/128, 499/256 for T = 1..10, strictly below V_T(4) at T = 1 and at every 3 <= T <= 10 with gaps 1/4, -, 3/20, 1/12, 3/40, 1/10, 653/12000, 269/2880, 741/16000, 13943/172800, and EQUAL to V₂(4) = 1 at T = 2
EK6routine2026-09-03
The formalisation layer: Guar / Force (the player's guarantee and the adversary's force, defined by induction on the remaining rounds), weak duality forceₗe_guar proved directly with NO minimax theorem, uniqueness of the value, the shift lemmas, AntiHold and Play for the antipodal adversary class, playₗeₐntihold (a matching Play/AntiHold pair pins the class's exact value), and four table lemmas turning a finite rational certificate table into each of the four predicates
EK7known2026-09-03
Cover's 1965 two-expert value V_T(2) = ceil(T/2) * C(T, floor(T/2)) / 2^T, kernel-checked at every 1 <= T <= 12 by the same machinery that produces the k = 3 and k = 4 values; and, as the matching control, the COMB adversary IS exactly minimax optimal for two experts at every one of those horizons
EK8routine2026-09-03
Negative controls: no player strategy guarantees less than the tabulated value and no adversary forces more (both directions, k = 3 and k = 4); no player strategy holds the COMB class below c_T; the COMB adversary does not yield the minimax value (through Play and its uniqueness); and the hypotheses carried by every table lemma are satisfied by the initial state with strictly positive values
EK9prose2026-09-03
The exact minimax regret for FIVE experts at every 1 <= T <= 10: V_T(5) = 4/5, 11/10, 5/4, 103/70, 193/120, 53/30, 2117/1120, 13351/6615, 150359/70560, 667189/297675
This ledger entry is reported in prose and is not bound to a Lean theorem.EK10prose2026-09-03
The closed form of EK1 holds at every 1 <= T <= 60, i.e. 3 * 2^T * V_T(3) = A152548(T); and the COMB gap V_T(3) - c_T is strictly positive at every one of those horizons. A proof for all T is open
This ledger entry is reported in prose and is not bound to a Lean theorem.Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Fix k experts and a horizon T. On each of T rounds an adversary sets a gain gᵢt ∈ 0,1 for every expert i; simultaneously the player, who has seen all previous rounds' gains but not this round's, picks an expert j(t) (and may randomise). The player receives g_(j(t),t); then all k gains are revealed. After T rounds the player's regret is
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7