One-round conditional gain accounting
ProvedBanditAlgorithm.bayesian_ts_conditional_gains_accountingbanditsinformation-theorythompson-sampling
Fix a round and let be the law of the history before that round. The average conditional regret equals the unconditional expected one-round regret,
The average conditional information gain is at most the corresponding increment of mutual information,
This statement supplies the disintegration and information-accounting interface needed to sum the one-round information-ratio bounds.
Formalization Note Histories are terminal-law prefix maps, and mutual information is represented as Kullback--Leibler divergence from the product of marginals.
Preamble
import Definitions.Def_BayesianTSRoundConditionalGains import Mathlib.InformationTheory.KullbackLeibler.ChainRule open MeasureTheory ProbabilityTheory InformationTheory
Formal statement
namespace BanditAlgorithm
/-- Disintegration and KL-chain-rule accounting for the conditional regret
and information gains in one Thompson-sampling round. -/
theorem bayesian_ts_conditional_gains_accounting
{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} (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)
(∫ p, (p.1 t (bayesianOptimalAction p.1) - p.1 t ((p.2 t).1))
∂bayesianAdversarialMeasure Q pi n le_rfl) =
∫ h, bayesianTSRoundConditionalRegretGain Q pi t h ∂nu ∧
(∫ 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.