Bounded-variation loss on the active chain
DefinitionOrderedExperts_Supplement_IsBVLossbandit-algorithmsonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1regret-bounds
A loss is a BV loss on the current active chain if
This is the per-round loss class of the BV problem.
Formalization Note The range bound holds on the entire action space; total variation is computed only along the distinct active recommendations. The variation of a singleton chain is the empty sum, hence zero.
Definition code
import Definitions.Def_OrderedExperts_chainPt
open Finset
namespace OrderedExperts.Supplement
/-- **A bounded-variation loss on the current active chain.**
Zuo, *Online Learning with Ordered Experts (via Two-point Feedback)*, STOC 2027 submission
(held version), Sec. 2.1, p. 5.
The loss takes values in `[0,1]` on the action space and its total variation along the increasing
list of distinct current recommendations is at most one.
**Formalization Note.** The range condition is global, while total variation is imposed on the
finite active chain. Ranks are the base mission's 1-based ranks, and the empty variation sum for a
singleton chain is zero. -/
def IsBVLoss {A : Type*} [LinearOrder A] [OrderBot A] {n : ℕ}
(current : Fin n → A) (loss : A → ℝ) : Prop :=
let rs : ℕ → Fin n → A := fun _ ↦ current
let m := chainSize rs 0
(∀ x, 0 ≤ loss x ∧ loss x ≤ 1) ∧
∑ j ∈ Icc 2 m, |loss (chainPt rs 0 j) - loss (chainPt rs 0 (j - 1))| ≤ 1
end OrderedExperts.Supplement
Source
Zuo, Online Learning with Ordered Experts (via Two-point Feedback), STOC 2027 submission (held version), Sec. 2.1, p. 5