Bandit Algorithms Introduce Bias in Post-Experiment Inference.

Bandit algorithms, widely used for adaptive sampling in scenarios like A/B testing or recommendation systems, generate data that can introduce significant bias into subsequent statistical inference. This research systematically analyzes this "post-bandit inference bias" for stable index algorithms, including popular ones like UCB1. The study provides sharp mathematical expressions for the leading-order bias in sample means and expected Z-statistics. A key finding is the identification of an "effective exploration rate," a quantity dependent on the index function, which explains the algorithmic origin of this bias. For instance, under UCB1, the standardized bias for any arm that is not uniquely optimal decays at an exceptionally slow rate of 1/√log T. This slow decay implies that the bias can persist for a very long time. The research also uncovers a crucial regret-bias trade-off: algorithms designed for more exploration (to reduce regret) tend to increase bias, and vice versa. This characterization uses a novel empirical fluid approximation of the algorithm's sampling dynamics.