Lemma C.5 — correction loss is at most
ProvedCalibeatBandit.lemma_C_5bandit-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. Then
This is the price of the optimistic correction added to the importance-weighted estimates.
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 , - 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 set_option autoImplicit false open MeasureTheory Matrix
Formal statement
namespace CalibeatBandit
/-- **Lemma C.5 (correction loss).** Under the hypotheses of Theorem 3.2, in every run of the
bandit calibeating algorithm, `E[∑_{t=1}^T ⟨x_t, v_t − y_t⟩] ≤ (e − 2)ηKT/(1 − μ)`.
Hartline, Wang, Wu, *Calibeating Bandit Advice* (manuscript, sha256 a65ccb08…), Lemma C.5, 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'`. -/
theorem lemma_C_5 {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 η μ)) :
∫ ω, ∑ t ∈ Finset.range T, run.algX η μ t ω ⬝ᵥ (run.algV η μ t ω - run.y t ω) ∂P
≤ (Real.exp 1 - 2) * η * K * T / (1 - μ) := by sorry
end CalibeatBandit
Source
Hartline, Wang, Wu, Calibeating Bandit Advice (manuscript, STOC 2027 submission, sha256 a65ccb0880e6e4698eee1717d9a7121019b84a5ebcb4dfaa2e1614dbd3de0b44), Lemma C.5, p.36 (PDF 36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.