Learning-augmented Online Algorithm for Two-level Ski-rental Problem
- URL: http://arxiv.org/abs/2402.06715v1
- Date: Fri, 9 Feb 2024 16:10:54 GMT
- Title: Learning-augmented Online Algorithm for Two-level Ski-rental Problem
- Authors: Keyuan Zhang, Zhongdong Liu, Nakjung Choi, Bo Ji
- Abstract summary: We study the two-level ski-rental problem,where a user needs to fulfill a sequence of demands for multiple items by choosing one of three payment options.
We develop a learning-augmented algorithm (LADTSR) by integrating Machine Learning predictions into the robust online algorithm.
- Score: 8.381344684943212
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the two-level ski-rental problem,where a user needs
to fulfill a sequence of demands for multiple items by choosing one of the
three payment options: paying for the on-demand usage (i.e., rent), buying
individual items (i.e., single purchase), and buying all the items (i.e., combo
purchase). Without knowing future demands, the user aims to minimize the total
cost (i.e., the sum of the rental, single purchase, and combo purchase costs)
by balancing the trade-off between the expensive upfront costs (for purchase)
and the potential future expenses (for rent). We first design a robust online
algorithm (RDTSR) that offers a worst-case performance guarantee. While online
algorithms are robust against the worst-case scenarios, they are often overly
cautious and thus suffer a poor average performance in typical scenarios. On
the other hand, Machine Learning (ML) algorithms typically show promising
average performance in various applications but lack worst-case performance
guarantees. To harness the benefits of both methods, we develop a
learning-augmented algorithm (LADTSR) by integrating ML predictions into the
robust online algorithm, which outperforms the robust online algorithm under
accurate predictions while ensuring worst-case performance guarantees even when
predictions are inaccurate. Finally, we conduct numerical experiments on both
synthetic and real-world trace data to corroborate the effectiveness of our
approach.
Related papers
- Learning-augmented Online Minimization of Age of Information and
Transmission Costs [24.873041306990288]
We develop an online algorithm to minimize the sum of transmission and staleness costs, ensuring a worst-case performance guarantee.
While online algorithms are robust, they are usually overly conservative and may have a poor average performance in typical scenarios.
We show that our learning-augmented algorithm achieves both consistency and robustness.
arXiv Detail & Related papers (2024-03-05T01:06:25Z) - Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.029788598491077]
We study online conversion with switching costs, a family of online problems that capture emerging problems at the intersection of energy and sustainability.
We introduce competitive (robust) threshold-based algorithms for both the deterministic and deterministic variants of this problem.
We then propose learning-augmented algorithms that take advantage of black-box advice to achieve significantly better average-case performance.
arXiv Detail & Related papers (2023-10-31T16:34:49Z) - Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions.
We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers.
We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
arXiv Detail & Related papers (2023-02-02T16:30:33Z) - TransPath: Learning Heuristics For Grid-Based Pathfinding via
Transformers [64.88759709443819]
We suggest learning the instance-dependent proxies that are supposed to notably increase the efficiency of the search.
The first proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one.
The second proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path.
arXiv Detail & Related papers (2022-12-22T14:26:11Z) - Online Search with Predictions: Pareto-optimal Algorithm and its
Applications in Energy Markets [32.50099216716867]
This paper develops learning-augmented algorithms for energy trading in volatile electricity markets.
We incorporate machine-learned predictions to design competitive algorithms for online search problems.
arXiv Detail & Related papers (2022-11-12T04:12:10Z) - Online Adversarial Attacks [57.448101834579624]
We formalize the online adversarial attack problem, emphasizing two key elements found in real-world use-cases.
We first rigorously analyze a deterministic variant of the online threat model.
We then propose algoname, a simple yet practical algorithm yielding a provably better competitive ratio for $k=2$ over the current best single threshold algorithm.
arXiv Detail & Related papers (2021-03-02T20:36:04Z) - 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) - Cost-Efficient Online Hyperparameter Optimization [94.60924644778558]
We propose an online HPO algorithm that reaches human expert-level performance within a single run of the experiment.
Our proposed online HPO algorithm reaches human expert-level performance within a single run of the experiment, while incurring only modest computational overhead compared to regular training.
arXiv Detail & Related papers (2021-01-17T04:55:30Z) - 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) - Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice [14.139763648079537]
We study the problem of augmenting online algorithms with machine learned (ML) advice.
In particular, we consider the emphmulti-shop ski rental (MSSR) problem, which is a generalization of the classical ski rental problem.
We obtain both deterministic and randomized online algorithms with provably improved performance when either a single or multiple ML predictions are used to make decisions.
arXiv Detail & Related papers (2020-02-13T22:59:36Z)
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.