# Demand Balancing in Primal-Dual Optimization for Blind Network Revenue Management

arXiv: https://arxiv.org/abs/2404.04467 · HTML: https://mlsanity.com/paper/2404.04467/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 56 references that are in the map.
- First posted on arXiv 6 Apr 2024.

## Builds on (most cited first, 8 of 8)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [On Hyperparameter Optimization of Machine Learning Algorithms: Theory and Practice](https://mlsanity.com/paper/2007.15745/) (2020)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)

## Built on by (most cited first, 2 of 2)

- [Dynamic Pricing with Adversarially-Censored Demands](https://mlsanity.com/paper/2502.06168/) (2025)
- [Resource-Adaptive Primal-Dual Learning for One-Warehouse Multi-Store Systems with Censored Demand](https://mlsanity.com/paper/2608.14096/) (2026)

## Abstract (arXiv)

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(poly(N,M,ln(T))√T) type of regret (in particular, tilde O(N3.5√T) plus additional high-order terms that are o(√T) with sufficiently large Tgg 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(N3.25√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.