Demand Balancing in Primal-Dual Optimization for Blind Network Revenue
  Management
Sentao Miao Yining Wang
This paper proposes a practically efficient algorithm with optimal
theoretical regret which solves the classical network revenue management (NRM)
problem with unknown, nonparametric demand. Over a time horizon of length $T$,
in each time period the retailer needs to decide prices of $N$ types of
products which are produced based on $M$ types of resources with
unreplenishable initial inventory. When demand is nonparametric with some mild
assumptions, Miao and Wang (2021) is the first paper which proposes an
algorithm with $O(\text{poly}(N,M,\ln(T))\sqrt{T})$ type of regret (in
particular, $\tilde O(N^{3.5}\sqrt{T})$ plus additional high-order terms that
are $o(\sqrt{T})$ with sufficiently large $T\gg N$). In this paper, we improve
the previous result by proposing a primal-dual optimization algorithm which is
not only more practical, but also with an improved regret of $\tilde
O(N^{3.25}\sqrt{T})$ free from additional high-order terms. A key technical
contribution of the proposed algorithm is the so-called demand balancing, which
pairs the primal solution (i.e., the price) in each time period with another
price to offset the violation of complementary slackness on resource inventory
constraints. Numerical experiments compared with several benchmark algorithms
further illustrate the effectiveness of our algorithm.