Timezone: »
Poster
A/B/n Testing with Control in the Presence of Subpopulations
Yoan Russac · Christina Katsimerou · Dennis Bohle · Olivier Cappé · Aurélien Garivier · Wouter Koolen
Motivated by A/B/n testing applications, we consider a finite set of distributions (called \emph{arms}), one of which is treated as a \emph{control}. We assume that the population is stratified into homogeneous subpopulations. At every time step, a subpopulation is sampled and an arm is chosen: the resulting observation is an independent draw from the arm conditioned on the subpopulation. The quality of each arm is assessed through a weighted combination of its subpopulation means. We propose a strategy for sequentially choosing one arm per time step so as to discover as fast as possible which arms, if any, have higher weighted expectation than the control. This strategy is shown to be asymptotically optimal in the following sense: if $\tau_\delta$ is the first time when the strategy ensures that it is able to output the correct answer with probability at least $1-\delta$, then $\mathbb{E}[\tau_\delta]$ grows linearly with $\log(1/\delta)$ at the exact optimal rate. This rate is identified in the paper in three different settings: (1) when the experimenter does not observe the subpopulation information, (2) when the subpopulation of each sample is observed but not chosen, and (3) when the experimenter can select the subpopulation from which each response is sampled. We illustrate the efficiency of the proposed strategy with numerical simulations on synthetic and real data collected from an A/B/n experiment.
Author Information
Yoan Russac (Ecole Normale Supérieure)
Christina Katsimerou (Booking.com)
Dennis Bohle (booking.com)
Olivier Cappé (CNRS)
Aurélien Garivier (ENS Lyon)
Wouter Koolen (Centrum Wiskunde & Informatica, Amsterdam)
More from the Same Authors
-
2021 Spotlight: Sequential Algorithms for Testing Closeness of Distributions »
Aadil Oufkir · Omar Fawzi · Nicolas Flammarion · Aurélien Garivier -
2021 : Regret Minimization in Heavy-Tailed Bandits »
Shubhada Agrawal · Sandeep Juneja · Wouter Koolen -
2023 Poster: Beyond Average Reward in Markov Decision Processes »
Alexandre Marthe · Aurélien Garivier · Claire Vernade -
2023 Poster: Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games »
Hedi Hadiji · Sarah Sachs · Tim van Erven · Wouter Koolen -
2022 Poster: Luckiness in Multiscale Online Learning »
Wouter Koolen · Muriel F. Pérez-Ortiz -
2021 Poster: Sequential Algorithms for Testing Closeness of Distributions »
Aadil Oufkir · Omar Fawzi · Nicolas Flammarion · Aurélien Garivier -
2021 Poster: Navigating to the Best Policy in Markov Decision Processes »
Aymen Al Marjani · Aurélien Garivier · Alexandre Proutiere -
2021 Poster: Optimal Best-Arm Identification Methods for Tail-Risk Measures »
Shubhada Agrawal · Wouter Koolen · Sandeep Juneja -
2019 Poster: Pure Exploration with Multiple Correct Answers »
Rémy Degenne · Wouter Koolen -
2019 Poster: Weighted Linear Bandits for Non-Stationary Environments »
Yoan Russac · Claire Vernade · Olivier Cappé -
2019 Poster: Non-Asymptotic Pure Exploration by Solving Games »
Rémy Degenne · Wouter Koolen · Pierre Ménard -
2018 Poster: Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling »
Emilie Kaufmann · Wouter Koolen · Aurélien Garivier -
2017 Poster: Random Permutation Online Isotonic Regression »
Wojciech Kotlowski · Wouter Koolen · Alan Malek -
2017 Poster: Monte-Carlo Tree Search by Best Arm Identification »
Emilie Kaufmann · Wouter Koolen -
2017 Spotlight: Monte-Carlo Tree Search by Best Arm Identification »
Emilie Kaufmann · Wouter Koolen -
2016 Poster: Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning »
Wouter Koolen · Peter Grünwald · Tim van Erven -
2016 Poster: MetaGrad: Multiple Learning Rates in Online Learning »
Tim van Erven · Wouter Koolen -
2016 Oral: MetaGrad: Multiple Learning Rates in Online Learning »
Tim van Erven · Wouter Koolen -
2015 : Discussion Panel »
Tim van Erven · Wouter Koolen · Peter Grünwald · Shai Ben-David · Dylan Foster · Satyen Kale · Gergely Neu -
2015 Workshop: Learning Faster from Easy Data II »
Tim van Erven · Wouter Koolen -
2015 Poster: Minimax Time Series Prediction »
Wouter Koolen · Alan Malek · Peter Bartlett · Yasin Abbasi Yadkori -
2014 Poster: Efficient Minimax Strategies for Square Loss Games »
Wouter M Koolen · Alan Malek · Peter Bartlett -
2014 Poster: Learning the Learning Rate for Prediction with Expert Advice »
Wouter M Koolen · Tim van Erven · Peter Grünwald -
2013 Workshop: Learning Faster From Easy Data »
Peter Grünwald · Wouter M Koolen · Sasha Rakhlin · Nati Srebro · Alekh Agarwal · Karthik Sridharan · Tim van Erven · Sebastien Bubeck -
2013 Workshop: Large Scale Matrix Analysis and Inference »
Reza Zadeh · Gunnar Carlsson · Michael Mahoney · Manfred K. Warmuth · Wouter M Koolen · Nati Srebro · Satyen Kale · Malik Magdon-Ismail · Ashish Goel · Matei A Zaharia · David Woodruff · Ioannis Koutis · Benjamin Recht -
2013 Poster: The Pareto Regret Frontier »
Wouter M Koolen -
2012 Poster: Putting Bayes to sleep »
Wouter M Koolen · Dmitri Adamskiy · Manfred K. Warmuth -
2012 Spotlight: Putting Bayes to sleep »
Wouter M Koolen · Dmitri Adamskiy · Manfred K. Warmuth -
2011 Poster: Adaptive Hedge »
Tim van Erven · Peter Grünwald · Wouter M Koolen · Steven D Rooij -
2011 Poster: Learning Eigenvectors for Free »
Wouter M Koolen · Wojciech Kotlowski · Manfred K. Warmuth -
2010 Poster: Parametric Bandits: The Generalized Linear Case »
Sarah Filippi · Olivier Cappé · Aurélien Garivier · Csaba Szepesvari -
2009 Workshop: Temporal Segmentation: Perspectives from Statistics, Machine Learning, and Signal Processing »
Stephane Canu · Olivier Cappé · Arthur Gretton · Zaid Harchaoui · Alain Rakotomamonjy · Jean-Philippe Vert