pipette
ESEspañol

Efficient Online Submodular Maximization with Bandit Feedback

Iasonas Nikolaou, Evimaria Terzi

PreprintClaims a big step

In the authors' words

We study online monotone submodular maximization under a cardinality constraint with bandit feedback. On each round, the learner selects at most elements from a ground set of size and observes only the value of the selected set. We develop an efficient algorithm achieving expected -regret over rounds. To our knowledge, this is the first polynomial-time algorithm with dependence on the horizon for arbitrary monotone submodular functions in the bandit setting. Our approach uses randomized sampling and a carefully constructed potential to reduce online submodular maximization to online linear optimization over the probability simplex.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 31 pages