Design Experiments To Compare Multi-armed Bandit Algorithms

Abstract

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 t

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keymeng2026design

Related papers

• Bayesian Bandits: Balancing The Exploration-exploitation Tradeoff Via Double Sampling (2017)0.00
• Computing The Performance Of A New Adaptive Sampling Algorithm Based On The Gittins Index In Experiments With Exponential Rewards (2023)0.00
• A Closer Look At The Worst-case Behavior Of Multi-armed Bandit Algorithms (2021)0.00
• A Frequency-domain Analysis Of The Multi-armed Bandit Problem: A New Perspective On The Exploration-exploitation Trade-off (2025)0.00
• Performance Comparisons Of Reinforcement Learning Algorithms For Sequential Experimental Design (2025)0.00
• Trading Off Rewards And Errors In Multi-armed Bandits (2026)0.00
• Adaptive Sequential Experiments With Unknown Information Arrival Processes (2019)0.00
• Pure Exploration Under Mediators' Feedback (2023)0.00