Conditional regret and information gains for a Thompson round
DefinitionBayesianTSRoundConditionalGainsbanditsinformation-theorythompson-sampling
Fix a Bayesian adversarial bandit, a round , and a pre-round history . The conditional regret gain is the regular conditional expectation
The conditional information gain is the relative entropy between the conditional joint law of the optimal arm and the newly observed pair and the product of their conditional marginals:
These are the canonical history-indexed quantities in the information-ratio proof of Bayesian Thompson-sampling regret bounds.
Formalization Note Regular conditional distributions are represented by Mathlib condDistrib; Kullback--Leibler divergence is converted from extended nonnegative reals to reals.
Definition code
import Definitions.Def_BayesianHistoryMutualInformation
import Mathlib.Probability.Kernel.CondDistrib
import Mathlib.InformationTheory.KullbackLeibler.ChainRule
/-!
Lattimore--Szepesvari, *Bandit Algorithms* (2020), Lemma 36.7,
printed p. 470 / free PDF p. 479.
These are the two history-indexed quantities used in the information-ratio
proof. The regret gain is conditional expected one-round regret. The
information gain is the conditional mutual information between the optimal
arm and the newly observed arm--reward pair.
-/
open MeasureTheory ProbabilityTheory InformationTheory
namespace BanditAlgorithm
/-- Conditional expected regret in round `t`, indexed by the history before
that round. -/
noncomputable def bayesianTSRoundConditionalRegretGain
{k n : ℕ} [NeZero k]
(Q : Measure (Fin n → Fin k → ℝ)) [IsProbabilityMeasure Q]
(pi : BanditPolicy k) (t : Fin n)
(h : BanditHistory k t.1) : ℝ :=
let mu := 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 roundRegret := fun p : (Fin n → Fin k → ℝ) × BanditHistory k n ↦
p.1 t (bayesianOptimalAction p.1) - p.1 t ((p.2 t).1)
∫ p, roundRegret p ∂condDistrib id history mu h
/-- Conditional mutual information gained in round `t`: given the history
before the round, this is the KL divergence between the conditional joint law
of the optimal arm and the new arm--reward observation and the product of its
conditional marginals. -/
noncomputable def bayesianTSRoundConditionalInformationGain
{k n : ℕ} [NeZero k]
(Q : Measure (Fin n → Fin k → ℝ)) [IsProbabilityMeasure Q]
(pi : BanditPolicy k) (t : Fin n)
(h : BanditHistory k t.1) : ℝ :=
let mu := 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 optimal := fun p : (Fin n → Fin k → ℝ) × BanditHistory k n ↦
bayesianOptimalAction p.1
let observation := fun p : (Fin n → Fin k → ℝ) × BanditHistory k n ↦ p.2 t
let joint := condDistrib (fun p ↦ (optimal p, observation p)) history mu h
let optimalMarginal := condDistrib optimal history mu h
let observationMarginal := condDistrib observation history mu h
(klDiv joint (optimalMarginal.prod observationMarginal)).toReal
end BanditAlgorithm
Source
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.