All-history FTRL bound of GIA-FTRL against a comparison law (G.218)–(G.241)
ProvedIAFTRL.lemma_G_2_ftrlbandit-algorithmslinear-banditsonline-learning
Setting. As in Proposition G.2: a GIA-FTRL run of rounds on a compact generator of , against an adaptive environment. Write and let be the reference measure (3.3).
Claim. Let . Let be a probability measure supported on with and integrable log-density. Let satisfy for every . Then
Proof outline ((G.218)–(G.241)).
- Telescope the potential . It is nondecreasing in and satisfies .
- Bound the per-round term pathwise: .
- Condition on the latent action: .
- Use marginal domination: .
- Use unbiased difference estimates.
Preamble
import Mathlib import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **All-history FTRL bound against a comparison law (Proposition G.2, (G.218)–(G.241)).**
Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), proof of
Proposition G.2, pp.145–147: for a deterministic comparison law `q`,
`Reg_T(u) ≤ β_T D_KL(q, µ) + Σ_t E[D_t] + Σ_t 8d/β_t + Σ_t E[⟨q − δ_u, xᵀθ_t⟩]` (G.241), with
`E_{t−1}[D_t] ≤ C_t(p_t) ≤ 2d/β_t` (G.232).
For every execution of GIA-FTRL for `T ≥ 1` rounds, every comparator `u ∈ 𝒦`, every probability
measure `q` on `𝒦` with `q ≪ µ` and integrable log-density, and every `ε` with
`|(∫ x q(dx) − u)ᵀϑ| ≤ ε` whenever `‖ϑ‖_𝒜 ≤ 1`:
`Reg_T(u) ≤ β_T D_KL(q, µ) + Σ_{t=1}^T 10d/β_t + Tε`. -/
theorem lemma_G_2_ftrl {d : ℕ} (hd : 1 ≤ d) (𝒜 ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ)
(h𝒜 : IsCompact 𝒜) (hℬ : IsCompact ℬ) (hgen : IsGenerator 𝒜 ℬ)
(hball : ∀ a ∈ 𝒜, a ⬝ᵥ a ≤ 1) (hspan : Submodule.span ℝ 𝒜 = ⊤) (hk : 1 ≤ kdim ℬ)
(he : Function.Surjective e) {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (T : ℕ) (R : GRun d Ω) (hT : 1 ≤ T) (hR : IsGIAFTRLRun P 𝒜 ℬ e T R)
(u : Fin d → ℝ) (hu : u ∈ Kset ℬ) (q : Measure (Fin d → ℝ)) [IsProbabilityMeasure q]
(hqK : q (Kset ℬ)ᶜ = 0) (hqμ : q ≪ refMu ℬ e)
(hKL : Integrable (fun x => Real.log (q.rnDeriv (refMu ℬ e) x).toReal) q) (ε : ℝ)
(hε : ∀ ϑ : Fin d → ℝ, setNorm 𝒜 ϑ ≤ 1 → |((fun i => ∫ x, x i ∂q) - u) ⬝ᵥ ϑ| ≤ ε) :
gRegretVs P T R u ≤ gbeta d T * ∫ x, Real.log (q.rnDeriv (refMu ℬ e) x).toReal ∂q +
∑ t ∈ Finset.range T, 10 * (d : ℝ) / gbeta d (t + 1) + T * ε := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry (STOC submission version; arXiv:2611.01299), Appendix G.6.3, proof of Proposition G.2, pp. 145–147