Efficient Online Submodular Maximization with Bandit Feedback
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