Efficient Online Submodular Maximization with Bandit Feedback

Iasonas Nikolaou, Evimaria TerziarXiv 2026 · arXiv

TL;DR

This paper introduces Sub-EW (Submodular-Exponential-Weights), the first polynomial-time algorithm to achieve $O(\sqrt{T})$ expected regret for online monotone submodular maximization with bandit feedback. By combining a novel "non-oblivious" potential function with a randomized sampling strategy, the authors bridge the theoretical gap between bandit and full-information regret rates for arbitrary monotone submodular functions.

What Problem Does This Paper Address?

Submodular optimization is the mathematical language of "diminishing returns," appearing in everything from sensor placement to recommender systems. In the Online Submodular Maximization (OSM) setting, a learner must choose a set of items at each time step to maximize a reward function that changes over time.

The "Bandit" version of this problem is particularly difficult: the learner only sees the single scalar reward for the set they chose, rather than the entire reward function. Because submodular optimization relies heavily on calculating "marginal gains" (how much value an extra item adds), bandit feedback makes it incredibly hard to know which items are actually driving the reward. Until now, the best algorithms for general submodular functions were stuck with a regret of $O(T^{2/3})$. The community has long wondered if a computationally efficient algorithm could reach the gold standard of $O(\sqrt{T})$ regret.

Methods

The authors achieve this breakthrough by reducing the submodular problem to Online Linear Optimization (OLO) over a probability simplex. Their approach, Sub-EW, is built on two key innovations:

  1. A Non-Oblivious Potential: They construct a potential function $G_t(p)$ that aggregates the expected rewards of sampling different numbers of elements (from 1 to $k$). This potential is carefully weighted so that its gradient provides a linear upper bound on the submodular regret, specifically targeting the $(1 - 1/e)$ approximation ratio necessitated by the problem's inherent NP-hardness.
  2. Randomized Sampling for Gradient Estimation: In the full-information setting, one could simply calculate the gradient of this potential. In the bandit setting, the authors use a clever trick: at each round, they randomly choose a number of elements $M_t \in \{1, \dots, k\}$ to sample. By randomizing the sample size and using importance weighting, they can construct an unbiased estimate of the potential's gradient from a single reward observation.

The underlying engine is a bandit exponential-weights method (based on EXP3), which maintains a distribution over the ground set and updates it using these gradient estimates.

The full-information reduction that serves as the foundation for the bandit algorithm.

Datasets

The authors evaluated Sub-EW on three distinct monotone submodular maximization benchmarks:

  • Influence: A weighted influence-maximization task using the classic Zachary’s Karate Club graph.
  • TeamFormation: A roster-selection problem where the objective is a quadratic submodular function that penalizes redundancy between candidates with similar skills.
  • Coverage: A synthetic weighted-coverage problem where elements cover various "topics" with varying importance across tasks.

Key Insights and Ideas

  • The Power of $M < k$: Standard approaches usually sample exactly $k$ items. This paper shows that occasionally sampling fewer than $k$ items is the key to "peeking" inside the submodular function's structure to estimate gradients without needing full information.
  • Regret Transfer: The paper provides a formal framework to transfer regret bounds from linear optimizers directly to submodular ones. As shown in the table below, this work is the first to hit the $\sqrt{T}$ mark for the general "Sub." (arbitrary submodular) class under adversarial settings.
Comparison of regret bounds for various Bandit-OSM algorithms. This work is the first to achieve $\sqrt{T}$ for arbitrary submodular functions.
  • Computational Efficiency: The algorithm is highly practical, with a per-round time complexity of $O(n + k \log n)$, where $n$ is the ground set size and $k$ is the budget.

Key Results

  • Theoretical: The authors prove an expected $(1 - 1/e)$-regret bound of $O(k\sqrt{nT \log(n/k)})$. This confirms that the $\sqrt{T}$ dependence on the horizon is achievable for arbitrary monotone submodular functions.
  • Empirical: In experiments, Sub-EW consistently outperformed $O(T^{2/3})$ baselines like Bandit-IG and BanditMLSM. While it trailed the MSE3 algorithm on some datasets, the authors note that MSE3's theoretical guarantees only apply to a specific subclass of submodular functions (sum-max), whereas Sub-EW is universal.

Limitations and Future Work

  • Variance: The use of importance weighting in the gradient estimator can lead to high variance. This might explain why the algorithm, despite its superior asymptotic theory, sometimes trails simpler heuristics in short-term practical experiments.
  • Matroid Constraints: The current $O(\sqrt{T})$ result is specific to cardinality constraints (picking at most $k$ items). Extending this rate to more complex constraints, such as general matroids, remains an open and challenging problem.
  • Practical Refinement: Designing variants that reduce variance while maintaining the $\sqrt{T}$ guarantee is a suggested path for future research.

Summary updated

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.
BibTeX
@misc{nikolaou2026efficient,
  author = {Iasonas Nikolaou and Evimaria Terzi},
  title = {{Efficient Online Submodular Maximization with Bandit Feedback}},
  year = {2026},
  eprint = {2611.11808},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.11808},
}

Loading related content...

Figure