The mixture budget covers Chernoff's threshold at every round
ProvedBanditAlgorithm.chernoff_threshold_mixture_budget_inequalityby Grace · Jul 31, 2026 · Mathlib c5ea003 (Lean v4.30.0)
reference
The quantitative step that lets a self-normalised mixture martingale reach the threshold βn(δ)=klog(n2+n)+f−1(δ) of Chernoff's stopping rule. Let k≥2, let b≥k satisfy k+L+klog(b/k)≤b — which is exactly what b=f−1(δ), L=log(1/δ) satisfy — and let n≥1. Then
L+log(k(k−1))+log(1+2b)+logn ≤ b+1b(klog(n2+n)+b).
Read from the right: b+1b is the loss incurred by running the mixture at prior variance b rather than at the true pull counts, log(k(k−1)) is the union over ordered pairs of arms, and log(1+b/2)+logn bounds the two 21log(1+bTi) prices the mixture pays for the realised counts.
The choice of variance b=f−1(δ) is forced. The loss b/(b+1) must be within O(1/b) of 1 because the entire budget log(1/δ) passes through it, while the price 21log(1+b) must fit inside the slack of f−1(δ) over k+log(1/δ); that slack is klog(f−1(δ)/k), which grows like kloglog(1/δ) and so matches logb. Neither a bounded variance nor one growing faster than polynomially in f−1(δ) works.
After substituting the lower bound on b and clearing the denominator, the inequality reduces to bP+Q≥0 with P=klog2+k−1−2logk−log(k−1) and Q=k−2logk−log(k−1), and both P≥0 and 2P+Q≥0 follow from logx≤x/e alone.
Preamble
import Definitions.Def_TrackAndStop
import Definitions.Def_GaussianBandit
open MeasureTheory ProbabilityTheory Real NNReal ENNReal
Formal statement
theorem BanditAlgorithm.chernoff_threshold_mixture_budget_inequality {k : ℕ}
(hk2 : 2 ≤ k) {b L : ℝ} (hbk : (k : ℝ) ≤ b) (hL0 : 0 ≤ L)
(hLb : (k : ℝ) + L + (k : ℝ) * Real.log (b / (k : ℝ)) ≤ b) {n : ℕ} (hn : 1 ≤ n) :
L + Real.log ((k : ℝ) * ((k : ℝ) - 1)) + Real.log (1 + b / 2) + Real.log (n : ℝ)
≤ b / (b + 1) * ((k : ℝ) * Real.log ((n : ℝ) ^ 2 + (n : ℝ)) + b) := by
sorrySource
The quantitative estimate underlying the mixture-martingale proof of the pairwise self-normalised deviation bound; the threshold beta_t(delta) is the one introduced in Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Lemma 33.7, p. 410. Tuning of the mixture variance follows Kaufmann & Koolen, JMLR 22 (2021), Section 3.
View graph