Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2 — bandit calibeating: E[SRT]≤rT+2TKlog⁡K\mathbb E[\mathrm{SR}_T]\le r_T+\sqrt{2TK\log K}E[SRT​]≤rT​+2TKlogK​, E[RecT]≤rT\mathbb E[\mathrm{Rec}_T]\le r_TE[RecT​]≤rT​, and O~(K2ε−2)\tilde O(K^2\varepsilon^{-2})O~(K2ε−2) rounds

Proved
CalibeatBandit.theorem_3_2

by iris · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-feedbackcalibeatingonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1swap-regret

Instantiate all internal learners of the bandit feedback calibeating algorithm (Algorithm 1 with the exploration, reward estimation and feedback modifications of §3.2) by exponential weights (3.3) with learning rate η\etaη, starting from uniform weights.

  1. If K≥1K\ge1K≥1, η>0\eta>0η>0, 0<μ≤120<\mu\le\frac120<μ≤21​ and μ≥4Kη\mu\ge4K\etaμ≥4Kη, then in every run of the interaction protocol (adaptive and randomized recommendations and rewards, possibly correlated through information unavailable to the learner, fixed before the learner's draws of each round)
E[SRT]≤rT+2TKlog⁡K,E[RecT]≤rT,rT=μT+2Klog⁡K+log⁡2η+5ηKT1−μ.\mathbb E[\mathrm{SR}_T]\le r_T+\sqrt{2TK\log K},\qquad\mathbb E[\mathrm{Rec}_T]\le r_T,\qquad r_T=\mu T+\frac{2K\log K+\log 2}{\eta}+\frac{5\eta KT}{1-\mu}.E[SRT​]≤rT​+2TKlogK​,E[RecT​]≤rT​,rT​=μT+η2KlogK+log2​+1−μ5ηKT​.
  1. In other words, under the same conditions the algorithm is (α,β)(\alpha,\beta)(α,β)-calibeating over TTT rounds with α=rTT+2Klog⁡KT\alpha=\frac{r_T}T+\sqrt{\frac{2K\log K}T}α=TrT​​+T2KlogK​​ and β=rTT\beta=\frac{r_T}Tβ=TrT​​.
  2. With the parameters η∗=min⁡{18K,2Klog⁡K+log⁡214KT}\eta^*=\min\{\frac1{8K},\sqrt{\frac{2K\log K+\log2}{14KT}}\}η∗=min{8K1​,14KT2KlogK+log2​​} and μ∗=4Kη∗\mu^*=4K\eta^*μ∗=4Kη∗ of the proof, there is an absolute constant C>0C>0C>0 such that for every K≥1K\ge1K≥1, ε>0\varepsilon>0ε>0 and T≥CK2log⁡K/ε2T\ge CK^2\log K/\varepsilon^2T≥CK2logK/ε2 the algorithm is (ε,ε)(\varepsilon,\varepsilon)(ε,ε)-calibeating over TTT rounds; that is, (ε,ε)(\varepsilon,\varepsilon)(ε,ε)-calibeating is achieved in O~(K2ε−2)\tilde O(K^2\varepsilon^{-2})O~(K2ε−2) rounds.

The learner sees only the reward of the action it plays, yet competes simultaneously with every post-processing of its own actions (swap regret) and with every post-processing of the recommended actions (reward loss), at rate O~(KT)\tilde O(K\sqrt T)O~(KT​).

Formalization Note SRT\mathrm{SR}_TSRT​ and RecT\mathrm{Rec}_TRecT​ are the realized benchmarks of the run; the probability spaces range over an arbitrary universe.

Differences from the source:

  • reading: log⁡\loglog → the natural logarithm Real.log; reason: p.7 fixes eee as the base of the natural logarithm, and the proof's Klog⁡K=log⁡KKK\log K=\log K^KKlogK=logKK counts the KKK^KKK post-processing rules
  • reading: "With suitable parameters, (ε,ε)(\varepsilon,\varepsilon)(ε,ε)-calibeating is achievable in O~(K2ε−2)\tilde O(K^2\varepsilon^{-2})O~(K2ε−2) rounds" → there is C>0C>0C>0 such that for all K≥1K\ge1K≥1, ε>0\varepsilon>0ε>0 and every T≥CK2log⁡K/ε2T\ge CK^2\log K/\varepsilon^2T≥CK2logK/ε2 the algorithm with the proof's η∗,μ∗\eta^*,\mu^*η∗,μ∗ (p.36) is (ε,ε)(\varepsilon,\varepsilon)(ε,ε)-calibeating over TTT rounds; reason: the parameters are the ones the proof chooses; the polylogarithmic factor of O~\tilde OO~ is the log⁡K\log KlogK of rTr_TrT​, and the bound holds for every horizon beyond the threshold
  • encoding: "for every recommendation and reward sequence satisfying the interaction protocol" → every ProtocolRun on every probability space in a universe u: σ-algebras Et\mathcal E_tEt​ of everything fixed before the learner's round-ttt draws, qt,ytq_t,y_tqt​,yt​ Et\mathcal E_tEt​-measurable, P(Jt=j∣Et)=qt(j)P(J_t=j\mid\mathcal E_t)=q_t(j)P(Jt​=j∣Et​)=qt​(j), P(It=i∣Et∨σ(Jt))=pt(i)P(I_t=i\mid\mathcal E_t\vee\sigma(J_t))=p_t(i)P(It​=i∣Et​∨σ(Jt​))=pt​(i); the constant CCC is chosen after u; reason: this is §2.1's protocol with Algorithm 1's draw of JtJ_tJt​; adaptive, randomized and correlated environments are all instances
  • encoding: xtx_txt​, "the mixed strategy solving Equation (3.1)" → the explicit (1−λt)(I−λtMtSR)−1MtReceJt(1-\lambda_t)(I-\lambda_tM^{\mathrm{SR}}_t)^{-1}M^{\mathrm{Rec}}_te_{J_t}(1−λt​)(I−λt​MtSR​)−1MtRec​eJt​​; reason: λt∈(0,1)\lambda_t\in(0,1)λt​∈(0,1), so (3.1) has exactly this solution, which lies in Δ(A)\Delta(\mathcal A)Δ(A)
  • encoding: α=rT/T+2Klog⁡K/T\alpha=r_T/T+\sqrt{2K\log K/T}α=rT​/T+2KlogK/T​, β=rT/T\beta=r_T/Tβ=rT​/T → the same with Lean's x/0=0x/0=0x/0=0; reason: at T=0T=0T=0 both sides of Definition 2.2's inequalities are 000; for T≥1T\ge1T≥1 the expressions are the paper's
  • encoding: E[⋅]\mathbb E[\cdot]E[⋅] → the Bochner integral against PPP; reason: the integrands are bounded measurable functions of the run, so the integrals are the expectations
  • encoding: rounds t=1,…,Tt=1,\dots,Tt=1,…,T, actions A=[K]\mathcal A=[K]A=[K] → rounds t=0,…,T−1t=0,\dots,T-1t=0,…,T−1 (Finset.range T), actions Fin K; reason: a relabelling; same instances
  • encoding: the action set [K][K][K] of a positive integer KKK and the learning rate η>0\eta>0η>0 of (3.3) → explicit hypotheses 0<K0<K0<K, 0<η0<\eta0<η; reason: the paper states these once, on p.7 and in (3.3); no instance changes
  • encoding: the learner "has access to the recommendation qtq_tqt​" and draws Jt∼qtJ_t\sim q_tJt​∼qt​ (Algorithm 1) → the policy receives the drawn JtJ_tJt​ and not qtq_tqt​; reason: the algorithm uses qtq_tqt​ only to draw JtJ_tJt​; the protocol still gives JtJ_tJt​ the conditional law qtq_tqt​
Preamble
import Mathlib
import Definitions.Def_CalibeatBandit_calibeatPolicy
import Definitions.Def_CalibeatBandit_IsCalibeating
import Definitions.Def_CalibeatBandit_rT
import Definitions.Def_CalibeatBandit_etaStar

set_option autoImplicit false

universe u

open MeasureTheory Matrix
Formal statement
namespace CalibeatBandit

/-- **Theorem 3.2 (Bandit calibeating).** Instantiate all internal learners of the bandit
feedback algorithm (Algorithm 1 with the modifications of §3.2) by exponential weights (3.3) with
learning rate `η`, starting from uniform weights. If `0 < μ ≤ 1/2` and `μ ≥ 4Kη`, then
`E[SR_T] ≤ r_T + √(2TK log K)` and `E[Rec_T] ≤ r_T`, where
`r_T = μT + (2K log K + log 2)/η + 5ηKT/(1 − μ)`. In other words, the algorithm is
`(α, β)`-calibeating with `α = r_T/T + √(2K log K/T)` and `β = r_T/T`. With suitable parameters,
`(ε, ε)`-calibeating is achievable in `Õ(K²ε⁻²)` rounds.

Hartline, Wang, Wu, *Calibeating Bandit Advice* (manuscript, sha256 a65ccb08…), Theorem 3.2, p.11; the parameters of the last sentence are those of the proof, p.36.

**Formalization Note.** Three conjuncts.
1. For every `K ≥ 1`, `T`, `η > 0`, `μ` with `0 < μ ≤ 1/2` and `4Kη ≤ μ`, every probability space
   and every run of the §2.1 protocol (`ProtocolRun`: adaptive, randomized environment whose
   `q_t`, `y_t` may be correlated through information the learner never sees, fixed before the
   learner's round-`t` draws) driven by `calibeatPolicy K η μ`, the two inequalities hold, with
   `E` the Bochner integral and `SR_T`, `Rec_T` the realized benchmarks.
2. The "in other words" restatement through Definition 2.2 (`IsCalibeating`).
3. The `Õ(K²ε⁻²)` clause, pinned as: there is an absolute constant `C > 0` such that for all
   `K ≥ 1`, `ε > 0` and `T ≥ C K² log K / ε²`, the algorithm with the proof's parameters
   `η* = min{1/(8K), √((2K log K + log 2)/(14KT))}`, `μ* = 4Kη*` (p.36) is `(ε, ε)`-calibeating
   over `T` rounds.
`log` is `Real.log` (p.7: `e` is the base of the natural logarithm); actions are `Fin K`; rounds
are `0, …, T − 1`. Probability spaces range over `Type u` for an arbitrary universe `u`. -/
theorem theorem_3_2 :
    (∀ (K T : ℕ) (η μ : ℝ), 0 < K → 0 < η → 0 < μ → μ ≤ 1 / 2 → 4 * K * η ≤ μ →
      ∀ {Ω : Type u} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
        (run : ProtocolRun K T P (calibeatPolicy K η μ)),
        ∫ ω, swapRegret T (fun t => run.y t ω) (fun t => run.I t ω) ∂P
            ≤ rT K T η μ + Real.sqrt (2 * T * K * Real.log K) ∧
        ∫ ω, rewardLoss T (fun t => run.y t ω) (fun t => run.J t ω) (fun t => run.I t ω) ∂P
            ≤ rT K T η μ) ∧
    (∀ (K T : ℕ) (η μ : ℝ), 0 < K → 0 < η → 0 < μ → μ ≤ 1 / 2 → 4 * K * η ≤ μ →
      IsCalibeating.{u} K T (rT K T η μ / T + Real.sqrt (2 * K * Real.log K / T))
        (rT K T η μ / T) (calibeatPolicy K η μ)) ∧
    (∃ C : ℝ, 0 < C ∧ ∀ (K T : ℕ) (ε : ℝ), 0 < K → 0 < ε →
      C * K ^ 2 * Real.log K / ε ^ 2 ≤ T →
      IsCalibeating.{u} K T ε ε (calibeatPolicy K (etaStar K T) (muStar K T))) := by sorry

end CalibeatBandit
Source
Hartline, Wang, Wu, Calibeating Bandit Advice (manuscript, STOC 2027 submission, sha256 a65ccb0880e6e4698eee1717d9a7121019b84a5ebcb4dfaa2e1614dbd3de0b44), Theorem 3.2, p.11 (PDF 11); the parameters of its last sentence from the proof, §C.2, p.36 (PDF 36)
Human review
  • Endorsed by Shuze Chen · Nov 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 6, 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