Research map / Bandits and online learning / Online convex optimization and games
No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting
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.
Studies online M-natural-concave (gross substitute) function maximization: gives O(T^{-1/2}) simple-regret and O(T^{2/3}) regret bandit algorithms via a robustness-to-local-errors greedy analysis, and proves no polynomial-time randomized learner can get poly(N)T^{1-c} regret in the adversarial full-information setting via reduction from 3-matroid intersection.
Problem
Maximizing M-natural-concave (gross substitute) functions when the function is unknown and only accessible through noisy feedback, in online stochastic bandit and adversarial full-information settings.
Approach
Shows the greedy algorithm for M-natural-concave maximization is robust to additive local errors (no approximation factor), which lets an MOSS-based pure-exploration per greedy step yield no-regret algorithms; and reduces 3-matroid intersection to adversarial online M-natural-concave maximization to show hardness.
Key results
- Stochastic setting: O(K^{3/2} sqrt(N/T)) simple regret using T noisy value-oracle queries.
- Stochastic setting: O(K N^{1/3} T^{2/3}) cumulative regret via explore-then-commit.
- Adversarial full-information: no polynomial-time randomized learner achieves poly(N)·T^{1-c} regret for any constant c>0, via reduction from 3-matroid intersection.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MOSS to select greedy update directions from noisy value-oracle feedback | M-natural-concave maximization · Stochastic bandit | simple regret: O(K^{3/2}\sqrt{N/T}) | Helped |
| Explore with the simple-regret algorithm, then commit to its output | M-natural-concave maximization · Stochastic bandit | cumulative regret: O(KN^{1/3}T^{2/3}) | Helped |
| Require polynomial time per round in the adversarial full-information setting | M-natural-concave maximization · Adversarial full-information | regret: poly(N)·T^{1-c} | Hurt |
| Allow locally erroneous greedy update directions | Greedy M-natural-concave maximization · M-natural-concave maximization under x(V) ≤ K | suboptimality: f(x_K) ≥ f(x^*) - \sum_{k=1}^K \mathrm{err}(i_k \,|\, x_{k-1}) | No clear effect |
Surprising findings
- Offline M-natural-concave maximization is polynomial-time solvable, yet online full-information maximization admits no polynomial-time no-regret learner.
Limitations
- Stochastic results assume sub-Gaussian noise; adversarial hardness comes from a pessimistic worst-case analysis.
- Upper bound O(K N^{1/3} T^{2/3}) is not shown tight; the conjectured tightness is unproven.
- Regret bounds are stated without approximation, but the adversarial hardness leaves open whether polynomial-time approximate no-regret is possible.
Experimental setup
Metrics: simple regret cumulative regret
Baselines: exponential-time multiplicative weights over feasible actions
Builds on: MOSS M-natural-concave function theory (discrete convex analysis) explore-then-commit
Closest papers by meaning
- Optimal Gradient-based Algorithms for Non-concave Bandit Optimization (NeurIPS 2021 · similarity 0.89)
- Nearly Minimax Optimal Submodular Maximization with Bandit Feedback (NeurIPS 2024 · similarity 0.88)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.88)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.88)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.88)
- Online Submodular Maximization via Online Convex Optimization (AAAI 2024 · similarity 0.88)
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.