Posterior diagonal representation for the Thompson-sampling information ratio
ProvedBanditAlgorithm.bayesian_ts_conditional_diagonal_representationbanditsconditional-probabilityinformation-ratiothompson-sampling
Consider Bayesian Thompson sampling with actions and rewards in . Fix a round and condition on the history . Let . For almost every history, there are conditional reward laws (given ) and reference reward laws such that
and
All displayed laws are probability measures and the divergences are finite. This is the posterior diagonal decomposition used in the information-ratio proof for Thompson sampling.
Formalization Note The reward laws are measures on the subtype , which makes the bounded-reward hypotheses explicit.
Preamble
import Definitions.Def_BayesianTSRoundConditionalGains open MeasureTheory ProbabilityTheory InformationTheory open scoped ENNReal BigOperators
Formal statement
namespace BanditAlgorithm
/-- Posterior diagonal representation in the conditional proof of the
Thompson-sampling information ratio. -/
theorem bayesian_ts_conditional_diagonal_representation
{k n : ℕ} [NeZero k]
(Q : Measure (Fin n → Fin k → ℝ)) [IsProbabilityMeasure Q]
(hQ : ∀ᵐ X ∂Q, ∀ (s : Fin n) (a : Fin k), X s a ∈ Set.Icc (0 : ℝ) 1)
{pi : BanditPolicy k} (hpi : IsBayesianTSPolicy Q pi) (t : Fin n) :
let history := fun p : (Fin n → Fin k → ℝ) × BanditHistory k n ↦
fun s : Fin t.1 ↦ p.2 (Fin.castLE (Nat.le_of_lt t.2) s)
let nu := Measure.map history (bayesianAdversarialMeasure Q pi n le_rfl)
∀ᵐ h ∂nu, ∃ (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) ≠ ∞) ∧
bayesianTSRoundConditionalRegretGain Q pi t h =
∑ a, p a * ((∫ z, z.1 ∂P a) - ∫ z, z.1 ∂M a) ∧
(∑ a, p a ^ 2 * (klDiv (P a) (M a)).toReal) ≤
bayesianTSRoundConditionalInformationGain Q pi t h := by
sorry
end BanditAlgorithmSource
Lattimore and Szepesvari, Bandit Algorithms (2020), Lemma 36.7, printed p. 470 / free PDF p. 479, especially the posterior action probabilities and diagonal KL terms in the proof.