Lemma 6, p. 20 —
ProvedExploreFirst.Collective.lemma_6kullback-leiblerp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pinsker-inequalityregret-lower-bound
This is a local refinement of Pinsker's inequality for Bernoulli distributions.
Let be the Kullback–Leibler divergence between Bernoulli distributions of parameters and , as in (5). For ,
The classical form follows from . The proof of Theorem 4 uses the outer inequality , which is sharper when is small.
Formalization Note takes values in (it is at , ), so the first inequality is stated in for the nonnegative real , and the second inequality between the two real lower bounds is stated in . The maximum of over the compact interval is written as a supremum of its image; it is attained and positive.
Preamble
import Mathlib import Definitions.Def_ExploreFirst_Collective_Setting
Formal statement
namespace ExploreFirst.Collective
open MeasureTheory ProbabilityTheory BanditAlgorithm
open scoped ENNReal
/-- Lemma 6, p. 20 (local refinement of Pinsker's inequality): for `0 ≤ p < q ≤ 1`,
`kl(p, q) ≥ (p - q)² / (2 max_{x ∈ [p, q]} x(1 - x)) ≥ (p - q)² / (2q)`. -/
theorem lemma_6 (p q : ℝ) (hp : 0 ≤ p) (hpq : p < q) (hq : q ≤ 1) :
ENNReal.ofReal ((p - q) ^ 2 / (2 * sSup ((fun x => x * (1 - x)) '' Set.Icc p q)))
≤ ExploreFirst.FundIneq.klBer p q ∧
(p - q) ^ 2 / (2 * q) ≤ (p - q) ^ 2 / (2 * sSup ((fun x => x * (1 - x)) '' Set.Icc p q)) := by sorry
end ExploreFirst.Collective
Source
Garivier, Ménard, Stoltz, Explore First, Exploit Next, arXiv:1602.07182v3, p. 20, Appendix A, Lemma 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.