Initial learning rate for an Algorithm 3 guess
DefinitionFirstOrderFG_Supplement_Alg1_initialEtabandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a current guess , every new meta-epoch of Algorithm 3 starts Algorithm 1 with
The maximum is exactly the initialization printed in Algorithm 3.
Definition code
import Mathlib
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **The initial fixed rate for a guess `A` in Algorithm 3.** Zhang–Zhang–Luo–Mineiro,
arXiv:2610.40861, Algorithm 3, lines 1 and 6, p.15:
`max{1/(KT), 1/(12A)}`. -/
noncomputable def Alg1.initialEta (K T : ℕ) (A : ℝ) : ℝ :=
max (1 / ((K : ℝ) * T)) (1 / (12 * A))
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Algorithm 3, lines 1 and 6, p.15