On the Advances and Challenges of Adaptive Online Testing
Bo Yang∗

Da Xu∗

LinkedIn Corporation
Sunnyvale, California, USA
by9ru@virginia.edu

Walmart Labs
Sunnyvale, California, USA
daxu5180@gmail.com

ABSTRACTIn recent years, the interest in developing adaptive solutions foronline testing has grown significantly in the industry. While theadvances related to this relative new technology have been developed in multiple domains, it lacks in the literature a systematicand complete treatment of the procedure that involves exploration,
inference, and analysis. This short paper aims to develop a comprehensive understanding of adaptive online testing, including various
building blocks and analytical results. We also address the latest
developments, research directions, and challenges that have beenless mentioned in the literature.

KEYWORDS
Adaptive decision making, Online exploration, Confidence boundmethod, Hypothesis testing, Information theory
ACM Reference Format:
Bo Yang and Da Xu∗ . 2022. On the Advances and Challenges of Adaptive
Online Testing. In Workshop on Decision Making for Modern Information
Retrieval System (WSDM ’22), February 21–25, 2022, Tempe, AZ, USA. ACM,
New York, NY, USA, 5 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn

1

INTRODUCTION

Decision making in modern industry is often driven by randomized
experiments behind the scenes. In particular for IT companies,
the production scenario ranges from deciding the best-performing
recommendation system to determining the size of an ad banner.
The traditional process of simultaneously launching alternative
services to randomly assigned users is also known as online A/B/n
testing [12, 25]. While A/B/n testing and its variants enjoy a highdegree of simplicity in planning and making inference, they stilllack adaptability when certain alternatives become clearly inferior.
Perhaps the most critical consequence would lost revenue anduser satisfaction, so optimizing online testing strategy has become
imperative for many, if not all.
We start our discussion by first characterizing an online experimentation. By convention, we use the notion of arm to indicate suchas a candidate webpage service, denote by: 𝑎 ∈ A with |A| = 𝑘 + 1.
Sampling (obtaining) an observation from arm 𝑎 is represented by:
𝑋𝑎,𝑖 ∼ 𝑃𝑎 , 𝑖 ∈ {1, . . . , 𝑛𝑎 }, where 𝑃𝑎 is the reward (e.g. impressionrate, revenue, return of investment) distribution associated witharm 𝑎. We use 𝑎 0 denote the control arm which often refers to thecurrently deployed service. We will follow this convention unlessspecified. While 𝑋𝑎,𝑖 are often assumed to be identically distributed
under each arm 𝑎, they are not necessarily independent. Handlingdependency will be an important topic in our following discussion, since it cannot be avoided by adaptive exploration, but would
violate traditional statistics inference assumptions [8].
∗ The two authors contribute equally to this work.

For the most part, the inference goal of an online experiment is
to test a statistical hypothesis often related to the data distribution,e.g. whether or not 𝜇 1 > 𝜇 2 where 𝜇𝑞 := E[𝑋𝑎𝑞 ,𝑖 ] is the expected
reward for arm 𝑞. The outcome of a hypothesis testing is usually
expressed via the null hypothesis 𝐻 0 , alternative hypothesis 𝐻 1 , asignificance level 𝛼 ∈ (0, 1), and the observed samples. For example,
when 𝐻 0 is rejected, it holds:𝑃𝑟 rejecting 𝐻 0 for 𝐻 1 | 𝐻 0 is true ≤ 𝛼,(1)
In other words, it is unlikely that 𝐻 1 better characterizes the observed data distribution just by chance. Also, the control arm 𝑎 0
usually plays a pivotal role in the hypothesis’s design: 𝑎 0 is often
assumed to be superior unless overturned by enough evidence.
Practically for IT companies, adaptive online testing means the
proportion of traffic guided to each arm during the random assignment can be adjusted based on the performance to date. Since
the purpose of online testing is purely exploratory, i.e. to explore
as much as possible without worrying about the cost, the problem setting differs naturally from bandit or reinforcement learningwhere exploitation is mandatory [5, 31]. Nevertheless, some exploration strategies from the bandit literature also suit the pure
exploration task [26], and they are often studied under the best-arm
identification problem [4, 27].
In particular, suppose 𝑎 [𝑖 ] is the arm with the 𝑖 th highest reward,
and denote by: Δ 𝑗 = 𝜇𝑎 [1] − 𝜇𝑎 𝑗 which is the suboptimality gap ofarm 𝑎 𝑗 . We use h𝑇 to represent the first 𝑇 samples where h𝑇 ∈ H𝑇 .
The exploratory algorithms from best-arm identification can be
described by a stopping time1 𝑇 and a data-adaptive decision rule D :H𝑇 → [𝑘] such that when the algorithm halts, the probability that𝑎 [1] is not identified (which equivalents to the event of ΔD(h𝑇 ) > 0)
becomes small:
𝑃𝑟 𝑇 < ∞ and ΔD(h𝑇 ) > 0 ≤ 𝛿,(2)where 𝛿 ∈ (0, 1) is also some pre-defined confidence level.
While best-arm identification and hypothesis testing are similarin finding the best candidate (hypothesis or arm) with some tolerance of making mistake due to randomness, their meanings areultimately different. One apparent reason is that the probability in(2) is taken w.r.t. the sampling and reward distributions, while theconditional probability in (1) is taken w.r.t. the distribution under𝐻 0 . The conclusion of one problem does not directly imply another.
Meanwhile, notice that as long as the correct statistical procedure
is employed, the hypothesis testing does not necessarily depend on
the sampling strategy. There is possibility to employ the samplingstrategy from best-arm identification and use hypothesis testing aspart of the stopping rule. This integration may bring adaptability
to online testing while not costing its statistical rigorousness. Now
both problems will be subject to new changes:
1 We assume the measurability of 𝑇 is granted throughout our discussion.

