Exp4 quadratic-mass expectation bound
ProvedBanditAlgorithm.exp4_quadratic_mass_expectation_boundbandit-algorithmsprobability
Let , , , and . Let rewards satisfy , let every expert advice row be a probability distribution, and suppose the learner follows Exp4 with exploration parameter . With and denoting the Exp4 expert weights and one-round expert score estimates, define
Then the cumulative quadratic term satisfies
This second-moment estimate is the variance-control ingredient that turns the Exp4 potential inequality into a square-root regret bound.
Formalization Note is represented by exp4QuadraticMass, recursively accumulated along the sampled bandit history.
Preamble
import Definitions.Def_ContextualAdversarialBandit import Definitions.Def_exp4Analysis open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.exp4_quadratic_mass_expectation_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 π) :
(∫ h, exp4QuadraticMass η E n h ∂(adversarialMeasure x π n)) ≤
(n : ℝ) * k := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge University Press, 2020), Theorem 18.1 proof, printed p. 230, Eq. (18.12) and the displayed calculation immediately below it. https://tor-lattimore.com/downloads/book/book.pdf