Improved algorithms for selecting best item sets with limited feedback
Efficient Online Submodular Maximization with Bandit Feedback
Machine Learning
Summary
Sometimes we want to pick the best group of things from a big collection, but we only get very limited information about how good our choices are. This paper shows a new way for a computer to learn how to make better choices over time, even when it only sees the result of what it picked, not what it could have picked. The authors created an efficient method that keeps getting smarter as it tries more rounds, and it's the first that works well for a wide range of these problems. Their approach changes the hard problem into a simpler one that experts already know how to handle.
What this means in practice
- •For online advertisers: Choose ad groups efficiently over time with limited feedback on performance to maximize engagement or sales.$Commercial implications: Enables better ad selection algorithms that learn from limited click data, improving targeting and campaign outcomes.
- •For recommendation system engineers: Improve item recommendation sets when only ratings for recommended items are observed, adapting quickly and efficiently.
Authors
Iasonas Nikolaou, Evimaria Terzi
Abstract
We study online monotone submodular maximization under a cardinality constraint with bandit feedback. On each round, the learner selects at most $k$ elements from a ground set of size $n$ and observes only the value of the selected set. We develop an efficient algorithm achieving $O\!\left(k\sqrt{nT\log(n/k)}\right)$ expected $(1-1/e)$-regret over $T$ rounds. To our knowledge, this is the first polynomial-time algorithm with $\sqrt{T}$ 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.