Single-Leg Revenue Management with Advice

• URL: http://arxiv.org/abs/2202.10939v3
• Date: Thu, 22 Jun 2023 20:34:48 GMT
• Title: Single-Leg Revenue Management with Advice
• Authors: Santiago Balseiro, Christian Kroer, Rachitesh Kumar
• Abstract summary: We look at the single-leg revenue management problem through the lens of the algorithms-with-advice framework. We characterize the tradeoff between consistency (performance when advice is accurate) and competitiveness (performance when advice is inaccurate) for every advice. We also study the class of protection level policies, which is the most widely-deployed technique for single-leg revenue management.
• Score: 27.21119630468227
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Single-leg revenue management is a foundational problem of revenue management that has been particularly impactful in the airline and hotel industry: Given $n$ units of a resource, e.g. flight seats, and a stream of sequentially-arriving customers segmented by fares, what is the optimal online policy for allocating the resource. Previous work focused on designing algorithms when forecasts are available, which are not robust to inaccuracies in the forecast, or online algorithms with worst-case performance guarantees, which can be too conservative in practice. In this work, we look at the single-leg revenue management problem through the lens of the algorithms-with-advice framework, which attempts to harness the increasing prediction accuracy of machine learning methods by optimally incorporating advice about the future into online algorithms. In particular, we characterize the Pareto frontier that captures the tradeoff between consistency (performance when advice is accurate) and competitiveness (performance when advice is inaccurate) for every advice. Moreover, we provide an online algorithm that always achieves performance on this Pareto frontier. We also study the class of protection level policies, which is the most widely-deployed technique for single-leg revenue management: we provide an algorithm to incorporate advice into protection levels that optimally trades off consistency and competitiveness. Moreover, we empirically evaluate the performance of these algorithms on synthetic data. We find that our algorithm for protection level policies performs remarkably well on most instances, even if it is not guaranteed to be on the Pareto frontier in theory. Our results extend to other unit-cost online allocations problems such as the display advertising and the multiple secretary problem together with more general variable-cost problems such as the online knapsack problem.

Related papers

• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  We propose a new framework in which the smoothness in the performance of the algorithm is enforced by means of a user-specified profile. We apply this new approach to a well-studied online problem, namely the one-way trading problem.
  arXiv  Detail & Related papers  (2024-08-07T23:15:21Z)
• Online Resource Allocation with Convex-set Machine-Learned Advice [27.662388663465006]
  We introduce a parameterized class of optimal online resource allocation algorithms that strike a balance between consistent and robust ratios. Specifically, in a C-reto optimal setting, we maximize the consistent ratio while ensuring that the robust ratio is at least C.
  arXiv  Detail & Related papers  (2023-06-21T14:09:33Z)
• Theoretically Principled Federated Learning for Balancing Privacy and Utility [61.03993520243198]
  We propose a general learning framework for the protection mechanisms that protects privacy via distorting model parameters. It can achieve personalized utility-privacy trade-off for each model parameter, on each client, at each communication round in federated learning.
  arXiv  Detail & Related papers  (2023-05-24T13:44:02Z)
• Online Resource Allocation: Bandits feedback and Advice on Time-varying Demands [12.081877372552606]
  We consider a general online resource allocation model with bandit feedback and time-varying demands. Motivated by the recent Online Algorithms with Advice framework, we explore how online advice can inform policy design. Our proposed algorithm is shown to have both theoretical performance and promising numerical results compared with other algorithms in literature.
  arXiv  Detail & Related papers  (2023-02-08T16:40:43Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  Various algorithms for reinforcement learning (RL) exhibit dramatic variation in their convergence rates as a function of problem structure. This research provides guarantees that explain textitex post the performance differences observed. A natural next step is to convert these theoretical guarantees into guidelines that are useful in practice.
  arXiv  Detail & Related papers  (2022-01-21T04:25:35Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  We study the nature of both the optimization and learning problems. We provide an algorithm, namely GCB, guaranteeing sublinear regret at the cost of a potentially linear number of constraints violations. More interestingly, we provide an algorithm, namely GCB_safe(psi,phi), guaranteeing both sublinear pseudo-regret and safety w.h.p. at the cost of accepting tolerances psi and phi.
  arXiv  Detail & Related papers  (2022-01-18T17:24:20Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)
• Online Apprenticeship Learning [58.45089581278177]
  In Apprenticeship Learning (AL), we are given a Markov Decision Process (MDP) without access to the cost function. The goal is to find a policy that matches the expert's performance on some predefined set of cost functions. We show that the OAL problem can be effectively solved by combining two mirror descent based no-regret algorithms.
  arXiv  Detail & Related papers  (2021-02-13T12:57:51Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. The goal is to design algorithms that are both consistent and robust. We provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions.
  arXiv  Detail & Related papers  (2020-10-22T04:51:01Z)

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.