A common edge point uniformly separates all outside actions
ProvedBanditAlgorithm.partial_monitoring_uniform_outside_gapbanditsconvex-geometrypartial-monitoring
Suppose at least one action lies outside . Then there are a common-cell distribution and a constant such that every action is uniformly worse than both and at :
The same and work for all outside actions. This is the uniform finite-action form of the strict separation encoded by Eq. (37.5).
Preamble
import Definitions.Def_PartialMonitoringGame import Theorems.Thm_BanditAlgorithm_partial_monitoring_outside_neighbourhood_strict_gap import Mathlib.Analysis.Convex.Combination import Mathlib.Data.Finset.Max import Mathlib.Tactic
Formal statement
theorem BanditAlgorithm.partial_monitoring_uniform_outside_gap
{k d : ℕ} {𝕊 : Type*} (G : PartialMonitoringGame k d 𝕊)
(a b : Fin k) (hout : ∃ c : Fin k, c ∉ pmNeighbourhood G a b) :
∃ u ∈ pmCell G a ∩ pmCell G b, ∃ ε : ℝ, 0 < ε ∧
∀ c : Fin k, c ∉ pmNeighbourhood G a b →
ε ≤ ∑ i, (G.L c i - G.L a i) * u i ∧
ε ≤ ∑ 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). The proof uses a finite convex average rather than the book’s centroid, yielding the same uniform strict-gap property.