Lemma J.4 — centered exponential bound for the proxy function
ProvedIAFTRL.lemma_J_4bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let . Then is
- even: ;
- convex on ;
- nonnegative;
- increasing in : implies ;
and for every real ,
Moreover, for every probability measure and every bounded measurable function ,
These inequalities convert the program's proxy function into a bound on the FTRL mixability gap (Lemmas D.4 and D.10).
Differences from the source:
- encoding: "increasing in " → ; reason: the standard meaning; same content
Preamble
import Mathlib import Definitions.Def_IAFTRL_chi
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **Lemma J.4 (Centered exponential bound for the proxy function).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Lemma J.4, p.206:
"Let `χ(x) = e^x + e^{−x} − 2`. It is even, convex, nonnegative, and increasing in `|x|`. For every
real `x`, `e^x − x − 1 ≤ χ(x)`, `χ(x) ≤ x²e^{|x|}`, `χ(x) ≤ 3/2 x² (|x| ≤ 1)`. For every probability
measure `q` and bounded measurable `f`, `∫ χ(f − ∫ f dq) dq ≤ ∫ χ(2f) dq`. (J.6)"
The function `χ(x) = e^x + e^{−x} − 2` is
1. even, 2. convex on `ℝ`, 3. nonnegative, 4. increasing in `|x|` (`|x| ≤ |y| ⇒ χ(x) ≤ χ(y)`),
and satisfies
5. `e^x − x − 1 ≤ χ(x)`, 6. `χ(x) ≤ x² e^{|x|}` for every real `x`,
7. `χ(x) ≤ (3/2)x²` for `|x| ≤ 1`,
8. (J.6) `∫ χ(f − ∫ f dq) dq ≤ ∫ χ(2f) dq` for every probability measure `q` and every bounded
measurable real function `f`. -/
theorem lemma_J_4 :
(∀ x : ℝ, chi (-x) = chi x) ∧ ConvexOn ℝ Set.univ chi ∧ (∀ x : ℝ, 0 ≤ chi x) ∧
(∀ x y : ℝ, |x| ≤ |y| → chi x ≤ chi y) ∧
(∀ x : ℝ, Real.exp x - x - 1 ≤ chi x) ∧ (∀ x : ℝ, chi x ≤ x ^ 2 * Real.exp |x|) ∧
(∀ x : ℝ, |x| ≤ 1 → chi x ≤ 3 / 2 * x ^ 2) ∧
(∀ {X : Type*} [MeasurableSpace X] (q : Measure X) [IsProbabilityMeasure q] (f : X → ℝ),
Measurable f → (∃ M : ℝ, ∀ x, |f x| ≤ M) →
∫ x, chi (f x - ∫ y, f y ∂q) ∂q ≤ ∫ x, chi (2 * f x) ∂q) := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix J.1, Lemma J.4, p.206, Eq. (J.6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.