# Sub-sampling for Efficient Non-Parametric Bandit Exploration

arXiv: https://arxiv.org/abs/2010.14323 · HTML: https://mlsanity.com/paper/2010.14323/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2020.

## Built on by (most cited first, 8 of 8)

- [Bregman Deviations of Generic Exponential Families](https://mlsanity.com/paper/2201.07306/) (2022)
- [Diffusion Approximations for Thompson Sampling in the Small Gap Regime](https://mlsanity.com/paper/2105.09232/) (2021)
- [On Limited-Memory Subsampling Strategies for Bandits](https://mlsanity.com/paper/2106.10935/) (2021)
- [From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits](https://mlsanity.com/paper/2111.09724/) (2021)
- [A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms](https://mlsanity.com/paper/2303.06058/) (2023)
- [Batch Ensemble for Variance Dependent Regret in Stochastic Bandits](https://mlsanity.com/paper/2409.08570/) (2024)
- [Efficient Algorithms for Extreme Bandits](https://mlsanity.com/paper/2203.10883/) (2022)
- [Approximate information maximization for bandit games](https://mlsanity.com/paper/2310.12563/) (2023)

## Abstract (arXiv)

In this paper we propose the first multi-armed bandit algorithm based on re-sampling that achieves asymptotically optimal regret simultaneously for different families of arms (namely Bernoulli, Gaussian and Poisson distributions). Unlike Thompson Sampling which requires to specify a different prior to be optimal in each case, our proposal RB-SDA does not need any distribution-dependent tuning. RB-SDA belongs to the family of Sub-sampling Duelling Algorithms (SDA) which combines the sub-sampling idea first used by the BESA [1] and SSMC [2] algorithms with different sub-sampling schemes. In particular, RB-SDA uses Random Block sampling. We perform an experimental study assessing the flexibility and robustness of this promising novel approach for exploration in bandit models.