BanditAlgorithm.contextual_bandit_exp4_regret_bound
Provedbanditscontextualexp4regret
(Exp4 regret bound, GOAL — L&S Theorem 18.1) Let and
For any adversarial rewards and any oblivious experts whose advice rows lie in the probability simplex, the regret of Exp4 against the best expert satisfies
(Eq. (18.7)).
Preamble
import Definitions.Def_ContextualAdversarialBandit import Definitions.Def_exp4Policy open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.contextual_bandit_exp4_regret_bound
{k M : ℕ} (hk : 0 < k) (hM : 1 < M) (n : ℕ) (hn : 0 < n)
(x : ℕ → Fin k → ℝ) (hx : ∀ t : ℕ, ∀ a : Fin k, x t a ∈ Set.Icc (0 : ℝ) 1)
(E : ℕ → Fin M → Fin k → ℝ)
(hE0 : ∀ t : ℕ, ∀ m : Fin M, ∀ a : Fin k, 0 ≤ E t m a)
(hE1 : ∀ t : ℕ, ∀ m : Fin M, ∑ a, E t m a = 1)
(π : BanditPolicy k)
(hπ : IsExp4Policy (Real.sqrt (2 * Real.log M / (n * k))) 0 E π) :
exp4Regret n x E π ≤ Real.sqrt (2 * n * k * Real.log M) := by
sorry
Source
L&S Theorem 18.1, p.230