Proposition G.1 — corrupted sharp-instance bound of GIA-FTRL for each allocation
ProvedIAFTRL.proposition_G_1bandit-algorithmslinear-banditsonline-learning
Setting. The setting is that of Proposition 3.1.
- is compact and spanning, is a compact generator with , and is a surjective enumeration of .
- The instance satisfies ; is the unique minimizer of on ; and the instance is sharp: on for some .
Claim. There is such that for every finite feasible centered sampling allocation on there is , independent of , and the run, with the following property. For every GIA-FTRL run of rounds in the corrupted stochastic regime with budget (that is, almost surely), and every ,
where and .
Proof outline (Appendix G.1.1). The regret against splits into a penalty term, a stability term, an exploration term and a direct corruption term (G.3)–(G.5). These are bounded by Lemmas G.1, G.4, G.5 and G.9 on the good events, together with the weighted failure estimate. The comparator correction for is then handled explicitly.
Preamble
import Mathlib import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **Proposition G.1 (Corrupted sharp-instance bound for each sampling allocation).** Zhao–Tan,
*Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Proposition G.1,
pp.123–124: "GIA-FTRL, with a fixed finite feasible centered sampling allocation `n_des`,
satisfies for every `T ≥ 1` and every allowed budget `C ≥ 0` …
`Reg_T ≤ 16 B C_rat⁴ c^{n_des}_ctr log(eT) + M_{n_des} + J^cor_θ √C log(e + C)` (G.2)", with
`B = 2^36(d+1)` and `C_rat = 64` (G.264); `J^cor_θ` does not depend on the allocation.
The setting is that of `proposition_3_1` (sharp instance `(θ, a*)`, `‖θ‖_𝒜 ≤ 1`, unique
optimal action `a* ∈ 𝒜`); `n` is a finite feasible centered sampling allocation on the generator
`ℬ`, `J` is chosen before `n`, and `M` depends on `n` but not on `T, C` or the run. -/
theorem proposition_G_1 {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) (θ astar : Fin d → ℝ) (hθ : setNorm 𝒜 θ ≤ 1)
(hastar : astar ∈ 𝒜) (huniq : ∀ a ∈ 𝒜, a ≠ astar → astar ⬝ᵥ θ < a ⬝ᵥ θ)
(hsharp : 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 ≤
16 * gB d * 64 ^ 4 * ctrCost θ astar n * Real.log (Real.exp 1 * T) + M +
J * Real.sqrt C * Real.log (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), Appendix G.1.1, Proposition G.1, pp. 123–124