Union bound over events turns a scalar tail into an tail
ProvedBanditAlgorithm.l1_deviation_union_boundLet and be real vectors on a finite set carrying the same total mass for every — in particular two probability vectors. If every event satisfies
then
This is the reduction that turns the scalar concentration of event probabilities into the concentration required by the confidence sets of UCRL2 (Lattimore and Szepesvári, Eq. 38.13 and Lemma 38.8). It carries no probabilistic content of its own: it is the variational identity followed by a union bound over the subsets of . The factor it produces is exactly what appears as the inside the logarithm of the UCRL2 confidence width .
The proof: for each with the variational identity supplies an event (namely ) with , so the deviation event is contained in the union over of the scalar deviation events; subadditivity over the finitely many subsets, of which there are , finishes the argument.
import Mathlib.MeasureTheory.Measure.Real open MeasureTheory
theorem BanditAlgorithm.l1_deviation_union_bound
{Ω : Type*} {mΩ : MeasurableSpace Ω} {μ : Measure Ω} [IsFiniteMeasure μ]
{ι : Type*} [Fintype ι] [DecidableEq ι]
(phat : Ω → ι → ℝ) (p : ι → ℝ) (ε b : ℝ)
(hsum : ∀ ω, ∑ a, phat ω a = ∑ a, p a)
(hbound : ∀ A : Finset ι, μ.real {ω | ε / 2 ≤ ∑ a ∈ A, (phat ω a - p a)} ≤ b) :
μ.real {ω | ε ≤ ∑ a, |phat ω a - p a|} ≤ 2 ^ Fintype.card ι * b := by
sorry