Lemma C.4 — estimation loss is at most
ProvedCalibeatBandit.lemma_C_4bandit-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. Both
are bounded by , where ranges over all maps .
The optimistic correction in makes a supermartingale for each fixed , and the rules give the .
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 set_option autoImplicit false open MeasureTheory Matrix
Formal statement
namespace CalibeatBandit
/-- **Lemma C.4 (estimation loss).** Under the hypotheses of Theorem 3.2, in every run of the
bandit calibeating algorithm, both
`E[max_f ∑_{t=1}^T ∑_i x_t(i)(y_t(f(i)) − v_t(f(i)))]` and `E[max_f ∑_{t=1}^T (y_t(f(J_t)) − v_t(f(J_t)))]`
are bounded by `K log K/η`.
Hartline, Wang, Wu, *Calibeating Bandit Advice* (manuscript, sha256 a65ccb08…), Lemma C.4, p.35.
**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_4 {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 η μ)) :
∫ ω, Finset.univ.sup' ⟨id, Finset.mem_univ _⟩ (fun f : Fin K → Fin K =>
∑ t ∈ Finset.range T, ∑ i, run.algX η μ t ω i * (run.y t ω (f i) - run.algV η μ t ω (f i))) ∂P
≤ K * Real.log K / η ∧
∫ ω, Finset.univ.sup' ⟨id, Finset.mem_univ _⟩ (fun f : Fin K → Fin K =>
∑ t ∈ Finset.range T, (run.y t ω (f (run.J t ω)) - run.algV η μ t ω (f (run.J t ω)))) ∂P
≤ K * Real.log K / η := by sorry
end CalibeatBandit
Source
Hartline, Wang, Wu, Calibeating Bandit Advice (manuscript, STOC 2027 submission, sha256 a65ccb0880e6e4698eee1717d9a7121019b84a5ebcb4dfaa2e1614dbd3de0b44), Lemma C.4, p.35 (PDF 35)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.