Online Resource Allocation With General Constraints

Abstract

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 \emph{stochastic} regime and $α$-regret of order $\widetilde{\mathcal O}(\sqrt{T})$ in the \emph{adversarial} regime, where $α$ 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 \emph{weak adaptivity} to get boundedness of the Lagrangian multipliers and best-of-both-world guarantees.