# A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 10 Mar 2023.

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

- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses](https://mlsanity.com/paper/2205.07704/) (2022)
- [On Bayesian index policies for sequential resource allocation](https://mlsanity.com/paper/1601.01190/) (2016)
- [Maillard Sampling: Boltzmann Exploration Done Optimally](https://mlsanity.com/paper/2111.03290/) (2021)
- [Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits](https://mlsanity.com/paper/2206.03520/) (2022)
- [Sub-sampling for Efficient Non-Parametric Bandit Exploration](https://mlsanity.com/paper/2010.14323/) (2020)
- [On Limited-Memory Subsampling Strategies for Bandits](https://mlsanity.com/paper/2106.10935/) (2021)

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

- [Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms](https://mlsanity.com/paper/2304.03056/) (2023)
- [Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits](https://mlsanity.com/paper/2405.15200/) (2024)
- [Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Sampling](https://mlsanity.com/paper/2502.14379/) (2025)
- [The Confusing Instance Principle for Online Linear Quadratic Control](https://mlsanity.com/paper/2510.19531/) (2025)

## Abstract (arXiv)

In this paper we propose a general methodology to derive regret bounds for randomized multi-armed bandit algorithms. It consists in checking a set of sufficient conditions on the sampling probability of each arm and on the family of distributions to prove a logarithmic regret. As a direct application we revisit two famous bandit algorithms, Minimum Empirical Divergence (MED) and Thompson Sampling (TS), under various models for the distributions including single parameter exponential families, Gaussian distributions, bounded distributions, or distributions satisfying some conditions on their moments. In particular, we prove that MED is asymptotically optimal for all these models, but also provide a simple regret analysis of some TS algorithms for which the optimality is already known. We then further illustrate the interest of our approach, by analyzing a new Non-Parametric TS algorithm (h-NPTS), adapted to some families of unbounded reward distributions with a bounded h-moment. This model can for instance capture some non-parametric families of distributions whose variance is upper bounded by a known constant.