Eq. (3.12) — high-probability regret of Exp3.P for general parameters
ProvedRegretBandits.Adversarial.exp3P_regret_generaladversarial-banditsbanditshigh-probabilityp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let , , and consider any adaptive adversary with gains in . Run Exp3.P with parameters , and satisfying
Then for every , with probability at least , the regret satisfies
This is the general bound proved in the course of Theorem 3.2; the tuned bounds (3.10) and (3.11) follow by substituting the parameters.
Formalization Note The book's Exp3.P has and ; strict is needed because the bound divides by . The hypotheses force .
Preamble
import Mathlib import Definitions.Def_RegretBandits_Adversarial_Protocol import Definitions.Def_RegretBandits_Adversarial_Exp3P open MeasureTheory
Formal statement
namespace RegretBandits.Adversarial
/-- Eq. (3.12) (Bubeck–Cesa-Bianchi, arXiv:1204.5721v2, p. 30, proof of Theorem 3.2). If Exp3.P is
run with `0 < β ≤ 1`, `η > 0`, `γ ≤ 1/2` and `(1 + β) K η ≤ γ` against any adaptive adversary
with gains in `[0,1]`, then for every `δ ∈ (0,1)`, with probability at least `1 - δ`,
`R_n ≤ β n K + γ n + (1 + β) η K n + ln(K δ⁻¹) / β + ln K / η`. -/
theorem exp3P_regret_general {K : ℕ} (hK : 2 ≤ K) (n : ℕ) (hn : 1 ≤ n) (g : Adversary K)
(β γ η δ : ℝ) (hβ0 : 0 < β) (hβ1 : β ≤ 1) (hη : 0 < η) (hγ : γ ≤ 1 / 2)
(hβηγ : (1 + β) * K * η ≤ γ) (hδ0 : 0 < δ) (hδ1 : δ < 1)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(I : ℕ → Ω → Fin K) (hI : IsRun P (exp3PProb β γ η g) I) :
ENNReal.ofReal (1 - δ) ≤
P {ω | regret g n I ω ≤
β * n * K + γ * n + (1 + β) * η * K * n + Real.log (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, p. 30, Eq. (3.12) (proof of Theorem 3.2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.