Uniform initialization of Algorithm 1
DefinitionFirstOrderFG_Supplement_Alg1_initbandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
Given arms and a learning rate , Algorithm 1 starts with the uniform EXP3 distribution and keeps fixed for the instance.
This initialization is reused at every restart made by Algorithm 3.
Definition code
import Mathlib import Definitions.Def_FirstOrderFG_Supplement_Alg1_State set_option autoImplicit false namespace FirstOrderFG.Supplement /-- **Initialization of Algorithm 1.** Zhang–Zhang–Luo–Mineiro, *Near-Optimal First-Order Regret for Bandits with Feedback Graphs*, arXiv:2610.40861, Algorithm 1, line 1, p.7: `p₁` is uniform on the `K` arms and the input learning rate is kept fixed throughout the instance. -/ noncomputable def Alg1.init (K : ℕ) (η : ℝ) : Alg1.State K := ⟨η, fun _ => 1 / (K : ℝ)⟩ end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Algorithm 1, line 1, p.7