# Combinatorial Stochastic-Greedy Bandit

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 13 Dec 2023.

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

- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [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)

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

- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [Global Rewards in Restless Multi-Armed Bandits](https://mlsanity.com/paper/2406.00738/) (2024)
- [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)
- [No-Regret Mnatural-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting](https://mlsanity.com/paper/2405.12439/) (2024)
- [Exploring Multiple High-Scoring Subspaces in Generative Flow Networks](https://mlsanity.com/paper/2602.11491/) (2026)
- [On the Sublinear Regret of Continuous K-Max Bandits](https://mlsanity.com/paper/2502.13467/) (2025)
- [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)
- [Offline Local Search for Online Stochastic Bandits](https://mlsanity.com/paper/2604.09423/) (2026)
- [Learning to Sparsify Stochastic Linear Bandits](https://mlsanity.com/paper/2605.10151/) (2026)
- [Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals](https://mlsanity.com/paper/2606.14650/) (2026)
- [Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning](https://mlsanity.com/paper/2608.12134/) (2026)
- [Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints](https://mlsanity.com/paper/2608.16375/) (2026)
- [Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy](https://mlsanity.com/paper/2608.24627/) (2026)

## Abstract (arXiv)

We propose a novel combinatorial stochastic-greedy bandit (SGB) algorithm for combinatorial multi-armed bandit problems when no extra information other than the joint reward of the selected set of n arms at each time step t∈ [T] is observed. SGB adopts an optimized stochastic-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms. Unlike existing methods that explore the entire set of unselected base arms during each selection step, our SGB algorithm samples only an optimized proportion of unselected arms and selects actions from this subset. We prove that our algorithm achieves a (1-1/e)-regret bound of O(n^frac13 k^frac23 T^frac23 log(T)^frac23) for monotone stochastic submodular rewards, which outperforms the state-of-the-art in terms of the cardinality constraint k. Furthermore, we empirically evaluate the performance of our algorithm in the context of online constrained social influence maximization. Our results demonstrate that our proposed approach consistently outperforms the other algorithms, increasing the performance gap as k grows.