Graph-bound choice for optimized Algorithm 2
DefinitionFirstOrderFG_Supplement_Alg2_boundAbandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
When is nonempty, the optimized Algorithm 2 guarantee uses the explicit Lemma 2.1 bound on ; when it is empty and no meta-action exists, Theorem 4.2 takes .
This definition records that case distinction exactly.
Definition code
import Mathlib
import Definitions.Def_FirstOrderFG_Vself
import Definitions.Def_FirstOrderFG_Supplement_alphaBound
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **The graph bound used in the optimized clause of Theorem 4.2.**
Zhang–Zhang–Luo–Mineiro, arXiv:2610.40861, Theorem 4.2, p.11: use the Lemma 2.1
bound on `G_self` when the meta-action exists, and take `A = 1` otherwise. -/
noncomputable def Alg2.boundA {K : ℕ} (E : Fin K → Fin K → Prop) [DecidableRel E]
(T : ℕ) : ℝ :=
if (FirstOrderFG.Vself E).Nonempty then alphaBound E T else 1
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Theorem 4.2, p.11