# Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 54 references that are in the map.
- First posted on arXiv 11 Oct 2024.

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

- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Combinatorial semi-bandit with known covariance](https://mlsanity.com/paper/1612.01859/) (2016)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [Constrained Submodular Maximization via New Bounds for DR-Submodular Functions](https://mlsanity.com/paper/2311.01129/) (2023)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [The Limitations of Optimization from Samples](https://mlsanity.com/paper/1512.06238/) (2015)
- [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)
- [Near-optimal Approximate Discrete and Continuous Submodular Function Minimization](https://mlsanity.com/paper/1909.00171/) (2019)
- [Constrained Submodular Maximization: Beyond 1/e](https://mlsanity.com/paper/1608.03611/) (2016)
- [On Maximizing Sums of Non-monotone Submodular and Linear Functions](https://mlsanity.com/paper/2205.15874/) (2022)
- [An Optimal Algorithm for Online Unconstrained Submodular Maximization](https://mlsanity.com/paper/1806.03349/) (2018)
- [Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2402.15171/) (2024)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [Minimizing Convex Functions with Rational Minimizers](https://mlsanity.com/paper/2007.01445/) (2020)

## Abstract (arXiv)

We address the online unconstrained submodular maximization problem (Online USM), in a setting with stochastic bandit feedback. In this framework, a decision-maker receives noisy rewards from a non monotone submodular function taking values in a known bounded interval. This paper proposes Double-Greedy - Explore-then-Commit (DG-ETC), adapting the Double-Greedy approach from the offline and online full-information settings. DG-ETC satisfies a O(dlog(dT)) problem-dependent upper bound for the 1/2-approximate pseudo-regret, as well as a O(dT2/3log(dT)1/3) problem-free one at the same time, outperforming existing approaches. In particular, we introduce a problem-dependent notion of hardness characterizing the transition between logarithmic and polynomial regime for the upper bounds.