Lemma 6 — local refinement of Pinsker's inequality
ProvedExploreFirst.Absolute.lemma_6kullback-leiblermulti-armed-banditsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret-lower-bound
For Bernoulli parameters , let . Then
This local refinement retains the interval-dependent factor used in the small-horizon bound. It includes and , where the divergence may be infinite.
Formalization Note The maximum is encoded by the supremum of the image of the nonempty compact interval ; its value is positive because .
Preamble
import Mathlib import Definitions.Def_ExploreFirst_Absolute_Setting
Formal statement
namespace ExploreFirst.Absolute
/-- Garivier–Ménard–Stoltz, Lemma 6, p. 20. -/
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.Absolute
Source
Garivier, Ménard, Stoltz, Explore First, Exploit Next, arXiv:1602.07182v3, p. 20, Lemma 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.