Proposition 2.1 — regret of IA-FTRL for every fixed feasible allocation
ProvedIAFTRL.proposition_2_1bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1
There 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.5). For every loss vector with and a unique optimal action , every with for all , and every feasible sampling allocation of (1.2), there is a constant (depending on the instance and on only) such that for every execution of IA-FTRL for rounds in the corrupted stochastic regime with any budget and every ,
Both guarantees hold for the same algorithm, which knows neither the regime nor , , or .
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.
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
Preamble
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 import Definitions.Def_IAFTRL_IsFeasibleAlloc import Definitions.Def_IAFTRL_allocCost
Formal statement
namespace IAFTRL
open Matrix MeasureTheory
/-- **Proposition 2.1 (regret for every fixed feasible allocation).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Proposition 2.1,
p.20: "For linear bandits with finite action sets, IA-FTRL guarantees
`Reg_T = O(d log K + √(dT log K))`, (2.4) in the adversarial regime. Simultaneously, for every
feasible sampling allocation `n` in (1.2), IA-FTRL guarantees
`Reg_T = O(c^n(𝒜, θ) log K · log T + M_n + J_{d,K,Δ_min}√C)`, (2.5) in the corrupted stochastic regime,
where `J_{d,K,Δ_min} = O(√(d log K) Δ_min^{−128/255})`, and `M_n` is a finite constant depending on the
instance `(𝒜, θ)` and the sampling allocation `n`, but independent of `T` and `C`."
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.5) for every `θ` with `‖θ‖_𝒜 ≤ 1` and unique optimal action `a*`, every `Δ₀ ∈ (0, 1]` with
`Δ₀ ≤ Δ(a)` for all `a ≠ a*`, and every feasible sampling allocation `n` of (1.2), 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^n(𝒜, θ) log K · log T + √(d log K) Δ₀^{−128/255} √C) + M` for every `u ∈ 𝒜`.
**Formalization Note.** `O(·)` is read with one absolute constant `c₀`, chosen before the instance.
`M` (the paper's `c₀M_n`) is chosen after `(d, K, 𝒜, θ, a*, Δ₀, n)` and before the probability space,
the horizon `T`, the budget `C` and the run, so it is independent of `T` and `C`; `J` is absorbed into
`c₀√(d log K)Δ₀^{−128/255}`. `Δ₀` is any lower bound in `(0, 1]` on the gaps; at `Δ₀ = Δ_min ≤ 1` this
is (2.5). The bound on every `Reg_T(u)` is the bound on `sup_u Reg_T(u)`. -/
theorem proposition_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) ⬝ᵥ θ) →
∀ n : Fin K → ℝ, IsFeasibleAlloc arms θ jstar n →
∃ 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₀ * (allocCost arms θ jstar n * Real.log K * Real.log T +
Real.sqrt ((d : ℝ) * Real.log K) * Δ₀ ^ (-(128 : ℝ) / 255) * Real.sqrt C) + M) := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Section 2.2, Proposition 2.1, p.20, Eqs. (2.4)–(2.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.