Equation (2.2), p. 7 — bound on the elimination round
ProvedBanditCovariates.SE.bound_2_2multi-armed-banditp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitysuccessive-elimination
For a gap , , and integer , let be the first positive integer round at which . Then
This deterministic estimate limits how long a suboptimal arm can remain active on the good event.
Formalization Note The paper defines as the ceiling of the positive real solution of the corresponding equality. The least-integer formulation gives that ceiling. The upper bound follows from rewards in .
Preamble
import Mathlib import Definitions.Def_BanditCovariates_SE_Setting
Formal statement
namespace BanditCovariates.SE
/-- Equation (2.2), p. 7: the deterministic stopping-round upper bound. -/
theorem bound_2_2 (T : ℕ) (hT : 1 ≤ T) (γ Δ : ℝ)
(hγ : 1 ≤ γ) (hΔ : 0 < Δ) (hΔ1 : Δ ≤ 1) :
(stoppingRound T γ Δ : ℝ) ≤
(19 * γ ^ 2 / Δ ^ 2) * logbar ((T : ℝ) * Δ ^ 2 / (18 * γ ^ 2)) := by sorry
end BanditCovariates.SE
Source
Perchet, Rigollet, The multi-armed bandit problem with covariates, arXiv:1110.6084v3, p. 7, (2.2) and its preceding definition of τ_i
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.