Proposition G.2 — all-history adversarial guarantee of GIA-FTRL
ProvedIAFTRL.proposition_G_2bandit-algorithmslinear-banditsonline-learning
Setting. Let () be a compact action set with .
- GIA-FTRL (Algorithm 2, definition
IAFTRL_GIAFTRL) runs on a compact generator , meaning , with for , and with a surjective enumeration of . - The run lasts rounds against an adaptive environment: is predictable, , , and .
Claim. For every comparator ,
No sharpness is assumed.
Proof outline (Appendix G.6.3).
- Use the potential (Lemma J.2). It telescopes as in (G.218)–(G.225), with a deterministic comparison law satisfying and (Lemma G.11).
- Bound the per-round term by , using the proxy constraint (3.7) and Lemma J.4.
- Bound the exploration term by , using marginal domination.
- Use unbiasedness of the reconstruction.
- Sum the schedule with .
Preamble
import Mathlib import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **Proposition G.2 (All-history adversarial guarantee).** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits* (STOC submission version), Proposition G.2, p.145: "GIA-FTRL obeys
`Reg_T ≤ U_SH(T) ≤ 320(d+1)√T log(eT)` for every predictable bounded-mean environment."
For every execution of GIA-FTRL on a compact generator `ℬ` of the compact action set
`𝒜 ⊆ 𝔹^d` (`span 𝒜 = ℝ^d`, `k = dim aff 𝒦 ≥ 1`, `e` an enumeration of `ℚ^d`) for `T ≥ 1` rounds
against an adaptive environment, and every comparator `u ∈ 𝒦 = Conv ℬ`,
`Reg_T(u) ≤ 320(d+1)√T log(eT)`. No sharpness is assumed. -/
theorem proposition_G_2 {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 ℬ) :
gRegretVs P T R u ≤ 320 * ((d : ℝ) + 1) * Real.sqrt T * Real.log (Real.exp 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, Proposition G.2, pp. 145–147