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.