Exp4 estimated-advantage bound
ProvedBanditAlgorithm.exp4_estimate_advantage_boundbandit-algorithmsonline-learning
Let , , and , and let the learning rate satisfy . In round , let be the reward of arm , and let each expert advice row be a probability distribution over the arms. Suppose the learner follows Exp4 with learning rate and exploration parameter .
For every fixed expert , write for its cumulative importance-weighted reward estimate and for the learner’s collected reward. Then
This is the reusable potential-and-second-moment estimate for Exp4 before unbiasedness is substituted and the maximum over comparator experts is taken.
Formalization Note The two expectations are integrals over adversarialMeasure; exp4Estimate denotes .
Preamble
import Definitions.Def_ContextualAdversarialBandit import Definitions.Def_exp4Policy open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.exp4_estimate_advantage_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 π)
(m : Fin M) :
(∫ h, exp4Estimate η 0 E n h m ∂(adversarialMeasure x π n)) -
(∫ h, (∑ t, (h t).2) ∂(adversarialMeasure x π n)) ≤
Real.log M / η + η * ((n : ℝ) * k) / 2 := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge University Press, 2020), Theorem 18.1 proof, printed p. 230, Lemma 18.2 and Eqs. (18.9), (18.11), and (18.12). https://tor-lattimore.com/downloads/book/book.pdf