Abstract
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 types 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 $\sqrt{T}\log 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.
Introduction
In the world of online resource allocation—ranging from airline ticket pricing to cloud computing spot instances—the primary objective is to maximize revenue while adhering to strict budget constraints. The central challenge lies in making irrevocable decisions today without perfect knowledge of future demand. This paper provides a significant theoretical advancement for the LP-based adaptive algorithm, a widely used heuristic in revenue management.
Problem Formulation
The study focuses on the Online Revenue Management problem. A decision maker manages $m$ resource types over a time horizon of $T$ periods. Each period brings a customer with a specific resource request and a reward. The decision maker must immediately accept or reject the request. Success is measured by Regret: the difference between the revenue of an omniscient "Fluid" benchmark (the optimal solution to the certainty-equivalent LP) and the expected revenue of the online algorithm.
The LP-based Adaptive Algorithm
The authors analyze a "frequent re-solving" adaptive approach:
- Estimation: Use historical data to estimate the distribution of future customer types.
- Optimization: Solve a Linear Program (LP) to determine optimal "acceptance probabilities" based on current resource levels and remaining time.
- Action: Implement the decision based on these probabilities.
While this algorithm is popular in practice, its theoretical performance was previously thought to be limited to $O(\log T)$ regret in the best cases.
Theoretical Breakthroughs
The core contribution of this work is a new analytical framework using a regret decomposition that focuses on the dual view (resource consumption) rather than the primal view (decision variables). By using martingale concentration inequalities, the authors prove that the algorithm is naturally self-correcting: if it over-consumes a resource early on, the next LP it solves will automatically lower the acceptance probabilities to compensate.
Nondegenerate Case: Bounded Regret
The most striking finding is that for nondegenerate problems, the algorithm achieves Bounded Regret ($O(1)$). This implies that the revenue loss due to uncertainty does not grow with the time horizon $T$. This is a major improvement over the previously established $O(\log T)$ bounds for this algorithm.
Degenerate Case: Robust Performance
In "degenerate" scenarios—where the optimal LP solution is not unique or is highly sensitive—the authors prove a regret bound of $O(\sqrt{T} \log T)$. This provides a theoretical safety net for practitioners, showing the algorithm remains robust even in mathematically complex environments.
Comparison with Existing Literature
The results presented in this paper significantly advance the state-of-the-art for LP-based adaptive algorithms. By relaxing assumptions like distribution knowledge and improving regret bounds, this work bridges the gap between theoretical guarantees and practical performance.
Numerical Validation
Synthetic experiments with varying resource and customer types confirm these theoretical findings. In nondegenerate simulations, the regret curve flattens as $T$ increases, while in degenerate cases, it follows the predicted sub-linear growth, perfectly matching the theoretical predictions.
Conclusion
This research demonstrates that the classic re-solving adaptive algorithm is more powerful than previously understood. By achieving bounded regret in nondegenerate settings and robust bounds in degenerate ones, it reaffirms the effectiveness of LP-based control in revenue management. Future work may explore extending these results to continuous distributions or reducing the computational overhead of frequent re-solving.
Summary updated