AI Paper Atlas

Research map / Bandits and online learning / Multi-armed bandits

Sub-sampling for Efficient Non-Parametric Bandit Exploration

Dorian Baudry, Emilie Kaufmann, Odalric-Ambrym Maillard

NeurIPS 2020 · Bandits and online learning › Multi-armed bandits · approach: Optimal stochastic bandit algorithms · 5 citations (OpenAlex)

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
Use RB-SDA instead of Thompson SamplingBernoulli bandits · Bernoulli experiments 1–4, T=20000regret: 11.2 -> 11.5; 22.9 -> 22.0; 94.2 -> 89.0; 108.1 -> 105.1Mixed
Use RB-SDA instead of Thompson SamplingGaussian bandits · Gaussian experiments 1–3, T=20000regret: 24.4 -> 25.6; 73.5 -> 71.0; 49.7 -> 50.4Mixed
Use RB-SDA instead of ReBootGaussian bandits · Gaussian experiments 1–3, T=20000regret: 92.2 -> 25.6; 277.1 -> 71.0; 190.9 -> 50.4Improved
Use RB-SDA instead of Thompson SamplingTruncated Gaussian bandits · Truncated Gaussian experiments 1–4, T=20000regret: 21.9 -> 1.4; 13.3 -> 4.4; 9.7 -> 7.1; 86.6 -> 64.9Improved
Add forced exploration f_r = sqrt(log r) (ablation)RB-SDA · Exponential arms, experiments 1–6average regret: 48.2 -> 44.9; 3.8 -> 3.6; 832.8 -> 837.5; 258.3 -> 244.8; 25.6 -> 23.6; 618.7 -> 578.9Mixed
Add forced exploration f_r = sqrt(log r) (ablation)RB-SDA · Exponential experiment 395% quantile regretNo clear effect
Use random-block sampling rather than random sampling without replacement (ablation)SSDA · Bernoulli and Gaussian experimentsregretMixed
Use random-block sampling rather than last-block sampling (ablation)SSDA · Bernoulli and Gaussian experimentsregretImproved
Use last-block sampling rather than the reward-dependent SSMC sampler (ablation)SSDA · Bernoulli and Gaussian experimentsregretNo clear effect
Use history perturbation with PHE instead of RB-SDABernoulli bandits · Bernoulli experiments 1–4regret: 11.5 -> 25.9; 22.0 -> 24.0; 89.0 -> 248.1; 105.1 -> 216.5Mixed
Use vanilla RB-SDA on exponential armsRB-SDA · Exponential experiment 399% quantile regret: 4209.4 -> 6813.1Hurt

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