Lemma G.12 — every sharp optimal action is a reference atom
ProvedIAFTRL.lemma_G_12bandit-algorithmslinear-banditsonline-learning
Setting.
- is compact and spanning, and is a compact generator of it.
- is a surjective enumeration of . The candidate is the lexicographically least minimizer of on , and is the set of first occurrences.
- is the unique minimizer of . Sharpness holds: on for some .
Claim. There is with . Hence is an atom of the reference measure , with .
Proof idea.
- Every with keeps as the unique minimizer on , by duality .
- Such a can be chosen rational.
- The enumeration reaches it, the lexicographic selection then picks , and the first occurrence lies in .
Preamble
import Mathlib import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **Lemma G.12 (Every sharp optimal action is a reference atom).** Zhao–Tan, *Best-of-Both-Worlds
FTRL for Linear Bandits* (STOC submission version), Lemma G.12, p.144: "Suppose a parameter has a
unique optimal action `a*` and `ς = inf_{a∈𝒦\{a*}} (a − a*)ᵀθ / ‖a − a*‖_𝒮 > 0`. Then `a* = b_{j*}`
for some finite index `j*`."
For a compact generator `ℬ` of a compact spanning action set `𝒜 ⊆ 𝔹^d`, a surjective enumeration
`e` of `ℚ^d`, and a sharp instance with unique optimal action `a* ∈ 𝒜`, the optimal action is the
candidate `cand ℬ e m` of some first-occurrence index `m ∈ J`; in particular it is an atom of the
reference measure (3.3). -/
theorem lemma_G_12 {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) :
∃ m ∈ Jset ℬ e, cand ℬ e m = astar := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry (STOC submission version; arXiv:2611.01299), Appendix G.6.2, Lemma G.12, pp. 144–145