Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Expected action-set count equals cumulative selection mass

Proved
BanditAlgorithm.pmStoch_expected_actionSetCount_eq_selection_mass

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

banditspartial-monitoringprobabilitytextbook

Let a policy π\piπ interact for nnn rounds with a stochastic partial-monitoring environment whose outcomes are independently distributed according to uuu. For any finite set of actions SSS, let TS(n)T_S(n)TS​(n) count the rounds on which the selected action belongs to SSS. Then

Eu[TS(n)]=∑t=0n−1Eu ⁣[πt(S∣Ht)]=∑t=0n−1Eu ⁣[∑c∈Sπt(c∣Ht)].\mathbb E_u[T_S(n)] = \sum_{t=0}^{n-1}\mathbb E_u\!\left[\pi_t(S\mid H_t)\right] = \sum_{t=0}^{n-1}\mathbb E_u\!\left[\sum_{c\in S}\pi_t(c\mid H_t)\right].Eu​[TS​(n)]=t=0∑n−1​Eu​[πt​(S∣Ht​)]=t=0∑n−1​Eu​[c∈S∑​πt​(c∣Ht​)].

This finite-horizon tower-property identity connects action counts on complete histories with the predictable selection masses that occur in adaptive KL chain rules. In particular, choosing S=[k]∖NabS=[k]\setminus N_{ab}S=[k]∖Nab​ gives the expected informative-action count Eua[T~(n)]\mathbb E_{u_a}[\widetilde T(n)]Eua​​[T(n)] used in the hard partial-monitoring lower bound.

Formalization Note The left-hand side writes TS(n)T_S(n)TS​(n) explicitly as a sum of indicators, while the right-hand side uses the real-valued masses of singleton action events under the policy kernel.

Preamble
import Definitions.Def_PartialMonitoringStochastic

open MeasureTheory ProbabilityTheory
open scoped BigOperators ENNReal
Formal statement
theorem BanditAlgorithm.pmStoch_expected_actionSetCount_eq_selection_mass
    {k d : ℕ} {𝕊 : Type*} [Fintype 𝕊] [MeasurableSpace 𝕊]
    (G : PartialMonitoringGame k d 𝕊) (π : PMPolicy k 𝕊)
    (u : Fin d → ℝ) (hu : u ∈ stdSimplex ℝ (Fin d))
    (S : Finset (Fin k)) : ∀ n : ℕ,
    (∫ h, ∑ t : Fin n, (if (h t).1 ∈ S then (1 : ℝ) else 0)
        ∂pmStochMeasure G π u hu n) =
      ∑ t ∈ Finset.range n,
        ∫ h, ∑ c ∈ S, (π.select t h).real {c}
          ∂pmStochMeasure G π u hu t := by
  sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (Cambridge University Press, 2020), Theorem 37.12 proof, printed pp. 490–491: Eq. (37.8) and the definition of T̃(n) in Step 3.

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