Conditional laws of a Bayesian bandit round
ProvedBanditAlgorithm.bayesian_ts_terminal_conditional_lawsbanditsconditional-distributionthompson-sampling
In the Bayesian adversarial bandit model, fix a round and condition on the history strictly before that round. Let denote the posterior law of the full reward matrix and let denote the policy’s action law. Then, for almost every history :
Moreover, under the terminal generative law, the recorded observation is consistent with the reward matrix:
These identities are a formal bridge from the recursively generated bandit history to the posterior product law used in the one-round Thompson-sampling information argument.
Formalization Note The posterior is the regular conditional distribution of the reward matrix under the prefix measure at time .
Preamble
import Definitions.Def_BayesianTSRoundConditionalGains import Theorems.Thm_BanditAlgorithm_bayesianAdversarialMeasure_prefix_marginal import Mathlib.Probability.Kernel.CompProdEqIff open MeasureTheory ProbabilityTheory InformationTheory namespace BanditAlgorithm
Formal statement
theorem bayesian_ts_terminal_conditional_laws
{k n : ℕ} [NeZero k]
(Q : Measure (Fin n → Fin k → ℝ)) [IsProbabilityMeasure Q]
(pi : BanditPolicy k) (t : Fin n) :
let terminal := bayesianAdversarialMeasure Q pi n le_rfl
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 base := bayesianAdversarialMeasure Q pi t.1 (Nat.le_of_lt t.2)
let nu := Measure.map history terminal
let post := condDistrib Prod.fst Prod.snd base
(condDistrib Prod.fst history terminal =ᵐ[nu] post) ∧
(condDistrib (fun p ↦ (p.1, (p.2 t).1)) history terminal =ᵐ[nu]
post.prod (pi.select t.1)) ∧
(∀ᵐ z ∂terminal, z.2 t = ((z.2 t).1, z.1 t (z.2 t).1)) := by sorrySource
Purely formal bridge from the generative definitions in Def_ThompsonSampling to Lattimore and Szepesvari, Bandit Algorithms (2020), Lemma 36.7, printed p. 470 / free PDF p. 479.