Proved
BanditAlgorithm.l1_dist_eq_two_max_event_excessLet be real vectors on a finite set with the same total mass, — in particular any two probability vectors. Then every event satisfies
and the bound is attained: there is an with . Together these say
the variational description of the (twice total-variation) distance. The maximiser is .
This identity is the bridge between the confidence sets of UCRL2 (Eq. 38.13) and scalar concentration. The categorical concentration inequality behind Lemma 38.8 — that the empirical transition vector is within of in — is proved by observing that an deviation of forces some event to have empirical probability exceeding its true probability by ; each such event probability is an average of independent indicators, so Hoeffding's inequality applies, and a union bound over the subsets produces the factor inside the logarithm.
The proof of the identity is elementary: split the index set at . On the summand equals and on the complement it equals ; since the total difference vanishes, the two halves are equal, giving . For an arbitrary , discarding the indices of outside only increases the sum, and adjoining the indices of outside increases it further.
import Mathlib.Analysis.SpecialFunctions.Sqrt import Mathlib.Algebra.Order.BigOperators.Ring.Finset
theorem BanditAlgorithm.l1_dist_eq_two_max_event_excess
{ι : Type*} [Fintype ι] [DecidableEq ι] (p q : ι → ℝ)
(hpq : ∑ i, p i = ∑ i, q i) :
(∀ B : Finset ι, 2 * ∑ i ∈ B, (p i - q i) ≤ ∑ i, |p i - q i|)
∧ ∃ A : Finset ι, ∑ i, |p i - q i| = 2 * ∑ i ∈ A, (p i - q i) := by
sorry