One-sided Bernoulli relative entropy
DefinitionklucbTruncatedRelativeEntropybandit-algorithmskl-ucbrelative-entropy
For Bernoulli parameters , define the one-sided, or truncated, relative entropy by
where is the relative entropy between Bernoulli distributions with means and .
This is the divergence used in the KL-UCB analysis to express whether an upper confidence threshold remains feasible. It makes the one-sided nature of an upper-confidence index explicit and is reused in the optimal-arm underestimation and suboptimal-arm overshoot counts.
Formalization Note The definition is real-valued and inherits the endpoint convention of bernoulliRelativeEntropy.
Definition code
import Definitions.Def_bernoulliRelativeEntropy
/-!
Lattimore--Szepesvári, *Bandit Algorithms* (CUP 2020), immediately before
Lemma 10.7, printed p. 138.
-/
namespace BanditAlgorithm
/-- The one-sided binary divergence used in Lemmas 10.7 and 10.8:
`d⁺(p,q) = d(p,q) 𝟙{p ≤ q}`. -/
noncomputable def klucbTruncatedRelativeEntropy (p q : ℝ) : ℝ :=
if p ≤ q then bernoulliRelativeEntropy p q else 0
end BanditAlgorithm
Source
Lattimore and Szepesvari, Bandit Algorithms (CUP 2020), Chapter 10, immediately before Lemma 10.7, printed p. 138 / PDF p. 147: d-bar(p,q)=d(p,q) I{p <= q}.