Lemma G.3 — Laplace decay of the GIA-FTRL reference measure away from the optimal action
ProvedIAFTRL.lemma_G_3bandit-algorithmslinear-banditsonline-learning
Setting. The sharp corrupted instance of Proposition 3.1 / G.1. Here is a compact action set in the Euclidean unit ball that spans , and is a compact generator () with , where . The direction enumeration is surjective, and . The action is the unique optimal action, the instance is sharp, and . The reference measure is of (3.3), and the learning rate is .
Claim (existential-constant form). There is a constant , depending only on the instance, such that the following holds for every round and every vector . If for all , then
Formalization Note. The paper proves the stronger decay for . The weaker for all follows by enlarging the constant. It suffices for the summations in Lemmas G.1, G.4 and G.5.
Proof idea.
- The integrand is at most with .
- Atomic part. The reinforced priorities for , together with sharpness, give the atomic cap of (G.50).
- Volume part. The affine contraction toward a maximizer of gives the volume cap . Then is the law of a mean of 16 independent volume samples, and .
Preamble
import Mathlib import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **Lemma G.3 (Laplace decay away from the optimal action).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Lemma G.3, p.129:
"If `t ≥ T*` and `X_t(a) ≥ 4t^{7/8}Δ(a)` for all `a ∈ K`, then
`(1/π*) ∫_{a≠a*} e^{−X_t(a)/(2β_t)} µ(da) ≤ A_L t^{−6}`."
Existential-constant form with the weaker decay `n^{−3}`, valid for every `n ≥ 1`: there is `A`
(depending only on the instance) such that for every round `n ≥ 1` and every cumulative estimate
`S` with `(a − a*)ᵀS ≥ 4 n^{7/8} Δ(a)` on `𝒦 = Conv ℬ`, where `Δ(a) = (a − a*)ᵀθ`,
`∫_{a ≠ a*} exp(−(a − a*)ᵀS/(2β_n)) µ(da) ≤ A n^{−3}`. -/
theorem lemma_G_3 {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) :
∃ A : ℝ, ∀ (n : ℕ) (S : Fin d → ℝ), 1 ≤ n →
(∀ a ∈ Kset ℬ, 4 * (n : ℝ) ^ ((7 : ℝ) / 8) * ((a - astar) ⬝ᵥ θ) ≤ (a - astar) ⬝ᵥ S) →
∫ a in {astar}ᶜ, Real.exp (-((a - astar) ⬝ᵥ S) / (2 * gbeta d n)) ∂(refMu ℬ e) ≤
A / (n : ℝ) ^ 3 := 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.2.1, Lemma G.3, (G.64)–(G.75), with Lemma G.2 (G.50)–(G.62)