Stochastic partial-monitoring feedback experiment
DefinitionPartialMonitoringStochasticbandit-algorithmsinformation-theorypartial-monitoring
Let be a finite partial-monitoring game and let be a probability distribution on outcomes. For each action , define the induced feedback law by
Interconnecting these action-dependent feedback laws with an adaptive partial-monitoring policy defines the stochastic history law through any finite horizon. The module also defines action counts, expected losses , 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).