Conditional mutual-information chain rule for one bandit round
ProvedBanditAlgorithm.bayesian_ts_conditional_information_gain_chain_rulebanditsinformation-theorythompson-sampling
Fix a round and let denote the conditional mutual information between the optimal arm and the new arm--reward observation, given the pre-round history. Then
This is the conditional mutual-information chain rule used to account for the information acquired in one bandit round.
Formalization Note Mutual information is represented by Kullback--Leibler divergence from the product of marginals, and histories are terminal-law prefix maps.
Preamble
import Definitions.Def_BayesianTSRoundConditionalGains import Mathlib.InformationTheory.KullbackLeibler.ChainRule open MeasureTheory ProbabilityTheory InformationTheory
Formal statement
namespace BanditAlgorithm
/-- Conditional mutual-information accounting for one additional bandit
observation. -/
theorem bayesian_ts_conditional_information_gain_chain_rule
{k n : ℕ} [NeZero k]
(Q : Measure (Fin n → Fin k → ℝ)) [IsProbabilityMeasure Q]
{pi : BanditPolicy k} (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, bayesianTSRoundConditionalInformationGain Q pi t h ∂nu) ≤
bayesianHistoryMutualInformation Q pi (t.1 + 1) (Nat.succ_le_iff.mpr t.2) -
bayesianHistoryMutualInformation Q pi t.1 (Nat.le_of_lt t.2) := 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.