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:
- 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.
- 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.
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.
- 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