Online Allocation with Unknown Shared Supply
Summary
This paper introduces the Online Shared Supply Allocation problem and proposes a deterministic threshold-proportional policy (GPA) that achieves a 4/3-approximation to the offline optimum. It also includes a learning-augmented extension to handle imperfect forecasts and demonstrates superior performance in synthetic and real-world experiments.
View Cached Full Text
Cached at: 05/11/26, 07:12 AM
# Online Allocation with Unknown Shared Supply Source: [https://arxiv.org/abs/2605.07080](https://arxiv.org/abs/2605.07080) [View PDF](https://arxiv.org/pdf/2605.07080) > Abstract:Many real\-world resource allocation systems, such as humanitarian logistics and vaccine distribution, must preposition limited supply across multiple locations before demand is realized while stockouts incur irreversible service losses\. To study this, we introduce the Online Shared Supply Allocation \(OSSA\) problem, a stateful online model in which a central hub allocates a finite, unknown supply to multiple sites facing sequential demand under fixed\-charge transportation costs and lost\-sales penalties\. Unlike classical make\-to\-stock or make\-to\-order inventory models, OSSA precludes backlogging and replenishment only hedges against future demand\. To tackle OSSA, we propose a deterministic threshold\-proportional policy GPA and prove that it achieves a $4/3$\-approximation to the offline optimum up to an additive term independent of the total supply\. We complement this with matching lower bounds showing that the $4/3$ ratio is tight and that the additive\-error dependence is unavoidable, even for randomized algorithms that know the total supply upfront\. Finally, we develop a learning\-augmented extension to GPA that principally incorporates imperfect forecasts \(e\.g\., from human experts or ML models\) commonly available in practice, enabling us to exploit high\-quality advice while being robust against arbitrary bad ones\. Synthetic and real\-world experiments show that GPA outperforms natural baselines with global supply is scarce\. ## Submission history From: Davin Choo \[[view email](https://arxiv.org/show-email/9fc0bcfc/2605.07080)\] **\[v1\]**Fri, 8 May 2026 00:59:11 UTC \(5,184 KB\)
Similar Articles
A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret
This paper introduces a first-order learning algorithm for online resource allocation that achieves constant expected additive regret independent of the horizon, using gradient ascent updates without solving linear programs or requiring nondegeneracy assumptions.
GAGPO: Generalized Advantage Grouped Policy Optimization
GAGPO proposes a critic-free RL method that uses a non-parametric grouped value proxy for step-level credit assignment in multi-turn agentic tasks, outperforming strong baselines on ALFWorld and WebShop.
Online Policy Evaluation for MDPs with Dynamic UBSR Measures
This paper proposes efficient online learning algorithms for policy evaluation in MDPs with dynamic utility-based shortfall risk (UBSR) measures under linear function approximation, introducing the UBSR-TD algorithm and demonstrating its convergence and practical effectiveness.
Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations
This paper presents a unified algorithmic framework for distributed online submodular maximization under partition matroid constraints, achieving sublinear (1-1/e)-regret guarantees for both full-information and bandit feedback. It also introduces a bounded stochastic pipage rounding scheme to ensure cumulative sampling violations remain sublinear.
PGPO: Potential-Guided Policy Optimization for Multi-Turn Agentic Tasks
PGPO proposes potential-guided policy optimization for multi-turn agentic tasks, enabling finer-grained credit assignment in LLM post-training and showing strong results on ALFWorld and WebShop benchmarks.