mlsanityData to 7 Oct 2026

Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback

arXiv 2302.01324 ↗First posted 2 Feb 2023cs.LG cs.AI math.OCcited by 19

Not on the map. Why?

Abstract (arXiv)

We investigate the problem of unconstrained combinatorial multi-armed bandits with full-bandit feedback and stochastic rewards for submodular maximization. Previous works investigate the same problem assuming a submodular and monotone reward function. In this work, we study a more general problem, i.e., when the reward function is not necessarily monotone, and the submodularity is assumed only in expectation. We propose Randomized Greedy Learning (RGL) algorithm and theoretically prove that it achieves a frac12-regret upper bound of tildeO(n T^frac23) for horizon T and number of arms n. We also show in experiments that RGL empirically outperforms other full-bandit variants in submodular and non-submodular settings.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 11 of its 40 references that are in the map. First posted on arXiv 2 Feb 2023.

Builds on

11 of 40 references.

References · 11

  1. 2018What Doubling Tricks Can and Can't Do for Multi-Armed Banditscited by 69
  2. 2016Restricted Strong Convexity Implies Weak Submodularitycited by 51
  3. 2013Thompson Sampling for Complex Bandit Problemscited by 43
  4. 2020Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraintcited by 21
  5. 2017Scalable Greedy Feature Selection via Weak Submodularitycited by 19
  6. 2015Online Influence Maximization (Extended Version)cited by 17
  7. 2020Online Influence Maximization under Linear Threshold Modelcited by 17
  8. 2020Submodular Bandit Problem Under Multiple Constraintscited by 15
  9. 2018Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexitycited by 14
  10. 2015Deterministic Algorithms for Submodular Maximization Problemscited by 10
  11. 2019Black Box Submodular Maximization: Discrete and Continuous Settingscited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 6; 2025: 3; 2026: 6.

19 papers.

Sort:

  1. 2023Combinatorial Stochastic-Greedy Banditcited by 18
  2. 2024Federated Combinatorial Multi-Agent Multi-Armed Banditscited by 11
  3. 2023Nearly Minimax Optimal Submodular Maximization with Bandit Feedbackcited by 7
  4. 2023FilFL: Client Filtering for Optimized Client Participation in Federated Learningcited by 5
  5. 2023Asymmetrically Decentralized Federated Learningcited by 5
  6. 2024Stochastic Q-learning for Large Discrete Action Spacescited by 5
  7. 2025Offline Learning for Combinatorial Multi-armed Banditscited by 5
  8. 2024Stochastic k-Submodular Bandits with Full Bandit Feedbackcited by 3
  9. 2025Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constantscited by 3
  10. 2024A Contextual Combinatorial Bandit Approach to Negotiationcited by 2
  11. 2024Decentralized Personalized Federated Learningcited by 1
  12. 2024Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Banditcited by 0
7 more
  1. 2025A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedbackcited by 0
  2. 2026Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedbackcited by 0
  3. 2026Multi-Agent Reinforcement Learning with Submodular Rewardcited by 0
  4. 2026Meritocratic Fairness via K-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedbackcited by 0
  5. 2026Stochastic Sequential Search in Very-High-Dimensional Feature Selectioncited by 0
  6. 2026Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learningcited by 0
  7. 2026Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policycited by 0