Hard-game information–regret tradeoff optimization
ProvedBanditAlgorithm.partial_monitoring_hard_tradeoff_analyticbanditsinequalitiespartial-monitoring
Let and . Then there is a constant , depending only on these three parameters, such that for every integer and every ,
This is the elementary optimization that completes the hard partial-monitoring lower bound after the information/regret tradeoff has been established: either the exploration count is already of order , or the testing term remains a constant fraction of .
Preamble
import Mathlib.Analysis.SpecialFunctions.Pow.Real import Mathlib.Analysis.SpecialFunctions.ExpDeriv
Formal statement
theorem BanditAlgorithm.partial_monitoring_hard_tradeoff_analytic
(ε C δ : ℝ) (hε : 0 < ε) (hC : 0 ≤ C) (hδ : 0 < δ) :
∃ c : ℝ, 0 < c ∧ ∀ (n : ℕ), 1 ≤ n → ∀ x : ℝ, 0 ≤ x →
ε / 2 * x +
(n : ℝ) * (δ * (n : ℝ) ^ (-(1 : ℝ) / 3)) / 8 *
Real.exp (-C * (δ * (n : ℝ) ^ (-(1 : ℝ) / 3)) ^ 2 * x) ≥
c * (n : ℝ) ^ ((2 : ℝ) / 3) := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms, Chapter 37, Theorem 37.12 proof, printed p. 491, final display and Exercise 37.7.