Bo Yang and Da Xu∗

WSDM ’22, February 21–25, 2022, Tempe, AZ, USA• the current sample may depend on the past ones due to theadaptive sampling strategy;• there will be continuous interactions between the stopping criteria (and stopping time) of the best-arm identification, the p-value,
and the significance level of hypothesis testing.
The first change rules out traditional hypothesis testing procedures(such as the Student’s t-test) since the observations are no longer
i.i.d. The impact of the second change is more involved since it concerns the working mechanisms of both best-arm identification andhypothesis testing. The good news is we can leverage confidencebounds to connect the decision-makings of best-arm identification
with hypothesis testing. Nevertheless, the nature of p-value andsignificance level will be different in the sequential setting, and theyneed to be adjusted along the path of adaptive exploration. Finally,
even the best strategy may struggle to find the best-performing arm
if the structure of a particular problem instance is unfriendly. Studying this instance-wise difficulty would be valuable for understanding
the inherent challenges of adaptive online testing.
Section 2 covers the basics of pure exploration and hypothesis
testing with a highlight on confidence interval. We study in Section
3 the more advanced tools and solutions for integrating interact
hypothesis testing with best-arm identification. In Section 4, we
discuss the difficulty of best-arm identification and the challenges
for adaptive online testing. We may omit technical details for thesake of space, and readers may refer to the references provided.
Contribution: since our paper is the first in IR literature thatsystematically discuss exploration, inference, and analysis of adaptive online testing, it aims to serve both as introductory material
for unfamiliar readers and a technical summary for domain experts.

2

PURE EXPLORATION, CONFIDENCE
INTERVAL, AND P-VALUE

The best-arm identification in (2), which we described as a pure
exploration problem, takes the fixed confidence setup2 [15]. Using
exploration strategy to optimize online problems means finding
the optimal arm with as few samples as possible. In particular, thestrategy must be carefully designed so each arm is explored justenough to be separated from the others with high confidence. The
traditional A/B/n testing acts like a uniform exploration policy where
the stopping rule is to reach the maximum round of experimentsor reject the null hypothesis. Probably the most important idea
behind many pure exploration algorithms is the confidence bound(CB) method [5], where empirical uncertainty is used to constructoptimistic/pessimistic overestimations of the mean reward.
Note that the randomness in finite samples can cause any esti 𝑘mation of 𝜇𝑖 𝑖=1 subject to uncertainty. Under mild distribution
assumptions such as 𝑃𝑎 is Gaussian or sub-Gaussian, there existsa (provably tight) region that contains 𝜇𝑖 with arbitrarily highprobability. The region is often constructed using finite-sample
concentration results such as the Hoeffding or Chernoff inequalities[7], which we exemplify as below.
Lemma 1 (Concentration of i.i.d. mean). Assume 𝑋𝑎,𝑖 , 𝑎 =0, . . . , 𝑘 are independent, 𝜎-sub-Gaussian random variables. Then for
2 There are two related but different settings in best-arm identification: fixed confidence

