Hard partial-monitoring lower bound from the information–regret tradeoff
ProvedBanditAlgorithm.partial_monitoring_hard_lower_of_tradeoffbanditsinformation-theorypartial-monitoring
Let be a finite partial-monitoring game. Suppose there are game-dependent constants and such that, for every , some satisfies
Then there is a constant for which
for every horizon . This formal bridge isolates the final optimization in the proof of the hard partial-monitoring lower bound from the preceding geometric and information-theoretic construction.
Preamble
import Definitions.Def_PartialMonitoringGame import Theorems.Thm_BanditAlgorithm_partial_monitoring_hard_tradeoff_analytic open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.partial_monitoring_hard_lower_of_tradeoff
{k d : ℕ} {𝕊 : Type*} [Fintype 𝕊] [MeasurableSpace 𝕊]
(G : PartialMonitoringGame k d 𝕊)
(htrade : ∃ ε 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) :
∃ c : ℝ, 0 < c ∧
∀ n : ℕ, c * (n : ℝ) ^ ((2 : ℝ) / 3) ≤ pmMinimaxRegret G n := by sorrySource
Formal bridge for Lattimore and Szepesvári, Bandit Algorithms, Chapter 37, Theorem 37.12 proof, printed p. 491, last three displays and Exercise 37.7; it invokes the separately proved p.491 analytic optimization theorem.