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

• URL: http://arxiv.org/abs/2404.04467v1
• Date: Sat, 6 Apr 2024 01:39:51 GMT
• Title: Demand Balancing in Primal-Dual Optimization for Blind Network Revenue Management
• Authors: Sentao Miao, Yining Wang,
• Abstract summary: This paper proposes a practically efficient algorithm with optimal theoretical regret which solves the classical network revenue management problem with unknown, nonparametric demand. A key technical contribution 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 slackness on resource inventory constraints.
• Score: 6.72809363581332
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: 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.

Related papers

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  We study the generalized low-rank matrix bandit problem, proposed in citelu2021low under the Generalized Linear Model (GLM) framework. To overcome the computational infeasibility and theoretical restrain of existing algorithms, we first propose the G-ESTT framework. We show that G-ESTT can achieve the $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret while G-ESTS can achineve the $tildeO
  arXiv  Detail & Related papers  (2024-01-14T14:14:19Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  We show how to achieve minimax-optimal regret without incurring any burn-in cost. We extend our theory to unveil the influences of problem-dependent quantities like the optimal value/cost and certain variances.
  arXiv  Detail & Related papers  (2023-07-25T15:42:11Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Learning to Order for Inventory Systems with Lost Sales and Uncertain Supplies [21.690446677016247]
  We consider a lost-sales inventory control system with a lead time $L$ over a planning horizon $T$. Supply is uncertain, and is a function of the order quantity. We show that our algorithm achieves a regret (i.e. the performance gap between the cost of our algorithm and that of an optimal policy over $T$ periods) of $O(L+sqrtT)$ when $Lgeqlog(T)$.
  arXiv  Detail & Related papers  (2022-07-10T22:11:32Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  We study human-in-the-loop reinforcement learning (RL) with trajectory preferences. Instead of receiving a numeric reward at each step, the agent only receives preferences over trajectory pairs from a human overseer. We propose the first optimistic model-based algorithm for PbRL with general function approximation.
  arXiv  Detail & Related papers  (2022-05-23T09:03:24Z)
• An Accelerated Stochastic Algorithm for Solving the Optimal Transport Problem [2.1485350418225244]
  A primal-dual accelerated gradient descent with variance reduction algorithm (PDASGD) is proposed to solve linear-constrained optimization problems. PDASGD enjoys the best-known computational complexity -- $widetildemathcalO(n2/epsilon)$, where $n$ is the number of atoms, and $epsilon>0$ is the accuracy.
  arXiv  Detail & Related papers  (2022-03-02T01:16:10Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  We consider an online allocation problem subject to lower and upper resource constraints, where the requests arrive sequentially. We propose a new algorithm that obtains $1-O(fracepsilonalpha-epsilon)$ -competitive ratio for the offline problems that know the entire requests ahead of time.
  arXiv  Detail & Related papers  (2021-12-28T02:21:06Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  Policy-based method in citetshani 2020optimistic is only $tildeO(sqrtSAH3K + sqrtAH4K)$ where $S$ is the number of states, $A$ is the number of actions, $H$ is the horizon, and $K$ is the number of episodes, and there is a $sqrtSH$ gap compared with the information theoretic lower bound $tildeOmega(sqrtSAH
  arXiv  Detail & Related papers  (2021-12-21T01:54:17Z)
• Constant Regret Re-solving Heuristics for Price-based Revenue Management [17.344365325417602]
  We show that a natural re-solving attains $O(1)$ regret compared to the value of the optimal policy. We also prove that there is an $Omega(ln T)$ gap between the value of the optimal policy and that of the fluid model.
  arXiv  Detail & Related papers  (2020-09-07T02:28:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.