G.3 Part 1, p. 52 (corrected: bracket in the intermediate bound) — D_σ = KL(η(σ) ‖ b) ≤ 256ε²/(1 − p★) ≤ 512ε²
ProvedOfflineCMC.Minimax.kl_perturbation_boundkl-divergenceminimax-lower-boundp2o-batch-pfp2ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be even, and . Let and let be its perturbation by the sign vector (the last row of in (G.19)). Then the Kullback–Leibler divergence satisfies
This bounds the information one visit to the special state carries about . Combined with the chain rule (G.22), it bounds the divergence between the path laws of the hard family.
Differences from the source:
- correction: the intermediate display → not stated; only is asserted; reason: as printed the middle expression is not (a lost bracket: ), while the two endpoints are correct
- generalization: even (Part 1's hypothesis) → even; reason: covers as well
Preamble
import Mathlib import Definitions.Def_OfflineCMC_Minimax_CMC import Definitions.Def_OfflineCMC_Minimax_HardFamily
Formal statement
namespace OfflineCMC.Minimax
theorem kl_perturbation_bound (d : ℕ) (hd : Even d) (hd0 : 0 < d) (p ε : ℝ) (hp : 0 < p)
(hpd : p < 1 / ((d : ℝ) + 1)) (hε : 0 < ε) (hε' : ε < 1 / 32) (σ : Fin (d / 2) → ℤˣ) :
klDivFin (etaRow d p ε σ) (baseRow d p) ≤ 256 * ε ^ 2 / (1 - p) ∧
256 * ε ^ 2 / (1 - p) ≤ 512 * ε ^ 2 := by sorry
end OfflineCMC.Minimax
Source
Banerjee, Honnappa & Rao, Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity, arXiv:2211.07092v5, p. 52, App. G.3 Part 1 (D_σ)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.