Exp3-IX pathwise regret decomposition
ProvedBanditAlgorithm.exp3ix_pathwise_regret_decompositionbandit-algorithmsprobabilityregret
This is the deterministic pathwise regret decomposition for Exp3-IX.
Let there be arms, let be the fixed reward table, let , and let be a length- history whose observed rewards lie in . Write for the Exp3-IX cumulative implicit-exploration loss estimate and for arm 's true cumulative loss. Then
This is the deterministic half of the high-probability Exp3-IX analysis and is reusable independently of the concentration argument.
Formalization Note The theorem is stated pointwise for an arbitrary bounded history and specializes the source identity to .
Preamble
import Definitions.Def_AdversarialBandit import Definitions.Def_exp3Policy open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.exp3ix_pathwise_regret_decomposition
{k : ℕ} (hk : 1 < k) (n : ℕ)
(x : ℕ → Fin k → ℝ) (hx : ∀ t : ℕ, ∀ i : Fin k, x t i ∈ Set.Icc (0 : ℝ) 1)
(η : ℝ) (hη : 0 < η) (h : BanditAlgorithm.BanditHistory k n)
(hh : ∀ t : Fin n, (h t).2 ∈ Set.Icc (0 : ℝ) 1) :
BanditAlgorithm.adversarialRandomRegret n x h ≤
Real.log k / η +
(⨆ i : Fin k,
BanditAlgorithm.exp3IXEstimate η (η / 2) n h i -
∑ t : Fin n, (1 - x t i)) +
η * ∑ i : Fin k, BanditAlgorithm.exp3IXEstimate η (η / 2) n h i := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (CUP 2020), proof of Theorem 12.1, printed p. 169 / PDF p. 178: combine Eq. (12.3) with Lemma 12.4 (the bias identity), then specialize gamma = eta/2.