BanditAlgorithm.adversarial_bandit_exp3_regret_bound_basic
Provedadversarialbanditsexp3
(Exp3, basic bound) Let with arms and horizon , and let be Exp3 with learning rate . Then
Preamble
import Definitions.Def_AdversarialBandit import Definitions.Def_exp3Policy open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.adversarial_bandit_exp3_regret_bound_basic
{k : ℕ} (hk : 1 < k) (n : ℕ) (hn : 0 < n)
(x : ℕ → Fin k → ℝ) (hx : ∀ t : ℕ, ∀ i : Fin k, x t i ∈ Set.Icc (0 : ℝ) 1)
(π : BanditPolicy k)
(hπ : IsExp3Policy (Real.sqrt (Real.log k / (n * k))) π) :
adversarialRegret n x π ≤ 2 * Real.sqrt (n * k * Real.log k) := by
sorry
Source
L&S Theorem 11.1, p.153