论文标题
堕落是可以的：网络收入管理的对数遗憾与不差异分布
Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions
论文作者
论文摘要
我们研究了接受/拒绝决策和$ t $ iid到达的经典网络收入管理（NRM）问题。我们考虑每次到达必须属于有限数量的可能类别的分布形式，每个类别都具有确定性的资源消耗向量，但随机值在间隔上连续分布。我们开发了一种在线算法，该算法在该模型下实现了$ o（\ log^2 t）$遗憾，唯一的（必要）假设是概率密度远离0。我们得出了第二阶增长的$ O（\ log t）$遗憾的第二个结果。据我们所知，这些是在NRM模型中获得对数级别后悔的第一个结果，该模型的持续价值不需要任何形式的“非分类”假设。我们的结果是通过新技术来实现的，包括一种新的近视遗憾的方法，对离线分配的“半流体”放松，以及对“双重融合”的改进。
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(\log^2 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".
