§C.1 (p.31) — sampling conversion
ProvedCalibeatBandit.sampling_conversion_C_1bandit-feedbackcalibeatingonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1swap-regret
Consider any learner and any run of the interaction protocol with actions, with the learner's mixed strategy in round . Then
Since has conditional law given the information before it is sampled, the differences have conditional mean zero and ; Hoeffding's lemma and a union over the maps give the term.
Formalization Note is run.played t.
Differences from the source:
- generalization: the learner of Algorithm 1 (and, by the proof of Theorem 3.2, the bandit algorithm) → every learner policy; reason: the argument uses only that has conditional law given and ; both algorithms are instances
- 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: in every run the integrands are bounded and almost everywhere measurable (the conditional law pins a.s.), 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 → the explicit hypothesis ; reason: the paper states this once, on p.7; no instance changes
Preamble
import Mathlib import Definitions.Def_CalibeatBandit_ProtocolRun import Definitions.Def_CalibeatBandit_pseudoSwapRegret import Definitions.Def_CalibeatBandit_swapRegret set_option autoImplicit false open MeasureTheory Matrix
Formal statement
namespace CalibeatBandit
/-- **Sampling conversion from pseudo swap regret to swap regret** (§C.1, proof of Lemma C.1,
p.31). In every run of the §2.1 protocol with `K ≥ 1` actions, with `p_t` the learner's mixed
strategy, `E[SR_T] ≤ E[R^{SR,p}_T] + √(2TK log K)`, where
`R^{SR,p}_T = max_f ∑_t (∑_i p_t(i) y_t(f(i)) − ⟨p_t, y_t⟩)`.
Hartline, Wang, Wu, *Calibeating Bandit Advice* (manuscript, sha256 a65ccb08…), §C.1, proof of Lemma C.1, p.31; reused in the proof of Theorem 3.2, p.36.
**Formalization Note.** Stated for an arbitrary learner `policy`; `p_t` is `run.played t`, and
`I_t` has conditional law `p_t` given `𝒪_{t−1} = info t ⊔ σ(J_t)` by the protocol. Rounds are
`0, …, T − 1`; `log` is `Real.log`; `E` is the Bochner integral. -/
theorem sampling_conversion_C_1 {K T : ℕ} {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(policy : Policy K) (run : ProtocolRun K T P policy) (hK : 0 < K) :
∫ ω, swapRegret T (fun t => run.y t ω) (fun t => run.I t ω) ∂P
≤ ∫ ω, pseudoSwapRegret T (fun t => run.played t ω) (fun t => run.y t ω) ∂P + Real.sqrt (2 * T * K * Real.log K) := by sorry
end CalibeatBandit
Source
Hartline, Wang, Wu, Calibeating Bandit Advice (manuscript, STOC 2027 submission, sha256 a65ccb0880e6e4698eee1717d9a7121019b84a5ebcb4dfaa2e1614dbd3de0b44), §C.1, proof of Lemma C.1, p.31 (PDF 31); reused in the proof of Theorem 3.2, p.36
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.