Theorem 3.2 — bandit calibeating: , , and rounds
ProvedCalibeatBandit.theorem_3_2bandit-feedbackcalibeatingonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1swap-regret
Instantiate all internal learners of the bandit feedback calibeating algorithm (Algorithm 1 with the exploration, reward estimation and feedback modifications of §3.2) by exponential weights (3.3) with learning rate , starting from uniform weights.
- If , , and , then in every run of the interaction protocol (adaptive and randomized recommendations and rewards, possibly correlated through information unavailable to the learner, fixed before the learner's draws of each round)
- In other words, under the same conditions the algorithm is -calibeating over rounds with and .
- With the parameters and of the proof, there is an absolute constant such that for every , and the algorithm is -calibeating over rounds; that is, -calibeating is achieved in rounds.
The learner sees only the reward of the action it plays, yet competes simultaneously with every post-processing of its own actions (swap regret) and with every post-processing of the recommended actions (reward loss), at rate .
Formalization Note and are the realized benchmarks of the run; the probability spaces range over an arbitrary universe.
Differences from the source:
- 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 - reading: "With suitable parameters, -calibeating is achievable in rounds" → there is such that for all , and every the algorithm with the proof's (p.36) is -calibeating over rounds; reason: the parameters are the ones the proof chooses; the polylogarithmic factor of is the of , and the bound holds for every horizon beyond the threshold
- encoding: "for every recommendation and reward sequence satisfying the interaction protocol" → every
ProtocolRunon every probability space in a universeu: σ-algebras of everything fixed before the learner's round- draws, -measurable, , ; the constant is chosen afteru; reason: this is §2.1's protocol with Algorithm 1's draw of ; adaptive, randomized and correlated environments are all instances - encoding: , "the mixed strategy solving Equation (3.1)" → the explicit ; reason: , so (3.1) has exactly this solution, which lies in
- encoding: , → the same with Lean's ; reason: at both sides of Definition 2.2's inequalities are ; for the expressions are the paper's
- 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
- encoding: the learner "has access to the recommendation " and draws (Algorithm 1) → the policy receives the drawn and not ; reason: the algorithm uses only to draw ; the protocol still gives the conditional law
Preamble
import Mathlib import Definitions.Def_CalibeatBandit_calibeatPolicy import Definitions.Def_CalibeatBandit_IsCalibeating import Definitions.Def_CalibeatBandit_rT import Definitions.Def_CalibeatBandit_etaStar set_option autoImplicit false universe u open MeasureTheory Matrix
Formal statement
namespace CalibeatBandit
/-- **Theorem 3.2 (Bandit calibeating).** Instantiate all internal learners of the bandit
feedback algorithm (Algorithm 1 with the modifications of §3.2) by exponential weights (3.3) with
learning rate `η`, starting from uniform weights. If `0 < μ ≤ 1/2` and `μ ≥ 4Kη`, then
`E[SR_T] ≤ r_T + √(2TK log K)` and `E[Rec_T] ≤ r_T`, where
`r_T = μT + (2K log K + log 2)/η + 5ηKT/(1 − μ)`. In other words, the algorithm is
`(α, β)`-calibeating with `α = r_T/T + √(2K log K/T)` and `β = r_T/T`. With suitable parameters,
`(ε, ε)`-calibeating is achievable in `Õ(K²ε⁻²)` rounds.
Hartline, Wang, Wu, *Calibeating Bandit Advice* (manuscript, sha256 a65ccb08…), Theorem 3.2, p.11; the parameters of the last sentence are those of the proof, p.36.
**Formalization Note.** Three conjuncts.
1. For every `K ≥ 1`, `T`, `η > 0`, `μ` with `0 < μ ≤ 1/2` and `4Kη ≤ μ`, every probability space
and every run of the §2.1 protocol (`ProtocolRun`: adaptive, randomized environment whose
`q_t`, `y_t` may be correlated through information the learner never sees, fixed before the
learner's round-`t` draws) driven by `calibeatPolicy K η μ`, the two inequalities hold, with
`E` the Bochner integral and `SR_T`, `Rec_T` the realized benchmarks.
2. The "in other words" restatement through Definition 2.2 (`IsCalibeating`).
3. The `Õ(K²ε⁻²)` clause, pinned as: there is an absolute constant `C > 0` such that for all
`K ≥ 1`, `ε > 0` and `T ≥ C K² log K / ε²`, the algorithm with the proof's parameters
`η* = min{1/(8K), √((2K log K + log 2)/(14KT))}`, `μ* = 4Kη*` (p.36) is `(ε, ε)`-calibeating
over `T` rounds.
`log` is `Real.log` (p.7: `e` is the base of the natural logarithm); actions are `Fin K`; rounds
are `0, …, T − 1`. Probability spaces range over `Type u` for an arbitrary universe `u`. -/
theorem theorem_3_2 :
(∀ (K T : ℕ) (η μ : ℝ), 0 < K → 0 < η → 0 < μ → μ ≤ 1 / 2 → 4 * K * η ≤ μ →
∀ {Ω : Type u} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(run : ProtocolRun K T P (calibeatPolicy K η μ)),
∫ ω, swapRegret T (fun t => run.y t ω) (fun t => run.I t ω) ∂P
≤ rT K T η μ + Real.sqrt (2 * T * K * Real.log K) ∧
∫ ω, rewardLoss T (fun t => run.y t ω) (fun t => run.J t ω) (fun t => run.I t ω) ∂P
≤ rT K T η μ) ∧
(∀ (K T : ℕ) (η μ : ℝ), 0 < K → 0 < η → 0 < μ → μ ≤ 1 / 2 → 4 * K * η ≤ μ →
IsCalibeating.{u} K T (rT K T η μ / T + Real.sqrt (2 * K * Real.log K / T))
(rT K T η μ / T) (calibeatPolicy K η μ)) ∧
(∃ C : ℝ, 0 < C ∧ ∀ (K T : ℕ) (ε : ℝ), 0 < K → 0 < ε →
C * K ^ 2 * Real.log K / ε ^ 2 ≤ T →
IsCalibeating.{u} K T ε ε (calibeatPolicy K (etaStar K T) (muStar K T))) := by sorry
end CalibeatBandit
Source
Hartline, Wang, Wu, Calibeating Bandit Advice (manuscript, STOC 2027 submission, sha256 a65ccb0880e6e4698eee1717d9a7121019b84a5ebcb4dfaa2e1614dbd3de0b44), Theorem 3.2, p.11 (PDF 11); the parameters of its last sentence from the proof, §C.2, p.36 (PDF 36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.