# Random Effect Bandits

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 30 references that are in the map.
- First posted on arXiv 23 Jun 2021.

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

- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Information-Theoretic Confidence Bounds for Reinforcement Learning](https://mlsanity.com/paper/1911.09724/) (2019)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [Multi-Armed Bandits with Correlated Arms](https://mlsanity.com/paper/1911.03959/) (2019)
- [Stochastic Rank-1 Bandits](https://mlsanity.com/paper/1608.03023/) (2016)
- [Perturbed-History Exploration in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1902.10089/) (2019)

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

- [reBandit: Random Effects based Online RL algorithm for Reducing Cannabis Use](https://mlsanity.com/paper/2402.17739/) (2024)
- [Robust Contextual Linear Bandits](https://mlsanity.com/paper/2210.14483/) (2022)
- [Provably Efficient Offline Reinforcement Learning with Perturbed Data Sources](https://mlsanity.com/paper/2306.08364/) (2023)
- [UCB Exploration for Fixed-Budget Bayesian Best Arm Identification](https://mlsanity.com/paper/2408.04869/) (2024)

## Abstract (arXiv)

This paper studies regret minimization in a multi-armed bandit. It is well known that side information, such as the prior distribution of arm means in Thompson sampling, can improve the statistical efficiency of the bandit algorithm. While the prior is a blessing when correctly specified, it is a curse when misspecified. To address this issue, we introduce the assumption of a random-effect model to bandits. In this model, the mean arm rewards are drawn independently from an unknown distribution, which we estimate. We derive a random-effect estimator of the arm means, analyze its uncertainty, and design a UCB algorithm ReUCB that uses it. We analyze ReUCB and derive an upper bound on its n-round Bayes regret, which improves upon not using the random-effect structure. Our experiments show that ReUCB can outperform Thompson sampling, without knowing the prior distribution of arm means.