Proposition 3.1 — GIA-FTRL regret for every fixed centered sampling allocation
ProvedIAFTRL.proposition_3_1Setting. 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 . This is (3.8).
- Corrupted stochastic regime. If the instance is sharp (1.3), then there is a finite constant with the following property. For every finite feasible centered sampling allocation on the generator (Definition 1.2 with in place of ), there is a finite constant such that, for all , and ,
The constant does not depend on , or . The constant depends on the instance and on , but not on or .
Theorem 3.1 follows from this proposition by choosing a fixed allocation with (Appendix F.1.1) and using (Lemma J.10).
Formalization Note. As in Theorem 3.1: (3.8) is stated for , is an absolute constant , and the regret bound is written for every comparator. In the formal statement, is chosen before .
import Mathlib import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL
namespace IAFTRL
open MeasureTheory
/-- **Proposition 3.1.** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission
version), Proposition 3.1, p.25: "For linear bandits with compact action sets, GIA-FTRL guarantees
`Reg_T = O(d√T log T)` (3.8) in the adversarial regime. Simultaneously, if the linear bandit
instance satisfies the sharpness condition in (1.3), then for every feasible centered sampling
allocation `n` in (1.4) and an arbitrary generator `ℬ` of `𝒜`, GIA-FTRL guarantees
`Reg_T = O(c^n_ctr(ℬ, θ) d log T + M_n + J^cor_θ √C log₊(C))` (3.9) in the corrupted stochastic
regime, where `J^cor_θ` is a finite instance-dependent constant independent of `T, C, n`, and `M_n`
is a finite constant depending on the instance and the sampling allocation `n`, but independent of
`T` and `C`."
The setting is that of `theorem_3_1`; the allocation `n` is a finite feasible centered sampling
allocation on the generator `ℬ` (`IsCtrAlloc ℬ θ a* n`), and `J` is chosen before `n`. -/
theorem proposition_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 →
∃ J : ℝ, ∀ n : Measure (Fin d → ℝ), IsCtrAlloc ℬ θ astar n →
∃ M : ℝ, ∀ {Ω : 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₀ * (ctrCost θ astar n * d * Real.log T) + M +
J * Real.sqrt C * Real.log (max (Real.exp 1) C)) := by sorry
end IAFTRL