Exp4 expert-score unbiasedness
ProvedBanditAlgorithm.exp4_estimate_unbiasedbandit-algorithmsprobability
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 , let be its cumulative importance-weighted reward estimate and let be its true cumulative expected reward. Then
Thus the score assigned by Exp4 to every fixed comparator expert is unbiased. This identity is reusable whenever an Exp4 potential bound must be translated into a bound against the experts’ actual rewards.
Formalization Note exp4Estimate is , expertTotalReward is , and the expectation is integration against the adversarial interaction measure.
Preamble
import Definitions.Def_ContextualAdversarialBandit import Definitions.Def_exp4Policy open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.exp4_estimate_unbiased
{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)) =
expertTotalReward n x E m := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge University Press, 2020), Theorem 18.1 proof, printed p. 230, Eq. (18.10). https://tor-lattimore.com/downloads/book/book.pdf