Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints

In this paper, we study a class of online optimization problems with long-term budget constraints where the objective functions are not necessarily concave (nor convex) but they instead satisfy the Diminishing Returns (DR) property. Specifically, a sequence of monotone DR-submodular objective functions ft(x)t=1T and monotone linear budget functions langle pt,x rangle t=1T arrive over time and assuming a total targeted budget BT, the goal is to choose points xt at each time t∈1,dots,T, without knowing ft and pt on that step, to achieve sub-linear regret bound while the total budget violation sumt=1T langle pt,xt rangle -BT is sub-linear as well. Prior work has shown that achieving sub-linear regret is impossible if the budget functions are chosen adversarially. Therefore, we modify the notion of regret by comparing the agent against a (1-frac1e)-approximation to the best fixed decision in hindsight which satisfies the budget constraint proportionally over any window of length W. We propose the Online Saddle Point Hybrid Gradient (OSPHG) algorithm to solve this class of online problems. For W=T, we recover the aforementioned impossibility result. However, when W=o(T), we show that it is possible to obtain sub-linear bounds for both the (1-frac1e)-regret and the total budget violation.