Tuned fixed learning rate of Theorem 3.2
DefinitionFirstOrderFG_Supplement_Alg1_tunedEtabandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
The optimized fixed rate in Theorem 3.2 is
Formalization Note At , the square-root expression is interpreted as before the minimum, so the inner minimum is ; this avoids Lean's total real division returning zero.
Definition code
import Mathlib
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **The tuned rate in Theorem 3.2.** Zhang–Zhang–Luo–Mineiro,
arXiv:2610.40861, Theorem 3.2, p.7:
`max{1/(KT), min{1/(12A), √(ln K/(A L⋆))}}`.
**Formalization Note.** When `L = 0`, the paper's positive-real expression has value `+∞`
before the minimum, so the minimum is `1/(12A)`; Lean's real division would instead return
zero. The explicit branch preserves the paper's convention. -/
noncomputable def Alg1.tunedEta (K T : ℕ) (A L : ℝ) : ℝ :=
max (1 / ((K : ℝ) * T))
(min (1 / (12 * A))
(if L = 0 then 1 / (12 * A) else Real.sqrt (Real.log K / (A * L))))
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Theorem 3.2, p.7