# Mixed-Effect Thompson Sampling

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 58 references that are in the map.
- First posted on arXiv 30 May 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Meta-Thompson Sampling](https://mlsanity.com/paper/2102.06129/) (2021)
- [Impact of Representation Learning in Linear Bandits](https://mlsanity.com/paper/2010.06531/) (2020)
- [Information-Theoretic Confidence Bounds for Reinforcement Learning](https://mlsanity.com/paper/1911.09724/) (2019)
- [Multi-Task Learning for Contextual Bandits](https://mlsanity.com/paper/1705.08618/) (2017)
- [Meta-learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2005.08531/) (2020)
- [Near-optimal Representation Learning for Linear Bandits and Linear RL](https://mlsanity.com/paper/2102.04132/) (2021)
- [Latent Bandits Revisited](https://mlsanity.com/paper/2006.08714/) (2020)
- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Meta Dynamic Pricing: Transfer Learning Across Experiments](https://mlsanity.com/paper/1902.10918/) (2019)
- [Sequential Transfer in Multi-armed Bandit with Finite Set of Models](https://mlsanity.com/paper/1307.6887/) (2013)
- [Provably Optimal Algorithms for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/1703.00048/) (2017)
- [Hierarchical Bayesian Bandits](https://mlsanity.com/paper/2111.06929/) (2021)
- [No Regrets for Learning the Prior in Bandits](https://mlsanity.com/paper/2107.06196/) (2021)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [IntelligentPooling: Practical Thompson Sampling for mHealth](https://mlsanity.com/paper/2008.01571/) (2020)
- [Metadata-based Multi-Task Bandits with Bayesian Hierarchical Models](https://mlsanity.com/paper/2108.06422/) (2021)
- [Multi-task Representation Learning with Stochastic Linear Bandits](https://mlsanity.com/paper/2202.10066/) (2022)
- [Deep Hierarchy in Bandits](https://mlsanity.com/paper/2202.01454/) (2022)
- [Metalearning Linear Bandits by Prior Update](https://mlsanity.com/paper/2107.05320/) (2021)
- [Bounded Regret for Finite-Armed Structured Bandits](https://mlsanity.com/paper/1411.2919/) (2014)
- [Variational inference for the multi-armed contextual bandit](https://mlsanity.com/paper/1709.03163/) (2017)
- [Towards Scalable and Robust Structured Bandits: A Meta-Learning Framework](https://mlsanity.com/paper/2202.13227/) (2022)

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

- [Exponential Smoothing for Off-Policy Learning](https://mlsanity.com/paper/2305.15877/) (2023)
- [Multi-Task Off-Policy Learning from Bandit Feedback](https://mlsanity.com/paper/2212.04720/) (2022)
- [reBandit: Random Effects based Online RL algorithm for Reducing Cannabis Use](https://mlsanity.com/paper/2402.17739/) (2024)
- [RoME: A Robust Mixed-Effects Bandit Algorithm for Optimizing Mobile Health Interventions](https://mlsanity.com/paper/2312.06403/) (2023)
- [Diffusion Models Meet Contextual Bandits](https://mlsanity.com/paper/2402.10028/) (2024)
- [Bayesian Off-Policy Evaluation and Learning for Large Action Spaces](https://mlsanity.com/paper/2402.14664/) (2024)
- [Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2402.05878/) (2024)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (2024)
- [Unified PAC-Bayesian Study of Pessimism for Offline Policy Learning with Regularized Importance Sampling](https://mlsanity.com/paper/2406.03434/) (2024)
- [Online Posterior Sampling with a Diffusion Prior](https://mlsanity.com/paper/2410.03919/) (2024)
- [Empirical Bayesian Multi-Bandit Learning](https://mlsanity.com/paper/2510.26284/) (2025)
- [Finite-Time Logarithmic Bayes Regret Upper Bounds](https://mlsanity.com/paper/2306.09136/) (2023)
- [Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals](https://mlsanity.com/paper/2606.14650/) (2026)
- [Leveraging Similarities in Multi-Armed Bandits](https://mlsanity.com/paper/2606.23414/) (2026)

## Abstract (arXiv)

A contextual bandit is a popular framework for online learning to act under uncertainty. In practice, the number of actions is huge and their expected rewards are correlated. In this work, we introduce a general framework for capturing such correlations through a mixed-effect model where actions are related through multiple shared effect parameters. To explore efficiently using this structure, we propose Mixed-Effect Thompson Sampling (meTS) and bound its Bayes regret. The regret bound has two terms, one for learning the action parameters and the other for learning the shared effect parameters. The terms reflect the structure of our model and the quality of priors. Our theoretical findings are validated empirically using both synthetic and real-world problems. We also propose numerous extensions of practical interest. While they do not come with guarantees, they perform well empirically and show the generality of the proposed framework.