# Design Experiments to Compare Multi-armed Bandit Algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 37 references that are in the map.
- First posted on arXiv 6 Mar 2026.

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

- [More Robust Doubly Robust Off-policy Evaluation](https://mlsanity.com/paper/1802.03493/) (2018)
- [Optimal and Adaptive Off-policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/1612.01205/) (2016)
- [Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes](https://mlsanity.com/paper/2110.15332/) (2021)
- [Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits](https://mlsanity.com/paper/2106.02029/) (2021)
- [Experimental Design in Two-Sided Platforms: An Analysis of Bias](https://mlsanity.com/paper/2002.05670/) (2020)
- [Design and Analysis of Switchback Experiments](https://mlsanity.com/paper/2009.00148/) (2020)
- [Why Adaptively Collected Data Have Negative Bias and How to Correct for It](https://mlsanity.com/paper/1708.01977/) (2017)
- [A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms](https://mlsanity.com/paper/2106.02126/) (2021)
- [Markovian Interference in Experiments](https://mlsanity.com/paper/2206.02371/) (2022)
- [Policy Learning with Adaptively Collected Data](https://mlsanity.com/paper/2105.02344/) (2021)
- [The Fragility of Optimized Bandit Algorithms](https://mlsanity.com/paper/2109.13595/) (2021)
- [Switchback Experiments under Geometric Mixing](https://mlsanity.com/paper/2209.00197/) (2022)
- [Weak Signal Asymptotics for Sequentially Randomized Experiments](https://mlsanity.com/paper/2101.09855/) (2021)
- [Artificial Replay: A Meta-Algorithm for Harnessing Historical Data in Bandits](https://mlsanity.com/paper/2210.00025/) (2022)
- [Data-Driven Switchback Experiments: Theoretical Tradeoffs and Empirical Bayes Designs](https://mlsanity.com/paper/2406.06768/) (2024)
- [Regret Distribution in Stochastic Bandits: Optimal Trade-off between Expectation and Tail Risk](https://mlsanity.com/paper/2304.04341/) (2023)
- [Reducing Symbiosis Bias Through Better A/B Tests of Recommendation Algorithms](https://mlsanity.com/paper/2309.07107/) (2023)
- [Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs](https://mlsanity.com/paper/2503.01134/) (2025)
- [Experimental Design For Causal Inference Through An Optimization Lens](https://mlsanity.com/paper/2408.09607/) (2024)
- [Choosing the Better Bandit Algorithm under Data Sharing: When Do A/B Experiments Work?](https://mlsanity.com/paper/2507.11891/) (2025)
- [Debiasing Samples from Online Learning Using Bootstrap](https://mlsanity.com/paper/2108.00236/) (2021)
- [Tackling Interference Induced by Data Training Loops in A/B Tests: A Weighted Training Approach](https://mlsanity.com/paper/2310.17496/) (2023)
- [Bandit Allocational Instability](https://mlsanity.com/paper/2602.07472/) (2026)
- [Improving the Estimation of Lifetime Effects in A/B Testing via Treatment Locality](https://mlsanity.com/paper/2407.19618/) (2024)

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

- [Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing](https://mlsanity.com/paper/2608.12831/) (2026)

## Abstract (arXiv)

Online platforms routinely compare multi-armed bandit algorithms, such as UCB and Thompson Sampling, to select the best-performing policy. Unlike standard A/B tests for static treatments, each run of a bandit algorithm over T users produces only one trajectory, because the algorithm's decisions depend on all past interactions. Reliable inference therefore demands many independent restarts of the algorithm, making experimentation costly and delaying deployment decisions. We propose Artificial Replay (AR) as a new experimental design for this problem. AR first runs one policy and records its trajectory. When the second policy is executed, it reuses a recorded reward whenever it selects an action the first policy already took, and queries the real environment only otherwise. We develop a new analytical framework for this design and prove three key properties of the resulting estimator: it is unbiased; it requires only T + o(T) user interactions instead of 2T for a run of the treatment and control policies, nearly halving the experimental cost when both policies have sub-linear regret; and its variance grows sub-linearly in T, whereas the estimator from a na"ive design has a linearly-growing variance. Numerical experiments with UCB, Thompson Sampling, and ε-greedy policies confirm these theoretical gains.