mlsanityData to 14 Oct 2026

Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit

arXiv 2410.08578 ↗First posted 11 Oct 2024cs.LG math.CO math.OCcited by 0

Not on the map. Why?

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.

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

22 of 54 references.

References · 22

  1. 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
  2. 2016Combinatorial Multi-Armed Bandit with General Reward Functionscited by 56
  3. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  4. 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimizationcited by 40
  5. 2020Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Banditscited by 31
  6. 2016Combinatorial semi-bandit with known covariancecited by 24
  7. 2023Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedbackcited by 19
  8. 2016Constrained Submodular Maximization via a Non-symmetric Techniquecited by 18
  9. 2014Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignmentscited by 17
  10. 2023Constrained Submodular Maximization via New Bounds for DR-Submodular Functionscited by 15
  11. 2021Adversarial Combinatorial Bandits with General Non-linear Reward Functionscited by 14
  12. 2015The Limitations of Optimization from Samplescited by 13
10 more
  1. 2015Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarizationcited by 11
  2. 2016Submodular Optimization under Noisecited by 11
  3. 2017Stochastic Submodular Maximization: The Case of Coverage Functionscited by 11
  4. 2019Near-optimal Approximate Discrete and Continuous Submodular Function Minimizationcited by 11
  5. 2016Constrained Submodular Maximization: Beyond 1/ecited by 7
  6. 2022On Maximizing Sums of Non-monotone Submodular and Linear Functionscited by 7
  7. 2018An Optimal Algorithm for Online Unconstrained Submodular Maximizationcited by 3
  8. 2024Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Banditscited by 3
  9. 2024Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraintcited by 3
  10. 2020Minimizing Convex Functions with Rational Minimizerscited by 2

Built on by

Not cited yet.