A Single Recipe for Online Submodular Maximization with Adversarial or Stochastic Constraints

In this paper, we consider an online optimization problem in which the reward functions are DR-submodular, and in addition to maximizing the total reward, the sequence of decisions must satisfy some convex constraints on average. Specifically, at each round t ∈ 1, . . . , T , upon committing to an action x t , a DR-submodular utility function f t (•) and a convex constraint function g t (•) are revealed, and the goal is to maximize the overall utility while ensuring the average of the constraint functions 1 T T t=1 g t (x t ) is non-positive. Such cumulative constraints arise naturally in applications where the average resource consumption is required to remain below a prespecified threshold. We study this problem under an adversarial model and a stochastic model for the convex constraints, where the functions g t can vary arbitrarily or according to an i.i.d. process over time slots t ∈ 1, . . . , T , respectively. We propose a single algorithm which achieves sub-linear (with respect to T ) regret as well as sub-linear constraint violation bounds in both settings, without prior knowledge of the regime. Prior works have studied this problem in the special case of linear constraint functions. Our results not only improve upon the existing bounds under linear cumulative constraints, but also give the first sub-linear bounds for general convex long-term constraints.