Best expert loss in hindsight
DefinitionOrderedExperts_Supplement_bestExpertLossbandit-algorithmsonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1regret-bounds
For a nonempty finite expert class, the best expert loss in hindsight is
It is the comparator subtracted from each learner's expected paid loss.
Formalization Note The minimum is an attained finite-set minimum, not a real infimum with an empty-set or unbounded-set default value.
Definition code
import Mathlib
open Finset
namespace OrderedExperts.Supplement
/-- **Loss of the best expert in hindsight.**
Zuo, *Online Learning with Ordered Experts (via Two-point Feedback)*, STOC 2027 submission
(held version), Sec. 2.2, p. 6.
**Formalization Note.** `Finset.inf'` is the genuine attained minimum over the finite nonempty
expert class. It has no empty-set or unbounded-set default value. -/
noncomputable def bestExpertLoss {A : Type*} {n : ℕ} [NeZero n] (T : ℕ)
(rec : ℕ → Fin n → A) (loss : ℕ → A → ℝ) : ℝ :=
Finset.univ.inf' Finset.univ_nonempty
(fun f ↦ ∑ t ∈ Finset.range T, loss t (rec t f))
end OrderedExperts.Supplement
Source
Zuo, Online Learning with Ordered Experts (via Two-point Feedback), STOC 2027 submission (held version), Sec. 2.2, p. 6