Exponential-weights regret with the exact stability term
ProvedBanditAlgorithm.expWeights_psi_regretexponential-weightsonline-learningpartial-monitoring
Let , let , and let be an arbitrary sequence. Define exponential-weights normalizers and distributions by
Then for every comparator action ,
where
No boundedness or sign condition is imposed on the estimated-loss vectors. This is the deterministic exponential-weights inequality used by Algorithm 26 before taking expectations.
Preamble
import Mathlib.Analysis.SpecialFunctions.Exp import Mathlib.Analysis.SpecialFunctions.Log.Basic import Mathlib.Data.Fintype.Order open scoped BigOperators namespace BanditAlgorithm
Formal statement
theorem expWeights_psi_regret
(k n : ℕ) (hk : 1 ≤ k) (η : ℝ) (hη : 0 < η)
(y : ℕ → Fin k → ℝ) :
let W := fun t : ℕ =>
∑ a : Fin k, Real.exp (- (η * ∑ s ∈ Finset.range t, y s a))
let Q := fun t : ℕ => fun a : Fin k =>
Real.exp (- (η * ∑ s ∈ Finset.range t, y s a)) / W t
∀ a₀ : Fin k,
(∑ t ∈ Finset.range n, ∑ a : Fin k, Q t a * (y t a - y t a₀)) ≤
Real.log k / η + (1 / η) *
∑ t ∈ Finset.range n, ∑ a : Fin k,
Q t a * (Real.exp (-η * y t a) + η * y t a - 1) := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (2020), equation (37.11), printed p. 493, used in the proof of Theorem 37.15 on pp. 494–495, https://tor-lattimore.com/downloads/book/book.pdf