Lemma 11 — around
ProvedBayesBAI.lemma_11bayesianbest-arm-identificationmulti-armed-banditsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1simple-regret
In the setting of Appendix C (, , , ),
This is the second-order expansion of the Bernoulli divergence, with a bound uniform as approaches the boundary at rate .
Differences from the source:
- generalization: C_KL, used before it is introduced → the constant 8; reason: this is the value the proof on p.18 gives, and implies the statement with any larger C_KL (Reading 9)
- encoding: h(T) = o(T^(−1/6)) and a threshold T₀ with 2h(T) < T^(−1/6), T^(−1/6) < 1/2 for T ≥ T₀ → the same inequalities at one real T, as KLSetting T l u h; reason: this gives the printed statement for every such h, T₀, and shows the constants are universal
Preamble
import Mathlib import Definitions.Def_BayesBAI_KLSetting import Definitions.Def_RegretBandits_Stochastic_klBernoulli
Formal statement
namespace BayesBAI
open RegretBandits.Stochastic in
/-- Lemma 11 (bound on the KL divergence around `l`), Komiyama, Ariu, Kato, Qin, arXiv:2111.09885v3,
pp.17–18: in the setting of p.17,
`|d_KL(l, u) - (u - l)²/(2l(1 - l))| ≤ C_KL h³ T^(1/3)`.
**Formalization Note.** The constant is the proof's `8` (p.18), since `C_KL` is used before it is
introduced. -/
theorem lemma_11 {T l u h : ℝ} (hs : KLSetting T l u h) :
|klBern l u - (u - l) ^ 2 / (2 * l * (1 - l))| ≤ 8 * h ^ 3 * T ^ ((1 : ℝ) / 3) := by sorry
end BayesBAI
Source
Komiyama, Ariu, Kato, Qin, Rate-optimal Bayesian Simple Regret in Best Arm Identification, arXiv:2111.09885v3, Lemma 11, pp.17–18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.