Approximate fixed-point distribution of Algorithm 1
DefinitionFirstOrderFG_Supplement_Alg1_qOfbandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
At each round, Algorithm 1 starts Picard iteration from the uniform distribution and repeatedly applies the smoothed fixed-point map (11) for the current and until the residual is at most . The resulting interior distribution is .
The uniform start is part of Algorithm 1 and is not an arbitrary input.
Definition code
import Mathlib
import Definitions.Def_FirstOrderFG_Supplement_Alg1_State
import Definitions.Def_FirstOrderFG_picardFixed
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **Algorithm 1's sampling distribution.** Zhang–Zhang–Luo–Mineiro,
*Near-Optimal First-Order Regret for Bandits with Feedback Graphs*, arXiv:2610.40861,
Algorithm 1, line 3, p.7: starting from the uniform distribution, Picard-iterate the
smoothed map (11) until the residual is at most `ε = 1/(KT²)`.
**Formalization Note.** Unlike published Algorithm 2, whose start is an admissible parameter,
Algorithm 1 uses the paper's prescribed uniform start on every round. -/
noncomputable def Alg1.qOf {K : ℕ} (E : Fin K → Fin K → Prop) [DecidableRel E]
(T : ℕ) (st : Alg1.State K) : Fin K → ℝ :=
FirstOrderFG.picardFixed E T st.p st.η (fun _ => 1 / (K : ℝ))
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Algorithm 1, line 3, p.7