Online resource allocation improved with replenishable budgets
Online Resource Allocation with Replenishable Budgets
Computer Science and Game Theory
Summary
Managing resources sequentially while respecting budgets is a common challenge, like in inventory or energy management. Traditional methods assume resources only get used up, but this work allows resources to be added back over time. The authors created an algorithm that adapts to both cases, performing well even when resources can be replenished. This approach ensures budget limits are never broken while improving performance guarantees when replenishment happens.
What this means in practice
- •For inventory managers: Optimize inventory control systems that allow stock replenishment to improve supply chain decisions under budget limits.
- •For energy grid operators: Manage energy resources dynamically by allocating capacity that can be both consumed and replenished over time to meet demand efficiently.
Authors
Eleonora Fidelia Chiefari, Francesco Emanuele Stradi, Alberto Marchesi
Abstract
Online Resource Allocation (ORA) is a fundamental framework for sequential decision-making problems under budget constraints. Classical ORA models typically assume that resources are monotonic, meaning that selecting actions can only decrease the available budget. In this work, we study a more general setting with replenishable budgets, in which actions may either consume or replenish resources over time. This extension is necessary to capture scenarios such as inventory systems or energy markets in which capacity can be actively recovered. We develop a dual-based algorithm that recovers best-of-both-worlds guarantees for standard ORA when the replenishment factor $β= 0$, and improves them when $β> 0$. In particular, our algorithm attains $\widetilde{\mathcal O}(\sqrt{T})$ regret in the stochastic setting and $\widetilde{\mathcal O}(\sqrt{T})$ $α$-regret in the adversarial setting, where $α$ depends on the per-round budget and on the replenishment factor of the void action. Moreover, the algorithm ensures strict satisfaction of the budget constraints.