BanditAlgorithm.partial_monitoring_hard_game_lower_bound
Proved(Hard games, Theorem 37.12) If is globally observable but not locally observable, then there exists a game-dependent constant such that for every horizon ,
import Definitions.Def_PartialMonitoringGame import Mathlib.Analysis.SpecialFunctions.Pow.Real open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.partial_monitoring_hard_game_lower_bound {k d : ℕ} {𝕊 : Type*}
[Fintype 𝕊] [MeasurableSpace 𝕊] (G : PartialMonitoringGame k d 𝕊)
(hglob : GloballyObservable G) (hloc : ¬ LocallyObservable G) :
∃ c : ℝ, 0 < c ∧
∀ n : ℕ, c * (n : ℝ) ^ ((2 : ℝ) / 3) ≤ pmMinimaxRegret G n := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup. is a partial-monitoring game: losses and signals over actions and outcomes. is its minimax regret at horizon : the infimum over signal-only policies of the supremum over deterministic outcome sequences of , where the expectation is over the interaction law in which the round- action comes from applied to the past (action, signal) pairs and the observed signal is . A pair of actions is neighbouring when both cells (sets of outcome distributions making the action weakly optimal) are nonempty of affine dimension and their intersection is nonempty of affine dimension ; a global estimator for such a pair is a function of (action, signal) with at every outcome ; a local estimator additionally vanishes on actions whose cell does not contain the intersection.
Assertion.
Hypotheses.
- is finite and carries a -algebra; , , and the losses are arbitrary (no boundedness of ).
- is globally observable: every neighbouring pair admits a global estimator.
- is not locally observable — unfolding the negation: some neighbouring pair admits no local estimator (in particular, at least one neighbouring pair exists).
Edge cases.
- The inequality is claimed for all , including , where it degenerates to ( is the real power, ).
- inherits the real inf/sup junk conventions (empty or unbounded sets give the value ); the hypotheses do not exclude these degenerate regimes explicitly.
Confirmed by the mission captain (proposal self-audit).