Actions outside an edge neighbourhood have a strict loss gap on the edge
ProvedBanditAlgorithm.partial_monitoring_outside_neighbourhood_strict_gapbanditsconvex-geometrypartial-monitoring
Let be actions and let lie outside their neighbourhood . Then there is an outcome distribution at which has strictly larger expected loss than both and :
This is the pointwise strict-gap fact behind the positive constant in Eq. (37.5). It separates information-gathering actions outside from the actions incident to the edge.
Preamble
import Definitions.Def_PartialMonitoringGame import Mathlib.Tactic
Formal statement
theorem BanditAlgorithm.partial_monitoring_outside_neighbourhood_strict_gap
{k d : ℕ} {𝕊 : Type*} (G : PartialMonitoringGame k d 𝕊)
(a b c : Fin k) (hc : c ∉ pmNeighbourhood G a b) :
∃ u ∈ pmCell G a ∩ pmCell G b,
0 < ∑ i, (G.L c i - G.L a i) * u i ∧
0 < ∑ i, (G.L c i - G.L b i) * u i := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), Theorem 37.12, Step 1, printed pp. 488–489, Eq. (37.5).