and fixed budget. The solutions can often be switched between the two settings [14],so we stick with the fixed confidence problem which has been studied in more depth.

any 𝜖 > 0:𝑛𝑎
 1 ∑︁

−𝑛𝑎 𝜖 2
𝑋𝑎,𝑖 − 𝜇𝑎 ≥ 𝜖 ≤ exp(),
𝑛𝑎 𝑖=1
2𝜎 2
Í 𝑎
𝑋𝑎,𝑖 − 𝜇𝑎 ≤ −𝜖).
and the same bound holds for 𝑃𝑟 ( 𝑛1𝑎 𝑛𝑖=1
𝑃𝑟

(3)

We immediately observe that by solving for exp( −𝑛2𝜎𝑎2𝜖 ) = 𝛿2 , itholds with probability at least 1 − 𝛿:
√︃
√︃


𝜇𝑎 ∈ 𝜇ˆ𝑎 − 2𝜎 2 log(1/𝛿)/𝑛𝑎 , 𝜇ˆ𝑎 + 2𝜎 2 log(1/𝛿)/𝑛𝑎 , (4)
|
{z
} |
{z
}
2

LCB (𝑎) (𝑛𝑎 ,𝛿)UCB (𝑎) (𝑛𝑎 ,𝛿)Í𝑛𝑎where 𝜇ˆ𝑎 = 1/𝑛𝑎 · 𝑖=1 𝑥𝑎,𝑖 , and LCB and UBC are shorthands forthe lower/upper confidence bound. Both 𝑈𝐶𝐵 and 𝐿𝐶𝐵 express as:𝜇ˆ ± CI(𝑛𝑎 , 𝛿), where 𝐶𝐼 is the confidence interval that depends on
the sample size and confidence level 𝛿.
For any two arms 𝑎 1 and 𝑎 2 , LCB (𝑎1 ) and UCB (𝑎2 ) provide thepessimistic and optimistic estimation of 𝜇1 and 𝜇2 , respectively.
If LCB (𝑎1 ) > UCB (𝑎2 ) , it is easy to show that 𝜇 1 > 𝜇 2 with highprobability, again by using concentration inequalities. Therefore,
the CB method provides an elegant but powerful approach to tailor
decision making based on the uncertainty of an estimation. The
two major algorithms for best-arm identification, namely Action
Elimination and Upper Confidence Bound, both rely on CB:• Action Elimination [11]: sample from each arm a pre-determined𝑛 init times, and eliminate according to: UCB (𝑎𝑖 ) < LCB (𝑎0 ) where𝑎 0 is a reference arm. Continue until only one arm is left.
• Upper Confidence Bound [4, 17]: keep sampling from the arm
indexed by arg max𝑎 UCB (𝑎) , and stop when there exists an 𝑎 ∗∗such that: LCB (𝑎 ) ≥ UCB (𝑎𝑖 ) for all 𝑖 = 1, . . . , 𝑘.
We point out that both approaches have their limitations whenused as an exploration strategy for online testing. The merit of
Action Elimination is to throw away arms only after we accumulate
enough confidence on their suboptimality. Although it improves
upon the uniform exploration, the suboptimal arms is still likely
to be explored more than necessary. The Upper Confidence Boundis on the opposite side: the leading arm will be overexplored, andeven the second-best arm may be underexplored. Luckily, both ofthem can be improved by using an variant of the Upper Confidence
Bound method, which is known as LUCB. LUCB aims to find abetter balance between exploring the leading arm and others:• LUCB [20, 23]: keep sampling from both the current best and
𝑘second-best arm (denote by 𝑎 ∗ and 𝑎 ∗∗ ) in terms of 𝑈 𝐶𝐵 (𝑖) 𝑖=1 ,∗∗∗and stop when: LCB (𝑎 ) > UCB (𝑎 ) .
For all the above algorithms, confidence intervals not only guides
how to explore, but also decides when to stop. As we show next,
this will be an advantage for bringing in hypothesis testing, because
confidence intervals can also be related to p-value.
Although criticized for biasing scientists and researchers towarda particular perspective of experimentation [3], p-value remains
an important metric to understand the significance of a discovery.
Generally speaking, p-value is the probability of obtaining test
results at least as extreme as what is observed, if the null hypothesis
𝐻 0 is correct. It usually involves a test statistic 𝑍 whose distribution
is known under 𝐻 0 . Suppose the observed test statistic is 𝑧, thenOn the Advances and Challenges of Adaptive Online Testing

the probability of having more extreme value on both sides of the
distribution is given by: 𝑃𝑟 |𝑍 > 𝑧| 𝐻 0 .
When the quantity of interest is mean reward, one straightforÍ 0Í 𝑘
𝑋𝑎0 ,𝑖 − 𝑛1𝑘 𝑛𝑖=1
ward choice is letting: 𝑍𝑘 := 𝑛10 𝑛𝑖=1
𝑋𝑎𝑘 ,𝑖 . Under
the null hypothesis 𝐻 0 : 𝜇𝑎0 = 𝜇𝑎𝑘 , for independent (sub)-Gaussian
𝑋𝑖 , the test statistic 𝑍𝑘 follows a zero-mean (sub)-Gaussian distribution. If the distribution of 𝑍𝑘 is symmetric, the p-value is:
𝑃𝑟 |𝑍𝑘 > 𝑧𝑘 | 𝐻 0 = 𝑃𝑟

𝑛𝑘
𝑛0

1 ∑︁
1 ∑︁
𝑋𝑎 ,𝑖 > |𝑧𝑘 | .
𝑋𝑎0 ,𝑖 −𝑛 0 𝑖=1
𝑛𝑘 𝑖=1 𝑘

As an immediate result, p-values can also be obtained from concentration inequalities similar to the ones in Lemma 1, since they bothmeasure the deviations under some fixed distribution. Following
the same logic as CB, it is easy to check that 𝑃𝑟 𝑍𝑘 > 𝑧𝑘 𝐻 0 ≤𝛼 (which 𝛼 is the pre-defined significance level) also leads to aconfidence-interval-based decision making, e.g.:
reject 𝐻 0 if 𝑧𝑘 ∉ −CB(𝑛𝑘 , 𝑛 0, 𝛼), CB(𝑛𝑘 , 𝑛 0, 𝛼) ,where CB is the associated confidence interval whose expression weomit here for brevity. In fact, interested readers may check that thesingle-arm p-values for comparing 𝑎 0 and 𝑎𝑘 under 𝐻 0 : 𝜇𝑎0 ≥ 𝜇𝑎𝑘
can be obtained by inverting 𝐿𝐶𝐵 and 𝑈𝐶𝐵 via [24]:𝑃𝑛𝑎 ,𝑛𝑘 = sup 𝛾 ∈ [0, 1] LCB (𝑎𝑘 ) (𝑛𝑘 , 𝛾) ≥ UCB (𝑎0 ) (𝑛 0, 𝛾) . (5)The above link between p-value and confidence interval demonstrate the feasibility of combining best-arm identification with hypothesis testing. In particular, there could exist a unified decisionmaking procedure using only confidence intervals. However, there
are several obstacles that require further investigation, notably:(1) how to obtain valid confidence intervals when the observations
are no longer independent;(2) how to make sure the p-value is always valid and the false
discovery rate is controlled, since the testing can be queried by
the adaptive exploration algorithm at any time.
In the next section, we discuss some of the more advanced tools
and methodologies that may address the above challenges.

3

ADVANCES IN BEST-ARM IDENTIFICATION
AND HYPOTHESIS TESTING

When 𝑋𝑖 are not independent, or when the sample size 𝑛(𝑇 ) itself
Íis a random variable that depends on some stopping time, 𝑛𝑖=1 𝑋𝑎,𝑖becomes a random walk whose concentration behavior differs fromthe Hoeffding-type inequalities we introduced earlier. Historically,
the law of iterated logarithm (LIL) [16] was developed to describe
the asymptotic behavior of a zero-mean unit-variance random walk:Í𝑛𝑋𝑖
lim sup √︁ 𝑖=1= 1, almost surely.
(6)𝑛→∞2𝑛 log log 𝑛
Unfortunately, LIL only characterizes the limiting behavior, while
real-world online testings often falls into the finite-sample regime.
The recent work by Zhao et al. [33] propose a novel finite-sample
bound for such cases, from which we can construct confidence
intervals for both best-arm identification and hypothesis testing.
Lemma 2 (Concentration of random walk). Let 𝑇 be anyÍrandom variable taking value in N. Let 𝑆𝑇 := 𝑇𝑖=1 𝑋𝑖 . There exists

WSDM ’22, February 21–25, 2022, Tempe, AZ, USA

𝑎 > 0 such that:√︃
𝑃𝑟 𝑆𝑇 ≥ 0.6𝑛 log(log1.1 𝑛 + 1) + 𝑎𝑛 ≤ 12 exp(−1.8𝑎).

(7)Comparing√︁ the convergence rates implied by Lemma 1 and 2,
we spot a log log 𝑛 difference caused by the extra stochasticity
from dependent observations. This also holds asymptotically if
we compare LIL with the law of large numbers. As a result, theconfidence intervals for adaptive online testing may just be wider
than its non-adaptive counterpart. It means that under the samecontext, more observations may be required to trigger a decision.
Now that we know how to compute confidence bounds correctly,
the next challenge is to make p-values valid at all times. This stepis critical if the stopping rule of online exploration can consult thep-value at any time. Just like having a monkey randomly tap a
typewriter indefinitely, it will almost surely enter any given text.
Ideally, an any-time p-value should allow guilt-free queries from thecontinuing adaptive exploration strategy, and the previous study byJohari et al. [19] suggests that a always valid p-value is a stochastic
process {𝑃 (𝑡 ) }𝑡∞=1 such that for any (random) stopping time𝑇 , under
any distribution P H0 that agrees with the null hypothesis, we have:
P H0 (𝑃 (𝑇 ) ≤ 𝛼) ≤ 𝛼 .

(8)Note that this definition extends a classical property of p-value thatit should follows uniform distribution under P H0 .
Recently, Yang et al. [32] proposes taking the minimum of all
single-arm p-value, from all the previous steps, to obtain an anytime p-value such that it satisfies (8). For instance, at step 𝑇 , let𝑛 0 (𝑇 ) and 𝑛𝑘 (𝑇 ) be the #samples from arm 𝑎 0 and 𝑎𝑘 collecteduntil the 𝑇 th step, then the any-time p-value for the experiment is:(𝑇 )𝑃𝑎0 ,𝑎𝑘 := min min 𝑃𝑛0 (𝑇 ),𝑛𝑖 (𝑇 ) .
𝑠 ≤𝑇 𝑖=1,...,𝑘The idea being taking all the minimums is to make sure that:Ð Ð 
P 𝑘𝑗=1 𝑡∞=1 𝑃𝑛0 (𝑡 ),𝑛 𝑗 (𝑡 ) ≤ 𝛼 ≤ 𝛼, so 𝑃 (𝑇 ) is always valid.
It is also known that controlling the false alarm error of each test
is not sufficient to achieve a small false discovery rate (FDR) when
multiple testings occur. Let 𝛼 (𝑡 ) be the significancelevel at step𝑡. When running an adaptive online testing, 1 𝑃 (𝑡 ) < 𝛼 (𝑡 ) will
be queried multiple times. Therefore, to control FDR in an online
fashion (we use 𝑅 (𝑡 ) = 1 to denote claiming a discovery at step 𝑡),(𝑡 −1)
it is intuitive that 𝛼 (𝑡 ) should be aware of the history {𝑅 ( 𝑗) } 𝑗=1 :𝛼 (𝑡 ) := 𝛼 (𝑡 ) 𝛼; 𝑅 (1) , . . . , 𝑅 (𝑡 −1) ,by using a proper
decision rule 𝛼 (𝑡 ) .iFormally, the FDR at step 𝑡 ish#True discoveries
defined as E #Discoveries
made before 𝑡 . In the non-adaptive setting,the Benjamini-Hochberg procedure is a standard way to control FDR[6]. For adaptive experimentation, we find the idea of "𝛼-investing"powerful for controlling online FDR [13]. The general idea is tolet the decision rule 𝛼 (𝑡 ) "invest" a small amount of confidence
each time when a testing is called, and 𝛼 (𝑡 ) will gain some reward
if a discovery is claimed. By choosing the proper investment andreward function, this procedure has been shown to achieve FDR
control. The implementation is quite straightforward and readers
may refer to the references herein [2, 18, 28].

Bo Yang and Da Xu∗

WSDM ’22, February 21–25, 2022, Tempe, AZ, USA

We now put together the pieces and present an exemplary adaptive online testing procedure. We first sample from each arm 𝑛 init
times for warm-start. After that, at each step 𝑡:(1) Obtain the adjusted significance level 𝛼 (𝑡 ) using the history−1 and rejections {𝑅 ( 𝑗) }𝑡 −1 , with 𝛼-investing.
p-values {𝑃 ( 𝑗) }𝑡𝑗=1
𝑗=1

 𝑘
(2) First follow LCUB: compute UCB𝑎𝑖 𝑛𝑖 (𝑡), 𝛼 (𝑡 ) 𝑖=0 , find 𝑎 ∗∗∗∗∗and 𝑎 ∗∗ . If not LCB𝑎 > UCB𝑎 and LCB𝑎 > UCB𝑎0 , sample∗∗∗
from 𝑎 and 𝑎 ; otherwise return them. Then compute andtrack the any-time p-value 𝑃 (𝑡 ).
(3) Record 𝑅 (𝑡 ) = 1 𝑃 (𝑡 ) > 𝛼 (𝑡 ) , and decide whether to stop
based on 𝑅 (𝑡 ) or other stopping criteria.

4

CHALLENGES OF ADAPTIVE ONLINETESTING

Although the recent advancements can refine the procedure ofadaptive online testing, they do not change the nature of the problem, especially its inherent difficulty. Here, the difficulty refers
to the minimum number of samples required by whatever smart
algorithm to achieve high-confidence decisions. For simplicity, assuming that each arm has unit variance. For uniform exploration,
it is obvious that the difficulty lies exactly in how separable theset of arms are (in terms of 𝜇𝑎 ). Adaptive explorations may help us
eliminate inferior arms faster, but the optimality of the eventual
performance will depend more heavily on the gap between 𝑎 [1]and 𝑎 [2] . In general, the distribution patterns of the suboptimality
gaps can induce different levels of difficulty for exploration, andthe recently Chen et al. [9] reveals a (tight) lower bound to justify
this phenomenon.
In the theoretical literature, information-theoretical lower boundif often used to describe the amount of information needed to
specify the answer related a particular problem instance. In the caseof best-arm identification, the problem instance can be effectively𝑘described by the set: I = Δ [ 𝑗 ] 𝑗=2 , where Δ [ 𝑗 ] := 𝜇𝑎 [1] − 𝜇𝑎 [ 𝑗 ] .
Lemma 3 (Difficulty of best-arm identification.). Let𝑇D (I, 𝛿)
be the stopping time for applying D on problem I such that it achieves
the 𝛿-correctness defined in (2). It holds that:
inf 𝑇D (I, 𝛿) = O
D

𝑘

 ∑︁
 lnlnΔ−1
1  1
[2]
ln
+𝐻
(I)
+
polylog(𝑘, 𝛿 −1 ) ,
2
2
𝛿
Δ [2]
𝑗=2 Δ [ 𝑗 ]where 𝐻 (I) is an entropy term of the set I.
Before we discuss this result, recall that adaptive exploration
does not account for the asymmetry of the null and alternative
hypothesis. Yang et al. [32] recently propose to give the control
arm a little bit of edge by manually increasing its estimation bysome 𝜖 > 0 at all time. Note that this procedure can change thegaps by at most 𝜖, so our following discussions are not affected bythis modification.
There are three quantities essential to the lower bound: 1). theÍterm 𝑘𝑗=2 1/Δ2[ 𝑗 ] which measures the overall complexity (total gap)of the problem instance; 2). the gap 1/Δ2[2] between the best arm
and the strongest contender; 3). the amount of variation (or divergence) in the gaps’ distribution, as reflected by 𝐻 (I). In general,the problem becomes more difficult when the gaps (especially Δ [2] )become smaller or more diverged.
The above result leads to our discussion on the challenges ofadaptive online testing. Intuitively, adaptive exploration will be
more efficient as we increase the number of arms. But now weunderstand how adding arms can also boost the complexity (eitherÍ𝑘22
𝑗=2 1/Δ [ 𝑗 ] or 1/Δ [2] ) or the entropy of the gaps. Consider a simple example with three arms and Δ [1] = 1, Δ [2] = 1. Suppose a newarm sits right on the middle of 𝑎 [1] and 𝑎 [2] and the gaps become:Δ [1] = 1/2, Δ [2] = 1/2, Δ [3] = 1. It means adding this new arm
makes the problem four times more difficult. Non-adaptive online
testing might just be as efficient in this case.
Not knowing the gaps in advance may not the the only factor
that undermines adaptive online testing. Note that we previously
assumed all arms have unit variance, which is unrealistic. Indeed,
the variance associated with arm also plays a non-negligible role
for the separability, and it actually acts as multiplicative factors on𝑘
1/Δ2[ 𝑗 ] 𝑗=2 [22]. Further, the confidence level will also become astochastic process (such as the 𝛼 (𝑡 ) in Section 3) instead of the fixed𝛿 we just discussed in Lemma 3. The stochasticity in confidence
level may further complicate the lower bound, and this scenario
still requires new technical results to analyze. In light of these facts,
conclusions cannot be made on how adaptive online testing is more
effective than traditional A/B/n testing and why.
In conclusion, while recent advances from multiple domains havemade adaptive online testing a practical and scientific alternative to
traditional A/B/n testing, the inherent difficultly of the problem still
poses challenges to fully embrace adaptive testing. Nevertheless,this technology has the potential to benefit multiple industries as
more research and empirical work are underway.

