Algorithm 3 state after a history
DefinitionFirstOrderFG_Supplement_Alg3_runbandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
From the printed initial state, this is Algorithm 3's state before the round following a given played-arm history from round onward.
The state is a deterministic function of the oblivious losses and observed sampled arms.
Definition code
import Mathlib
import Definitions.Def_FirstOrderFG_Supplement_Alg3_runFrom
import Definitions.Def_FirstOrderFG_Supplement_Alg3_init
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **Algorithm 3's state before the round following a history.**
Zhang–Zhang–Luo–Mineiro, arXiv:2610.40861, Algorithm 3, p.15. -/
noncomputable def Alg3.run {K : ℕ} (E : Fin K → Fin K → Prop) [DecidableRel E]
(T : ℕ) (ℓ : ℕ → Fin K → ℝ) (h : List (Fin K)) : Alg3.State K :=
Alg3.runFrom E T ℓ 1 (Alg3.init K T) h
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