Poster
Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints
Guanyu Nie · Vaneet Aggarwal · Christopher Quinn
West Ballroom A-D #5802
Abstract:
In this paper, we consider the problem of online monotone DR-submodular maximization subject to long-term stochastic constraints. Specifically, at each round , after committing an action , a random reward and an unbiased gradient estimate of the point (semi-bandit feedback) are revealed. Meanwhile, a budget of , which is linear and stochastic, is consumed of its total allotted budget . We propose a gradient ascent based algorithm that achieves -regret of with constraint violation with high probability. Moreover, when first-order full-information feedback is available, we propose an algorithm that achieves -regret of with constraint violation. These algorithms significantly improve over the state-of-the-art in terms of query complexity.
Chat is not available.