Finite-action Cauchy–Schwarz information-ratio step
ProvedBanditAlgorithm.finite_information_ratio_cauchy_schwarzbanditscauchy-schwarzinformation-theory
For real vectors , , and indexed by actions, suppose each coordinate satisfies . Then
This is the finite-dimensional Cauchy–Schwarz step used in the Thompson-sampling information-ratio bound.
Preamble
import Mathlib.Algebra.Order.Chebyshev import Mathlib.Data.Real.Basic open scoped BigOperators
Formal statement
theorem BanditAlgorithm.finite_information_ratio_cauchy_schwarz {k : ℕ}
(p gap info : Fin k → ℝ)
(hpoint : ∀ a, 2 * gap a ^ 2 ≤ info a) :
(∑ a, p a * gap a) ^ 2 ≤
((k : ℝ) / 2) * ∑ a, p a ^ 2 * info a := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), https://tor-lattimore.com/downloads/book/book.pdf, printed p. 470 (PDF p. 479), proof of Lemma 36.7, the Cauchy–Schwarz inequality immediately before the final Bayes-rule equality.