Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1, p. 16 — the IRT policy has regret vHO−vIRT=O(1)v^{\mathrm{HO}} - v^{\mathrm{IRT}} = O(1)vHO−vIRT=O(1), uniformly in TTT and CCC

Proved
ResolvingNRM.IRT.irt_regret_uniformly_bounded

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

network-revenue-managementp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1re-solvingregret

Consider the network revenue-management model with nnn customer classes arriving as independent Poisson processes of rates λj>0\lambda_j > 0λj​>0, revenues rj≥0r_j \ge 0rj​≥0, and mmm resources consumed according to a nonnegative bill-of-materials matrix AAA. The Infrequent Re-solving with Thresholding (IRT) policy (Algorithm 3) re-solves the deterministic LP at the K=⌈log⁡log⁡T/log⁡(6/5)⌉K = \lceil\log\log T/\log(6/5)\rceilK=⌈loglogT/log(6/5)⌉ times tu∗=T−T(5/6)ut^*_u = T - T^{(5/6)^u}tu∗​=T−T(5/6)u, uses the LP solution, rounded to 000 or 111 by the thresholds τu−1/4\tau_u^{-1/4}τu−1/4​, as acceptance probabilities in every epoch but the last, and the unrounded probabilities xjK/λjx^K_j/\lambda_jxjK​/λj​ in the last epoch.

There is a constant MMM, depending only on (λ,r,A)(\lambda, r, A)(λ,r,A), such that for every choice of optimal LP solutions, every horizon T∈{1,2,… }T \in \{1, 2, \dots\}T∈{1,2,…} and every capacity vector C≥0C \ge 0C≥0,

vHO(T,C)−vIRT(T,C)≤M.v^{\mathrm{HO}}(T, C) - v^{\mathrm{IRT}}(T, C) \le M .vHO(T,C)−vIRT(T,C)≤M.

Since vHOv^{\mathrm{HO}}vHO 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: MMM is chosen after (n,m,λ,r,A)(n, m, \lambda, r, A)(n,m,λ,r,A) and before the optimal-solution selector, TTT and CCC (the paper's constant does not depend on which optimal solution the LP returns). The standing assumptions λ>0\lambda > 0λ>0, r≥0r \ge 0r≥0, A≥0A \ge 0A≥0, C≥0C \ge 0C≥0 are those of Sec. 2, p. 7, left implicit on the page. For T∈{1,2}T \in \{1, 2\}T∈{1,2} (that is, T≤eT \le eT≤e) the printed KKK is undefined or negative and the formalization takes K=0K = 0K=0 (IRT is SPA there). The re-solve right-hand side is the remaining capacity over the remaining time, C(tu∗)/τuC(t^*_u)/\tau_uC(tu∗​)/τu​ (Algorithm 3 prints the index kkk for uuu).

Preamble
import Mathlib
import Definitions.Def_RLPBidPrice_Unbiased_Model
import Definitions.Def_ResolvingNRM_IRT_Model

open RLPBidPrice.Unbiased Matrix
Formal statement
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
Source
Bumpensanti, Wang, A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management, arXiv:1802.06192v3, Theorem 1, p. 16; Algorithm 3, p. 15
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me