# An Improved Analysis of LP-based Control for Revenue Management

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2021.

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

- [OptMATH: A Scalable Bidirectional Data Synthesis Framework for Optimization Modeling](https://mlsanity.com/paper/2502.11102/) (2025)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Contextual Decision-Making with Knapsacks Beyond the Worst Case](https://mlsanity.com/paper/2211.13952/) (2022)
- [Decoupling Learning and Decision-Making: Breaking the O(√T) Barrier in Online Resource Allocation with First-Order Methods](https://mlsanity.com/paper/2402.07108/) (2024)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Online Learning for Equilibrium Pricing in Markets under Incomplete Information](https://mlsanity.com/paper/2303.11522/) (2023)
- [Wait-Less Offline Tuning and Re-solving for Online Decision Making](https://mlsanity.com/paper/2412.09594/) (2024)
- [Online Regenerative Learning](https://mlsanity.com/paper/2209.08657/) (2022)
- [A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming](https://mlsanity.com/paper/2603.14673/) (2026)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)
- [LLM-Powered Predictive Decision-Making for Sustainable Data Center Operations](https://mlsanity.com/paper/2608.18503/) (2026)
- [Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving](https://mlsanity.com/paper/2609.28263/) (2026)

## Abstract (arXiv)

In this paper, we study a class of revenue management problems where the decision maker aims to maximize the total revenue subject to budget constraints on multiple type of resources over a finite horizon. At each time, a new order/customer/bid is revealed with a request of some resource(s) and a reward, and the decision maker needs to either accept or reject the order. Upon the acceptance of the order, the resource request must be satisfied and the associated revenue (reward) can be collected. We consider a stochastic setting where all the orders are i.i.d. sampled, i.e., the reward-request pair at each time is drawn from an unknown distribution with finite support. The formulation contains many classic applications such as the quantity-based network revenue management problem and the Adwords problem. We focus on the classic LP-based adaptive algorithm and consider regret as the performance measure defined by the gap between the optimal objective value of the certainty-equivalent linear program (LP) and the expected revenue obtained by the online algorithm. Our contribution is two-fold: (i) when the underlying LP is nondegenerate, the algorithm achieves a problem-dependent regret upper bound that is independent of the horizon/number of time periods T; (ii) when the underlying LP is degenerate, the algorithm achieves a regret upper bound that scales on the order of √Tlog T. To our knowledge, both results are new and improve the best existing bounds for the LP-based adaptive algorithm in the corresponding setting. We conclude with numerical experiments to further demonstrate our findings.