BanditAlgorithm.partial_monitoring_classification_theorem
Disproved⚠️ Retired — specification defect
The Lean statement below does not encode the problem shown on this page, so its
Disprovedstatus carries no information about that problem. Do not import this node or use it as a dependency.
(Classification theorem, GOAL, Theorem 37.11) The minimax regret of any finite adversarial partial-monitoring game falls into one of four categories:
- for all if has no pairs of neighbouring actions;
- if is locally observable and has neighbouring actions;
- if is globally observable but not locally observable;
- otherwise (i.e. has neighbouring actions but is not globally observable).
Per the book's note, the Landau symbols are in the traditional mathematical sense: constants are game-dependent and the two-sided bounds are asymptotic (for all beyond a game-dependent threshold), with all factors absorbed into the constants.
Why this node was retired
The posted statement is
theorem BanditAlgorithm.partial_monitoring_classification_theorem {k d : ℕ} {𝕊 : Type*}
[Fintype 𝕊] [MeasurableSpace 𝕊] (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
sorry
The finite feedback alphabet has an arbitrary sigma-algebra; with the indiscrete one, the policy cannot observe the nominally informative signal.
The recorded counterexample refutes the statement as encoded. It says nothing about the problem shown above, which is a different proposition.
Proposed corrected statement
Add [MeasurableSingletonClass 𝕊] (equivalently the discrete sigma-algebra for this finite signal type), and retain the loss, policy, and local-observability hypotheses.
Diagnosis and correction from the public Prove2Me statement audit (wamlat/prove2me-errors). The correction is natural-language mathematics and is not Lean-verified — it is a specification for a corrected node, not a drop-in replacement. No corrected replacement node exists yet.
import Definitions.Def_PartialMonitoringGame import Mathlib.Analysis.SpecialFunctions.Pow.Real import Mathlib.Data.Real.Sqrt open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.partial_monitoring_classification_theorem {k d : ℕ} {𝕊 : Type*}
[Fintype 𝕊] [MeasurableSpace 𝕊] (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
sorry