Corollary 6, p. 13, for BFPL* as on p. 14 (corrected: + E) — Regret_T ≤ Switches_T + E + Σ_e max_i R_e(i)/ε pointwise
ProvedLimitedSwitching.HighProb.corollary_6Let , , any budget and , and let be a loss sequence with values in . Let be Framework 1 applied to FPL (perturbation in epoch ), run with nonnegative perturbation vectors , one for each epoch. Let be the number of epochs used in rounds . Then, pointwise,
This is the specialisation of Corollary 6 used in the proof of Theorem 8 (p. 14). Combined with Lemma 3, which bounds , and Lemma 9, which bounds the sum of maxima, it gives the high-probability regret bound.
Formalization Note The term is a correction: Corollary 6 sums Lemma 5 over the epochs, and Lemma 5 needs (see its note), with for losses in . The general-perturbation form of Corollary 6 is not stated. Epochs are 0-based, so the sum runs over .
import Mathlib import Definitions.Def_LimitedSwitching_HighProb_Setting open MeasureTheory ProbabilityTheory open scoped ENNReal
namespace LimitedSwitching.HighProb
theorem corollary_6 {n : ℕ} [NeZero n] (ω : ℕ → Fin n → ℝ) (hω : ∀ e i, 0 ≤ ω e i)
(ε : ℝ) (hε : 0 < ε) (S' : ℝ) (T : ℕ) (hT : 1 ≤ T)
(ℓ : ℕ → Fin n → ℝ) (hℓ : IsLossSeq ℓ) :
regret T ℓ (play (batch (fplStar ε) S') ω ℓ)
≤ (switches T (play (batch (fplStar ε) S') ω ℓ) : ℝ)
+ (numEpochs (fplStar ε) S' ω ℓ T : ℝ)
+ ∑ e ∈ Finset.range (numEpochs (fplStar ε) S' ω ℓ T),
Finset.univ.sup' Finset.univ_nonempty (ω e) / ε := by sorry
end LimitedSwitching.HighProb
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.