Skip to yearly menu bar Skip to main content


Poster

Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints

Guanyu Nie · Vaneet Aggarwal · Christopher Quinn

West Ballroom A-D #5802
[ ]
[ Paper [ Poster [ OpenReview
Thu 12 Dec 11 a.m. PST — 2 p.m. PST

Abstract: In this paper, we consider the problem of online monotone DR-submodular maximization subject to long-term stochastic constraints. Specifically, at each round t[T], after committing an action xt, a random reward ft(xt) and an unbiased gradient estimate of the point ~ft(xt) (semi-bandit feedback) are revealed. Meanwhile, a budget of gt(xt), which is linear and stochastic, is consumed of its total allotted budget BT. We propose a gradient ascent based algorithm that achieves 12-regret of O(T) with O(T3/4) constraint violation with high probability. Moreover, when first-order full-information feedback is available, we propose an algorithm that achieves (11/e)-regret of O(T) with O(T3/4) constraint violation. These algorithms significantly improve over the state-of-the-art in terms of query complexity.

Chat is not available.