Research map / Bandits and online learning / Multi-armed bandits
Combinatorial Stochastic-Greedy Bandit
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes stochastic-greedy bandit (SGB), an explore-then-commit greedy method that samples only a random subset of remaining arms per greedy step, achieving an improved (1-1/e)-regret bound for monotone stochastic submodular rewards under full-bandit feedback, and evaluated on online social influence maximization.
Problem
Combinatorial multi-armed bandits with full-bandit (joint reward only) feedback and monotone stochastic submodular rewards under a cardinality constraint k, where exploring all remaining arms each greedy step is expensive for large ground sets.
Approach
Explore only a randomly sampled, epsilon-dependent fraction of the unselected arms at each greedy phase (fraction min{1, log(1/eps)/k}) within an explore-then-commit greedy scheme; choosing eps optimally yields a regret bound better in k than prior ETCG-style methods while keeping (1-1/e)-regret.
Key results
- SGB with optimal epsilon achieves regret bound O(n^{1/3} k^{2/3} T^{2/3} log(T)^{2/3}), improving the k-dependence over ETCG's k^{4/3}-type bound by k^{1/3}.
- In influence maximization experiments with k=8, 24, 32, SGB with optimal epsilon yields lower cumulative regret than ETCG, with the gap growing as k increases.
- For k=32, SGB ends exploration about 30 times faster than ETCG while reaching a solution within 0.01 of 0.37.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use optimized stochastic subset sampling instead of ETCG's full exploration | SGB · Online social influence maximization, k=8 | average cumulative regret | Helped |
| Use SGB with ε⋆ instead of ETCG | Online social influence maximization · k=24 and k=32 | average cumulative regret | Helped |
| Set ε to 0.2 or 0.5 instead of ε⋆ (ablation) | SGB · Online social influence maximization, k=8 | cumulative regret | Hurt |
| Use ε⋆ instead of other considered ε values (ablation) | SGB · Online social influence maximization, k=24 | solution quality | Helped |
| Use ε⋆ instead of other considered ε values (ablation) | SGB · Online social influence maximization, k=32 | solution quality | Helped |
Surprising findings
- With non-optimal epsilon (0.2 and 0.5) at k=8, SGB has higher cumulative regret than ETCG.
Limitations
- Bound is O(T^{2/3}); whether O(T^{1/2}) is achievable under full-bandit stochastic submodular feedback is open.
- Optimal epsilon depends on n, k, T and performance is sensitive to epsilon choice (non-optimal epsilon can underperform ETCG at small k).
- Experiments limited to one Facebook community subgraph with a single infection probability (0.1) and ten runs per horizon.
Experimental setup
Datasets: Facebook network subgraph (534 nodes, 8158 edges)
Benchmarks: online social influence maximization on Facebook network subgraph
Metrics: cumulative regret immediate reward
Baselines: ETCG
Builds on: explore-then-commit greedy (ETCG) stochastic greedy for submodular maximization Hoeffding inequality
Closest papers by meaning
- Combinatorial semi-bandit with known covariance (NeurIPS 2016 · similarity 0.92)
- Federated Combinatorial Multi-Agent Multi-Armed Bandits (ICML 2024 · similarity 0.90)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.90)
- Stochastic Matching Bandits with Rare Optimization Updates (NeurIPS 2026 · similarity 0.90)
- Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit (AAAI 2024 · similarity 0.89)
- p-Mean Regret for Stochastic Bandits (AAAI 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.