A/B Test and Online Experiment Under Diminishing Marginal Effects: Regret Minimization and Statistical Inference

When large online platforms test a new strategy to implement with their user traffic, the phenomenon of diminishing marginal effects may arise. For example, when a strategy is implemented on 100% of the user traffic, the expected per-user effect can be lower compared to the expected per-user effect when a strategy is implemented on 10% of the user traffic, potentially due to limits of overall budget, resource, attention or content involved with that strategy. This diminishing marginal effect phenomenon brings an additional delicacy to online sequential experiments. In particular, for the classical goal of achieving the largest expected reward, the optimal decision may no longer be assigning 100% traffic to one strategy, but instead a mixture of strategies. We deliver two tasks for online sequential experiments in presence of diminishing marginal effect: (1) Adaptively identify the optimal traffic allocation to maximize the expected cumulative reward and (2) Construct valid central limit theorem (which is critically needed for A/B tests in online platforms) to perform reliable statistical inference for the expected reward under the optimal traffic allocation that is a priori unknown. We show that classical algorithms can fail to deliver the second task, especially because the statistical inference task presents its own difficulty. We develop a new online algorithm that leverages an additional smoothness condition on how the marginal effects change to achieve both tasks. We prove that this algorithm obtains the best achievable expected cumulative reward. Further, crucially for online platforms' need to do trustworthy statistical inference, the algorithm is proved to enjoy a valid central limit theorem. The theoretical findings are illustrated through numerical experiments.