Eq. (C.5) — second-order bound
ProvedCalibeatBandit.eq_C_5bandit-feedbackcalibeatingonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1swap-regret
Let , and with for every . Then
The first inequality uses for , the second . Combined with (C.4) it reduces the regret on corrected rewards to a second moment.
Differences from the source:
- generalization: the algorithm's , , for which the paper derives from and → any and with ; reason: the algorithm's quantities satisfy the hypothesis, as the page shows
- 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: actions →
Fin K; reason: a relabelling; same instances
Preamble
import Mathlib import Definitions.Def_CalibeatBandit_IsProbVec set_option autoImplicit false open MeasureTheory Matrix
Formal statement
namespace CalibeatBandit
/-- **(C.5): the second-order bound on the log-moment** (§C.2, proof of Lemma C.3, p.34).
For `x ∈ Δ(𝒜)`, `η > 0` and a vector `v` with `0 ≤ ηv(j) ≤ 1` for every `j`,
`(1/η) log(∑_j x(j) exp(ηv(j))) − ⟨x, v⟩
≤ (1/η) log(1 + η⟨x, v⟩ + (e − 2)η² ∑_j x(j)v(j)²) − ⟨x, v⟩ ≤ (e − 2)η ∑_j x(j)v(j)²`.
Hartline, Wang, Wu, *Calibeating Bandit Advice* (manuscript, sha256 a65ccb08…), §C.2, display (C.5), p.34.
**Formalization Note.** The paper derives `0 ≤ ηv_t(j) ≤ 1` for the algorithm's `v_t` from
`p_t(j) ≥ 4η` and `η ≤ 1/8`; here that range is the hypothesis, for arbitrary `x`, `v`. `log` is
`Real.log`, `e` is `Real.exp 1`, `⟨x, v⟩` is `x ⬝ᵥ v`. -/
theorem eq_C_5 {K : ℕ} (η : ℝ) (hη : 0 < η) (x v : Fin K → ℝ) (hx : IsProbVec x)
(hv : ∀ j, 0 ≤ η * v j ∧ η * v j ≤ 1) :
1 / η * Real.log (∑ j, x j * Real.exp (η * v j)) - x ⬝ᵥ v
≤ 1 / η * Real.log (1 + η * (x ⬝ᵥ v) + (Real.exp 1 - 2) * η ^ 2 * ∑ j, x j * v j ^ 2)
- x ⬝ᵥ v ∧
1 / η * Real.log (1 + η * (x ⬝ᵥ v) + (Real.exp 1 - 2) * η ^ 2 * ∑ j, x j * v j ^ 2)
- x ⬝ᵥ v
≤ (Real.exp 1 - 2) * η * ∑ j, x j * v j ^ 2 := by sorry
end CalibeatBandit
Source
Hartline, Wang, Wu, Calibeating Bandit Advice (manuscript, STOC 2027 submission, sha256 a65ccb0880e6e4698eee1717d9a7121019b84a5ebcb4dfaa2e1614dbd3de0b44), §C.2, display (C.5), p.34 (PDF 34)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.