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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup. is a completely arbitrary partial-monitoring game: actions, outcomes, finite measurable signal alphabet , real loss matrix (no boundedness), signal matrix . is the minimax regret at horizon (infimum over signal-only policies of the supremum over deterministic outcome sequences of the expected excess loss versus the best fixed action). "Neighbouring pair", "globally observable" (every neighbouring pair has a global loss estimator with for all ), and "locally observable" (the estimator can be chosen supported on the pair's neighbourhood) are as in the definition bundle.
Assertion. The conjunction of four implications, each asserted for this arbitrary :
- If no pair of actions is neighbouring, then for every (exact equality, all horizons including ).
- If is locally observable and some neighbouring pair exists, then
- If is globally observable and not locally observable, then
- If some neighbouring pair exists and is not globally observable, then
(a lower bound only; no matching upper bound is claimed in this case).
Hypotheses.
- Only: finite with a -algebra. There is no hypothesis bounding the losses, no , no non-degeneracy — each of the four implications is claimed for every game.
Edge cases.
- In particular, the upper bounds of cases 2 and 3 are asserted for games with arbitrarily large (unbounded) real losses.
- In cases 2–4 the bounds are only required from some existential threshold on, and the constants and thresholds may differ between cases; case 1's equality has no threshold.
- The antecedents may be unsatisfiable or overlap; an implication with a false antecedent holds vacuously. Since "locally/globally observable" are vacuously true without neighbouring pairs, the explicit "some neighbouring pair exists" conjuncts in cases 2 and 4 are what keeps those antecedents from covering the trivial case.
- inherits the real inf/sup junk conventions (value on empty or unbounded sets, e.g. when and no policy exists).
Confirmed by the mission captain (proposal self-audit).