5

FUTURE RESEARCH DIRECTIONS

We briefly discuss several promising directions that may contribute
greatly to decision-making with adaptive online testing for IR.
• Extension to the fixed budget setting. The fixed budget setting
may be more practical for certain IT productions such as advertising [30]. While the best-arm identification algorithms can often
switch between the fixed confidence and fixed budget setting [14],the focus of hypothesis testing may vary. Increasing the power ofa experiment design, rather than controlling the false discovery
rate, might be more demanding for fixed budget problems. Moreresearch is needed to incorporate the new objective.
• Thompson Sampling (TS) for exploration. The Bayesian idea behind TS’s exploration strategy is as powerful as the CB method[1], and Russo [29] recently developed TS-driven best-arm identification algorithm. A distinctive advantage of TS is to include
prior knowledge about the experimentation (e.g. offline testing
results). Although hypothesis testing is strictly a frequentist’s
choice, there is possibility to seek collaboration especially when
TS involves only in exploration.
• Involving contextual information. Just like how contextual information serves multi-armed bandit, they can also be used to
optimize adaptive online testing. For instance, when an online
testing is designed to select the best banner size, the unknown
rewards for each arm may be size-related. If so, an extra learningOn the Advances and Challenges of Adaptive Online Testing

step can lead to better exploration. Kato and Ariu [21] and Chen
and Kasiviswanathan [10] has done some preliminary work inthis direction, but this field remains largely unstudied.
• Real-world examination. Most of the methods in this short paper
have only been tested via simulation or small-scale studies. Their
efficacy in large-scale IT productions remains to be told. The
real-time computation and updates required by adaptive online
testing will certainly put a test on the infrastructure at the serving end. Business requirements may also complicate the design
and analysis of adaptive online testing. Applied research with
deployment solutions will be highly appreciated.

