Lemma C.10 (v1) — the comparison law built from a feasible allocation is feasible for (2.3)
ProvedIAFTRL.lemma_C_10This is the feasibility step behind the objective comparison in the exploration analysis of IA-FTRL: on good histories, mixing the FTRL weights with a scaled copy of a fixed feasible sampling allocation produces a law that satisfies every constraint of the sampling program (2.3).
Setting. Let be a finite action set in (), let satisfy with optimal action , and let satisfy for . Let be a feasible sampling allocation of (1.2) with total mass . Fix a round and a cumulative estimate , write , for the exponential weights at rate , for the platform constant Bc K, and . Assume:
- and ;
- the separation for every ;
- a number with for , and
Set , , . Then the comparison law
is feasible for (2.3) at round . That is, it satisfies the mixture constraint , the update-magnitude constraint (2.3d), the second-moment constraint (2.3e) and the exponential proxy constraint , all with the reconstruction .
The objective comparison then charges the learner only per round on good histories, which produces the term of (2.5).
Formalization Note In the source, and the hypotheses describe the event with . Here any with the stated properties is allowed, is replaced by , and the separation is used only with the smaller exponent . is written .
import Mathlib import Definitions.Def_LinearBanditProtocol import Definitions.Def_IAFTRL_IsActionSet import Definitions.Def_IAFTRL_actionNorm import Definitions.Def_IAFTRL_IsUniqueMin import Definitions.Def_IAFTRL_IsFeasibleAlloc import Definitions.Def_IAFTRL_allocMass import Definitions.Def_IAFTRL_IsFeasible2_3
namespace IAFTRL
open Matrix
/-- **Lemma C.10 (feasibility of the comparison distribution built from the allocation `n`).**
Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299v1, Lemma C.10 (p.61) with
(C.57) (p.58): "On `𝒲_t` with `t ≥ T_◦`, the above distribution admits a covariance reconstruction
satisfying every constraint of (3.3)", where `ρ_t = 16B𝓛_t²/t`,
`𝒲_t = 𝒢_t ∩ {𝓛_t² ≤ √t/a_n} ∩ {𝓛_t² ≤ t/a_{Δmin}}`, `a_n = max{1, 4BC_βN_n/d}`,
`a_{Δmin} = 64BΔ_min^{-2}`, `w^c_{t,a} = ρ_t n_a 1{a ≠ a*}`, `γ^c_t = Σ_a w^c_{t,a}`,
`p^c_t = (1 − γ^c_t)q_t + w^c_t`, and `T_◦` includes `t ≥ (32C_β)^8` and `t ≥ (4C_β log(eK))^4`.
Fix a feasible sampling allocation `n` of (1.2), a paper round `t` and a cumulative estimate
`S = Σ_{s<t} θ̂_s`, and write `X_a = (a − a*)^⊤S` and `Δ(a) = (a − a*)^⊤θ`. Suppose
`t ≥ (32C_β)^8`, `t ≥ (4C_β log(eK))^4`, the separation `X_a ≥ 4t^{3/4}` holds for `a ≠ a*`, and
`L ≥ 1` satisfies `tΔ(a) ≤ L X_a` for `a ≠ a*`, `L² ≤ √t/a_n` and `L² ≤ t/a_{Δ₀}`. Then the
comparison law `p^c = (1 − γ^c)q_t + w^c` with `w^c_a = ρ n_a 1{a ≠ a*}`, `ρ = 16BL²/t`, is feasible
for program (2.3) at round `t`.
**Formalization Note.** `C_β = 16d + √(d/(1 + log K))` and `log(eK) = 1 + log K` (the platform's
`β_t = 16d + √(dt/(1 + log K))`). The paper's `𝓛_t = max{1, max_{a≠a*} tΔ(a)/X_{t,a}}` is replaced by
any `L ≥ 1` with `tΔ(a) ≤ L X_a`; on `𝒢_t` the separation `X_{t,a} ≥ 4τ_t ≥ 4t^α` is used with the
smaller exponent `3/4 ≤ α`; `Δ_min` is replaced by any `Δ₀ ∈ (0, 1]` below the gaps
(`a_{Δ₀} = 64B/Δ₀² ≥ a_{Δmin}`). The reconstruction is the platform's `vCoef` (`v_b = M(p)^{-1}b`). -/
theorem lemma_C_10 {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ) (hA : IsActionSet arms)
(θ : Fin d → ℝ) (hθ : actionNorm arms θ ≤ 1) (jstar : Fin K) (hu : IsUniqueMin arms θ jstar)
(Δ₀ : ℝ) (hΔ₀ : 0 < Δ₀) (hΔ₀1 : Δ₀ ≤ 1)
(hgap : ∀ j, j ≠ jstar → Δ₀ ≤ (arms j - arms jstar) ⬝ᵥ θ)
(n : Fin K → ℝ) (hn : IsFeasibleAlloc arms θ jstar n)
(t : ℕ) (S : Fin d → ℝ) (L : ℝ)
(hT1 : (32 * (16 * (d : ℝ) + Real.sqrt (d / (1 + Real.log K)))) ^ 8 ≤ t)
(hT2 : (4 * (16 * (d : ℝ) + Real.sqrt (d / (1 + Real.log K))) * (1 + Real.log K)) ^ 4 ≤ t)
(hsep : ∀ a, a ≠ jstar → 4 * (t : ℝ) ^ ((3 : ℝ) / 4) ≤ (arms a - arms jstar) ⬝ᵥ S)
(hL1 : 1 ≤ L)
(hLX : ∀ a, a ≠ jstar →
t * ((arms a - arms jstar) ⬝ᵥ θ) ≤ L * ((arms a - arms jstar) ⬝ᵥ S))
(hLn : L ^ 2 ≤ Real.sqrt t / max 1
(4 * Bc K * (16 * (d : ℝ) + Real.sqrt (d / (1 + Real.log K))) * allocMass n / d))
(hLΔ : L ^ 2 ≤ t / (64 * Bc K / Δ₀ ^ 2)) :
IsFeasible2_3 arms t S (fun a =>
(1 - ∑ b, (if b = jstar then 0 else 16 * Bc K * L ^ 2 / t * n b)) *
qSoft (beta d K t) arms S a +
(if a = jstar then 0 else 16 * Bc K * L ^ 2 / t * n a)) := by sorry
end IAFTRL