Sec. 2.2.2, p. 9 — the hindsight optimum is at most the DLP value:
ProvedResolvingNRM.IRT.hindsight_le_dlpConsider the network revenue-management model with classes of Poisson rates , revenues and a nonnegative bill-of-materials matrix . For every horizon and every capacity vector , the hindsight optimum is bounded by the value of the deterministic LP:
Together with this makes the hindsight optimum a tighter upper bound than the DLP; it is what turns Proposition 5's bound against the DLP into a bound on the regret against the hindsight optimum.
Formalization Note Only the second inequality of the display is stated: the optimal value over all admissible policies is not defined in this mission. The positivity of the rates and the nonnegativity of and are the standing assumptions of Sec. 2, p. 7, which the page leaves implicit. The horizon is real.
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model import Definitions.Def_ResolvingNRM_IRT_Model open RLPBidPrice.Unbiased Matrix
namespace ResolvingNRM.IRT
theorem hindsight_le_dlp {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (r lam : Fin n → ℝ)
(hlam : ∀ j, 0 < lam j) (hr : ∀ j, 0 ≤ r j) (hA : ∀ l j, 0 ≤ A l j)
(T : ℝ) (hT : 0 < T) (C : Fin m → ℝ) (hC : 0 ≤ C) :
hindsightValue A r lam T C ≤ dlpValue A r lam T C := by sorry
end ResolvingNRM.IRT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.