Lemma 7, p. 13 (FPL* with perturbation −R/ε; sign corrected) — E[Switches_τ(FPL*_ε)] ≤ (ετ + 2 log n)/(1 − ε)
ProvedLimitedSwitching.HighProb.lemma_7Let and , and let be any loss sequence with values in , fixed in advance. Run FPL: draw i.i.d. standard exponential, and at each round play the action minimising . Then for every horizon the expected number of switches satisfies
This is property (i) of Framework 1 for FPL. Through Lemma 3 it gives the high-probability switching bound of BFPL.
Formalization Note The paper's FPL has . For that variant the bound fails numerically (with , , it averages about 25.8 switches against a bound of 16.0). The statement is made for the sign-corrected perturbation , the exponential analogue of Kalai–Vempala's algorithm. The hypothesis makes meaningful. The expectation is a lower Lebesgue integral of the natural-valued switch count.
import Mathlib import Definitions.Def_LimitedSwitching_HighProb_Setting open MeasureTheory ProbabilityTheory open scoped ENNReal
namespace LimitedSwitching.HighProb
theorem lemma_7 {n : ℕ} [NeZero n] (ε : ℝ) (hε : 0 < ε) (hε1 : ε < 1) (τ : ℕ)
(ℓ : ℕ → Fin n → ℝ) (hℓ : IsLossSeq ℓ) :
∫⁻ R, (switches τ (play (fplStar ε) R ℓ) : ℝ≥0∞) ∂(expLaw n)
≤ ENNReal.ofReal ((ε * τ + 2 * Real.log n) / (1 - ε)) := by sorry
end LimitedSwitching.HighProb
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.