Expected action-set count equals cumulative selection mass
ProvedBanditAlgorithm.pmStoch_expected_actionSetCount_eq_selection_massbanditspartial-monitoringprobabilitytextbook
Let a policy interact for rounds with a stochastic partial-monitoring environment whose outcomes are independently distributed according to . For any finite set of actions , let count the rounds on which the selected action belongs to . Then
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 gives the expected informative-action count used in the hard partial-monitoring lower bound.
Formalization Note The left-hand side writes 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
sorrySource
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.