Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Conditional regret and information gains for a Thompson round

Definition
BayesianTSRoundConditionalGains

by Harry_Xu · Aug 2, 2026 · Mathlib c5ea003 (Lean v4.30.0)

banditsinformation-theorythompson-sampling

Fix a Bayesian adversarial bandit, a round ttt, and a pre-round history hhh. The conditional regret gain is the regular conditional expectation

rt(h)=E[Xt,A∗−Xt,At∣Ht=h].r_t(h)=\mathbb E[X_{t,A^*}-X_{t,A_t}\mid H_t=h].rt​(h)=E[Xt,A∗​−Xt,At​​∣Ht​=h].

The conditional information gain is the relative entropy between the conditional joint law of the optimal arm A∗A^*A∗ and the newly observed pair (At,Xt,At)(A_t,X_{t,A_t})(At​,Xt,At​​) and the product of their conditional marginals:

gt(h)=D ⁣(L(A∗,(At,Xt,At)∣Ht=h) ∥ L(A∗∣Ht=h)⊗L((At,Xt,At)∣Ht=h)).g_t(h)=D\!\left(\mathcal L(A^*,(A_t,X_{t,A_t})\mid H_t=h)\,\middle\|\,\mathcal L(A^*\mid H_t=h)\otimes\mathcal L((A_t,X_{t,A_t})\mid H_t=h)\right).gt​(h)=D(L(A∗,(At​,Xt,At​​)∣Ht​=h)∥L(A∗∣Ht​=h)⊗L((At​,Xt,At​​)∣Ht​=h)).

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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me