Exp4 mixture score equals expected reward
ProvedBanditAlgorithm.exp4_mixture_estimate_expectation_eq_rewardbandit-algorithmsprobability
Let , , , and . Let rewards satisfy , let every expert advice row be a probability distribution, and suppose the learner follows Exp4 with exploration parameter . If is the exponential weight of expert and is its one-round importance-weighted score, then
Thus the Exp4 mixture score has exactly the learner’s expected collected reward. This identity converts the linear term in the potential inequality into the regret benchmark.
Formalization Note The left process is exp4MixtureEstimate; the right process sums the reward coordinate of the bandit history.
Preamble
import Definitions.Def_ContextualAdversarialBandit import Definitions.Def_exp4Analysis open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.exp4_mixture_estimate_expectation_eq_reward
{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, exp4MixtureEstimate η E n h ∂(adversarialMeasure x π n)) =
∫ h, (∑ t, (h t).2) ∂(adversarialMeasure x π n) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge University Press, 2020), Theorem 18.1 proof, printed p. 230, Eq. (18.10) and the conditional-expectation step leading to Eq. (18.11). https://tor-lattimore.com/downloads/book/book.pdf