REFERENCES[1] Shipra Agrawal and Navin Goyal. 2012. Analysis of thompson sampling for themulti-armed bandit problem. In Conference on learning theory. JMLR Workshop
and Conference Proceedings, 39–1.
[2] Ehud Aharoni and Saharon Rosset. 2014. Generalized 𝛼 -investing: definitions,
optimality results and application to public databases. Journal of the Royal
Statistical Society: Series B: Statistical Methodology (2014), 771–794.
[3] Valentin Amrhein, Sander Greenland, and Blake McShane. 2019. Scientists rise
up against statistical significance.
[4] Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. 2010. Best arm identification in multi-armed bandits.. In COLT. Citeseer, 41–53.
[5] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. 2002. Finite-time analysis of
the multiarmed bandit problem. Machine learning 47, 2 (2002), 235–256.
[6] Yoav Benjamini and Yosef Hochberg. 1995. Controlling the false discovery rate: apractical and powerful approach to multiple testing. Journal of the Royal statisticalsociety: series B (Methodological) 57, 1 (1995), 289–300.
[7] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. 2013. Concentration
inequalities: A nonasymptotic theory of independence. Oxford university press.
[8] George Casella and Roger L Berger. 2021. Statistical inference. Cengage Learning.
[9] Lijie Chen, Jian Li, and Mingda Qiao. 2017. Towards instance optimal bounds forbest arm identification. In Conference on Learning Theory. PMLR, 535–592.
[10] Shiyun Chen and Shiva Kasiviswanathan. 2020. Contextual online false discovery
rate control. In International Conference on Artificial Intelligence and Statistics.
PMLR, 952–961.
[11] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. 2002. PAC bounds for multiarmed bandit and Markov decision processes. In International Conference on
Computational Learning Theory. Springer, 255–270.
[12] Aleksander Fabijan, Pavel Dmitriev, Helena Holmstrom Olsson, and Jan Bosch.
2018. Online controlled experimentation at scale: an empirical survey on thecurrent state of A/B testing. In 2018 44th Euromicro Conference on Software Engineering and Advanced Applications (SEAA). IEEE, 68–72.
[13] Dean P Foster and Robert A Stine. 2008. 𝛼 -investing: a procedure for sequential
control of expected false discoveries. Journal of the Royal Statistical Society: Series
B (Statistical Methodology) 70, 2 (2008), 429–444.
[14] Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. 2012. Bestarm identification: A unified approach to fixed budget and fixed confidence. In
NIPS-Twenty-Sixth Annual Conference on Neural Information Processing Systems.
[15] Aurélien Garivier and Emilie Kaufmann. 2016. Optimal best arm identification
with fixed confidence. In Conference on Learning Theory. PMLR, 998–1027.
[16] Philip Hartman and Aurel Wintner. 1941. On the law of the iterated logarithm.
American Journal of Mathematics 63, 1 (1941), 169–176.
[17] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. 2014.
lil’ucb: An optimal exploration algorithm for multi-armed bandits. In Conference
on Learning Theory. PMLR, 423–439.
[18] Adel Javanmard and Andrea Montanari. 2018. Online rules for control of false
discovery rate and false discovery exceedance. The Annals of statistics 46, 2 (2018),
526–554.
[19] Ramesh Johari, Leo Pekelis, and David J Walsh. 2015. Always valid inference:
Bringing sequential analysis to A/B testing. arXiv preprint arXiv:1512.04922(2015).
[20] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. 2012.
PAC subset selection in stochastic multi-armed bandits.. In ICML, Vol. 12. 655–
662.
[21] Masahiro Kato and Kaito Ariu. 2021. The Role of Contextual Information in BestArm Identification. arXiv preprint arXiv:2106.14077 (2021).
[22] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. 2016. On the complexityof best-arm identification in multi-armed bandit models. The Journal of Machine
Learning Research 17, 1 (2016), 1–42.
[23] Emilie Kaufmann and Shivaram Kalyanakrishnan. 2013. Information complexity
in bandit subset selection. In Conference on Learning Theory. PMLR, 228–251.

