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 a 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 nontrivial manner. This is the first result which achieves the regret of the form $O(\text{poly}(n,m,\ln (T))\sqrt{T})$ (where $\text{poly}(n,m,\ln (T))$ is a polynomial function of $n,m,\ln (T)$) in the current literature on the nonparametric NRM problem.

Funding: S. Miao gratefully acknowledges financial support provided by the Ruegg Family Scholar and the Leeds School of Business.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2022.0086.