cs.LGNov 9, 2026

Efficient Online Submodular Maximization with Bandit Feedback

Authors: Iasonas Nikolaou, Evimaria Terzi

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 kk elements from a ground set of size nn and observes only the value of the selected set. We develop an efficient algorithm achieving O ⁣(knTlog⁡(n/k))O\!\left(k\sqrt{nT\log(n/k)}\right) expected (1−1/e)(1-1/e)-regret over TT rounds. To our knowledge, this is the first polynomial-time algorithm with T\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.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations

    Jul 1, 2026Bin Du, Chang Liu, Dingqi Zhu +2Submodular OptimizationDistributed Optimization