Research map / Bandits and online learning / Multi-armed bandits
Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms
Mohsen Bayati, Nima Hamidi, Ramesh Johari, Khashayar Khosravi
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| subsample arms to sqrt(T) before running the algorithm | UCB, TS and Greedy · Many-armed simulation, 400 runs, Gaussian rewards uniform prior | per-instance regret | Improved |
| use Greedy instead of UCB/TS with active exploration | many-armed bandit · Many-armed simulation | regret | Improved |
| use SS-Greedy over all other algorithms | many-armed bandit · Many-armed simulation and Letter Recognition contextual (k=300) | regret | Improved |
| use SS-TS instead of SS-Greedy | contextual many-armed bandit · Letter Recognition, k=300 | regret mean and variance | Mixed |
| increase context dimension from d=2 to d=6 | Greedy · Letter Recognition, k=300 | regret | Improved |
| reduce number of arms from k=300 to k=8 | Greedy · Letter Recognition, d=2 | regret | Hurt |
| use Bernoulli rewards and beta priors instead of Gaussian/uniform | Greedy and SS-Greedy · simulation robustness | regret | No clear effect |
Closest papers by meaning
- Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory (AAAI 2020 · similarity 0.92)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.90)
- Combinatorial Stochastic-Greedy Bandit (AAAI 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.89)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.89)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (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.
