BanditAlgorithm.partial_monitoring_hard_game_lower_bound
Provedlower-boundsonline-learningpartial-monitoring
(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 ,
Preamble
import Definitions.Def_PartialMonitoringGame import Mathlib.Analysis.SpecialFunctions.Pow.Real open MeasureTheory ProbabilityTheory
Formal statement
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
Source
L&S Theorem 37.12, p.488