Theorem 13.4, p. 210 — KT wealth lower bound for continuous coins
ProvedModernOnlineLearning.ParameterFree.theorem_13_4coin-bettinggamma-functiononline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1
Start the KT bettor with wealth and give it outcomes for rounds , where . Write . Then
This is the continuous-coin wealth guarantee used to derive KT's one-dimensional regret bound.
Formalization Note The hypothesis gives a defined real denominator in the exponential expression and follows the intended domain of the printed bound.
Preamble
import Mathlib import Definitions.Def_ModernOnlineLearning_ParameterFree_Defs
Formal statement
namespace ModernOnlineLearning.ParameterFree
/-- Theorem 13.4, p. 210: continuous-coin KT wealth and its exponential lower bound. -/
theorem theorem_13_4 (ε : ℝ) (hε : 0 < ε) (T : ℕ) (hT : 1 ≤ T)
(c : ℕ → ℝ)
(hc : ∀ t ∈ Finset.Icc 1 T, -1 ≤ c t ∧ c t ≤ 1) :
let C : ℝ := ∑ t ∈ Finset.Icc 1 T, c t
ktPotential ε T C ≤ ktWealth ε c T ∧
ε * Real.exp (C ^ 2 / (2 * (T : ℝ)) - Real.log (T : ℝ) / 2 - 1) ≤
ktPotential ε T C := by sorry
end ModernOnlineLearning.ParameterFree
Source
Orabona, arXiv:1912.13213v10, Theorem 13.4, p. 210
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.