Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure
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.
Characterizes exactly when the greedy (exploitation-only) algorithm succeeds (sublinear regret) or fails (linear regret) in structured bandits and contextual bandits with a known finite reward structure, via self-identifiability vs. decoys, and extends to DMSO with arbitrary feedback.
Problem
When does the greedy (exploitation-only) algorithm achieve sublinear vs. linear regret in bandits with a known reward structure (structured bandits, contextual bandits, and decision-making with structured observations)?
Approach
Shows that greedy succeeds exactly when the instance is self-identifiable (fixing a suboptimal arm's expected reward identifies it as suboptimal given the reward class), and fails with positive probability whenever a decoy reward function exists; any non-degenerate algorithm succeeds under self-identifiability.
Key results
- Greedy achieves O(log t) expected regret under self-identifiability with rate (K/Gamma)^2 O(log t) for MAB.
- If a decoy exists, Greedy with one warm-up sample per arm gets stuck on the decoy arm with probability at least e^{-O(K/Gamma^2)}, giving linear regret.
- Linear bandits and discretized Lipschitz bandits admit decoys for almost all instances, while linear contextual bandits are self-identifiable when context sets are sufficiently diverse.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require self-identifiability in a finite structured bandit | Greedy on StructuredMAB · StructuredMAB | regret growth: linear regret -> sublinear regret | Helped |
| Allow a decoy reward function and one warm-up sample per arm | Greedy on StructuredMAB · StructuredMAB | regret growth: sublinear regret -> linear regret | Hurt |
| Require self-identifiability in a contextual bandit | Greedy on StructuredCB · StructuredCB | regret growth: linear regret -> sublinear regret | Helped |
| Use GreedyMLE with self-identifiability for structured observations | GreedyMLE on DMSO · DMSO | regret growth: linear regret -> sublinear regret | Helped |
| Use ε-self-identifiability for an infinite reward structure | Greedy on StructuredMAB · StructuredMAB with an infinite function class | expected regret: T_0 + (K/\varepsilon)^2 \cdot O(\log t) | Helped |
| Use a sufficiently diverse context set with linear rewards | Greedy on linear contextual bandits · Linear contextual bandits | regret growth | Helped |
| Use a low-dimensional context set with linear rewards under the stated conditions | Greedy on linear contextual bandits · Linear contextual bandits | regret growth | Hurt |
| Use Lipschitz reward structures | Greedy on Lipschitz bandits · Discretized Lipschitz bandits | regret growth | Hurt |
Surprising findings
- Greedy fails for almost all instances of linear, Lipschitz, and polynomial bandits, contrary to the common view that exploration is necessary only in worst cases.
- Self-identifiability is incomparable to the Graves-Lai coefficient being zero, so GLC does not capture greedy's per-instance behavior.
Limitations
- Negative results only give a positive but possibly very small failure probability, so constants are loose.
- Infinite reward structures are handled only by a partial characterization with an epsilon margin.
Experimental setup
Metrics: expected regret sublinear vs linear regret
Baselines: GreedyMLE Lipschitz bandit reward structures
Builds on: Decision-Making with Structured Observations linear bandits Lipschitz bandits bandits with regression oracles
Closest papers by meaning
- Local Anti-Concentration Class: Logarithmic Regret for Greedy Linear Contextual Bandit (NeurIPS 2024 · similarity 0.90)
- Factored-Reward Bandits with Intermediate Observations (ICML 2024 · similarity 0.90)
- Testing the Feasibility of Linear Programs with Bandit Feedback (ICML 2024 · similarity 0.90)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.90)
- Infrequent Exploration in Linear Bandits (NeurIPS 2025 · similarity 0.90)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · 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.