Exp4 expected potential bound
ProvedBanditAlgorithm.exp4_expected_potential_boundbandit-algorithmsonline-learning
Let , , , and . Let rewards satisfy , let every expert advice row be a probability distribution, and suppose the learner follows Exp4 with exploration parameter . Write for the exponential weight of expert , for its one-round importance-weighted score, and
For every fixed expert ,
This is the expected form of the exponential-weights potential inequality used in Exp4, before the mixture score and quadratic term are evaluated.
Formalization Note exp4MixtureEstimate is the cumulative double sum and exp4QuadraticMass is ; all expectations are integrals over the adversarial interaction measure.
Preamble
import Definitions.Def_ContextualAdversarialBandit import Definitions.Def_exp4Analysis open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.exp4_expected_potential_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, exp4MixtureEstimate η E n h ∂(adversarialMeasure x π n)) ≤
Real.log M / η +
(η / 2) *
(∫ h, exp4QuadraticMass η E n h ∂(adversarialMeasure x π n)) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge University Press, 2020), Lemma 18.2 and Theorem 18.1 proof, printed p. 230, especially Eq. (18.9). https://tor-lattimore.com/downloads/book/book.pdf