Design Experiments to Compare Multi-armed Bandit Algorithms

Authors	Huiling Meng et al.
Year	2026
Field	Machine Learning
arXiv	2603.05919
PDF	Download
Categories	cs.LG, stat.ML

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 dependent 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ïve design has a linearly-growing variance. Numerical experiments with UCB, Thompson Sampling, and $ε$-greedy policies confirm these theoretical gains.

---

Engineering Breakdown

Plain English

This paper addresses a fundamental problem in online experimentation: comparing bandit algorithms like UCB and Thompson Sampling is expensive because each algorithm run produces only one dependent trajectory, requiring many costly independent restarts. The authors propose Artificial Replay (AR), an experimental design technique that runs one policy first, records its trajectory, then reuses those recorded rewards when a second policy takes the same actions—querying the real environment only for new action selections. This dramatically reduces the number of independent algorithm runs needed while maintaining statistical validity, making bandit algorithm comparison faster and cheaper for production deployment decisions.

Core Technical Contribution

The core innovation is Artificial Replay: a clever counterfactual inference mechanism that decouples the cost of comparing two bandit algorithms by allowing policy B to reuse observed rewards from policy A's historical trajectory whenever their action selections overlap. Unlike standard A/B testing where treatments are static, bandit algorithms adapt their decisions online, making naive policy comparison wasteful; AR solves this by recognizing that the reward for action X in context Y is invariant across policies, so only new exploration paths require real environment queries. This moves bandit experimentation from requiring N independent full-horizon runs per policy to requiring roughly one run per policy plus marginal queries, achieving order-of-magnitude sample efficiency gains.

How It Works

The Artificial Replay protocol operates in two phases: (1) Policy A executes for T steps against the real environment, recording a complete trajectory of (context, action, reward) tuples; (2) Policy B then executes the same T-step horizon, but with modified feedback—whenever B selects an action that A previously selected in a similar context, B receives the logged reward instead of querying the environment, and when B selects a novel action, it queries the real environment and logs that new reward. The key insight is that rewards are deterministic functions of actions (or at least their expectations are consistent across policy executions within reasonable time windows), so reward reuse is statistically valid. The second policy's trajectory is built from a hybrid of cached and fresh rewards, reducing environment interactions by roughly the overlap percentage between the two policies' action sequences. At the end, both policies' final performance metrics are estimated from their respective trajectories, and standard inference (confidence intervals, hypothesis tests) can be applied because the trajectories are now independent despite the reward sharing.

Production Impact

For teams running online experiments at scale (ride-sharing, recommendations, ads), this technique cuts experimentation cost dramatically. Instead of running each bandit algorithm variant for weeks or months on real traffic, AR lets you compare policies in days by reusing logged rewards from the first policy run; this accelerates deployment decisions and reduces opportunity cost of running suboptimal policies in production. Integration is straightforward: log all (action, context, reward) tuples from your baseline policy run into a lookup table, then when evaluating candidate policies, check the cache first before hitting your live environment—no changes to the bandit algorithms themselves. Trade-offs include a dependency on reward stationarity (if user preferences drift over time, cached rewards become stale and comparisons become biased), and you must ensure the first policy's trajectory is representative (if it explores poorly, the second policy may be unable to evaluate actions it cares about). The approach also assumes you can accurately key/match contexts across time, which can be fragile if your state space is high-dimensional or noisy.

Limitations and When Not to Use This

This method assumes reward stationarity within the experimental window—if user behavior, seasonality, or environment dynamics shift between policy A's execution and policy B's execution, reused rewards become confounded and comparisons fail. The technique is biased toward policy B: since B gets to see A's rewards, B has an inherent information advantage when A was exploratory; the paper likely addresses this through careful statistical adjustment, but residual bias may remain in practice. AR also cannot compare policies that fundamentally require different action spaces or contexts, since there's no cached reward to reuse for unseen states—policies must operate over the same domain. Finally, this is an offline experimental design improvement, not a solution to the underlying bandit learning problem; it doesn't help you learn better bandit policies, only compare existing ones more efficiently.

Research Context

This work sits at the intersection of causal inference, experimental design, and online learning—directly extending the A/B testing playbook to the harder setting of adaptive algorithms. It builds on decades of bandit algorithm research (Robbins' classic work through modern variants like Contextual Thompson Sampling) by acknowledging that the bottleneck is not algorithm design but expensive experimentation. The paper likely relates to counterfactual estimation literature (inverse probability weighting, doubly robust estimation) and offline RL, where reusing logged data is standard practice. This opens a research direction on sample-efficient algorithm comparison: future work might explore AR variants that weight cached rewards adaptively, handle non-stationary environments, or extend to comparing deep RL policies where state spaces are high-dimensional and matching becomes harder.

---

:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::

---

Back to Research Lab → · Subscribe to AI Letters →