Theorem 3.2, Eq. (3.10) — high-probability regret of Exp3.P tuned to δ
ProvedRegretBandits.Adversarial.exp3P_high_prob_regretadversarial-banditsbanditshigh-probabilityp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let arms, a horizon and a confidence level be given, and run Exp3.P with
against any adaptive adversary with gains in . Then, with probability at least ,
This is the first high-probability bound of Theorem 3.2, for the version of Exp3.P that takes as an input.
Formalization Note The statement holds for every ; the book's proof notes that the bound is trivial when because (the page says "", a misprint). In that trivial range may exceed ; then Exp3.P's vector can have negative entries (and then no run exists), but in either case the printed bound is already implied by there. Outside it, and .
Preamble
import Mathlib import Definitions.Def_RegretBandits_Adversarial_Protocol import Definitions.Def_RegretBandits_Adversarial_Exp3P open MeasureTheory
Formal statement
namespace RegretBandits.Adversarial
/-- Theorem 3.2, eq. (3.10) (Bubeck–Cesa-Bianchi, arXiv:1204.5721v2, pp. 29–30). For any
`δ ∈ (0,1)`, if Exp3.P is run with `β = √(ln(K δ⁻¹)/(nK))`, `η = 0.95 √(ln K/(nK))`,
`γ = 1.05 √(K ln K/n)` against any adaptive adversary with gains in `[0,1]`, then with probability
at least `1 - δ`, `R_n ≤ 5.15 √(n K ln(K δ⁻¹))`. -/
theorem exp3P_high_prob_regret {K : ℕ} (hK : 2 ≤ K) (n : ℕ) (hn : 1 ≤ n) (g : Adversary K)
(δ : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(I : ℕ → Ω → Fin K)
(hI : IsRun P
(exp3PProb (Real.sqrt (Real.log (K * δ⁻¹) / (n * K)))
(1.05 * Real.sqrt (K * Real.log K / n))
(0.95 * Real.sqrt (Real.log K / (n * K))) g) I) :
ENNReal.ofReal (1 - δ) ≤
P {ω | regret g n I ω ≤ 5.15 * Real.sqrt (n * K * Real.log (K * δ⁻¹))} := by sorry
end RegretBandits.Adversarial
Source
Bubeck, Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, arXiv:1204.5721v2, pp. 29–30, Theorem 3.2, Eq. (3.10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.