Eq. (C.6) —
ProvedCalibeatBandit.eq_C_6bandit-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. Let be the information immediately before is sampled. Then for every round ,
the equality holding almost surely and the inequalities for every outcome.
This bounds the variance term of (C.5) by propensity scoring: and .
Formalization Note is run.preDraw t .
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: , "all information immediately before sampling " →
run.preDraw t; reason: this is the σ-algebra the protocol conditions the draw of on - 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
/-- **(C.6): the conditional second moment of the corrected estimates** (§C.2, proof of
Lemma C.3, p.34). In every run of the bandit calibeating algorithm under the hypotheses of
Theorem 3.2, for every round `t`, with `𝒪_{t−1}` the information immediately before `I_t` is sampled,
`E[∑_j x_t(j) v_t(j)² | 𝒪_{t−1}] = ∑_j (x_t(j)/p_t(j)) (y_t(j)² + 2(e − 2)ηy_t(j) + (e − 2)²η²/p_t(j))
≤ 2 ∑_j x_t(j)/p_t(j) ≤ 2K/(1 − μ)`.
Hartline, Wang, Wu, *Calibeating Bandit Advice* (manuscript, sha256 a65ccb08…), §C.2, display (C.6), p.34.
**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'`. `𝒪_{t−1}` is `run.preDraw t = info t ⊔ σ(J_t)` (p.31: "all
information immediately before sampling I_t"); the equality holds `P`-almost surely, the two
inequalities for every outcome. -/
theorem eq_C_6 {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 : ℕ) (ht : t < T) :
condExp (run.preDraw t) P (fun ω => ∑ j, run.algX η μ t ω j * run.algV η μ t ω j ^ 2)
=ᵐ[P] (fun ω => ∑ j, run.algX η μ t ω j / run.algP η μ t ω j *
(run.y t ω j ^ 2 + 2 * (Real.exp 1 - 2) * η * run.y t ω j
+ (Real.exp 1 - 2) ^ 2 * η ^ 2 / run.algP η μ t ω j)) ∧
(∀ ω, ∑ j, run.algX η μ t ω j / run.algP η μ t ω j *
(run.y t ω j ^ 2 + 2 * (Real.exp 1 - 2) * η * run.y t ω j
+ (Real.exp 1 - 2) ^ 2 * η ^ 2 / run.algP η μ t ω j) ≤ 2 * ∑ j, run.algX η μ t ω j / run.algP η μ t ω j) ∧
(∀ ω, 2 * ∑ j, run.algX η μ t ω j / run.algP η μ t ω j ≤ 2 * K / (1 - μ)) := by sorry
end CalibeatBandit
Source
Hartline, Wang, Wu, Calibeating Bandit Advice (manuscript, STOC 2027 submission, sha256 a65ccb0880e6e4698eee1717d9a7121019b84a5ebcb4dfaa2e1614dbd3de0b44), §C.2, display (C.6), p.34 (PDF 34)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.