A Unifying Framework for Online Optimization with Long-Term Constraints

We study online learning problems in which a decision maker has to take a sequence of decisions subject to m long-term constraints. The goal of the decision maker is to maximize their total reward, while at the same time achieving small cumulative constraints violations across the T rounds. We present the first best-of-both-world type algorithm for this general class of problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown stochastic model, and in the case in which they are selected at each round by an adversary. Our algorithm is the first to provide guarantees in the adversarial setting with respect to the optimal fixed strategy that satisfies the long-term constraints. In particular, it guarantees a \rho/(1 \rho) fraction of the optimal utility and sublinear regret, where \rho is a feasibility parameter related to the existence of strictly feasible solutions.