Quadratic KL bound for perturbed partial-monitoring signals
ProvedBanditAlgorithm.pmSignalMeasure_kl_le_symmetric_perturbationbanditsinformation-theorykullback-leiblerpartial-monitoring
Let be a categorical outcome distribution, let be a zero-mass perturbation direction, and suppose for every outcome. For , let and be the feedback laws obtained by playing action under the two outcome distributions and . Then
The estimate is uniform over actions and feedback maps. It is the finite-alphabet quadratic relative-entropy estimate used in the hard partial-monitoring lower bound. Data processing passes from categorical outcome laws to feedback laws, while the coordinate margin prevents division by vanishing perturbed masses.
Formalization Note The outcome law and induced feedback law are the canonical objects from PartialMonitoringStochastic; the feedback alphabet may carry any measurable space.
Preamble
import Definitions.Def_PartialMonitoringStochastic import Theorems.Thm_InformationTheory_categorical_toReal_klDiv_eq_sum import Theorems.Thm_InformationTheory_klDiv_map_eq_klDiv_trim_comap import Theorems.Thm_InformationTheory_klDiv_trim_le_of_isFiniteMeasure open MeasureTheory ProbabilityTheory InformationTheory open scoped ENNReal BigOperators
Formal statement
theorem BanditAlgorithm.pmSignalMeasure_kl_le_symmetric_perturbation
{k d : ℕ} {𝕊 : Type*} [MeasurableSpace 𝕊] [NeZero d]
(G : PartialMonitoringGame k d 𝕊) (c : Fin k)
(u q : Fin d → ℝ) {δ Δ : ℝ}
(hδ : 0 < δ) (hΔ0 : 0 ≤ Δ) (hΔ : Δ ≤ δ / 2)
(hmargin : ∀ i, δ * |q i| ≤ u i)
(hqsum : ∑ i, q i = 0) (humass : ∑ i, u i = 1) :
klDiv (pmSignalMeasure G (fun i => u i - Δ * q i) c)
(pmSignalMeasure G (fun i => u i + Δ * q i) c) ≤
ENNReal.ofReal ((8 * Δ ^ 2 / δ) * ∑ i, |q i|) := by
sorry
Source
Lattimore and Szepesvari, Bandit Algorithms (Cambridge UP, 2020), Theorem 37.12 Step 2, printed p. 490, Eq. (37.9), using the categorical KL estimate Eq. (37.4), printed p. 488, and data processing from Exercise 14.10, printed p. 196.