Theorem 3.2(i) — information-acquisition lower bound on a sharp curve: and
ProvedIAFTRL.theorem_3_2_iSetting. Let
The unique optimal action of is , with gap . The feedback is a sign observation of the linear mean: playing yields with (Proposition H.1). A policy is consistent if it plays only actions of and satisfies for every and every sharp stochastic instance on this curve, i.e. every with , a unique optimal action, and geometric sharpness.
Claim. The centered information-acquisition complexity (1.4) of is
and every consistent policy satisfies
On this sharp curve the minimum positive gap is zero. The claim shows that the logarithmic term in the upper bound of Theorem 3.1 cannot be improved beyond a constant factor.
Formalization Note is cstarCtr curve θ ![-1/2, 0]. The environment is signEnv θ, and consistency is IsConsistentOn curve (sharpInstances curve) π with IsSupportedLinearPolicy curve π. The lower limit is stated in its elementary form: for every , eventually .
import Mathlib import Definitions.Def_LinearBanditProtocol import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL import Definitions.Def_IAFTRL_SignModel
namespace IAFTRL
open MeasureTheory ProbabilityTheory Matrix BanditAlgorithm Filter Topology
/-- **Theorem 3.2, first part (information-acquisition lower bound).** Zhao–Tan,
*Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Theorem 3.2, p.25:
"On `A_curve = {(−1/2 + s/4, (s + s²)/4) : 0 ≤ s ≤ 1}`, `θ_τ = (τ, 0)` and `0 < τ ≤ 1`, we have
`c*_ctr = 8/τ`. Every consistent policy satisfies
`liminf_{T→∞} Reg_{T,θ_τ} / log T ≥ 7/(16τ) = (7/128) c*_ctr`."
The feedback model is that of Proposition H.1 (p.193): sign observations of the linear mean, and
consistency is on the sharp stochastic instances on this curve.
The optimal action of `θ_τ` is `a(0) = (−1/2, 0)`, which is the `a*` of `c*_ctr` in (1.4). The
lower limit is stated in its elementary form: for every `ε > 0`, eventually
`(7/(16τ) − ε) log T ≤ Reg_{T,θ_τ}`. -/
theorem theorem_3_2_i (τ : ℝ) (hτ : 0 < τ) (hτ1 : τ ≤ 1) :
let curve : Set (Fin 2 → ℝ) := {a | ∃ s ∈ Set.Icc (0 : ℝ) 1, a = ![-1 / 2 + s / 4, (s + s ^ 2) / 4]}
let θ : Fin 2 → ℝ := ![τ, 0]
cstarCtr curve θ ![-1 / 2, 0] = 8 / τ ∧
∀ π : LinearBanditPolicy 2, IsSupportedLinearPolicy curve π →
IsConsistentOn curve (sharpInstances curve) π →
∀ ε : ℝ, 0 < ε → ∀ᶠ T : ℕ in atTop,
(7 / (16 * τ) - ε) * Real.log T ≤ (signEnv θ).regret curve π T := by sorry
end IAFTRL