Theorem 3.1 — regret of GIA-FTRL in the sharp action case
ProvedIAFTRL.theorem_3_1bandit-algorithmslinear-banditsonline-learning
Setting. Let () be a compact action set with . GIA-FTRL (Algorithm 2) runs on a compact generator , meaning , with and a fixed enumeration of . The regret against a comparator is , and . In the corrupted stochastic regime, with and almost surely, and has a unique optimal action . All objects are those of the definition IAFTRL_GIAFTRL.
There is an absolute constant with the following two properties.
- Adversarial regime. Every run of GIA-FTRL satisfies, for all and all ,
- Corrupted stochastic regime. If the instance satisfies the sharpness condition (1.3), then there are finite constants and , independent of and , such that for all , and ,
where and is the centered information-acquisition complexity of Definition 1.2.
This is the paper's main guarantee for compact action sets. It gives a single FTRL-based algorithm with adversarial regret and, on sharp instances, stochastic regret plus an corruption term.
Formalization Note.
- is the absolute constant . Since at , (3.8) is stated for .
- The bound on is written as a bound for every comparator.
- The constants and may depend on , , , the enumeration and .
Preamble
import Mathlib import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **Theorem 3.1 (Regret in the sharp action case).** Zhao–Tan, *Best-of-Both-Worlds FTRL for
Linear Bandits* (STOC submission version), Theorem 3.1, p.25: "For linear bandits with compact
action sets, GIA-FTRL guarantees (3.8) `Reg_T = O(d√T log T)` in the adversarial regime.
Simultaneously, if the linear bandit instance satisfies the sharpness condition in (1.3),
GIA-FTRL guarantees `Reg_T = O(c*_ctr(𝒜, θ) d log T + M_{𝒜,θ} + J^cor_θ √C log₊(C))` (3.10) in
the corrupted stochastic regime, where `M_{𝒜,θ}` and `J^cor_θ` are finite parameter-dependent
constants independent of `T, C`."
GIA-FTRL is run on a compact generator `ℬ` of the compact action set `𝒜 ⊆ 𝔹^d`
(`span 𝒜 = ℝ^d`, `k = dim aff 𝒦 ≥ 1`) with an enumeration `e` of `ℚ^d`. `Reg_T = sup_{u∈𝒜}
Reg_T(u)` is written as a bound for every comparator `u ∈ 𝒜`. `O(·)` is an absolute constant
`c₀`; (3.8) is stated for `T ≥ 2` (at `T = 1`, `√T log T = 0`). `log₊ x = log max{e, x}`. -/
theorem theorem_3_1 : ∃ c₀ : ℝ, 0 < c₀ ∧
∀ {d : ℕ}, 1 ≤ d → ∀ (𝒜 ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ),
IsCompact 𝒜 → IsCompact ℬ → IsGenerator 𝒜 ℬ → (∀ a ∈ 𝒜, a ⬝ᵥ a ≤ 1) →
Submodule.span ℝ 𝒜 = ⊤ → 1 ≤ kdim ℬ → Function.Surjective e →
(∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (T : ℕ)
(R : GRun d Ω), 2 ≤ T → IsGIAFTRLRun P 𝒜 ℬ e T R →
∀ u ∈ 𝒜, gRegretVs P T R u ≤ c₀ * ((d : ℝ) * Real.sqrt T * Real.log T)) ∧
(∀ (θ astar : Fin d → ℝ), setNorm 𝒜 θ ≤ 1 → astar ∈ 𝒜 →
(∀ a ∈ 𝒜, a ≠ astar → astar ⬝ᵥ θ < a ⬝ᵥ θ) → IsSharp 𝒜 θ astar →
∃ M J : ℝ, ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(T : ℕ) (C : ℝ) (R : GRun d Ω), 1 ≤ T → 0 ≤ C →
IsGIAFTRLRun P 𝒜 ℬ e T R → IsCorruptedG P 𝒜 θ C T R →
∀ u ∈ 𝒜, gRegretVs P T R u ≤
c₀ * (cstarCtr 𝒜 θ astar * d * Real.log T) + M +
J * Real.sqrt C * Real.log (max (Real.exp 1) C)) := 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), Section 3.2, Theorem 3.1, p. 25 (proof in Appendix F, pp. 120–123)