Eq. (C.1) — the mixing feedback telescopes (with the analogue)
ProvedCalibeatBandit.eq_C_1bandit-feedbackcalibeatingonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1swap-regret
For the bandit calibeating algorithm with learning rate (any exploration parameter ) and every history of recommended actions, played actions and observed rewards,
and
Because each internal learner is exponential weights started from uniform weights, the per-round feedback is a difference of log-partition functions and the sum telescopes. The identity drives the bound on the regret on corrected rewards (Lemma C.3).
Differences from the source:
- generalization: the identity for of the algorithm → the identity for every history and every , together with the analogous identity for ; reason: the telescoping uses only the exponential-weights update; the Rec identity is the one the paper's "similar" analysis of the second term of Lemma C.3 uses
- 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: rounds , actions → rounds (
Finset.range T), actionsFin K; reason: a relabelling; same instances
Preamble
import Mathlib import Definitions.Def_CalibeatBandit_algState set_option autoImplicit false open MeasureTheory Matrix
Formal statement
namespace CalibeatBandit
/-- **(C.1): the mixing learner's `SR` feedback telescopes** (§C.2, proof of Lemma C.3,
p.32). For the bandit calibeating algorithm with learning rate `η > 0` and every history,
`∑_{t=1}^T H^SR_t = (1/η) ∑_i log((1/K) ∑_j exp(η ∑_{t=1}^T x_t(i) v_t(j)))`,
and likewise
`∑_{t=1}^T H^Rec_t = (1/η) ∑_i log((1/K) ∑_j exp(η ∑_{t=1}^T 1{J_t = i} v_t(j)))`.
Hartline, Wang, Wu, *Calibeating Bandit Advice* (manuscript, sha256 a65ccb08…), §C.2, display (C.1), p.32; the `Rec` identity is the "similar" analysis of the
second term of Lemma C.3 (p.32).
**Formalization Note.** `algHSR`, `algHRec`, `algX`, `algV` are the algorithm's `H^SR_t`,
`H^Rec_t`, `x_t`, `v_t` computed from the learner's observations `J`, `I` and observed rewards
`r` (any sequences); rounds are `0, …, T − 1`; `log` is `Real.log`. The identity is exact for every
history and every exploration parameter `μ`. The second conjunct is the `Rec` analogue that the
paper uses without displaying it. -/
theorem eq_C_1 {K : ℕ} (η μ : ℝ) (hη : 0 < η) (J I : ℕ → Fin K) (r : ℕ → ℝ) (T : ℕ) :
∑ t ∈ Finset.range T, algHSR η μ J I r t
= 1 / η * ∑ i, Real.log (1 / K * ∑ j, Real.exp
(η * ∑ t ∈ Finset.range T, algX η μ J I r t i * algV η μ J I r t j)) ∧
∑ t ∈ Finset.range T, algHRec η μ J I r t
= 1 / η * ∑ i, Real.log (1 / K * ∑ j, Real.exp
(η * ∑ t ∈ Finset.range T, (if J t = i then algV η μ J I r t j else 0))) := by sorry
end CalibeatBandit
Source
Hartline, Wang, Wu, Calibeating Bandit Advice (manuscript, STOC 2027 submission, sha256 a65ccb0880e6e4698eee1717d9a7121019b84a5ebcb4dfaa2e1614dbd3de0b44), §C.2, display (C.1), p.32 (PDF 32); the Rec identity is the analysis of the second term of Lemma C.3 ("similar", p.32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.