Bandit feedback is only one point on a spectrum: a learner might see more than its own loss (full information) or less (a spam filter never learns what happened to mail it deleted). Chapter 37 of Lattimore–Szepesvári studies finite adversarial games where the loss matrix and the feedback matrix are decoupled. The goal theorem is the celebrated classification theorem: every finite partial-monitoring game has minimax regret exactly , , or — determined by two purely combinatorial conditions, global and local observability, on the game's neighbourhood structure. A single geometric dichotomy thus governs the price of information in every online decision problem with finite actions and feedback.
theorem BanditAlgorithm.partial_monitoring_classification_theorem_discrete_signals
{k d : ℕ} {𝕊 : Type*}
[Fintype 𝕊] [MeasurableSpace 𝕊] [MeasurableSingletonClass 𝕊]
(G : PartialMonitoringGame k d 𝕊) :
(¬ HasNeighbouringActions G → ∀ n : ℕ, pmMinimaxRegret G n = 0) ∧
(LocallyObservable G ∧ HasNeighbouringActions G →
∃ c C : ℝ, 0 < c ∧ 0 < C ∧ ∃ N : ℕ, ∀ n : ℕ, N ≤ n →
c * Real.sqrt n ≤ pmMinimaxRegret G n ∧
pmMinimaxRegret G n ≤ C * Real.sqrt n) ∧
(GloballyObservable G ∧ ¬ LocallyObservable G →
∃ c C : ℝ, 0 < c ∧ 0 < C ∧ ∃ N : ℕ, ∀ n : ℕ, N ≤ n →
c * (n : ℝ) ^ ((2 : ℝ) / 3) ≤ pmMinimaxRegret G n ∧
pmMinimaxRegret G n ≤ C * (n : ℝ) ^ ((2 : ℝ) / 3)) ∧
(HasNeighbouringActions G ∧ ¬ GloballyObservable G →
∃ c : ℝ, 0 < c ∧ ∃ N : ℕ, ∀ n : ℕ, N ≤ n →
c * (n : ℝ) ≤ pmMinimaxRegret G n) := by
sorryLet be a finite adversarial partial-monitoring game with actions, outcomes, and a finite signal alphabet equipped with the discrete measurable structure. Write for its minimax regret at horizon . Then
The constants implicit in and , as well as the horizon from which the bounds hold, may depend on the game. This classification separates trivial, easy, hard, and hopeless finite partial-monitoring games according to the geometry of their cells and the observability of neighbouring loss differences.
Formalization Note The hypothesis that every singleton of is measurable, together with finiteness of , makes its measurable structure discrete. This is the measurable-space counterpart of the source treating the finite signal alphabet as an ordinary discrete set.
No open leaves. Every sub-goal is proved or awaiting decomposition.