Stochastic partial-monitoring regret is bounded by worst-case regret
ProvedBanditAlgorithm.pmStochPseudoRegret_le_worst_pmRegretbanditsminimaxpartial-monitoringyao-principle
Fix a finite partial-monitoring game, a policy, a horizon , an outcome distribution , and a comparator action . Let be the expected stochastic pseudo-regret when the outcomes are sampled independently from . Then
where the maximum on the right is the policy’s regret over deterministic outcome sequences, with its usual best fixed-action comparator.
This is the finite-mixture/Yao bridge used when a stochastic two-environment lower bound is converted into a lower bound for adversarial minimax regret. The stochastic experiment is a probability mixture of the deterministic experiments, and regret against the fixed action is bounded pointwise by regret against the best fixed action.
Preamble
import Definitions.Def_PartialMonitoringStochastic open MeasureTheory ProbabilityTheory open scoped BigOperators ENNReal
Formal statement
theorem BanditAlgorithm.pmStochPseudoRegret_le_worst_pmRegret
{k d : ℕ} {𝕊 : Type*} [Fintype 𝕊] [MeasurableSpace 𝕊]
(G : PartialMonitoringGame k d 𝕊) (π : PMPolicy k 𝕊)
(u : Fin d → ℝ) (hu : u ∈ stdSimplex ℝ (Fin d))
(n : ℕ) (a : Fin k) :
pmStochPseudoRegret G π u hu n a ≤
⨆ i : Fin n → Fin d, pmRegret G π n i := by
sorry
Source
Lattimore and Szepesvari, Bandit Algorithms (Cambridge UP, 2020), Theorem 37.12 Step 3, printed p. 491, the display beginning R_n(pi,u_a)+R_n(pi,u_b), together with the adversarial minimax definition in Section 37.2, printed p. 483. The bridge is the finite-mixture interpretation of the stochastic environments used there.