Handling General Constraints in Online Resource Allocation
Poster C: Tuesday -- 11:00 - 12:30
Eleonora Fidelia Chiefari, Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi
Keywords: Online Resource Allocation, Best-of-both-worlds
Online resource allocation (ORA) is a fundamental framework for sequential decision-making problems under budget constraints, with applications ranging from online advertising to revenue management. In this work, we study a broader setting that includes both budget constraints and general constraints, extending the classical budget-only model. This extension is essential for modeling critical economic requirements, such as Return-on-Investment (ROI) constraints.
We develop an algorithm that achieves best-of-both-world guarantees within this generalized framework. In particular, against a dynamic benchmark, our algorithm achieves $\widetilde{\mathcal O}(\sqrt{T})$ regret in the stochastic regime and $\alpha$-regret of order $\widetilde{\mathcal O}(\sqrt{T})$ in the adversarial regime, where $\alpha$ depends on the feasibility margin of the corresponding offline problem. At the same time, our algorithm guarantees strict satisfaction of the budget constraints and $\widetilde{\mathcal O}(\sqrt{T})$ cumulative violation for the general ones.
From a technical perspective, introducing general constraints alongside budgets precludes the use of standard budget-focus methods. While budget methods rely on a zero-consumption "safe" action to ensure feasibility, general constraints are much less "aligned" towards feasibility. We overcome these difficulties with a new analysis that exploits weak adaptivity to get boundedness of the Lagrangian multipliers and best-of-both-world guarantees.