# Batch Ensemble for Variance Dependent Regret in Stochastic Bandits

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 14 references that are in the map.
- First posted on arXiv 13 Sep 2024.

## Builds on (most cited first, 6 of 6)

- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Ensemble Bootstrapping for Q-Learning](https://mlsanity.com/paper/2103.00445/) (2021)
- [Perturbed-History Exploration in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1902.10089/) (2019)
- [Residual Bootstrap Exploration for Bandit Algorithms](https://mlsanity.com/paper/2002.08436/) (2020)
- [Sub-sampling for Efficient Non-Parametric Bandit Exploration](https://mlsanity.com/paper/2010.14323/) (2020)

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

- [IL-SOAR : Imitation Learning with Soft Optimistic Actor cRitic](https://mlsanity.com/paper/2502.19859/) (2025)
- [Provably avoiding over-optimization in Direct Preference Optimization without knowing the data distribution](https://mlsanity.com/paper/2602.06239/) (2026)
- [Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning](https://mlsanity.com/paper/2606.20107/) (2026)

## Abstract (arXiv)

Efficiently trading off exploration and exploitation is one of the key challenges in online Reinforcement Learning (RL). Most works achieve this by carefully estimating the model uncertainty and following the so-called optimistic model. Inspired by practical ensemble methods, in this work we propose a simple and novel batch ensemble scheme that provably achieves near-optimal regret for stochastic Multi-Armed Bandits (MAB). Crucially, our algorithm has just a single parameter, namely the number of batches, and its value does not depend on distributional properties such as the scale and variance of the losses. We complement our theoretical results by demonstrating the effectiveness of our algorithm on synthetic benchmarks.