Lemma 1, p. 11 — the worst-case regret of proxy cost c^π against c⋆ is sin θ(c⋆, c^π), or 1 when θ ≥ π/2
ProvedCtxInvOpt.Offline.lemma1_realized_worst_case_regretLet and . Fix a proxy cost and a true cost . Consider all instances consisting of an action set (nonempty, compact, diameter at most ), a -Lipschitz context function , an action chosen by the proxy policy (any minimizer, so ties are broken adversarially), and an optimal action . The worst-case regret
is attained and equals
The lemma converts a policy that acts as if the cost were into a purely geometric quantity: its worst-case loss depends only on the angle between and the true cost. It is the basis of the upper bound in Theorem 1.
Formalization Note The supremum is stated with IsGreatest: the value is a regret of some admissible instance, and it bounds the regret of every admissible instance. The proxy policy is represented by its cost vector (as on p. 10 of the paper). The hypothesis is not written in the paper but is needed: in every regret is . The hypothesis is the paper's standing assumption of §2.
import Mathlib import Definitions.Def_CtxInvOpt_Offline_Geometry
namespace CtxInvOpt.Offline
/-- **Lemma 1 (Realized worst-case regret), arXiv:2106.14015v3, p. 11.** For a proxy cost
`c^π ∈ S^d` and a true cost `c⋆ ∈ S^d`, the worst-case regret (8)
`L(c^π, c⋆) = sup_{x^π ∈ ψ(c^π, X, f), X ∈ 𝔅, f ∈ 𝔉} (f(x^π) − f(x⋆))′c⋆`
equals `sin θ(c⋆, c^π)` if `θ(c⋆, c^π) < π/2` and `1` otherwise; the supremum is attained. -/
theorem lemma1_realized_worst_case_regret {n d : ℕ} (hn : 1 ≤ n) (hd : 2 ≤ d)
(cpi cstar : EuclideanSpace ℝ (Fin d)) (hcpi : cpi ∈ unitSphere d)
(hcstar : cstar ∈ unitSphere d) :
IsGreatest
{r : ℝ | ∃ (X : Set (EuclideanSpace ℝ (Fin n)))
(f : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin d))
(xpi xstar : EuclideanSpace ℝ (Fin n)),
IsActionSet X ∧ IsContext f ∧ xpi ∈ argminSet cpi X f ∧
xstar ∈ argminSet cstar X f ∧ r = inner ℝ (f xpi - f xstar) cstar}
(regretCap (vecAngle cstar cpi)) := by sorry
end CtxInvOpt.Offline
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.