Efficient Online Submodular Maximization with Bandit Feedback
En palabras de los autores
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.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 31 pages