Bernoulli KL is antitone in its first argument below the target
ProvedBanditAlgorithm.bernoulliRelativeEntropy_antitone_fstanalysisbanditsrelative-entropy
Fix . On the interval , Bernoulli relative entropy is nonincreasing in its first argument. Thus, whenever ,
In words, moving the first Bernoulli parameter toward the fixed second parameter cannot increase their relative entropy.
This is the monotonicity step used in Lemma 10.8: if an empirical mean lies below , then its divergence from the larger threshold is at least .
Formalization Note: The first parameter may equal zero. The proof rewrites the divergence using the continuous extension of , proves the derivative is nonpositive in the interior, and then applies the derivative monotonicity theorem on the closed interval.
Preamble
import Definitions.Def_bernoulliRelativeEntropy open Set
Formal statement
theorem BanditAlgorithm.bernoulliRelativeEntropy_antitone_fst
{x y q : ℝ} (hx : x ∈ Set.Icc (0 : ℝ) 1)
(hxy : x ≤ y) (hyq : y ≤ q) (hq : q ∈ Set.Ioo (0 : ℝ) 1) :
BanditAlgorithm.bernoulliRelativeEntropy y q ≤
BanditAlgorithm.bernoulliRelativeEntropy x q := by
sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (2020), monotonicity used in the proof of Lemma 10.8, printed pp. 138–139.