Next-arm law of Algorithm 1
DefinitionFirstOrderFG_Supplement_Alg1_playbandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
After any played-arm history, the next arm of Algorithm 1 is drawn from the approximate fixed-point distribution computed from the current state.
This gives the conditional sampling law at every node of the finite trajectory tree.
Definition code
import Mathlib
import Definitions.Def_FirstOrderFG_Supplement_Alg1_run
import Definitions.Def_FirstOrderFG_Supplement_Alg1_qOf
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **The law of Algorithm 1's next sampled arm.** Zhang–Zhang–Luo–Mineiro,
arXiv:2610.40861, Algorithm 1, lines 3–4, p.7: after history `h`, draw from the
approximate fixed point computed from the current `p_t`. -/
noncomputable def Alg1.play {K : ℕ} (E : Fin K → Fin K → Prop) [DecidableRel E]
(T : ℕ) (ℓ : ℕ → Fin K → ℝ) (η : ℝ) (h : List (Fin K)) : Fin K → ℝ :=
Alg1.qOf E T (Alg1.run E T ℓ η h)
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Algorithm 1, lines 3–4, p.7