Conditional Thompson information-ratio inequality
ProvedBanditAlgorithm.bayesian_ts_conditional_gains_information_ratiobanditsinformation-theorythompson-sampling
Fix a round of Bayesian Thompson sampling, and let denote the law of the history before that round. Let be conditional expected regret and let be the conditional mutual information between the optimal arm and the new arm--reward observation. Then , , and are integrable and, for -almost every history,
This is the conditional information-ratio inequality at the core of Lemma 36.7 and is reusable independently of the later time-summation argument.
Formalization Note The reward-matrix prior is supported on , and Thompson sampling is expressed by equality of the posterior optimal-arm law with the policy kernel.
Preamble
import Definitions.Def_BayesianTSRoundConditionalGains import Theorems.Thm_BanditAlgorithm_thompson_sampling_one_step_information_ratio_varying_reference open MeasureTheory ProbabilityTheory InformationTheory
Formal statement
namespace BanditAlgorithm
/-- The conditional Thompson-sampling information-ratio inequality of
Lattimore--Szepesvari, Lemma 36.7. -/
theorem bayesian_ts_conditional_gains_information_ratio
{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)
Integrable (bayesianTSRoundConditionalRegretGain Q pi t) nu ∧
Integrable (fun h ↦ bayesianTSRoundConditionalRegretGain Q pi t h ^ 2) nu ∧
Integrable (bayesianTSRoundConditionalInformationGain Q pi t) nu ∧
(∀ᵐ h ∂nu,
bayesianTSRoundConditionalRegretGain Q pi t h ^ 2 ≤
((k : ℝ) / 2) * bayesianTSRoundConditionalInformationGain Q pi t h) := by
sorry
end BanditAlgorithmSource
Lattimore and Szepesvári, Bandit Algorithms (2020), Lemma 36.7, printed p. 470 (free PDF p. 479), https://tor-lattimore.com/downloads/book/book.pdf; conditional-law and Bayes/chain-rule formalization.