Theorem 2.1 — best-of-both-worlds regret of IA-FTRL
ProvedIAFTRL.theorem_2_1There is an absolute constant such that the following holds for every dimension and every finite action set in the unit ball of spanning , with .
- Adversarial regime (2.4). For every execution of IA-FTRL for rounds against an adaptive environment and every comparator ,
- Corrupted stochastic regime (2.6). For every loss vector with and a unique optimal action , and every with for all , there is a constant (depending on the instance only) such that for every execution of IA-FTRL for rounds in the corrupted stochastic regime with any budget and every ,
Here is the information-acquisition complexity (1.2).
The same algorithm, without knowing the regime, , , or , attains the minimax adversarial rate and the instance-optimal -type rate (up to ), with an additive corruption term whose coefficient does not depend on .
Formalization Note is read with one absolute constant. The paper's is absorbed into the -term, and into , which is chosen before the probability space, the horizon, the budget and the run. is the published BanditAlgorithm.linearBanditAllocationValue arms (−θ) (that definition uses rewards, hence ).
Differences from the source:
- reading: → one absolute constant chosen before the dimension, the action set and the instance; reason: the stronger of the two readings; an instance-dependent constant in front of the leading term would empty the statement, and the proof's constants are absolute ((C.3)–(C.5), (D.7), Proposition D.2)
- reading: the constant and , "independent of , " → after and before the probability space, , and the run; absorbed into ; reason: is defined in (D.5) from instance constants only;
- reading: protocol , → action law given , feedback identity given , for the pre-action filtration ; reason: Appendix J.1, p.204: "Enlarging the pre-action filtration to include an environment's fresh pre-action randomization does not reveal it to the learner"
- reading: corrupted regime: fixed → fixed with ; reason: the stochastic regime's assumption (p.5), used in the corrupted regime as (p.86)
- reading: IA-FTRL with "a fixed -measurable rule" for → every -measurable minimizer of (2.3); reason: p.17 leaves the rule open ("e.g., the lexicographically smallest"); the proof uses only the objective comparison (C.1)/(D.158)
- generalization: → any with for all ; reason: at (assumed by the paper) this is the source's bound; also covers , where is undefined and the regret is
- encoding: (2.1), (2.3d)–(2.3f) → softmax closed form of (2.1); computable forms of (2.3d)–(2.3f); reason: the paper states both equivalences itself (pp.18–19, (D.151))
- encoding: , rounds , actions as a set → a bound for every comparator action ; 0-based rounds with ;
Fin Kactions with theFin Korder for ties; reason: Lean conventions; same instances - encoding: horizon , dimension → , ; reason: is undefined at (where the regret is ); the paper works in
- encoding: of (1.2) →
BanditAlgorithm.linearBanditAllocationValue arms (−θ); reason: same allocations and objective under a unique minimizer (rewards convention, hence )
import Mathlib import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_IsIAFTRLRun import Definitions.Def_LinearBanditProtocol import Definitions.Def_IAFTRL_actionNorm import Definitions.Def_IAFTRL_IsUniqueMin import Definitions.Def_IAFTRL_IsCorrupted import Definitions.Def_IAFTRL_regretVs
namespace IAFTRL
open Matrix MeasureTheory
/-- **Theorem 2.1 (best-of-both-worlds regret of IA-FTRL).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Theorem 2.1, p.20: "For
linear bandits with finite action sets, IA-FTRL simultaneously guarantees (2.4) in the adversarial
regime, and `Reg_T = O(c*(𝒜, θ) log K · log T + M_{𝒜,θ} + J_{d,K,Δ_min}√C)`, (2.6) in the corrupted
stochastic regime, where `M_{𝒜,θ} = M_{n◦}` and `J_{d,K,Δ_min} = O(√(d log K) Δ_min^{−128/255})` are
instance-dependent constants independent of `T, C`", with (2.4) of Proposition 2.1:
"`Reg_T = O(d log K + √(dT log K))`".
There is an absolute constant `c₀ > 0` such that for every dimension `d ≥ 1` and every spanning
finite action set `𝒜` in the unit ball of `ℝ^d`, with `K = |𝒜|`:
1. (2.4) every execution of IA-FTRL for `T ≥ 1` rounds against an adaptive environment has
`Reg_T(u) ≤ c₀(d log K + √(dT log K))` for every comparator `u ∈ 𝒜`;
2. (2.6) for every `θ` with `‖θ‖_𝒜 ≤ 1` and unique optimal action `a*`, and every `Δ₀ ∈ (0, 1]` with
`Δ₀ ≤ Δ(a)` for all `a ≠ a*`, there is a constant `M` such that every execution of IA-FTRL for
`T ≥ 1` rounds in the corrupted stochastic regime with any budget `C ≥ 0` has
`Reg_T(u) ≤ c₀(c*(𝒜, θ) log K · log T + √(d log K) Δ₀^{−128/255} √C) + M` for every `u ∈ 𝒜`.
Both bounds concern the same algorithm, which knows neither the regime, nor `θ`, `C`, `T` or `Δ_min`.
**Formalization Note.** `O(·)` is read with one absolute constant `c₀`, chosen before the instance.
`M` (the paper's `c₀M_{𝒜,θ}`) is chosen after `(d, K, 𝒜, θ, a*, Δ₀)` and before the probability space,
the horizon `T`, the budget `C` and the run; `J` is absorbed into `c₀√(d log K)Δ₀^{−128/255}`.
`c*(𝒜, θ)` is the published `BanditAlgorithm.linearBanditAllocationValue arms (−θ)` (rewards
convention, hence `−θ`). `Δ₀` is any lower bound in `(0, 1]` on the gaps; at `Δ₀ = Δ_min ≤ 1` this
is (2.6). The run predicate `IsIAFTRLRun` allows every `F_{t−1}`-measurable minimizer of (2.3), an
adaptive environment, and the pre-action σ-algebras of p.204. The bound on every `Reg_T(u)` is the
bound on `sup_u Reg_T(u)`. -/
theorem theorem_2_1 : ∃ c₀ : ℝ, 0 < c₀ ∧
∀ {d K : ℕ}, 1 ≤ d → ∀ (arms : Fin K → Fin d → ℝ), IsActionSet arms →
(∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (T : ℕ)
(R : Run d K Ω), 1 ≤ T → IsIAFTRLRun P arms T R →
∀ u : Fin K, regretVs P arms T R u ≤
c₀ * ((d : ℝ) * Real.log K + Real.sqrt ((d : ℝ) * T * Real.log K))) ∧
(∀ (θ : Fin d → ℝ) (jstar : Fin K) (Δ₀ : ℝ),
actionNorm arms θ ≤ 1 → IsUniqueMin arms θ jstar → 0 < Δ₀ → Δ₀ ≤ 1 →
(∀ j, j ≠ jstar → Δ₀ ≤ (arms j - arms jstar) ⬝ᵥ θ) →
∃ M : ℝ, ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(T : ℕ) (C : ℝ) (R : Run d K Ω), 1 ≤ T → 0 ≤ C →
IsIAFTRLRun P arms T R → IsCorrupted P arms θ C T R →
∀ u : Fin K, regretVs P arms T R u ≤
c₀ * (BanditAlgorithm.linearBanditAllocationValue arms (-θ) * Real.log K *
Real.log T +
Real.sqrt ((d : ℝ) * Real.log K) * Δ₀ ^ (-(128 : ℝ) / 255) * Real.sqrt C) + M) := by sorry
end IAFTRL
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.