# Linear Submodular Maximization with Bandit Feedback

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 30 references that are in the map.
- First posted on arXiv 2 Jul 2024.

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

- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Submodular Bandit Problem Under Multiple Constraints](https://mlsanity.com/paper/2006.00661/) (2020)
- [Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization](https://mlsanity.com/paper/1511.07211/) (2015)
- [Submodular Optimization under Noise](https://mlsanity.com/paper/1601.03095/) (2016)
- [Stochastic Submodular Maximization: The Case of Coverage Functions](https://mlsanity.com/paper/1711.01566/) (2017)
- [Leveraging Sparsity for Efficient Submodular Data Summarization](https://mlsanity.com/paper/1703.02690/) (2017)
- [Submodular Cost Submodular Cover with an Approximate Oracle](https://mlsanity.com/paper/1908.00653/) (2019)
- [Dynamic Influence Maximization](https://mlsanity.com/paper/2110.12602/) (2021)
- [SAGA: A Submodular Greedy Algorithm For Group Recommendation](https://mlsanity.com/paper/1712.09123/) (2017)
- [Almost Optimal Streaming Algorithms for Coverage Problems](https://mlsanity.com/paper/1610.08096/) (2016)

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

- [Multi-Agent Reinforcement Learning with Submodular Reward](https://mlsanity.com/paper/2603.06810/) (2026)

## Abstract (arXiv)

Submodular optimization with bandit feedback has recently been studied in a variety of contexts. In a number of real-world applications such as diversified recommender systems and data summarization, the submodular function exhibits additional linear structure. We consider developing approximation algorithms for the maximization of a submodular objective function f:2U→ℝ≥ 0, where f=sumi=1dwiFi. It is assumed that we have value oracle access to the functions Fi, but the coefficients wi are unknown, and f can only be accessed via noisy queries. We develop algorithms for this setting inspired by adaptive allocation algorithms in the best-arm identification for linear bandit, with approximation guarantees arbitrarily close to the setting where we have value oracle access to f. Finally, we empirically demonstrate that our algorithms make vast improvements in terms of sample efficiency compared to algorithms that do not exploit the linear structure of f on instances of move recommendation.