Hard-game geometric and information–regret tradeoff
ProvedBanditAlgorithm.partial_monitoring_hard_game_tradeoffbanditsinformation-theorypartial-monitoring
Let be a finite globally observable but not locally observable partial-monitoring game. Then there are game-dependent constants and such that for every horizon there is an expected off-neighbourhood play count satisfying
The first term is the regret paid for informative actions outside the critical neighbourhood; the second is the testing cost for distinguishing the two stochastic environments constructed around a non-locally-observable neighbouring pair. This is precisely the geometric and information-theoretic core of the hard-game lower bound.
Preamble
import Definitions.Def_PartialMonitoringGame import Mathlib.Analysis.SpecialFunctions.Pow.Real open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.partial_monitoring_hard_game_tradeoff {k d : ℕ} {𝕊 : Type*}
[Fintype 𝕊] [MeasurableSpace 𝕊] (G : PartialMonitoringGame k d 𝕊)
(hglob : GloballyObservable G) (hloc : ¬ LocallyObservable G) :
∃ ε C δ : ℝ, 0 < ε ∧ 0 ≤ C ∧ 0 < δ ∧
∀ (n : ℕ), 1 ≤ n → ∃ x : ℝ, 0 ≤ x ∧
ε / 2 * x +
(n : ℝ) * (δ * (n : ℝ) ^ (-(1 : ℝ) / 3)) / 8 *
Real.exp (-C * (δ * (n : ℝ) ^ (-(1 : ℝ) / 3)) ^ 2 * x) ≤
2 * pmMinimaxRegret G n := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms, Chapter 37, Theorem 37.12 proof, printed pp. 488–491: Step 1 and Eq. (37.5)–(37.7), Step 2 Eq. (37.8)–(37.9), Step 3 Eq. (37.10) and the Bretagnolle–Huber display.