Exp4 regret bound at a general learning rate
ProvedBanditAlgorithm.exp4_regret_general_eta_boundadversarialbanditsconcentrationcontextual
Let , , and . Let the learning rate satisfy . In each round , the adversarial reward vector has coordinates , and every expert advice row is a probability distribution over the arms. If the learner follows Exp4 with learning rate and exploration parameter , then its expected regret against the best of the oblivious experts satisfies
This is the reusable, pre-optimization form of the Exp4 regret theorem. Choosing the learning rate as a function of , , and yields the usual square-root regret bound.
Formalization Note The expected regret is exp4Regret; the predicate IsExp4Policy fixes the history-dependent policy to Algorithm 11.
Preamble
import Definitions.Def_ContextualAdversarialBandit import Definitions.Def_exp4Policy open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.exp4_regret_general_eta_bound
{k M : ℕ} (hk : 0 < k) (hM : 1 < M) (n : ℕ) (hn : 0 < n)
(η : ℝ) (hη : 0 < η)
(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 η 0 E π) :
exp4Regret n x E π ≤
Real.log M / η + η * ((n : ℝ) * k) / 2 := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (2020), Theorem 18.1 proof, printed p. 230, especially Eqs. (18.11) and (18.12), with the substitution immediately before Eq. (18.7).