Lemma 3.1 — high-probability bound for the biased gain estimates
ProvedRegretBandits.Adversarial.biased_gain_estimate_boundConsider the adversarial bandit protocol with arms and an adaptive adversary with gains , and let be a run of a forecaster that draws from the probability vector , a function of . Fix an arm with for every round and every history, a horizon , and , and let
Then, with probability at least ,
The lemma says that the biased estimate used by Exp3.P overestimates the true cumulative gain only by an additive with high probability; it is the concentration step in the proof of Theorem 3.2.
Formalization Note The book states the lemma for the distributions of Exp3.P with the single hypothesis . The statement here holds for any forecaster rule (the book's proof uses only that and are determined by and that given the past), which contains Exp3.P. It adds the hypotheses implicit on the page: (the bound divides by ), (the estimate divides by ; Exp3.P has and positive exponential weights), , and the standing of the protocol (p. 6). "With probability at least " is under the law of the run.
import Mathlib import Definitions.Def_RegretBandits_Adversarial_Protocol open MeasureTheory
namespace RegretBandits.Adversarial
/-- Lemma 3.1 (Bubeck–Cesa-Bianchi, arXiv:1204.5721v2, p. 28). Let `p` be a forecaster rule run
against an adaptive adversary `g` with gains in `[0,1]`, fix an arm `i` with `p_{i,t} > 0`, and
let `0 < β ≤ 1`, `δ ∈ (0,1)`. With `g̃_{i,t} = (g_{i,t} 𝟙{I_t = i} + β) / p_{i,t}`, with probability
at least `1 - δ`,
`∑_{t=1}^n g_{i,t} ≤ ∑_{t=1}^n g̃_{i,t} + ln(δ⁻¹) / β`. -/
theorem biased_gain_estimate_bound {K : ℕ} (hK : 2 ≤ K) (n : ℕ) (g : Adversary K)
(p : ℕ → (ℕ → Fin K) → Fin K → ℝ) (hp : IsForecasterRule p) (i : Fin K)
(hpos : ∀ t h, 0 < p t h i) (β δ : ℝ) (hβ0 : 0 < β) (hβ1 : β ≤ 1)
(hδ0 : 0 < δ) (hδ1 : δ < 1)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(I : ℕ → Ω → Fin K) (hI : IsRun P p I) :
ENNReal.ofReal (1 - δ) ≤
P {ω | ∑ t ∈ Finset.Icc 1 n, g.val t (fun s => I s ω) i ≤
∑ t ∈ Finset.Icc 1 n,
(g.val t (fun s => I s ω) i * (if I t ω = i then 1 else 0) + β) /
p t (fun s => I s ω) i +
Real.log δ⁻¹ / β} := by sorry
end RegretBandits.Adversarial
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.