Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Stochastic partial-monitoring feedback experiment

Definition
PartialMonitoringStochastic

by Harry_Xu · Aug 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmsinformation-theorypartial-monitoring

Let G=(L,Φ)G=(L,\Phi)G=(L,Φ) be a finite partial-monitoring game and let uuu be a probability distribution on outcomes. For each action ccc, define the induced feedback law by

Pcu(σ)=∑i: Φ(c,i)=σui.P_c^u(\sigma)=\sum_{i:\,\Phi(c,i)=\sigma}u_i.Pcu​(σ)=i:Φ(c,i)=σ∑​ui​.

Interconnecting these action-dependent feedback laws with an adaptive partial-monitoring policy defines the stochastic history law PuP_uPu​ through any finite horizon. The module also defines action counts, expected losses ⟨Lc,u⟩\langle L_c,u\rangle⟨Lc​,u⟩, and stochastic pseudo-regret relative to a fixed action.

These are the canonical stochastic-environment objects used in the relative-entropy lower bound for finite partial monitoring, and provide a reusable bridge between deterministic outcome-sequence regret and information-theoretic experiments.

Definition code
import Definitions.Def_PartialMonitoringGame
import Mathlib.MeasureTheory.Measure.Dirac

/-!
Lattimore--Szepesvari, *Bandit Algorithms*, Chapter 37, Theorem 37.12,
Step 2 (p.490), especially Eq. (37.8).

This file supplies the stochastic partial-monitoring interface used in the
lower bound.  An outcome distribution `u` induces, for each action `c`, the
feedback law `P_c^u`; interconnecting these laws with a policy gives the
history law `P_u` from the book.
-/

open MeasureTheory ProbabilityTheory
open scoped BigOperators ENNReal

namespace BanditAlgorithm

variable {k d : ℕ} {𝕊 : Type*}

/-- The categorical measure on the finite outcome set with mass vector `u`.
It is a probability measure whenever `u` belongs to the standard simplex. -/
noncomputable def pmOutcomeMeasure (u : Fin d → ℝ) : Measure (Fin d) :=
  Measure.sum fun i => ENNReal.ofReal (u i) • Measure.dirac i

theorem pmOutcomeMeasure_isProbabilityMeasure (u : Fin d → ℝ)
    (hu : u ∈ stdSimplex ℝ (Fin d)) :
    IsProbabilityMeasure (pmOutcomeMeasure u) := by
  apply HasSum.isProbabilityMeasure_sum_dirac
  · exact hu.1
  · simpa [hu.2] using (hasSum_fintype u)

/-- The feedback law `P_c^u` generated by outcome distribution `u` after
playing action `c`: the pushforward of `u` through `i ↦ Φ(c,i)`. -/
noncomputable def pmSignalMeasure [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊) (u : Fin d → ℝ) (c : Fin k) : Measure 𝕊 :=
  (pmOutcomeMeasure u).map (G.Φ c)

theorem pmSignalMeasure_isProbabilityMeasure [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊) (u : Fin d → ℝ)
    (hu : u ∈ stdSimplex ℝ (Fin d)) (c : Fin k) :
    IsProbabilityMeasure (pmSignalMeasure G u c) := by
  letI := pmOutcomeMeasure_isProbabilityMeasure u hu
  exact Measure.isProbabilityMeasure_map (measurable_of_countable _).aemeasurable

/-- The kernel sending an action to its feedback law under stochastic
outcome distribution `u`. -/
noncomputable def pmSignalKernel [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊) (u : Fin d → ℝ)
    (hu : u ∈ stdSimplex ℝ (Fin d)) : Kernel (Fin k) 𝕊 :=
  Kernel.ofFunOfCountable (pmSignalMeasure G u)

instance pmSignalKernel.instIsMarkovKernel [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊) (u : Fin d → ℝ)
    (hu : u ∈ stdSimplex ℝ (Fin d)) :
    IsMarkovKernel (pmSignalKernel G u hu) :=
  ⟨pmSignalMeasure_isProbabilityMeasure G u hu⟩

/-- One stochastic partial-monitoring round: choose an action according to
the policy, then draw its feedback from `P_c^u`. -/
noncomputable def pmStochStepKernel [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊) (π : PMPolicy k 𝕊)
    (u : Fin d → ℝ) (hu : u ∈ stdSimplex ℝ (Fin d)) (t : ℕ) :
    Kernel (PMHistory k 𝕊 t) (Fin k × 𝕊) :=
  (π.select t).compProd
    ((pmSignalKernel G u hu).comap Prod.snd measurable_snd)

instance pmStochStepKernel.instIsMarkovKernel [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊) (π : PMPolicy k 𝕊)
    (u : Fin d → ℝ) (hu : u ∈ stdSimplex ℝ (Fin d)) (t : ℕ) :
    IsMarkovKernel (pmStochStepKernel G π u hu t) := by
  rw [pmStochStepKernel]
  infer_instance

/-- The stochastic feedback-history law `P_u` through horizon `n`. -/
noncomputable def pmStochMeasure [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊) (π : PMPolicy k 𝕊)
    (u : Fin d → ℝ) (hu : u ∈ stdSimplex ℝ (Fin d)) :
    (n : ℕ) → Measure (PMHistory k 𝕊 n)
  | 0 => Measure.dirac (fun t => t.elim0)
  | n + 1 =>
      ((pmStochMeasure G π u hu n).compProd (pmStochStepKernel G π u hu n)).map
        (fun p => Fin.snoc (α := fun _ => Fin k × 𝕊) p.1 p.2)

instance pmStochMeasure.instIsProbabilityMeasure [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊) (π : PMPolicy k 𝕊)
    (u : Fin d → ℝ) (hu : u ∈ stdSimplex ℝ (Fin d)) (n : ℕ) :
    IsProbabilityMeasure (pmStochMeasure G π u hu n) := by
  induction n with
  | zero => exact Measure.dirac.isProbabilityMeasure
  | succ n ih =>
      rw [pmStochMeasure]
      haveI := ih
      exact Measure.isProbabilityMeasure_map measurable_pmHistorySnoc.aemeasurable

/-- Number of times action `c` occurs in a feedback history. -/
def pmActionCount {n : ℕ} (c : Fin k) (h : PMHistory k 𝕊 n) : ℕ :=
  {t | (h t).1 = c}.toFinset.card

/-- Expected loss of action `c` against outcome distribution `u`. -/
def pmExpectedLoss (G : PartialMonitoringGame k d 𝕊)
    (u : Fin d → ℝ) (c : Fin k) : ℝ :=
  ∑ i, G.L c i * u i

/-- Expected stochastic pseudo-regret relative to action `a`. -/
noncomputable def pmStochPseudoRegret [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊) (π : PMPolicy k 𝕊)
    (u : Fin d → ℝ) (hu : u ∈ stdSimplex ℝ (Fin d))
    (n : ℕ) (a : Fin k) : ℝ :=
  ∫ h, ∑ t : Fin n,
    (pmExpectedLoss G u (h t).1 - pmExpectedLoss G u a)
    ∂pmStochMeasure G π u hu n

end BanditAlgorithm
Source
Lattimore and Szepesvari, Bandit Algorithms (Cambridge University Press, 2020), Chapter 37, Theorem 37.12 Step 2, p. 490, definition of P_c^r and P_r immediately before Eq. (37.8).

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