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

Aug 25, 2026

Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy

We study adversarial bandit maximization of monotone submodular functions under a matroid constraint. For a rank-kk matroid on nn elements, we give a randomized oracle-polynomial algorithm that makes one feasible value query per round and has expected (1−1/e)(1-1/e)-regret O~(n1/3k2/3T2/3)\widetilde O(n^{1/3}k^{2/3}T^{2/3}). This is the first sublinear-regret algorithm for adversarial bandit submodular maximization under general matroid constraints. Technically, we view the problem as learning an exchange policy for the Poisson base walk. This connects the problem to contextual bandits and gives an information-theoretic sublinear-regret guarantee, but directly learning the exponentially many policies requires exponential time and space. We therefore introduce balanced fractional exchanges, which compress the policy mixture into a single fractional base while retaining the exchange information needed by the Poisson analysis. This leads to an polynomial time algorithm with the same regret guarantee.
Jul 1, 2026

Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations

We study distributed online submodular maximization under partition matroid constraints, in which multiple agents select a limited number of actions from their own subsets sequentially to maximize the cumulative value of a sequence of objective functions. We develop a unified algorithmic framework that accommodates full-information and bandit feedback models. For both feedback models, we prove that the proposed algorithms achieve sublinear (1−1/e)(1-1/e)-regret guarantees, which are comparable to those achieved by existing centralized counterparts. Furthermore, to tackle the sampling violation issue caused by continuous relaxation and rounding, we develop a bounded stochastic pipage rounding scheme and show that the probability of sampling violation vanishes asymptotically. As a result, the cumulative sampling violation remains sublinear in TT, which is further shown to be not improvable under certain conditions. Numerical results validate the theoretical findings in this paper.
Nov 15, 2026

Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse

We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every ε>0ε>0, we give an algorithm with recourse O(ε−2)O(ε^{-2}) whose reported set has, at every time, expected value at least 1/4−ε1/4-ε times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above 1/41/4, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above 1/41/4 requires recourse that grows as a positive power of the cardinality budget. Thus 1/41/4 is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was 3−22≈0.1723-2\sqrt2\approx0.172. Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.