Research map / Bandits and online learning / Online convex optimization and games
Nearly Minimax Optimal Submodular Maximization with Bandit Feedback
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.
Proves the first minimax regret lower bound for submodular maximization with cardinality constraint under stochastic bandit feedback (robust greedy regret) and proposes Sub-UCB, which matches the bound up to logs for a restricted algorithm class.
Problem
Regret minimization when maximizing an unknown monotone submodular set function under cardinality constraint k with noisy bandit feedback; the known upper bounds scale as k n^{1/3} T^{2/3} while naive MAB gives sqrt(C(n,k) T), and the optimal dependence was unknown.
Approach
Defines robust greedy regret against epsilon-approximate greedy sets and shows a minimax lower bound interpolating between T^{2/3} and sqrt(C(n,k)T). The Sub-UCB algorithm runs an explore-then-commit greedy phase for the first k-L steps and then UCB over all size-k supersets of the greedy prefix, with L chosen from the lower bound.
Key results
- Lower bound: for any algorithm, sup_f E[R_gr] is at least order (k-i*)^{1/3} T^{2/3} n^{1/3} plus sqrt(C(n-k,i*) T), giving Omega~(min_L(L^{1/3} n^{1/3} T^{2/3} + sqrt(C(n,k-L) T))).
- Sub-UCB achieves regret O~(min_L (L n^{1/3} T^{2/3} + sqrt(C(n,k-L) T))), matching the lower bound for the restricted non-adaptive greedy-threshold class up to log factors.
- In experiments, Sub-UCB with stop level k-i* outperforms ETCG and naive UCB on size-k arms across horizons.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Sub-UCB with stop level k - i* instead of ETCG | Submodular bandit optimization · Experiments (weighted set cover and unique greedy path) | regret | Helped |
| Use Sub-UCB with stop level k - i* instead of UCB over all size-k arms | Submodular bandit optimization · Experiments, smaller T | regret | Helped |
| Use Sub-UCB with stop level k - i* instead of ETCG or naive UCB | Submodular bandit optimization · Experiments, increasing T | regret | Helped |
| Vary the greedy stop level (ablation) | Sub-UCB · Unique greedy path function, n=20 and k=5 | regret | Mixed |
| Choose the worst-case-optimal stop level k - i* rather than an instance-specific best stop level (ablation) | Sub-UCB · Unique greedy path function, n=20 and k=5 | regret | Mixed |
Surprising findings
- Common R_alpha regret with alpha=1-1/e can be a very loose lower bound on the greedy-based regret; a random selection can get zero or negative R_alpha regret on modular functions.
Limitations
- Gap of k^{2/3} between the general lower bound and the upper bound remains open
- Lower bound for general algorithms is weaker (L^{1/3}) than for the restricted class (L)
- Results only for cardinality constraints and monotone submodular functions; matroid and non-monotone cases are open
Experimental setup
Benchmarks: unique greedy path hard instance (n=20, k=5) weighted set cover (n=15, k=4)
Metrics: cumulative robust greedy regret
Baselines: ETCG (explore-then-commit greedy) UCB on all size-k arms
Builds on: UCB greedy algorithm (Nemhauser et al.) explore-then-commit greedy (ETCG)
Closest papers by meaning
- From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization (NeurIPS 2024 · similarity 0.91)
- Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints (NeurIPS 2024 · similarity 0.90)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.90)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.90)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.89)
- Online Submodular Maximization via Online Convex Optimization (AAAI 2024 · 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.