Minimax partial-monitoring regret is bounded by any policy’s worst-case regret
ProvedBanditAlgorithm.pmMinimaxRegret_le_policy_of_unit_lossesbandit-theoryminimaxpartial-monitoring
Consider a finite partial-monitoring game with losses in and at least one action. For any horizon and any admissible policy , the minimax regret is at most the worst-case regret of that policy:
This is the policy-specialization principle for the infimum in the definition of minimax regret. The unit-loss assumption supplies a uniform lower bound on every policy’s worst-case regret, which is required because Lean represents the real infimum using a conditionally complete lattice. The statement also covers horizons or outcome spaces for which the set of outcome sequences is empty.
Preamble
import Definitions.Def_PartialMonitoringGame import Mathlib.Data.Fintype.Order open MeasureTheory ProbabilityTheory open scoped BigOperators namespace BanditAlgorithm
Formal statement
theorem pmMinimaxRegret_le_policy_of_unit_losses
{k d n : ℕ} {𝕊 : Type*} [Fintype 𝕊] [MeasurableSpace 𝕊]
(G : PartialMonitoringGame k d 𝕊) (hk : 1 ≤ k)
(hL : ∀ a i, G.L a i ∈ Set.Icc (0 : ℝ) 1)
(π : PMPolicy k 𝕊) :
pmMinimaxRegret G n ≤ ⨆ i : Fin n → Fin d, pmRegret G π n i := by sorrySource
Formal bridge from the definition of minimax regret in Lattimore and Szepesvári, Bandit Algorithms (2020), §37.1 p. 480 and §37.2 p. 483; used in Theorem 37.15, pp. 494–495, https://tor-lattimore.com/downloads/book/book.pdf