AI Paper Atlas

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

NeurIPS 2020 · Bandits and online learning › Multi-armed bandits · approach: Optimal stochastic bandit algorithms

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 changedWhereMeasuredEffect
subsample arms to sqrt(T) before running the algorithmUCB, TS and Greedy · Many-armed simulation, 400 runs, Gaussian rewards uniform priorper-instance regretImproved
use Greedy instead of UCB/TS with active explorationmany-armed bandit · Many-armed simulationregretImproved
use SS-Greedy over all other algorithmsmany-armed bandit · Many-armed simulation and Letter Recognition contextual (k=300)regretImproved
use SS-TS instead of SS-Greedycontextual many-armed bandit · Letter Recognition, k=300regret mean and varianceMixed
increase context dimension from d=2 to d=6Greedy · Letter Recognition, k=300regretImproved
reduce number of arms from k=300 to k=8Greedy · Letter Recognition, d=2regretHurt
use Bernoulli rewards and beta priors instead of Gaussian/uniformGreedy and SS-Greedy · simulation robustnessregretNo clear effect

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy