2022/10/14 by Jiashuo Jiang, Will Ma, Jiang, Jiashuo +3 · 1 citation
Decision Sciences · Engineering · Social Sciences · #Auction Theory and Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Probability (math.PR) #Smart Parking Systems Research #Transportation Planning and Optimization
paper · pdf · doi:10.48550/arxiv.2210.07996
openalex publication_date 2022/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the classical Network Revenue Management (NRM) problem with accept/reject decisions and T IID arrivals. We consider a distributional form where each arrival must fall under a finite number of possible categories, each with a deterministic resource consumption vector, but a random value distributed continuously over an interval. We develop an online algorithm that achieves O(log2 T) regret under this model, with the only (necessary) assumption being that the probability densities are bounded away from 0. We derive a second result that achieves O(log T) regret under an additional assumption of second-order growth. To our knowledge, these are the first results achieving logarithmic-level regret in an NRM model with continuous values that do not require any kind of "non-degeneracy" assumptions. Our results are achieved via new techniques including a new method of bounding myopic regret, a "semi-fluid" relaxation of the offline allocation, and an improved bound on the "dual convergence".