Theorem 2.2 — finite-action corruption lower bound with
ProvedIAFTRL.theorem_2_2Let be the standard basis of and . For and , let . Losses are minimized, so the unique optimal action of is .
- The instances. For each , the instance has a unique optimal action and minimum gap exactly . Its information-acquisition complexity (1.2) is
- The lower bound. Fix a corruption budget and an integer . Then there are two corrupted stochastic environments, indexed by , with the following properties. Each has fixed loss vector , bounded feedback in with mean , and total corruption . Moreover, every policy that plays actions in satisfies
Here is computed in the environment indexed by , using the actual (corrupted) loss vectors .
The two instances keep bounded while can be arbitrarily small. The theorem therefore shows that the coefficient of in the corruption term of a regret bound cannot, in general, be bounded in terms of alone; it must grow like . This complements the term of Theorem 2.1.
Formalization Note. The actions are listed as arms = (−e₁, e₁, e₂), and is Set.range arms. The complexity is linearBanditAllocationValue arms (−θ), the loss-convention reading of (1.2) also used in Theorem 2.1. A policy is any LinearBanditPolicy 2 (Markov kernels from histories to actions) with IsSupportedLinearPolicy (Set.range arms) π. The environments are oblivious LinEnvs (definition IAFTRL_LinEnv), with deterministic corruption and feedback laws that depend only on the round and the action. Exhibiting environments in this subclass is at least as strong as the source's existence claim. The condition is written ⌈(Δ ^ 2)⁻¹⌉₊ ≤ T.
import Mathlib import Definitions.Def_LinearBanditProtocol import Definitions.Def_IAFTRL_IsUniqueMin import Definitions.Def_IAFTRL_LinEnv
namespace IAFTRL
open MeasureTheory ProbabilityTheory Matrix BanditAlgorithm
/-- **Theorem 2.2 (finite-action corruption lower bound).** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits* (STOC submission version), Theorem 2.2, p.20: "Let `𝒜 = {−e₁, e₁, e₂}` and
`θ_σ = (σΔ_min/2, 1/2)`, with `σ = ±1` and `0 < Δ_min ≤ 1/2`. Both instances have minimum gap
`Δ_min` and `c*(𝒜, θ_σ) = 4/(1+Δ_min) = Θ(1)` for all `0 < Δ_min ≤ 1/2`. For every corruption
budget `C ≥ Δ_min⁻¹` and every integer `T ≥ ⌈Δ_min⁻²⌉`, there are two corrupted stochastic
environments indexed by `σ = ±1`, each with loss vector `θ_σ`, such that every policy satisfies
`max_{σ=±1} Reg_{T,σ} ≥ (1/16) min{√T, √(C/Δ_min)}` in the corrupted stochastic regime with budget
at most `C`."
The actions are listed as `arms = (−e₁, e₁, e₂)`; `c*` is `linearBanditAllocationValue arms (−θ)`
(the loss convention of (1.2), as in Theorem 2.1). A policy is any `LinearBanditPolicy 2` that
plays only actions of `𝒜`. The two environments are oblivious (`LinEnv`): deterministic
corruption and feedback whose law depends only on the round and the action. -/
theorem theorem_2_2 (Δ : ℝ) (hΔ : 0 < Δ) (hΔ' : Δ ≤ 1 / 2) :
let arms : Fin 3 → Fin 2 → ℝ := ![![-1, 0], ![1, 0], ![0, 1]]
let θ : ℝ → Fin 2 → ℝ := fun σ => ![σ * Δ / 2, 1 / 2]
(∀ σ : ℝ, (σ = 1 ∨ σ = -1) →
(∃ jstar : Fin 3, IsUniqueMin arms (θ σ) jstar ∧
(∀ j, j ≠ jstar → Δ ≤ (arms j - arms jstar) ⬝ᵥ θ σ) ∧
∃ j, j ≠ jstar ∧ (arms j - arms jstar) ⬝ᵥ θ σ = Δ) ∧
linearBanditAllocationValue arms (-θ σ) = 4 / (1 + Δ)) ∧
∀ C : ℝ, Δ⁻¹ ≤ C → ∀ T : ℕ, ⌈(Δ ^ 2)⁻¹⌉₊ ≤ T →
∃ E : ℝ → LinEnv 2,
(∀ σ : ℝ, (σ = 1 ∨ σ = -1) → (E σ).IsCorruptedStoch (Set.range arms) (θ σ) C T) ∧
∀ π : LinearBanditPolicy 2, IsSupportedLinearPolicy (Set.range arms) π →
(1 / 16) * min (Real.sqrt T) (Real.sqrt (C / Δ)) ≤
max ((E 1).regret (Set.range arms) π T) ((E (-1)).regret (Set.range arms) π T) := by sorry
end IAFTRL