Tuned master rate of Theorem 4.2
DefinitionFirstOrderFG_Supplement_Alg2_tunedThetabandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
With and , the tuned master rate is
Formalization Note At , the second term is interpreted as , so the minimum is rather than Lean's zero-valued real division.
Definition code
import Mathlib
import Definitions.Def_FirstOrderFG_Bset
import Definitions.Def_FirstOrderFG_GammaA
import Definitions.Def_FirstOrderFG_cConst
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **The tuned master rate in Theorem 4.2.** Zhang–Zhang–Luo–Mineiro,
arXiv:2610.40861, Theorem 4.2, p.11, with the proof's
`c = 1/(2¹³e²)` from p.31:
`min{c/Γ_A, √(ln(MT)/(Γ_A L⋆))}`.
**Formalization Note.** At `L = 0`, the square-root expression is mathematically `+∞`, so
the minimum is `c/Γ_A`; the branch avoids Lean real division's default value zero. -/
noncomputable def Alg2.tunedTheta {K : ℕ} (E : Fin K → Fin K → Prop) [DecidableRel E]
(T : ℕ) (A L : ℝ) : ℝ :=
min (FirstOrderFG.cConst / FirstOrderFG.GammaA E T A)
(if L = 0 then FirstOrderFG.cConst / FirstOrderFG.GammaA E T A
else Real.sqrt
(Real.log (((FirstOrderFG.Bset E).card : ℝ) * T) /
(FirstOrderFG.GammaA E T A * L)))
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Theorem 4.2, p.11; proof of Theorem 4.2, p.31