Reference identification for GIA-FTRL on Laplace histories
ProvedIAFTRL.lemma_G_ref_idSetting. The sharp instance of Proposition 3.1. Here is a compact action set in the unit ball spanning , and is a compact generator. The enumeration is surjective, is the unique optimal action, the instance is sharp, and . GIA-FTRL chooses at round the reference action of (3.4), where is the least index minimizing over the candidate atoms with reinforced priorities of (3.2).
Claim. There is a round , depending only on the instance, such that the following holds for every and every . If
then the reference action is .
Formalization Note. This is the deterministic part of the statement "on the reference is " in Lemma G.26. The Laplace lower bound of (G.554) holds on , and the claim shows that this bound alone forces the reference to be for large .
import Mathlib import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL
namespace IAFTRL
open MeasureTheory
/-- **Reference identification on Laplace histories.** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Lemma G.26, p.174: "On `G_t^cor` the reference is
`a*`", with the reference index (3.4) `r_t = argmin_{j∈J} {b_jᵀ L̂_{t−1} + β_t h_j}` and the
reinforced priorities (3.2).
Deterministic form: in the sharp setting there is a round `T_r` such that for every round
`n ≥ T_r` and every cumulative estimate `S` with `(a − a*)ᵀS ≥ 4 n^{7/8} Δ(a)` on `𝒦`, the
reference action of program (3.6) is `b_{r_n} = a*`. -/
theorem lemma_G_ref_id {d : ℕ} (hd : 1 ≤ d) (𝒜 ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ)
(h𝒜 : IsCompact 𝒜) (hℬ : IsCompact ℬ) (hgen : IsGenerator 𝒜 ℬ)
(hball : ∀ a ∈ 𝒜, a ⬝ᵥ a ≤ 1) (hspan : Submodule.span ℝ 𝒜 = ⊤)
(he : Function.Surjective e) (θ astar : Fin d → ℝ)
(hastar : astar ∈ 𝒜) (huniq : ∀ a ∈ 𝒜, a ≠ astar → astar ⬝ᵥ θ < a ⬝ᵥ θ)
(hsharp : IsSharp 𝒜 θ astar) :
∃ Tr : ℕ, ∀ (n : ℕ) (S : Fin d → ℝ), Tr ≤ n →
(∀ a ∈ Kset ℬ, 4 * (n : ℝ) ^ ((7 : ℝ) / 8) * ((a - astar) ⬝ᵥ θ) ≤ (a - astar) ⬝ᵥ S) →
gref ℬ e n S = astar := by sorry
end IAFTRL