# Nearly Minimax Optimal Submodular Maximization with Bandit Feedback

arXiv: https://arxiv.org/abs/2310.18465 · HTML: https://mlsanity.com/paper/2310.18465/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 45 references that are in the map.
- First posted on arXiv 27 Oct 2023.

## Builds on (most cited first, 26 of 26)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [An Efficient Bandit Algorithm for Realtime Multivariate Optimization](https://mlsanity.com/paper/1810.09558/) (2018)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains](https://mlsanity.com/paper/1606.05615/) (2016)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Submodular Functions: from Discrete to Continous Domains](https://mlsanity.com/paper/1511.00394/) (2015)
- [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization](https://mlsanity.com/paper/1511.07211/) (2015)
- [Stochastic Top-K Subset Bandits with Linear Space and Non-Linear Feedback](https://mlsanity.com/paper/1811.11925/) (2018)
- [Best-of-K Bandits](https://mlsanity.com/paper/1603.02752/) (2016)
- [DART: aDaptive Accept RejecT for non-linear top-K subset identification](https://mlsanity.com/paper/2011.07687/) (2020)
- [Improved Regret Bounds for Online Submodular Maximization](https://mlsanity.com/paper/2106.07836/) (2021)
- [Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback](https://mlsanity.com/paper/2303.13604/) (2023)
- [Continuous Submodular Maximization: Beyond DR-Submodularity](https://mlsanity.com/paper/2006.11726/) (2020)

## Built on by (most cited first, 7 of 7)

- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [No-Regret Mnatural-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting](https://mlsanity.com/paper/2405.12439/) (2024)
- [On the Sublinear Regret of Continuous K-Max Bandits](https://mlsanity.com/paper/2502.13467/) (2025)
- [A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback](https://mlsanity.com/paper/2503.12285/) (2025)
- [Bandit Guided Submodular Curriculum for Adaptive Subset Selection](https://mlsanity.com/paper/2511.22944/) (2025)
- [Meritocratic Fairness via K-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/2605.00762/) (2026)
- [Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy](https://mlsanity.com/paper/2608.24627/) (2026)

## Abstract (arXiv)

We consider maximizing an unknown monotonic, submodular set function f: 2[n] rightarrow [0,1] with cardinality constraint under stochastic bandit feedback. At each time t=1,dots,T the learner chooses a set St subset [n] with |St| ≤ k and receives reward f(St) + ηt where ηt is mean-zero sub-Gaussian noise. The objective is to minimize the learner's regret with respect to an approximation of the maximum f(S_*) with |S_*| = k, obtained through robust greedy maximization of f. To date, the best regret bound in the literature scales as k n1/3 T2/3. And by trivially treating every set as a unique arm one deduces that √ n choose k T  is also achievable using standard multi-armed bandit algorithms. In this work, we establish the first minimax lower bound for this setting that scales like tildeOmega(minL ≤ k(L1/3n1/3T2/3 + √n choose k - LT)). For a slightly restricted algorithm class, we prove a stronger regret lower bound of tildeOmega(minL ≤ k(Ln1/3T2/3 + √n choose k - LT)). Moreover, we propose an algorithm Sub-UCB that achieves regret tildeO(minL ≤ k(Ln1/3T2/3 + √n choose k - LT)) capable of matching the lower bound on regret for the restricted class up to logarithmic factors.