The window parameters of Definition G.8 satisfy all window hypotheses for t ≥ t₀
ProvedG26G.Sharp.win_okbandit-algorithmslinear-banditsonline-learning
Setting. The standing hypotheses Sharp of the sharp corrupted instance hold (see runN_FI), and is surjective. Let , , , and for a round set
where (H.M0 he) is an instance constant.
Claim. If (H.t0f he C), then all of the following hold: , ; ; ; ; ; and ; ; ; ; ; and the tail bounds
These are the comparisons ", , , , " of Definition G.8, made explicit, together with the conversions of the window error terms into .
Formalization Note Rounds are 0-based; the statement uses let for , , .
Preamble
import Mathlib
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
import Definitions.Def_IAFTRL_G26_body
import Definitions.Def_IAFTRL_G26_run
import Definitions.Def_IAFTRL_G26_window
open MeasureTheory ProbabilityTheory Set IAFTRL Matrix J11
open G26G
open G26 G26R
variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ} {θ astar : Fin d → ℝ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
{T : ℕ} {R : GRun d Ω}
open G26G.Sharp
variable (H : Sharp 𝒜 ℬ θ astar) (he : Function.Surjective e)
include H heFormal statement
theorem G26G.Sharp.win_ok {C : ℝ} (hC : 0 ≤ C) {t : ℕ} (ht0 : H.t0f he C ≤ t) :
let Hc := Hcf C
let m := mw (H.M0 he) Hc t
let z := zw m t
1 ≤ m ∧ m ≤ t ∧ 2 * ((m : ℝ) + 1) ≤ (t : ℝ) + 1 ∧
cTw d H.sig⁻¹ H.kb ≤ root8 ((m : ℝ) + 1) ∧ H.sig⁻¹ * C ≤ (m : ℝ) + 1 ∧
2 * H.Sref he + 2 ≤ m ∧
2 ^ 21 * (((nCf C : ℝ) + 1) * Real.log (Real.exp 1 * ((nCf C : ℝ) + 1))) ≤ (m : ℝ) + 1 ∧
0 < z ∧ (m : ℝ) + 1 ≤ z ∧
z ≤ ((t : ℝ) + 1) * root8 (((m : ℝ) + 1) / ((t : ℝ) + 1)) ^ 7 ∧
H.κ1 * root8 (((m : ℝ) + 1) / ((t : ℝ) + 1)) ≤ 1 ∧
(((m : ℝ) + 1) / z) ^ 8 ≤ ((m : ℝ) + 1) / ((t : ℝ) + 1) ∧
((t : ℝ) + 1) / ((m : ℝ) + 1) ≤ (m : ℝ) + 1 ∧
tauB z t ≤ (t : ℝ) + 1 ∧
(tauB z t / ((t : ℝ) + 1)) ^ 16 ≤
2 ^ 16 * (1 / ((t : ℝ) + 1) ^ 2 + 4 ^ 16 * (((m : ℝ) + 1) / ((t : ℝ) + 1)) ^ 4) ∧
(((m : ℝ) + 1) / ((t : ℝ) + 1)) ^ 4 ≤
16 * (((H.M0 he : ℝ) + 3) ^ 4 + 1) * (Hc / ((t : ℝ) + 1)) ^ 2 ∧
(((nCf C : ℝ) + 1) ^ 4 + 1) / ((m : ℝ) + 1) ^ 4 ≤
(Hc / ((t : ℝ) + 1)) ^ 2 + 1 / ((t : ℝ) + 1) ^ 2 ∧
1 / ((m : ℝ) + 1) ^ 4 ≤ 1 / ((t : ℝ) + 1) ^ 2 := by sorrySource
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, Definition G.8, (G.522) and the comparisons stated after it (p.173)