BanditAlgorithm.adversarial_bandit_exp3_regret_bound
Provedbanditsexp3regret
(Exp3, improved bound, GOAL) Let be an adversarial bandit 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
{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 (2 * Real.log k / (n * k))) π) :
adversarialRegret n x π ≤ Real.sqrt (2 * n * k * Real.log k) := by
sorry
Source
L&S Theorem 11.2, p.156