Adaptive Parametric and Nonparametric Multi-Product Pricing via Self-Adjusting Controls

We study a multi-period network revenue management (RM) problem where a seller sells multiple products made from multiple resources with finite capacity in an environment where the demand function is unknown a priori. The objective of the seller is to jointly learn the demand and price the products to minimize his expected revenue loss. Both the parametric and the nonparametric cases are considered in this paper. It is widely known in the literature that the revenue loss of any pricing policy under either case is at least k^{1/2} However, there is a considerable gap between this lower bound and the performance bound of the best known heuristic in the literature. To close the gap, we develop several self-adjusting heuristics with strong performance bound. For the general parametric case, our proposed Parametric Self-adjusting Control (PSC) attains a O(k^{1/2}) revenue loss, matching the theoretical lower bound. If the parametric demand function family further satisfies a well-separated condition, by taking advantage of passive learning, our proposed Accelerated Parametric Self-adjusting Control achieves a much sharper revenue loss of O(log^2 k). For the nonparametric case, our proposed Nonparametric Self-adjusting Control (NSC) obtains a revenue loss of O(k^{1/2+ϵ} log k) for any arbitrarily small ϵ > 0 if the demand function is sufficiently smooth. Our results suggest that in terms of performance, the nonparametric approach can be as robust as the parametric approach, at least asymptotically. All the proposed heuristics are computationally very efficient and can be used as a baseline for developing more sophisticated heuristics for large-scale problems