Initialization of Algorithm 3
DefinitionFirstOrderFG_Supplement_Alg3_initbandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
Algorithm 3 starts with , , and a fresh Algorithm 1 instance with
The embedded Algorithm 1 distribution is uniform.
Definition code
import Mathlib
import Definitions.Def_FirstOrderFG_Supplement_Alg3_State
import Definitions.Def_FirstOrderFG_Supplement_Alg1_init
import Definitions.Def_FirstOrderFG_Supplement_Alg1_initialEta
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **Initialization of Algorithm 3.** Zhang–Zhang–Luo–Mineiro,
arXiv:2610.40861, Algorithm 3, lines 1–2, p.15: `A₁ = 1`,
`η₁,₁ = max{1/(KT),1/(12A₁)}`, `S = 0`, and a fresh uniform Algorithm 1 instance. -/
noncomputable def Alg3.init (K T : ℕ) : Alg3.State K :=
⟨1, Alg1.init K (Alg1.initialEta K T 1), 0⟩
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Algorithm 3, lines 1–2, p.15