§2, p. 9 — comparison of the φ function
ProvedBanditCovariates.SE.phi_variationmulti-armed-banditp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitysuccessive-elimination
For , define for . If , then
The comparison replaces a sum over distinct arm gaps by a bound at one cutoff in the final step of Theorem 2.1.
Formalization Note Here in the paper's application. The page prints in that slot and swaps in the sentence applying the inequality; the derivation from (2.2) and the theorem require and the order stated here.
Preamble
import Mathlib import Definitions.Def_BanditCovariates_SE_Setting
Formal statement
namespace BanditCovariates.SE
/-- The comparison of φ on p. 9, using T in the overlined logarithm. -/
theorem phi_variation (a x x' : ℝ) (ha : 0 < a) (hx' : 0 < x')
(hxx' : x' ≤ x) :
phi a x ≤ 2 * Real.exp (-(1 / 2 : ℝ)) * phi a x' := by sorry
end BanditCovariates.SE
Source
Perchet, Rigollet, The multi-armed bandit problem with covariates, arXiv:1110.6084v3, p. 9, φ-variation display and paragraph after (2.7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.