Lemma J.2 — full-history entropy identities for FTRL
ProvedIAFTRL.lemma_J_2bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-v1
Finite part. Let be positive, let be arbitrary, , , and let
For every coordinate and every ,
Relative part. Let be a probability measure on a measurable space with measurable singletons, an atom with , , bounded measurable functions, , and the Gibbs measure with density with respect to , . With and , both
and
hold. The coarse bound gives the adversarial regret; the local bound charges only the entropy that remains as the regularization grows.
Formalization Note Rounds are 1-based, as in the paper. Positivity and monotonicity of are required for .
Differences from the source:
- encoding: nondecreasing → and for ; reason: the exponential weights are only defined for
- encoding: horizon → ; reason: is undefined at
- reading: , not stated → ; reason: the proof uses , and Algorithm 1 starts from
- reading: (J.5) written as a chain "" → two separate bounds on the left-hand side; reason: read as a chain it would assert , false for strictly increasing and ; the finite analogues (J.3)/(J.4) are separate bounds
- encoding: losses in the relative part, unspecified → bounded measurable ; measurable singletons; reason: makes every integral, and finite and meaningful; the paper applies it to bounded losses on compact sets
- encoding: → with the explicit Gibbs density; reason: the definition of relative entropy for
Preamble
import Mathlib
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **Lemma J.2 (Full-history entropy identities).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Lemma J.2, p.205: "For
nondecreasing `β_t`, let `q_{t,a} ∝ exp(−S_{t−1,a}/β_t)`, `S_t = S_{t−1} + g_t`, and
`D_t = ⟨q_t, g_t⟩ + β_t log Σ_a q_{t,a} e^{−g_{t,a}/β_t}`. For every fixed coordinate `u`,
`Σ_{t≤T} ⟨q_t − e_u, g_t⟩ ≤ β_T log K + Σ_t D_t`, (J.3)
`Σ_{t≤T} ⟨q_t − e_u, g_t⟩ ≤ β_1 log K + Σ_{t=2}^T (β_t − β_{t−1})H(q_t) + Σ_t D_t`, (J.4)
where `H(q) = −Σ_a q_a log q_a`. For a probability reference `µ`, relative-entropy FTRL
`q_t(da) ∝ e^{−S_{t−1}(a)/β_t}µ(da)`, and an atom `u` of mass `π_u > 0`, the corresponding bounds are
`Σ_t (∫ g_t dq_t − g_t(u)) ≤ β_T log(1/π_u) + Σ_t D_t`,
`≤ β_1h_u + Σ_{t=2}^T (β_t − β_{t−1})[h_u − D_KL(q_t, µ)] + Σ_t D_t`, (J.5)
with `h_u = log(1/π_u)` and the integral definition of `D_t`."
**Finite part.** For positive nondecreasing `β_1 ≤ β_2 ≤ …`, arbitrary losses `g_t ∈ ℝ^K`,
`S_0 = 0`, `S_t = S_{t−1} + g_t`, the exponential weights `q_{t,a} = e^{−S_{t−1,a}/β_t} / Σ_b e^{−S_{t−1,b}/β_t}`
satisfy (J.3) and (J.4) for every coordinate `u` and every horizon `T ≥ 1`.
**Relative part.** For a probability measure `µ` on a measurable space with measurable singletons,
an atom `u` with `π_u = µ({u}) > 0`, bounded measurable losses `g_t`, `S_t = Σ_{s≤t} g_s`, the Gibbs
measures `q_t = (e^{−S_{t−1}/β_t} / Z_t) · µ` with `Z_t = ∫ e^{−S_{t−1}/β_t} dµ`,
`D_t = ∫ g_t dq_t + β_t log ∫ e^{−g_t/β_t} dq_t` and `D_KL(q_t, µ) = ∫ log(dq_t/dµ) dq_t`: both bounds of
(J.5) hold, each bounding the left-hand side `Σ_{t≤T} (∫ g_t dq_t − g_t(u))`.
**Formalization Note.** Rounds are 1-based as in the paper (`β 1 = β_1`, sums over `t ∈ [1, T]`);
`β t > 0` and monotonicity are required for `t ≥ 1` (the exponential weights need `β_t > 0`). In
(J.5) the second "≤" bounds the left side: read as a chain it would assert
`Σ_t (β_t − β_{t−1})D_KL(q_t, µ) ≤ 0`, false whenever `β` increases strictly and some `q_t ≠ µ`.
Boundedness and measurability of `g_t` make every integral, `D_t` and `D_KL` finite. `D_KL` is written
as the explicit integral of the log-density. -/
theorem lemma_J_2 :
(∀ {K : ℕ} (β : ℕ → ℝ) (g : ℕ → Fin K → ℝ) (u : Fin K) (T : ℕ),
(∀ t, 1 ≤ t → 0 < β t) → (∀ t, 1 ≤ t → β t ≤ β (t + 1)) → 1 ≤ T →
let S : ℕ → Fin K → ℝ := fun t a => ∑ s ∈ Finset.Icc 1 t, g s a
let q : ℕ → Fin K → ℝ := fun t a =>
Real.exp (-(S (t - 1) a) / β t) / ∑ b, Real.exp (-(S (t - 1) b) / β t)
let D : ℕ → ℝ := fun t =>
∑ a, q t a * g t a + β t * Real.log (∑ a, q t a * Real.exp (-(g t a) / β t))
let H : (Fin K → ℝ) → ℝ := fun p => -∑ a, p a * Real.log (p a)
(∑ t ∈ Finset.Icc 1 T, (∑ a, q t a * g t a - g t u) ≤
β T * Real.log K + ∑ t ∈ Finset.Icc 1 T, D t) ∧
(∑ t ∈ Finset.Icc 1 T, (∑ a, q t a * g t a - g t u) ≤
β 1 * Real.log K + ∑ t ∈ Finset.Icc 2 T, (β t - β (t - 1)) * H (q t) +
∑ t ∈ Finset.Icc 1 T, D t)) ∧
(∀ {X : Type*} [MeasurableSpace X] [MeasurableSingletonClass X] (μ : Measure X)
[IsProbabilityMeasure μ] (β : ℕ → ℝ) (g : ℕ → X → ℝ) (u : X) (T : ℕ),
(∀ t, 1 ≤ t → 0 < β t) → (∀ t, 1 ≤ t → β t ≤ β (t + 1)) → 1 ≤ T → 0 < μ {u} →
(∀ t, Measurable (g t)) → (∀ t, ∃ M : ℝ, ∀ x, |g t x| ≤ M) →
let S : ℕ → X → ℝ := fun t x => ∑ s ∈ Finset.Icc 1 t, g s x
let Z : ℕ → ℝ := fun t => ∫ x, Real.exp (-(S (t - 1) x) / β t) ∂μ
let dens : ℕ → X → ℝ := fun t x => Real.exp (-(S (t - 1) x) / β t) / Z t
let q : ℕ → Measure X := fun t => μ.withDensity fun x => ENNReal.ofReal (dens t x)
let D : ℕ → ℝ := fun t =>
∫ x, g t x ∂(q t) + β t * Real.log (∫ x, Real.exp (-(g t x) / β t) ∂(q t))
let KL : ℕ → ℝ := fun t => ∫ x, Real.log (dens t x) ∂(q t)
let h : ℝ := Real.log (1 / (μ {u}).toReal)
(∑ t ∈ Finset.Icc 1 T, (∫ x, g t x ∂(q t) - g t u) ≤
β T * h + ∑ t ∈ Finset.Icc 1 T, D t) ∧
(∑ t ∈ Finset.Icc 1 T, (∫ x, g t x ∂(q t) - g t u) ≤
β 1 * h + ∑ t ∈ Finset.Icc 2 T, (β t - β (t - 1)) * (h - KL t) +
∑ t ∈ Finset.Icc 1 T, D t)) := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix J.1, Lemma J.2, p.205, Eqs. (J.3)–(J.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.