Explicit independence-number bound on
DefinitionFirstOrderFG_Supplement_alphaBoundbandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
The explicit graph bound from Lemma 2.1 is
It is the concrete value substituted into the optimized clauses of the supplement.
Definition code
import Mathlib
import Definitions.Def_FirstOrderFG_indepNumber
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **The explicit Lemma 2.1 graph bound used by the supplement.**
Zhang–Zhang–Luo–Mineiro, arXiv:2610.40861, Lemma 2.1, p.4:
`2α ln(1 + (K³T+K)/α) + 2`. -/
noncomputable def alphaBound {K : ℕ} (E : Fin K → Fin K → Prop) (T : ℕ) : ℝ :=
2 * (FirstOrderFG.indepNumber E : ℝ) *
Real.log (1 + ((K : ℝ) ^ 3 * T + K) / FirstOrderFG.indepNumber E) + 2
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Lemma 2.1, p.4