Ordinary-simplex EXP3 update of Algorithm 1
DefinitionFirstOrderFG_Supplement_Alg1_updatebandit-algorithmsgraph-theorymachine-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a current distribution , loss estimate , and learning rate , Algorithm 1 chooses
where is the negative-entropy Bregman divergence. The feasible region is the ordinary simplex, not Algorithm 2's clipped simplex.
Definition code
import Mathlib
set_option autoImplicit false
namespace FirstOrderFG.Supplement
/-- **The ordinary-simplex EXP3 update of Algorithm 1.** Zhang–Zhang–Luo–Mineiro,
*Near-Optimal First-Order Regret for Bandits with Feedback Graphs*, arXiv:2610.40861,
Eq. (1), p.4, and Algorithm 1, line 5, p.7:
`argmin_{r ∈ Δ_K} {η ⟨r, ℓ̂_t⟩ + D_h(r,p_t)}`.
**Formalization Note.** This is the ordinary simplex `Δ_K`, not Algorithm 2's clipped
simplex. The argmin is `Classical.epsilon` over `IsMinOn`; negative-entropy divergence is
written explicitly over all `K` arms. -/
noncomputable def Alg1.update {K : ℕ} (η : ℝ) (p lt : Fin K → ℝ) : Fin K → ℝ :=
Classical.epsilon fun pn =>
pn ∈ {r : Fin K → ℝ | (∀ i, 0 ≤ r i) ∧ ∑ i, r i = 1} ∧
IsMinOn
(fun r => η * ∑ i, r i * lt i +
∑ i, (r i * Real.log (r i / p i) - r i + p i))
{r : Fin K → ℝ | (∀ i, 0 ≤ r i) ∧ ∑ i, r i = 1} pn
end FirstOrderFG.Supplement
Source
Zhang–Zhang–Luo–Mineiro, Near-Optimal First-Order Regret for Bandits with Feedback Graphs, arXiv:2610.40861, Eq. (1), p.4; Algorithm 1, line 5, p.7