Degeneracy Is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions

• 成果类型: Article; Early Access
• 署名作者: Jiang, Jiashuo; Ma, Will; Zhang, Jiawei
• 署名单位: Hong Kong University of Science & Technology; Columbia University; New York University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0641
• 发表日期: 2025
• 关键词: bid-price controls

摘要

We study the classic network revenue management (NRM) problem with accept/ reject decisions and T independent and identically distributed arrivals. We consider a distributional form in which 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 zero. 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 nondegeneracy assumptions. Our results are achieved via new techniques, including a new method of bounding myopic regret, a semifluid relaxation of the off-line allocation, and an improved bound on the dual convergence.