# Single-Sample and Robust Online Resource Allocation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 63 references that are in the map.
- First posted on arXiv 5 May 2025.

## Builds on (most cited first, 24 of 24)

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Primal Beats Dual on Online Packing LPs in the Random-Order Model](https://mlsanity.com/paper/1311.2578/) (2013)
- [Prophet Inequalities with Limited Information](https://mlsanity.com/paper/1307.3736/) (2013)
- [How the Experts Algorithm Can Help Solve LPs Online](https://mlsanity.com/paper/1407.5298/) (2014)
- [Single-Sample Prophet Inequalities via Greedy-Ordered Selection](https://mlsanity.com/paper/2111.03174/) (2021)
- [Dynamic Placement in Refugee Resettlement](https://mlsanity.com/paper/2105.14388/) (2021)
- [Random-Order Models](https://mlsanity.com/paper/2002.12159/) (2020)
- [Online Weighted Matching with a Sample](https://mlsanity.com/paper/2104.05771/) (2021)
- [Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs](https://mlsanity.com/paper/1612.03161/) (2016)
- [Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems](https://mlsanity.com/paper/1903.03944/) (2019)
- [Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders](https://mlsanity.com/paper/1911.02716/) (2019)
- [Prophet Inequalities Require Only a Constant Number of Samples](https://mlsanity.com/paper/2311.09141/) (2023)
- [Prophet Inequalities with Linear Correlations and Augmentations](https://mlsanity.com/paper/2001.10600/) (2020)
- [An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions](https://mlsanity.com/paper/2004.09784/) (2020)
- [Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality](https://mlsanity.com/paper/2011.06516/) (2020)
- [Online Combinatorial Allocations and Auctions with Few Samples](https://mlsanity.com/paper/2409.11091/) (2024)
- [Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier](https://mlsanity.com/paper/2010.01420/) (2020)
- [Robust Secretary and Prophet Algorithms for Packing Integer Programs](https://mlsanity.com/paper/2112.12920/) (2021)
- [Robust Algorithms under Adversarial Injections](https://mlsanity.com/paper/2004.12667/) (2020)
- [Knapsack Secretary with Bursty Adversary](https://mlsanity.com/paper/2006.11607/) (2020)
- [Online Contention Resolution Schemes for Network Revenue Management and Combinatorial Auctions](https://mlsanity.com/paper/2403.05378/) (2024)

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

- [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)
- [A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming](https://mlsanity.com/paper/2603.14673/) (2026)

## Abstract (arXiv)

Online Resource Allocation problem is a central problem in many areas of Computer Science, Operations Research, and Economics. In this problem, we sequentially receive n stochastic requests for m kinds of shared resources, where each request can be satisfied in multiple ways, consuming different amounts of resources and generating different values. The goal is to achieve a (1-ε)-approximation to the hindsight optimum, where ε>0 is a small constant, assuming each resource has a large budget. In this paper, we investigate the learnability and robustness of online resource allocation. Our primary contribution is a novel Exponential Pricing algorithm with the following properties: 1. It requires only a single sample from each of the n request distributions to achieve a (1-ε)-approximation for online resource allocation with large budgets. Such an algorithm was previously unknown, even with access to polynomially many samples, as prior work either assumed full distributional knowledge or was limited to i.i.d.,or random-order arrivals. 2. It is robust to corruptions in the outliers model and the value augmentation model. Specifically, it maintains its (1 - ε)-approximation guarantee under both these robustness models, resolving the open question posed in Argue, Gupta, Molinaro, and Singla (SODA'22). 3. It operates as a simple item-pricing algorithm that ensures incentive compatibility. The intuition behind our Exponential Pricing algorithm is that the price of a resource should adjust exponentially as it is overused or underused. It differs from conventional approaches that use an online learning algorithm for item pricing. This departure guarantees that the algorithm will never run out of any resource, but loses the usual no-regret properties of online learning algorithms, necessitating a new analytical approach.