Lemma 4, p. 20 — if C(I_t) ⊆ E(W_t, U_t) and the test (12) holds, the period's regret is at most ε
ProvedCtxInvOpt.Pointed.lemma4_low_regret_periodellipsoidal-coneinverse-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Let , , let and , and let the expert actions be optimal for . Fix a period with and , a positive definite diagonal and an orthonormal such that
Let the policy play , let be the effective difference and . If (12) holds, , then the one-period regret is at most :
Periods that pass the test are therefore cheap, and EllipsoidalCones does not spend a cone update on them.
Formalization Note Lean period is the paper's , and knowledgeSet C0 X f xstar t is the paper's . The paper's parameter is a hypothesis (for the test can hold while the regret is ).
Preamble
import Mathlib import Definitions.Def_CtxInvOpt_Greedy_Online import Definitions.Def_CtxInvOpt_Pointed_EllCone
Formal statement
namespace CtxInvOpt.Pointed
open Matrix
/-- **Lemma 4, p. 20.** Let `C(I_t) ⊆ E(W_t, U_t)` (Lean period `t`, the paper's `t + 1`), where the
knowledge set is built from `C₀ ⊆ S^d` and expert actions optimal for `c⋆ ∈ C₀`. If the policy plays
`x^π_t ∈ ψ(U_t e₁, X_t, f_t)` and the test (12) `δ̄′_{[2:d]} W_t δ̄_{[2:d]} ≤ ε²` holds for
`δ̄ = U_t⁻¹δ^π_t`, then the one-period regret `(f_t(x^π_t) − f_t(x⋆_t))′c⋆` is at most `ε`. -/
theorem lemma4_low_regret_period {n m : ℕ} {ε : ℝ} (hε : 0 < ε)
(C0 : Set (EuclideanSpace ℝ (Fin (m + 1)))) (hC0 : C0 ⊆ CtxInvOpt.Offline.unitSphere (m + 1))
(cstar : EuclideanSpace ℝ (Fin (m + 1))) (hcstar : cstar ∈ C0)
(X : ℕ → Set (EuclideanSpace ℝ (Fin n)))
(f : ℕ → EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin (m + 1)))
(xstar : ℕ → EuclideanSpace ℝ (Fin n))
(hxstar : ∀ s, xstar s ∈ CtxInvOpt.Offline.argminSet cstar (X s) (f s))
(t : ℕ) (hX : CtxInvOpt.Offline.IsActionSet (X t)) (hf : CtxInvOpt.Offline.IsContext (f t))
(w : Fin m → ℝ) (hw : ∀ i, 0 < w i)
(U : Matrix (Fin (m + 1)) (Fin (m + 1)) ℝ) (hU : U ∈ Matrix.orthogonalGroup (Fin (m + 1)) ℝ)
(hK : CtxInvOpt.Greedy.knowledgeSet C0 X f xstar t ⊆ ellCone w U)
(xpi : EuclideanSpace ℝ (Fin n)) (hxpi : xpi ∈ CtxInvOpt.Offline.argminSet (axisVec U) (X t) (f t))
(h12 : tailQuad w (rotCoord U (effDiff (f t xpi - f t (xstar t)))) ≤ ε ^ 2) :
inner ℝ (f t xpi - f t (xstar t)) cstar ≤ ε := by sorry
end CtxInvOpt.Pointed
Source
Besbes, Fonseca, Lobel, Contextual Inverse Optimization: Offline and Online Learning, arXiv:2106.14015v3, p. 20, Lemma 4; proof App-12–App-13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.