Theorem 1, p. 16 — the IRT policy has regret , uniformly in and
ProvedResolvingNRM.IRT.irt_regret_uniformly_boundedConsider the network revenue-management model with customer classes arriving as independent Poisson processes of rates , revenues , and resources consumed according to a nonnegative bill-of-materials matrix . The Infrequent Re-solving with Thresholding (IRT) policy (Algorithm 3) re-solves the deterministic LP at the times , uses the LP solution, rounded to or by the thresholds , as acceptance probabilities in every epoch but the last, and the unrounded probabilities in the last epoch.
There is a constant , depending only on , such that for every choice of optimal LP solutions, every horizon and every capacity vector ,
Since bounds the expected revenue of every admissible policy, IRT loses a bounded amount of revenue against the optimal policy, whatever the horizon and the capacities, and in particular without any nondegeneracy assumption on the DLP.
Formalization Note The quantifier order is the content of the theorem: is chosen after and before the optimal-solution selector, and (the paper's constant does not depend on which optimal solution the LP returns). The standing assumptions , , , are those of Sec. 2, p. 7, left implicit on the page. For (that is, ) the printed is undefined or negative and the formalization takes (IRT is SPA there). The re-solve right-hand side is the remaining capacity over the remaining time, (Algorithm 3 prints the index for ).
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model import Definitions.Def_ResolvingNRM_IRT_Model open RLPBidPrice.Unbiased Matrix
namespace ResolvingNRM.IRT
theorem irt_regret_uniformly_bounded {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) :
∃ M : ℝ, ∀ sel : (Fin m → ℝ) → (Fin n → ℝ), IsDLPSelector A r lam sel →
∀ T : ℕ, 1 ≤ T → ∀ C : Fin m → ℝ, 0 ≤ C →
hindsightValue A r lam (T : ℝ) C - irtValue A r lam sel (Kirt T) (T : ℝ) C ≤ M := by sorry
end ResolvingNRM.IRT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.