State of Algorithm 3
DefinitionFirstOrderFG_Supplement_Alg3_Statebandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
Algorithm 3's state records the current graph-bound guess , the current fresh or continuing Algorithm 1 instance, and the realized incurred-loss accumulator since the latest restart.
The meta-epoch and epoch counters are represented by the values that the pseudocode actually reads: and the current instance's learning rate.
Definition code
import Mathlib import Definitions.Def_FirstOrderFG_Supplement_Alg1_State set_option autoImplicit false namespace FirstOrderFG.Supplement /-- **State of Algorithm 3 between rounds.** Zhang–Zhang–Luo–Mineiro, *Near-Optimal First-Order Regret for Bandits with Feedback Graphs*, arXiv:2610.40861, Algorithm 3, p.15: the current guess `A_m`, current fresh-or-continuing Algorithm 1 instance, and realized incurred-loss accumulator `S` since the most recent restart. -/ structure Alg3.State (K : ℕ) where A : ℝ inst : Alg1.State K S : ℝ end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Algorithm 3, p.15