Per-arm regret of Algorithm 2
DefinitionFirstOrderFG_Supplement_Alg2_RegKbandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
Against arm , the published Algorithm 2 instance with parameters has expected regret equal to its expected incurred loss minus .
This is the left-hand side of Theorem 4.2.
Definition code
import Mathlib
import Definitions.Def_FirstOrderFG_Supplement_Alg2_expLoss
import Definitions.Def_FirstOrderFG_Lk
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **Published Algorithm 2's expected regret against arm `k`.**
Zhang–Zhang–Luo–Mineiro, arXiv:2610.40861, §2, p.3, and Theorem 4.2, p.11. -/
noncomputable def Alg2.RegK {K : ℕ} (E : Fin K → Fin K → Prop) [DecidableRel E]
(T : ℕ) (ℓ : ℕ → Fin K → ℝ) (q₀ : (Fin K → ℝ) → ℝ → Fin K → ℝ)
(A θ : ℝ) (k : Fin K) : ℝ :=
Alg2.expLoss E T ℓ q₀ A θ - FirstOrderFG.Lk T ℓ k
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, §2, p.3; Theorem 4.2, p.11