A nonlocally observable edge admits an indistinguishable perturbation direction
ProvedBanditAlgorithm.partial_monitoring_nonlocal_edge_directionbanditsinformation-theorylinear-algebrapartial-monitoring
Fix neighbouring actions in a finite partial-monitoring game, and suppose their loss difference has no estimator supported on the neighbourhood . Then there is a direction satisfying
and, for every and every feedback symbol ,
Thus the perturbations preserve total probability and induce identical feedback distributions for every action in , while separating the expected losses of and at unit rate.
Preamble
import Definitions.Def_PartialMonitoringGame import Mathlib.Analysis.InnerProductSpace.PiL2 import Mathlib.Analysis.InnerProductSpace.Projection.FiniteDimensional
Formal statement
theorem BanditAlgorithm.partial_monitoring_nonlocal_edge_direction
{k d : ℕ} {𝕊 : Type*} [Fintype 𝕊] [DecidableEq 𝕊]
(G : PartialMonitoringGame k d 𝕊) (a b : Fin k)
(hab : NeighbouringActions G a b)
(hnlocal : ¬ ∃ f : Fin k × 𝕊 → ℝ, IsLocalLossEstimator G a b f) :
∃ q : Fin d → ℝ,
(∑ i, q i) = 0 ∧
(∑ i, (G.L a i - G.L b i) * q i) = 1 ∧
∀ c : Fin k, c ∈ pmNeighbourhood G a b → ∀ σ : 𝕊,
(∑ i ∈ Finset.univ.filter (fun i ↦ G.Φ c i = σ), q i) = 0 := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), Theorem 37.12, Step 1, printed pp. 489–490, Eq. (37.6) and the construction immediately following it.