A non-locally observable edge has an action outside its neighbourhood
ProvedBanditAlgorithm.exists_action_outside_nonlocal_neighbourhoodbanditsinformation-theorypartial-monitoring
Let be a finite partial-monitoring game. If is globally observable but not locally observable, then there are neighbouring actions such that their loss difference has a global feedback estimator, while at least one action lies outside the neighbourhood :
This isolates the first logical consequence used in the hard-game lower-bound construction: the failure of local observability occurs on a concrete edge, and global observability still supplies an estimator on that edge.
Preamble
import Definitions.Def_PartialMonitoringGame
Formal statement
theorem BanditAlgorithm.exists_action_outside_nonlocal_neighbourhood
{k d : ℕ} {𝕊 : Type*} (G : PartialMonitoringGame k d 𝕊)
(hglob : GloballyObservable G) (hloc : ¬ LocallyObservable G) :
∃ a b : Fin k, NeighbouringActions G a b ∧
(∃ f : Fin k × 𝕊 → ℝ, IsGlobalLossEstimator G a b f) ∧
∃ c : Fin k, c ∉ pmNeighbourhood G a b := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), Theorem 37.12, Step 1, printed pp. 488–489, especially Eq. (37.5).