Network Revenue Management with Nonparametric Demand Learning : \sqrt{T}-regret and Polynomial Dimension Dependency

This paper studies the classic price-based network revenue management (NRM) problem with demand learning. The retailer dynamically decides prices of n products over a finite selling season (of length T) subject to m resource constraints, with the purpose of maximizing the cumulative revenue. In this paper, we focus on nonparametric demand model with some mild technical assumptions which are satisfied by most of the commonly used demand functions. We propose a robust ellipsoid method adapted to the NRM setting in a non-trivial manner, and this algorithm achieves the regret O(n^{3.5}\sqrt{T}\ln^6(nT)). This is the first result which achieves the regret of the form O(poly(n,m,\ln(T))\sqrt{T}) (where poly(n,m,\ln(T)) is a polynomial function of n,m,\ln(T)) in the current literature on nonparametric NRM problem. Furthermore, we demonstrate that the regret can be further improved to O(n\sqrt{T}\ln(nT)) given that the nonparametric demand is "nearly linear''. This improvement is achieved by a primal-dual algorithm which combines stochastic gradient descent and online convex optimization technique