Online Resource Allocation under Horizon Uncertainty
- URL: http://arxiv.org/abs/2206.13606v3
- Date: Thu, 22 Jun 2023 20:56:00 GMT
- Title: Online Resource Allocation under Horizon Uncertainty
- Authors: Santiago Balseiro, Christian Kroer, Rachitesh Kumar
- Abstract summary: In revenue management and online advertising, number of requests can vary widely because of fluctuations in demand or user traffic intensity.
In this work, we develop online algorithms that are robust to horizon uncertainty.
In particular, our competitive ratio attains the optimal rate of growth (up to logarithmic factors) as the horizon uncertainty grows large.
- Score: 27.21119630468227
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study stochastic online resource allocation: a decision maker needs to
allocate limited resources to stochastically-generated sequentially-arriving
requests in order to maximize reward. At each time step, requests are drawn
independently from a distribution that is unknown to the decision maker. Online
resource allocation and its special cases have been studied extensively in the
past, but prior results crucially and universally rely on the strong assumption
that the total number of requests (the horizon) is known to the decision maker
in advance. In many applications, such as revenue management and online
advertising, the number of requests can vary widely because of fluctuations in
demand or user traffic intensity. In this work, we develop online algorithms
that are robust to horizon uncertainty. In sharp contrast to the known-horizon
setting, no algorithm can achieve even a constant asymptotic competitive ratio
that is independent of the horizon uncertainty. We introduce a novel
generalization of dual mirror descent which allows the decision maker to
specify a schedule of time-varying target consumption rates, and prove
corresponding performance guarantees. We go on to give a fast algorithm for
computing a schedule of target consumption rates that leads to near-optimal
performance in the unknown-horizon setting. In particular, our competitive
ratio attains the optimal rate of growth (up to logarithmic factors) as the
horizon uncertainty grows large. Finally, we also provide a way to incorporate
machine-learned predictions about the horizon which interpolates between the
known and unknown horizon settings.
Related papers
- Uncertainty Quantification for Forward and Inverse Problems of PDEs via
Latent Global Evolution [110.99891169486366]
We propose a method that integrates efficient and precise uncertainty quantification into a deep learning-based surrogate model.
Our method endows deep learning-based surrogate models with robust and efficient uncertainty quantification capabilities for both forward and inverse problems.
Our method excels at propagating uncertainty over extended auto-regressive rollouts, making it suitable for scenarios involving long-term predictions.
arXiv Detail & Related papers (2024-02-13T11:22:59Z) - Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences.
Our method is especially suitable for problems with well-specified likelihoods.
We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
arXiv Detail & Related papers (2023-11-08T00:10:21Z) - Fairness in Matching under Uncertainty [78.39459690570531]
algorithmic two-sided marketplaces have drawn attention to the issue of fairness in such settings.
We axiomatize a notion of individual fairness in the two-sided marketplace setting which respects the uncertainty in the merits.
We design a linear programming framework to find fair utility-maximizing distributions over allocations.
arXiv Detail & Related papers (2023-02-08T00:30:32Z) - Sequential Fair Resource Allocation under a Markov Decision Process
Framework [9.440900386313213]
We study the sequential decision-making problem of allocating a limited resource to agents that reveal their demands on arrival over a finite horizon.
We propose a new algorithm, SAFFE, that makes fair allocations with respect to the entire demands revealed over the horizon.
We show that SAFFE leads to more fair and efficient allocations and achieves close-to-optimal performance in settings with dense arrivals.
arXiv Detail & Related papers (2023-01-10T02:34:00Z) - 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) - 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) - The Best of Many Worlds: Dual Mirror Descent for Online Allocation
Problems [7.433931244705934]
We consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model unknown to the decision maker.
We design general class of algorithms that attain good performance in various input models without knowing which type of input they are facing.
Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online mirror descent.
arXiv Detail & Related papers (2020-11-18T18:39:17Z) - Coordinated Online Learning for Multi-Agent Systems with Coupled
Constraints and Perturbed Utility Observations [91.02019381927236]
We introduce a novel method to steer the agents toward a stable population state, fulfilling the given resource constraints.
The proposed method is a decentralized resource pricing method based on the resource loads resulting from the augmentation of the game's Lagrangian.
arXiv Detail & Related papers (2020-10-21T10:11:17Z) - Online Decision Trees with Fairness [8.949941684885323]
We propose a novel framework of online decision tree with fairness in the data stream with possible distribution drifting.
Specifically, first, we propose two novel fairness splitting criteria that encode the data as well as possible.
Second, we propose two fairness decision tree online growth algorithms that fulfills different online fair decision-making requirements.
arXiv Detail & Related papers (2020-10-15T02:50:13Z) - Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
We introduce the emphregularized online allocation problem, a variant that includes a non-linear regularizer acting on the total resource consumption.
In this problem, requests repeatedly arrive over time and, for each request, a decision maker needs to take an action that generates a reward and consumes resources.
The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints.
arXiv Detail & Related papers (2020-07-01T14:24:58Z)
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.