Number of pre-round -doublings in Algorithm 3
DefinitionFirstOrderFG_Supplement_Alg3_doublingIndexbandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
If the current guess fails , Algorithm 3 doubles and starts a fresh Algorithm 1 instance repeatedly. The doubling index is the first for which the fresh instance at guess passes the test.
This permits several doublings before one sampled round and therefore permits empty meta-epochs.
Definition code
import Mathlib
import Definitions.Def_FirstOrderFG_Supplement_Alg1_init
import Definitions.Def_FirstOrderFG_Supplement_Alg1_initialEta
import Definitions.Def_FirstOrderFG_Supplement_Alg1_qOf
import Definitions.Def_FirstOrderFG_Hgraph
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **Number of consecutive `A`-doublings before one sampled round of Algorithm 3.**
Zhang–Zhang–Luo–Mineiro, arXiv:2610.40861, Algorithm 3, lines 5–8, p.15.
It is the first `j ≥ 1` for which the fresh Algorithm 1 instance at guess `A·2^j`
passes `H^G(q_t) ≤ A·2^j`.
**Formalization Note.** The `sInf` models the while-loop, including empty intermediate
meta-epochs. The set is nonempty because the paper proves `H^G(q) ≤ K`. -/
noncomputable def Alg3.doublingIndex {K : ℕ} (E : Fin K → Fin K → Prop) [DecidableRel E]
(T : ℕ) (A : ℝ) : ℕ :=
sInf {j : ℕ | 1 ≤ j ∧
FirstOrderFG.Hgraph E T
(Alg1.qOf E T
(Alg1.init K (Alg1.initialEta K T (A * 2 ^ j)))) ≤ A * 2 ^ j}
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Algorithm 3, lines 5–8, p.15