Finitely many positive linear gaps are stable under small perturbations
Provedfinite_linear_gaps_stablebanditslinear-algebrapartial-monitoringperturbation
Let and be finite index sets. Suppose every linear functional has value at least at . Then all these gaps remain at least after a sufficiently small perturbation in a fixed direction :
The radius is uniform over the finite family. This packages the Hölder/triangle-inequality stability step used when perturbing stochastic bandit environments.
Preamble
import Mathlib.Algebra.BigOperators.Fin import Mathlib.Data.Real.Basic import Mathlib.Tactic
Formal statement
theorem finite_linear_gaps_stable
{C I : Type*} [Fintype C] [Fintype I]
(A : C → I → ℝ) (u q : I → ℝ) (ε : ℝ) (hε : 0 < ε)
(hgap : ∀ c : C, ε ≤ ∑ i, A c i * u i) :
∃ δ : ℝ, 0 < δ ∧ ∀ Δ : ℝ, |Δ| ≤ δ → ∀ c : C,
ε / 2 ≤ ∑ i, A c i * (u i + Δ * q i) := by sorrySource
Lattimore and Szepesvári, Bandit Algorithms (Cambridge UP, 2020), Theorem 37.12, Step 3, printed p. 490: the bounds following Eq. (37.9), where the loss gap decreases by at most Δ times an ℓ1 norm.