# Sum-max Submodular Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 23 references that are in the map.
- First posted on arXiv 10 Nov 2023.

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

- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [TopRank: A practical algorithm for online stochastic ranking](https://mlsanity.com/paper/1806.02248/) (2018)
- [Tight Bounds for Bandit Combinatorial Optimization](https://mlsanity.com/paper/1702.07539/) (2017)
- [Best-of-K Bandits](https://mlsanity.com/paper/1603.02752/) (2016)
- [Online Learning of Facility Locations](https://mlsanity.com/paper/2007.02801/) (2020)

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

- [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)
- [Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints](https://mlsanity.com/paper/2608.16375/) (2026)

## Abstract (arXiv)

Many online decision-making problems correspond to maximizing a sequence of submodular functions. In this work, we introduce sum-max functions, a subclass of monotone submodular functions capturing several interesting problems, including best-of-K-bandits, combinatorial bandits, and the bandit versions on facility location, M-medians, and hitting sets. We show that all functions in this class satisfy a key property that we call pseudo-concavity. This allows us to prove big(1 - frac1ebig)-regret bounds for bandit feedback in the nonstochastic setting of the order of √MKT (ignoring log factors), where T is the time horizon and M is a cardinality constraint. This bound, attained by a simple and efficient algorithm, significantly improves on the widetildeObig(T2/3big) regret bound for online monotone submodular maximization with bandit feedback.