Posterior diagonal representation for Thompson sampling
ProvedBanditAlgorithm.posterior_diagonal_representationbanditsinformation-theoryrelative-entropythompson-sampling
Let be a posterior law on a latent state , let take values in , and independently sample an action with the posterior law of . For each action , let be its reward. Then there are posterior arm probabilities and probability laws on such that every is finite,
and the diagonal information terms satisfy
This is the reusable posterior-measure core of the Thompson-sampling information-ratio argument. It explicitly handles zero-posterior-probability arms by taking .
Formalization Note Rewards are represented as values of the subtype , and mutual information is represented by KL divergence between the joint law and the product of its marginals.
Preamble
import Mathlib.Probability.Kernel.CondDistrib import Mathlib.InformationTheory.KullbackLeibler.ChainRule import Theorems.Thm_InformationTheory_finite_range_mutualInformation_ne_top import Theorems.Thm_InformationTheory_klDiv_compProd_self_eq_lintegral_of_ae import Mathlib.MeasureTheory.Integral.Bochner.SumMeasure import Mathlib.MeasureTheory.Integral.Prod open MeasureTheory ProbabilityTheory InformationTheory open scoped ENNReal BigOperators namespace BanditAlgorithm
Formal statement
theorem posterior_diagonal_representation
{k : ℕ} [NeZero k]
{X : Type*} [MeasurableSpace X] [StandardBorelSpace X] [Nonempty X]
(R : Measure X) [IsProbabilityMeasure R]
(opt : X → Fin k) (hopt : Measurable opt)
(reward : Fin k → X → Set.Icc (0 : ℝ) 1)
(hreward : ∀ a, Measurable (reward a)) :
let q := Measure.map opt R
let rho := R.prod q
let obs := fun z : X × Fin k ↦ (z.2, reward z.2 z.1)
∃ (p : Fin k → ℝ)
(P M : Fin k → Measure (Set.Icc (0 : ℝ) 1)),
(∀ a, IsProbabilityMeasure (P a)) ∧
(∀ a, IsProbabilityMeasure (M a)) ∧
(∀ a, klDiv (P a) (M a) ≠ ∞) ∧
(∫ z, ((reward (opt z.1) z.1).1 - (reward z.2 z.1).1) ∂rho) =
∑ a, p a * ((∫ z, z.1 ∂P a) - ∫ z, z.1 ∂M a) ∧
(∑ a, p a ^ 2 * (klDiv (P a) (M a)).toReal) ≤
(klDiv (Measure.map (fun z ↦ (opt z.1, obs z)) rho)
(q.prod (Measure.map obs rho))).toReal := by sorrySource
Lattimore and Szepesvari, Bandit Algorithms (2020), Lemma 36.7 and equation (36.9), printed p. 470 / free PDF p. 479.