Theorem 16 — approachability rate bounds OLO regret
ProvedApproachRegret.ToOLO.theorem16_regret_leblackwell-approachabilityonline-linear-optimizationp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be nonempty, compact, and convex, and set . Feed each loss vector to any algorithm that selects a point of from past admissible losses. Algorithm 1 uses that same decision as its OLO decision and evaluates it in the lifted Blackwell instance. For every horizon ,
where is the Euclidean distance of the average vector payoff to Algorithm 1's target. The bound transfers a finite-horizon approachability guarantee to regret.
Formalization Note The source's division by requires ; the zero-set case has zero regret but an undefined source instance. Histories and sums use rounds . No approachability-rate hypothesis is imposed on .
Preamble
import Mathlib import Definitions.Def_ApproachRegret_ToOLO_AlgorithmOne open scoped RealInnerProductSpace
Formal statement
namespace ApproachRegret.ToOLO
/-- Theorem 16, p. 37: Algorithm 1 converts any approachability algorithm into OLO. -/
theorem theorem16_regret_le {d : ℕ} (K : Set (E d))
(hK : IsCompact K) (hconv : Convex ℝ K) (hne : K.Nonempty)
(hk : 0 < kappa K)
(A : (n : ℕ) → (Fin n → E d) → E d)
(hA : ∀ n (h : Fin n → E d),
(∀ i, h i ∈ Metric.closedBall (0 : E d) 1) → A n h ∈ K)
(f : ℕ → E d) (T : ℕ) (hT : 1 ≤ T)
(hf : ∀ t, 1 ≤ t → t ≤ T → f t ∈ Metric.closedBall (0 : E d) 1) :
regret K A f T / (T : ℝ) ≤
2 * kappa K * approachRate K A f T := by sorry
end ApproachRegret.ToOLO
Source
Abernethy, Bartlett, Hazan, Blackwell Approachability and No-Regret Learning are Equivalent, COLT 2011, JMLR W&CP 19, https://proceedings.mlr.press/v19/abernethy11b.html, Theorem 16, p. 37 (PDF p. 11); proof ends p. 38 (PDF p. 12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.