Degeneracy Is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions
放松了非退化假设，为具有一般非离散奖励分布的网络收益管理问题实现了对数遗憾，开发了包括短视遗憾边界、半流体松弛和对偶收敛改进等新技术。
The network revenue management problem is a fundamental problem in online decision making with resource constraints. Tremendous efforts have been devoted to deriving near-optimal policies for the network revenue management problem with a theoretical guarantee better than the classic $O(\sqrt{T})$ regret. Logarithmic or better regret has been derived, however, with an additional nondegeneracy assumption that requires the underlying fluid approximation to enjoy a unique optimal basis. This work relaxes the nondegeneracy assumption and achieves logarithmic regret for network revenue management problems for general indiscrete reward distribution. To achieve these advances, this work develops several 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, which has the potential to inspire other works. All in all, this work takes a fundamental step toward relaxing the nondegeneracy assumption, which traditionally limits the scope of online algorithms.