pipette
ENEnglish

Efficient Online Submodular Maximization with Bandit Feedback

Iasonas Nikolaou, Evimaria Terzi

PreprintDice ser un gran avance

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 31 pages