Lemma A.7, p. 71 — D²_H(Ber(p), Ber(q)) ≤ (p−q)²(1/(p+q) + 1/(2−p−q)); D²_H(Ber(1/2+Δ), Ber(1/2)) ≤ 3Δ²; D²_H(Ber(1/2+Δ), Ber(1/2+2Δ)) ≤ 5Δ²
ProvedStatComplexityDM.MAB.bernoulli_hellinger_boundsbernoulli-distributionhellinger-distanceinformation-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be the squared Hellinger distance and the Bernoulli distribution with mean . Then:
- For all ,
- For all , .
- For all , .
The second bound is the information property of the hard family in the multi-armed bandit lower bound (Proposition 5.3); the third enters the gap-dependent variant.
Formalization Note The Hellinger distance carries no factor , as in the paper's (5). At (resp. ) the term (resp. ) has a zero denominator; Lean evaluates , and the left side is also there, so the first bound is stated for all of as on the page.
Preamble
import Mathlib import Definitions.Def_FoundationsRL_GeneralDM_Divergences import Definitions.Def_StatComplexityDM_MAB_Bernoulli
Formal statement
namespace StatComplexityDM.MAB
open FoundationsRL.GeneralDM
/-- Lemma A.7 (arXiv:2112.13487v3, p. 71), divergence for Bernoulli distributions:
for all `p, q ∈ [0, 1]`, `D²_H(Ber(p), Ber(q)) ≤ (p − q)² · (1/(p + q) + 1/(1 − p + 1 − q))`;
for all `Δ ∈ (0, 1/2)`, `D²_H(Ber(1/2 + Δ), Ber(1/2)) ≤ 3Δ²`; and for all `Δ ∈ (0, 1/4)`,
`D²_H(Ber(1/2 + Δ), Ber(1/2 + 2Δ)) ≤ 5Δ²`. `D²_H` is `hellingerSq` (no factor `1/2`, (5), p. 10).
At `p = q = 0` and `p = q = 1` a denominator vanishes; Lean's `x / 0 = 0` makes the right side `0`,
which the left side also equals there. -/
theorem bernoulli_hellinger_bounds :
(∀ p q : ℝ, 0 ≤ p → p ≤ 1 → 0 ≤ q → q ≤ 1 →
hellingerSq (ber p) (ber q) ≤ (p - q) ^ 2 * (1 / (p + q) + 1 / (1 - p + (1 - q)))) ∧
(∀ Δ : ℝ, 0 < Δ → Δ < 1 / 2 →
hellingerSq (ber (1 / 2 + Δ)) (ber (1 / 2)) ≤ 3 * Δ ^ 2) ∧
(∀ Δ : ℝ, 0 < Δ → Δ < 1 / 4 →
hellingerSq (ber (1 / 2 + Δ)) (ber (1 / 2 + 2 * Δ)) ≤ 5 * Δ ^ 2) := by sorry
end StatComplexityDM.MAB
Source
arXiv:2112.13487v3, Lemma A.7, p. 71
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.