Proof of Theorem 3.2 (p.36) — for
ProvedCalibeatBandit.pseudo_regret_boundbandit-feedbackcalibeatingonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1swap-regret
Assume , , and , and consider any run of the interaction protocol driven by the bandit calibeating algorithm, with the mixed strategy it plays. Then
It combines the decomposition of §C.2 with Lemmas C.3–C.5 and .
Differences from the source:
- encoding: the algorithm's quantities in an interaction satisfying the §2.1 protocol →
run.algX,run.algP,run.algValong the realized history of aProtocolRundriven bycalibeatPolicy K η μ; reason: the run is the protocol of §2.1 (adaptive, randomized environment, and drawn by the learner); the policy reads only , and , - reading: → the natural logarithm
Real.log; reason: p.7 fixes as the base of the natural logarithm, and the proof's counts the post-processing rules - encoding: → the Bochner integral against ; reason: the integrands are bounded measurable functions of the run, so the integrals are the expectations
- encoding: rounds , actions → rounds (
Finset.range T), actionsFin K; reason: a relabelling; same instances - encoding: the action set of a positive integer and the learning rate of (3.3) → explicit hypotheses , ; reason: the paper states these once, on p.7 and in (3.3); no instance changes
Preamble
import Mathlib import Definitions.Def_CalibeatBandit_calibeatPolicy import Definitions.Def_CalibeatBandit_pseudoSwapRegret import Definitions.Def_CalibeatBandit_pseudoRewardLoss import Definitions.Def_CalibeatBandit_rT set_option autoImplicit false open MeasureTheory Matrix
Formal statement
namespace CalibeatBandit
/-- **The pseudo regrets are at most `r_T`** (§C.2, proof of Theorem 3.2, p.36). Under the
hypotheses of Theorem 3.2, in every run of the bandit calibeating algorithm, for both
`a ∈ {SR, Rec}`, `E[R^{a,p}_T] ≤ μT + (2K log K + log 2)/η + 5ηKT/(1 − μ) = r_T`, where
`R^{SR,p}_T = max_f ∑_t (∑_i p_t(i) y_t(f(i)) − ⟨p_t, y_t⟩)` and
`R^{Rec,p}_T = max_f ∑_t (y_t(f(J_t)) − ⟨p_t, y_t⟩)` (§C.1, p.30).
Hartline, Wang, Wu, *Calibeating Bandit Advice* (manuscript, sha256 a65ccb08…), §C.2, proof of Theorem 3.2, p.36.
**Formalization Note.** The hypotheses are those of Theorem 3.2: `K ≥ 1`, learning rate `η > 0`, `0 < μ ≤ 1/2`,
`μ ≥ 4Kη`; `run` is any run of the §2.1 protocol driven by the bandit calibeating algorithm.
`x_t`, `p_t`, `v_t` are `run.algX`, `run.algP`, `run.algV` (the algorithm's quantities along the
realized history); `E` is the Bochner integral against `P`. Rounds are `0, …, T − 1`; `log` is
`Real.log`, `e` is `Real.exp 1`; the maximum over all `f : Fin K → Fin K` is `Finset.sup'`. `p_t` is the mixed strategy the algorithm plays. -/
theorem pseudo_regret_bound {K T : ℕ} {η μ : ℝ} (hK : 0 < K) (hη : 0 < η) (hμ0 : 0 < μ) (hμ : μ ≤ 1 / 2)
(hKη : 4 * K * η ≤ μ) {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (run : ProtocolRun K T P (calibeatPolicy K η μ)) :
∫ ω, pseudoSwapRegret T (fun t => run.algP η μ t ω) (fun t => run.y t ω) ∂P ≤ rT K T η μ ∧
∫ ω, pseudoRewardLoss T (fun t => run.algP η μ t ω) (fun t => run.y t ω) (fun t => run.J t ω) ∂P ≤ rT K T η μ := by sorry
end CalibeatBandit
Source
Hartline, Wang, Wu, Calibeating Bandit Advice (manuscript, STOC 2027 submission, sha256 a65ccb0880e6e4698eee1717d9a7121019b84a5ebcb4dfaa2e1614dbd3de0b44), §C.2, proof of Theorem 3.2, p.36 (PDF 36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.