Eq. (2.4) — pseudo-regret of -UCB for rewards
ProvedRegretBandits.Stochastic.alpha_ucb_pseudo_regretbanditsp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-bookp2o-v1regretucb
Consider a stochastic bandit with arms whose rewards take values in , with means , and gaps . Taking in (2.2) (Hoeffding's lemma) gives , and -UCB with this is called -UCB. For and every horizon ,
This is the most used special case of Theorem 2.1, for bounded rewards; the matching lower bound in its dependence on is Theorem 2.2 combined with (2.8).
Formalization Note. The algorithm is run with and plays every arm once before using the index. Rewards lie in almost surely. Here , so the printed constant is correct as stated.
Preamble
import Mathlib import Definitions.Def_ImprovedLinBandits_UCBDelta_armModel import Definitions.Def_RegretBandits_Stochastic_model import Definitions.Def_RegretBandits_Stochastic_alphaPsiUCB
Formal statement
namespace RegretBandits.Stochastic
open MeasureTheory ImprovedLinBandits.UCBDelta
/-- Eq. (2.4) of Bubeck and Cesa-Bianchi (arXiv:1204.5721v2, p. 11): for `[0, 1]`-valued rewards,
α-UCB, i.e. (α, ψ)-UCB with `ψ(λ) = λ²/8` (Hoeffding's lemma, `ψ*(ε) = 2ε²`) and `α > 2`, satisfies
`R̄_n ≤ ∑_{i : Δ_i > 0} ((2α/Δ_i) ln n + α/(α - 2))`. -/
theorem alpha_ucb_pseudo_regret {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] {K : ℕ} (hK : 2 ≤ K) (X : Fin K → ℕ → Ω → ℝ) (μ : Fin K → ℝ)
(hX : IsStochasticBandit P X μ)
(hbdd : ∀ i k, ∀ᵐ ω ∂P, X i k ω ∈ Set.Icc (0 : ℝ) 1)
(α : ℝ) (hα : 2 < α) (I : ℕ → Ω → Fin K) (hI : ∀ t, Measurable (I t))
(hrun : IsAlphaPsiUCBRun (fun l => l ^ 2 / 8) α X I) (n : ℕ) :
pseudoRegretBar P μ I n ≤
∑ i ∈ Finset.univ.filter (fun i => 0 < gap μ i),
(2 * α / gap μ i * Real.log (n : ℝ) + α / (α - 2)) := by sorry
end RegretBandits.Stochastic
Source
Bubeck, Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, arXiv:1204.5721v2, p. 11, Eq. (2.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.