Lemma 5, p. 13 (corrected: M·(Switches_T + 1)) — pointwise regret bound for FPL with perturbations P_t
ProvedLimitedSwitching.HighProb.lemma_5Let and , and let be arbitrary real perturbations and arbitrary real losses. Let FPL play at round the (lowest-index) minimiser of , with , for every . In particular is the perturbed leader after round . Let bound the loss differences: for all and all . Then, pointwise,
This is property (ii) of Framework 1 for FPL-type algorithms: regret is controlled by switching plus a perturbation term that does not depend on the adversary.
Formalization Note As printed, with , the lemma is false. Take , , , otherwise, and : then the regret is while the printed right side is . The printed proof (p. 27) bounds , which also counts a move to the never-played leader . Hence . The paper's is the supremum of over losses; here is any bound for the given losses, which is at least as strong.
import Mathlib import Definitions.Def_LimitedSwitching_HighProb_Setting open MeasureTheory ProbabilityTheory open scoped ENNReal
namespace LimitedSwitching.HighProb
theorem lemma_5 {n : ℕ} [NeZero n] (P : ℕ → Fin n → ℝ) (ℓ : ℕ → Fin n → ℝ) (T : ℕ) (M : ℝ)
(hM0 : 0 ≤ M) (hM : ∀ t ∈ Finset.Icc 1 T, ∀ i j, |ℓ t i - ℓ t j| ≤ M) :
regret T ℓ (fplPlay P ℓ)
≤ M * ((switches T (fplPlay P ℓ) : ℝ) + 1)
+ (⨆ i, ∑ t ∈ Finset.Icc 1 (T + 1), P t i)
- ∑ t ∈ Finset.Icc 1 (T + 1), P t (fplPlay P ℓ t) := by sorry
end LimitedSwitching.HighProb
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.