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

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

## Key facts

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

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

- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Restricted Strong Convexity Implies Weak Submodularity](https://mlsanity.com/paper/1612.00804/) (2016)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint](https://mlsanity.com/paper/2007.05014/) (2020)
- [Scalable Greedy Feature Selection via Weak Submodularity](https://mlsanity.com/paper/1703.02723/) (2017)
- [Online Influence Maximization (Extended Version)](https://mlsanity.com/paper/1506.01188/) (2015)
- [Online Influence Maximization under Linear Threshold Model](https://mlsanity.com/paper/2011.06378/) (2020)
- [Submodular Bandit Problem Under Multiple Constraints](https://mlsanity.com/paper/2006.00661/) (2020)
- [Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity](https://mlsanity.com/paper/1808.06932/) (2018)
- [Deterministic Algorithms for Submodular Maximization Problems](https://mlsanity.com/paper/1508.02157/) (2015)
- [Black Box Submodular Maximization: Discrete and Continuous Settings](https://mlsanity.com/paper/1901.09515/) (2019)

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

- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [FilFL: Client Filtering for Optimized Client Participation in Federated Learning](https://mlsanity.com/paper/2302.06599/) (2023)
- [Asymmetrically Decentralized Federated Learning](https://mlsanity.com/paper/2310.05093/) (2023)
- [Stochastic Q-learning for Large Discrete Action Spaces](https://mlsanity.com/paper/2405.10310/) (2024)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Stochastic k-Submodular Bandits with Full Bandit Feedback](https://mlsanity.com/paper/2412.10682/) (2024)
- [Every Call is Precious: Global Optimization of Black-Box Functions with Unknown Lipschitz Constants](https://mlsanity.com/paper/2502.04290/) (2025)
- [A Contextual Combinatorial Bandit Approach to Negotiation](https://mlsanity.com/paper/2407.00567/) (2024)
- [Decentralized Personalized Federated Learning](https://mlsanity.com/paper/2406.06520/) (2024)
- [Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit](https://mlsanity.com/paper/2410.08578/) (2024)
- [A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback](https://mlsanity.com/paper/2503.12285/) (2025)
- [Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback](https://mlsanity.com/paper/2602.16183/) (2026)
- [Multi-Agent Reinforcement Learning with Submodular Reward](https://mlsanity.com/paper/2603.06810/) (2026)
- [Meritocratic Fairness via K-Shapley Values in Budgeted Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/2605.00762/) (2026)
- [Stochastic Sequential Search in Very-High-Dimensional Feature Selection](https://mlsanity.com/paper/2608.01502/) (2026)
- [Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning](https://mlsanity.com/paper/2608.12134/) (2026)
- [Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy](https://mlsanity.com/paper/2608.24627/) (2026)

## 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.