Research map / Bandits and online learning / Multi-armed bandits
Sub-sampling for Efficient Non-Parametric Bandit Exploration
Dorian Baudry, Emilie Kaufmann, Odalric-Ambrym Maillard
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 |
|---|---|---|---|
| Use RB-SDA instead of Thompson Sampling | Bernoulli bandits · Bernoulli experiments 1–4, T=20000 | regret: 11.2 -> 11.5; 22.9 -> 22.0; 94.2 -> 89.0; 108.1 -> 105.1 | Mixed |
| Use RB-SDA instead of Thompson Sampling | Gaussian bandits · Gaussian experiments 1–3, T=20000 | regret: 24.4 -> 25.6; 73.5 -> 71.0; 49.7 -> 50.4 | Mixed |
| Use RB-SDA instead of ReBoot | Gaussian bandits · Gaussian experiments 1–3, T=20000 | regret: 92.2 -> 25.6; 277.1 -> 71.0; 190.9 -> 50.4 | Improved |
| Use RB-SDA instead of Thompson Sampling | Truncated Gaussian bandits · Truncated Gaussian experiments 1–4, T=20000 | regret: 21.9 -> 1.4; 13.3 -> 4.4; 9.7 -> 7.1; 86.6 -> 64.9 | Improved |
| Add forced exploration f_r = sqrt(log r) (ablation) | RB-SDA · Exponential arms, experiments 1–6 | average regret: 48.2 -> 44.9; 3.8 -> 3.6; 832.8 -> 837.5; 258.3 -> 244.8; 25.6 -> 23.6; 618.7 -> 578.9 | Mixed |
| Add forced exploration f_r = sqrt(log r) (ablation) | RB-SDA · Exponential experiment 3 | 95% quantile regret | No clear effect |
| Use random-block sampling rather than random sampling without replacement (ablation) | SSDA · Bernoulli and Gaussian experiments | regret | Mixed |
| Use random-block sampling rather than last-block sampling (ablation) | SSDA · Bernoulli and Gaussian experiments | regret | Improved |
| Use last-block sampling rather than the reward-dependent SSMC sampler (ablation) | SSDA · Bernoulli and Gaussian experiments | regret | No clear effect |
| Use history perturbation with PHE instead of RB-SDA | Bernoulli bandits · Bernoulli experiments 1–4 | regret: 11.5 -> 25.9; 22.0 -> 24.0; 89.0 -> 248.1; 105.1 -> 216.5 | Mixed |
| Use vanilla RB-SDA on exponential arms | RB-SDA · Exponential experiment 3 | 99% quantile regret: 4209.4 -> 6813.1 | Hurt |
Closest papers by meaning
- On Limited-Memory Subsampling Strategies for Bandits (ICML 2021 · similarity 0.91)
- Double Thompson Sampling for Dueling Bandits (NeurIPS 2016 · similarity 0.90)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.89)
- Feel-Good Thompson Sampling for Contextual Dueling Bandits (ICML 2024 · similarity 0.88)
- Fusing Reward and Dueling Feedback in Stochastic Bandits (ICML 2025 · similarity 0.88)
- Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit (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.
