Lemma D.1 — attainment, measurable lexicographic selection, integrability
ProvedIAFTRL.lemma_D_1bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1
Let be a finite action set in the unit ball of () spanning .
- For every round and every cumulative estimate , the program (2.3) has a minimizer.
- For every there is a Borel measurable map such that, for every , minimizes (2.3) and is lexicographically smallest (in the fixed action order) among all minimizers; in particular it is unique.
- For every execution of IA-FTRL for rounds on a probability space, the estimates () and the action-loss differences (, all actions ) are integrable.
This makes the optimization step a well-defined measurable decision rule and justifies the expectations in the analysis.
Formalization Note The history enters (2.3) only through , so Borel measurability in composed with the measurable map from the history to is Borel measurability in the history. The lexicographic order is toLex on Fin K → ℝ.
Differences from the source:
- encoding: "Borel measurable in the history" → Borel measurable in ; reason: the program depends on the history only through ("Borel in ", p.66); composition with history
- encoding: "uniquely defined" → is the least minimizer in the linear order
toLex; reason: uniqueness of a least element of a linear order - reading: "covariance estimates and action-loss differences" → and ; reason: the quantities bounded in (D.14)–(D.16)
- generalization: integrability for the lexicographic rule → integrability for every execution (any -measurable minimizer, any environment of the protocol); reason: the bounds (D.14)–(D.16) use only feasibility; specializes to the lexicographic rule
- encoding: , rounds → , ; reason: the paper's setting
- 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"
Preamble
import Mathlib import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_IsMin2_3 import Definitions.Def_IAFTRL_IsIAFTRLRun
Formal statement
namespace IAFTRL
open Matrix MeasureTheory
/-- **Lemma D.1 (Attainment and measurable sampling-law selection).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Lemma D.1, p.65:
"On every finite history, the objective in (2.3), with `v = v(p)` prescribed by
`M(p) = Σ_{a∈𝒜} p_a aa^⊤` and `v_a(p) = M(p)^{-1}a`, attains its minimum over `p`. The
lexicographically least minimizing `p_t`, in the fixed action ordering, is uniquely defined and
Borel measurable in the history. For every fixed finite horizon, its covariance estimates and
action-loss differences are integrable."
For a spanning finite action set in the unit ball of `ℝ^d` (`d ≥ 1`):
1. for every paper round `t ≥ 1` and every cumulative estimate `S`, program (2.3) has a minimizer;
2. for every `t ≥ 1` there is a Borel map `S ↦ sel(S)` such that `sel(S)` is, for every `S`, the
lexicographically least minimizer of (2.3) (in the order of `Fin K`);
3. for every execution of IA-FTRL on a probability space, every horizon `T` and every round, the
estimates `θ̂_t` (`t < T`) and the action-loss differences `L̂_{t,a} − L̂_{t,c}` (`t ≤ T`) are
integrable.
**Formalization Note.** The history enters (2.3) only through `S = Σ_{s<t} θ̂_s` (p.56; "Borel in
`Σ_{s=1}^{t−1} θ̂_s`", p.66); composing `sel` with the measurable map history ↦ `S` gives Borel
dependence on the history. Uniqueness of the lexicographically least minimizer is the
antisymmetry of the linear order `toLex`. Clause 3 is stated for every run, i.e. for any
`F_{t−1}`-measurable minimizer, since the bounds (D.14)–(D.16) use only feasibility. -/
theorem lemma_D_1 {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ) (hA : IsActionSet arms) :
(∀ t : ℕ, 1 ≤ t → ∀ S : Fin d → ℝ, ∃ p : Fin K → ℝ, IsMin2_3 arms t S p) ∧
(∀ t : ℕ, 1 ≤ t → ∃ sel : (Fin d → ℝ) → (Fin K → ℝ), Measurable sel ∧
∀ S, IsMin2_3 arms t S (sel S) ∧
∀ p : Fin K → ℝ, IsMin2_3 arms t S p → toLex (sel S) ≤ toLex p) ∧
(∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (T : ℕ)
(R : Run d K Ω), IsIAFTRLRun P arms T R →
(∀ t < T, Integrable (R.thetaHat arms t) P) ∧
∀ t ≤ T, ∀ a c : Fin K,
Integrable (fun ω => arms a ⬝ᵥ R.cumEst arms t ω - arms c ⬝ᵥ R.cumEst arms t ω) P) := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix D.1.2, Lemma D.1, p.65
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.