Exact finite-horizon minimax pseudoregret of the two-armed Bernoulli bandit for its two classical adversaries
Abstract
A learner pulls one of two Bernoulli arms for T rounds, sees only the reward of the arm it pulled, may randomise, and pays the pseudoregret (the gap times the expected number of pulls of the worse arm). We determine the minimax pseudoregret over randomised history-dependent learners, exactly, for the two adversary classes of the classical lower-bound arguments: the symmetric class, arms (1/2+e,1/2-e) or their swap, and the one-good-arm class, arms (1/2+e,1/2) or their swap; in both the adversary chooses e ∈ [0,1/2] as well as the labelling, and the learner knows neither. For the symmetric class the minimax at a fixed gap is attained by the follow-the-leader player at every gap (Kobzar–Kohn), so the minimax over the class is the maximum of one polynomial P_T; we compute P₅,…,P₈ exactly and enclose R^(*)(5),…,R^(*)(8) in rational windows of width 2 · 10⁻¹⁵, beyond the horizon T=4 at which Fabius and van Zwet stopped in 1970 calling the algebra prohibitive, and we prove that the best and the worst policy sit symmetrically about the fair-coin policy: P_T(e)+Pᵐᵃˣ_T(e)=2Te for all T and e. For the one-good-arm class no gap-independent optimal player exists, and the value is pinned by a sandwich: the exact value of the game at one rational gap from below, a gap-free policy certified by a polynomial inequality from above. The sandwich closes at K ≤ 3 and at K=5, where V^(*)(5)=27/50 exactly, at the gap 2/5; at K=4,6,7 it leaves windows of width at most 4 · 10⁻⁸. Every value, polynomial and certificate stated as a theorem is machine-checked in Lean 4 with Mathlib.
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
e6586bf0354d114efa7394cf50a2963cd87fbf047b40ff70d8e4996eb8ce526d
Claim ledger
Stated results
SM1known2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM2known2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM3routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM4routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM5known2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM6candidate2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM7routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM8routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM9routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM10routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
This ledger entry is reported in prose and is not bound to a Lean theorem.SM11candidate2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM12candidate2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM13routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
This ledger entry is reported in prose and is not bound to a Lean theorem.SM14routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM15routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM16routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM17candidate2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM18candidate2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
SM19routine2026-09-03
Statement description is not included in this imported ledger snapshot. See the PDF for the full theorem wording.
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Two Bernoulli arms whose means sum to one: (1/2 + e, 1/2 − e) or its arm-swap, with the gap ϵ = 2e and the identity of the better arm both chosen by the adversary. A learner with horizon T picks an arm each round from the history of *its own past arms and the rewards it observed*, may randomise, and pays the pseudoregret ϵ · E[number of pulls of the worse arm].
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7