Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BanditAlgorithm.contextual_bandit_exp4_regret_bound

Proved

by Shuze Chen · Jul 28, 2026 · Mathlib c5ea003 (Lean v4.30.0)

banditscontextualexp4regret

(Exp4 regret bound, GOAL — L&S Theorem 18.1) Let γ=0\gamma = 0γ=0 and

η=2log⁡Mnk.\eta = \sqrt{\frac{2\log M}{nk}}.η=nk2logM​​.

For any adversarial rewards x∈[0,1]n×kx \in [0,1]^{n\times k}x∈[0,1]n×k and any M≥2M \ge 2M≥2 oblivious experts whose advice rows lie in the probability simplex, the regret of Exp4 against the best expert satisfies

Rn≤2nklog⁡MR_n \le \sqrt{2nk\log M}Rn​≤2nklogM​

(Eq. (18.7)).

Preamble
import Definitions.Def_ContextualAdversarialBandit
import Definitions.Def_exp4Policy


open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.contextual_bandit_exp4_regret_bound
    {k M : ℕ} (hk : 0 < k) (hM : 1 < M) (n : ℕ) (hn : 0 < n)
    (x : ℕ → Fin k → ℝ) (hx : ∀ t : ℕ, ∀ a : Fin k, x t a ∈ Set.Icc (0 : ℝ) 1)
    (E : ℕ → Fin M → Fin k → ℝ)
    (hE0 : ∀ t : ℕ, ∀ m : Fin M, ∀ a : Fin k, 0 ≤ E t m a)
    (hE1 : ∀ t : ℕ, ∀ m : Fin M, ∑ a, E t m a = 1)
    (π : BanditPolicy k)
    (hπ : IsExp4Policy (Real.sqrt (2 * Real.log M / (n * k))) 0 E π) :
    exp4Regret n x E π ≤ Real.sqrt (2 * n * k * Real.log M) := by
  sorry
Source
L&S Theorem 18.1, p.230
Read-back

What the Lean code literally says, in plain math · claude-fable-5

Setup and notation. A kkk-armed adversarial bandit with deterministic reward table xt(a)x_t(a)xt​(a) (t∈{0,1,… }t \in \{0,1,\dots\}t∈{0,1,…}, a∈{1,…,k}a \in \{1,\dots,k\}a∈{1,…,k}) is played by a policy π\piπ with the advice of MMM experts Et(m,a)E_t(m,a)Et​(m,a). The interaction law P\mathbb{P}P on length-nnn histories draws, at each round t=0,…,n−1t = 0,\dots,n-1t=0,…,n−1, the arm AtA_tAt​ from the policy's Markov kernel applied to the past history and records the pair (At,xt(At))(A_t, x_t(A_t))(At​,xt​(At​)). The regret against the experts is

Rn  =  (max⁡m∑t=0n−1∑a=1kEt(m,a) xt(a))  −  EP[∑t=0n−1Xt].R_n \;=\; \Bigl(\max_{m} \sum_{t=0}^{n-1}\sum_{a=1}^{k} E_t(m,a)\,x_t(a)\Bigr) \;-\; \mathbb{E}_{\mathbb{P}}\Bigl[\sum_{t=0}^{n-1} X_t\Bigr].Rn​=(mmax​t=0∑n−1​a=1∑k​Et​(m,a)xt​(a))−EP​[t=0∑n−1​Xt​].

The policy is assumed to be an Exp4 policy: writing S^0(m)=0\hat S_0(m)=0S^0​(m)=0, wt(m)=eηS^t(m)/∑m′eηS^t(m′)w_t(m) = e^{\eta \hat S_t(m)}/\sum_{m'} e^{\eta \hat S_t(m')}wt​(m)=eηS^t​(m)/∑m′​eηS^t​(m′), Pt(a)=∑mwt(m)Et(m,a)P_t(a) = \sum_m w_t(m) E_t(m,a)Pt​(a)=∑m​wt​(m)Et​(m,a), and S^t+1(m)=S^t(m)+∑aEt(m,a)(1−1{At=a}(1−Xt)/(Pt(a)+γ))\hat S_{t+1}(m) = \hat S_t(m) + \sum_a E_t(m,a)\bigl(1 - \mathbb{1}\{A_t=a\}(1-X_t)/(P_t(a)+\gamma)\bigr)S^t+1​(m)=S^t​(m)+∑a​Et​(m,a)(1−1{At​=a}(1−Xt​)/(Pt​(a)+γ)), the policy's kernel at every round ttt and every history equals ∑amax⁡(Pt(a),0) δa\sum_a \max(P_t(a),0)\,\delta_a∑a​max(Pt​(a),0)δa​ — here with the specific parameters

η  =  2log⁡Mn k,γ  =  0.\eta \;=\; \sqrt{\frac{2\log M}{n\,k}}, \qquad \gamma \;=\; 0.η=nk2logM​​,γ=0.

Assertion.

Rn  ≤  2 n k log⁡M.R_n \;\le\; \sqrt{2\,n\,k\,\log M}.Rn​≤2nklogM​.

Hypotheses.

  • k≥1k \ge 1k≥1, M≥2M \ge 2M≥2 (strictly 1<M1 < M1<M), and n≥1n \ge 1n≥1.
  • Rewards are bounded: xt(a)∈[0,1]x_t(a) \in [0,1]xt​(a)∈[0,1] (closed interval) for every t∈{0,1,2,… }t \in \{0,1,2,\dots\}t∈{0,1,2,…} — all rounds, not only t<nt < nt<n — and every arm aaa.
  • Advice rows are probability vectors at every round: Et(m,a)≥0E_t(m,a) \ge 0Et​(m,a)≥0 and ∑a=1kEt(m,a)=1\sum_{a=1}^k E_t(m,a) = 1∑a=1k​Et​(m,a)=1 for all t∈{0,1,2,… }t \in \{0,1,2,\dots\}t∈{0,1,2,…} and all mmm.
  • π\piπ is an Exp4 policy for (η,γ)=(2log⁡M/(nk), 0)(\eta, \gamma) = \bigl(\sqrt{2\log M/(nk)},\, 0\bigr)(η,γ)=(2logM/(nk)​,0) and the given advice EEE, in the exact kernel-equality sense above.

Edge cases.

  • With γ=0\gamma = 0γ=0, the estimator's divisor is Pt(a)P_t(a)Pt​(a) alone; if Pt(a)=0P_t(a) = 0Pt​(a)=0 the division yields 000 by convention.
  • Since M≥2M \ge 2M≥2, log⁡M>0\log M > 0logM>0, so η\etaη is a genuine positive real and the right-hand side is a positive real square root.
  • The bound is on the expected-regret quantity RnR_nRn​ (a Bochner integral appears in its definition; convention 000 if non-integrable); this is not a high-probability statement.
  • The Exp4-policy hypothesis is an exact measure equality required at every history; if no policy satisfies it for the given data, the statement is vacuously true for that data.
Human review
  • Endorsed by Community (Bot) · Jul 28, 2026

  • Endorsed by Shuze Chen · Jul 28, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me