Efficient Online Submodular Maximization with Bandit Feedback
Organizations: Boston University
Abstract
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.
Figures & tables
| Paper | Setting | Function class | Constraint | Bandit regret |
| Streeter and Golovin (2008) | Adv. | Sub. | Card. | |
| Streeter et al. (2009) | Adv. | Sub. | Assign. | |
| Zhang et al. (2019) | Adv. | DR-S / Sub. | Downward-closed convex / Gen. matroid | |
| Nie et al. (2022) | Stoch. | Sub. | Card. | |
| Niazadeh et al. (2023) | Adv. | Sub. | Card. | |
| Wan et al. (2023) | Adv. | Sub. | Part. |
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | Task types | |||
| Influence | 34 | 2 | Fresh live-edge graph | |
| TeamFormation | 100 | 3 | 10 | |
| Coverage | 100 | 3 | 10 |
| Dataset | Sub-EW | MSE3 | OpaqueGreedy | Bandit-IG |
| Influence | 4 | 4 | 16 | 64 |
| TeamFormation | 4 | 4 | 64 | 64 |
| Coverage | 4 | 4 | 64 | 64 |
| Dataset | BanditMLSM | Poisson-BE | ||
| Influence | 128 | 0.2 | 16 | |
| TeamFormation | 512 | 0.2 | 256 | |
| Coverage | 512 | 0.2 | 256 | |
Submodular Optimization
Submodular optimization studies efficient selection and allocation when each added item tends to provide diminishing returns.
See all 61 papers