WSDM ’22, February 21–25, 2022, Tempe, AZ, USA[24] Robert W Keener. 2010. Theoretical statistics: Topics for a core course. Springer
Science & Business Media.
[25] Ron Kohavi and Roger Longbotham. 2017. Online Controlled Experiments and
A/B Testing. Encyclopedia of machine learning and data mining 7, 8 (2017),
922–929.
[26] Tor Lattimore and Csaba Szepesvári. 2020. Bandit algorithms. Cambridge University Press.
[27] Edward Paulson. 1964. A sequential procedure for selecting the population withthe largest mean from k normal populations. The Annals of Mathematical Statistics(1964), 174–180.
[28] Aaditya Ramdas, Fanny Yang, Martin J Wainwright, and Michael I Jordan. 2017.
Online control of the false discovery rate with decaying memory. Advances inneural information processing systems 30 (2017), 5650–5659.
[29] Daniel Russo. 2016. Simple bayesian algorithms for best arm identification. In
Conference on Learning Theory. PMLR, 1417–1418.
[30] Rajat Sen, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. 2017. Identifying best interventions through online importance sampling. In
International Conference on Machine Learning. PMLR, 3057–3066.
[31] Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction. MIT press.
[32] Fanny Yang, Aaditya Ramdas, Kevin Jamieson, and Martin Wainwright. 2017.
A framework for multi-A (rmed)/B (andit) testing with online FDR control. In
Proceedings of the 31st International Conference on Neural Information Processing
Systems. 5959–5968.
[33] Shengjia Zhao, Enze Zhou, Ashish Sabharwal, and Stefano Ermon. 2016. Adaptive
concentration inequalities for sequential decision problems. Advances in Neural
Information Processing Systems 29 (2016), 1343–1351.