Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Algorithm 26 vector estimators and exploration–stability objective

Definition
PartialMonitoringAlgorithm26

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

exponential-weightsonline-learningpartial-monitoring

This interface packages the optimization objects used by the exponential-weights partial-monitoring policy of Algorithm 26.

For a finite comparator set SSS, a vector estimator f(a,σ)bf(a,\sigma)_bf(a,σ)b​ vanishes outside SSS and estimates every loss coordinate in SSS up to a common outcome-dependent additive shift:

∑af(a,Φai)b=Lbi+ci.\sum_a f(a,\Phi_{ai})_b=L_{bi}+c_i.a∑​f(a,Φai​)b​=Lbi​+ci​.

The stability function is

Ψq(z)=⟨q,e−z+z−1⟩.\Psi_q(z)=\langle q,e^{-z}+z-1\rangle.Ψq​(z)=⟨q,e−z+z−1⟩.

For a learning rate η\etaη, reference distribution qqq, sampling distribution ppp in the relative interior of the simplex, estimator fff, and outcome iii, the Algorithm 26 objective is

(p−q)⊤Leiη+1η2∑apaΨq ⁣(ηf(a,Φai)pa).\frac{(p-q)^\top L e_i}{\eta} +\frac1{\eta^2}\sum_a p_a\Psi_q\!\left(\frac{\eta f(a,\Phi_{ai})}{p_a}\right).η(p−q)⊤Lei​​+η21​a∑​pa​Ψq​(pa​ηf(a,Φai​)​).

The bundle also records simplex-interiority and support predicates used by equations (37.12)–(37.13).

Definition code
import Definitions.Def_PartialMonitoringGame
import Mathlib.Analysis.SpecialFunctions.Exp


open scoped BigOperators

namespace BanditAlgorithm

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

/-- The book's vector loss-estimator class `E^vec`, parameterized by the
finite set `S` of comparator actions on which exponential weights runs. -/
def PMVectorEstimatorOn (G : PartialMonitoringGame k d 𝕊)
    (S : Finset (Fin k)) (f : Fin k → 𝕊 → Fin k → ℝ) : Prop :=
  (∀ a σ b, b ∉ S → f a σ b = 0) ∧
  ∀ i : Fin d, ∃ c : ℝ, ∀ b ∈ S,
    ∑ a : Fin k, f a (G.Φ a i) b = G.L b i + c

/-- The exact exponential-weights stability function
`Psi_q(z) = <q, exp(-z) + z - 1>`. -/
noncomputable def pmPsi (q z : Fin k → ℝ) : ℝ :=
  ∑ b : Fin k, q b * (Real.exp (-z b) + z b - 1)

/-- A probability vector in the relative interior of the finite simplex. -/
def PMInteriorDistribution (p : Fin k → ℝ) : Prop :=
  p ∈ stdSimplex ℝ (Fin k) ∧ ∀ a, 0 < p a

/-- `q` is supported on the comparator set `S`. -/
def PMSupportedOn (S : Finset (Fin k)) (q : Fin k → ℝ) : Prop :=
  q ∈ stdSimplex ℝ (Fin k) ∧ ∀ a, a ∉ S → q a = 0

/-- The exploration--stability objective inside Eq. (37.12), for one
outcome `i`. -/
noncomputable def pmAlgorithm26Objective
    (G : PartialMonitoringGame k d 𝕊) (η : ℝ)
    (q p : Fin k → ℝ) (f : Fin k → 𝕊 → Fin k → ℝ)
    (i : Fin d) : ℝ :=
  (1 / η) * ∑ a : Fin k, (p a - q a) * G.L a i +
    (1 / η ^ 2) * ∑ a : Fin k, p a *
      pmPsi q (fun b => η * f a (G.Φ a i) b / p a)

end BanditAlgorithm
Source
Lattimore and Szepesvári, Bandit Algorithms (2020), §37.5, printed pp. 492–494, equations (37.12)–(37.14), 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