Eq. (13), p. 29 — regret of IRT is
ProvedResolvingNRM.IRT.regret_decompositionFix the data of the network revenue-management model: Poisson rates , revenues and a nonnegative bill-of-materials matrix . For let be the policy that re-solves the DLP at the times , , with thresholded acceptance probabilities in the epochs before the last re-solve and plain probabilities in the last epoch .
There are constants and , depending only on , such that for every choice of optimal DLP solutions, every , every capacity and every number of re-solves ,
With this is the regret of IRT itself, and the right-hand side is then bounded independently of ; with it recovers SPA's regret against the hindsight optimum.
Formalization Note The paper states (13) for "the decision maker re-solves times" after an induction on the number of re-solves; the statement here holds for every number of re-solves, with constants uniform in , and is the instance used for Theorem 1. The exponent is raised to , i.e. . is existential for the reason given at Proposition 1. The standing assumptions are those of Sec. 2, p. 7. The horizon is a real .
import Mathlib import Definitions.Def_RLPBidPrice_Unbiased_Model import Definitions.Def_ResolvingNRM_IRT_Model open RLPBidPrice.Unbiased Matrix
namespace ResolvingNRM.IRT
theorem regret_decomposition {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) :
∃ κ : ℝ, 0 < κ ∧ ∃ M : ℝ, ∀ sel : (Fin m → ℝ) → (Fin n → ℝ), IsDLPSelector A r lam sel →
∀ T : ℝ, 1 ≤ T → ∀ C : Fin m → ℝ, 0 ≤ C → ∀ K' : ℕ,
hindsightValue A r lam T C - irtValue A r lam sel K' T C ≤
M * (∑ u ∈ Finset.range K',
T ^ ((5 / 6 : ℝ) ^ u) * Real.exp (-κ * T ^ ((5 / 6 : ℝ) ^ u / 6))) +
M * T ^ ((5 / 6 : ℝ) ^ K' / 2) := by sorry
end ResolvingNRM.IRT
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.