Lemma 15 — a valid halfspace oracle for Algorithm 1
ProvedApproachRegret.ToOLO.lemma15_oracleblackwell-approachabilityconic-dualityp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be nonempty, compact, and convex, with , and let and be the payoff and target of Algorithm 1. There is an oracle such that, for every halfspace containing , it returns and
This gives the reduction a valid oracle for every eligible halfspace.
Formalization Note The representation includes zero normals and arbitrary offsets; makes the payoff's division meaningful.
Preamble
import Mathlib import Definitions.Def_ApproachRegret_ToOLO_AlgorithmOne open scoped RealInnerProductSpace
Formal statement
namespace ApproachRegret.ToOLO
/-- Lemma 15, p. 37: an oracle for every halfspace containing the target. -/
theorem lemma15_oracle {d : ℕ} (K : Set (E d))
(hK : IsCompact K) (hconv : Convex ℝ K) (hne : K.Nonempty)
(hk : 0 < kappa K) :
∃ O : E (d + 1) → ℝ → E d,
∀ (a : E (d + 1)) (c : ℝ),
target K ⊆ {z | ⟪a, z⟫ ≤ c} →
O a c ∈ K ∧
∀ f ∈ Metric.closedBall (0 : E d) 1,
⟪a, payoff K (O a c) f⟫ ≤ c := 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, Lemma 15, p. 37 (PDF p. 11); halfspace oracle definition, p. 32 (PDF p. 6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.