Online Multi-Armed Bandits with Adaptive Inference
Authors: Maria Dimakopoulou
Zhimei Ren
Zhengyuan Zhou
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bandits
Online learning
Adaptive Inference

Abstract: During online decision making in Multi-Armed Bandits (MAB), one needs to conduct inference on the true mean reward of each arm based on data collected so far at each step. However, since the arms are adaptively selected--thereby yielding non-iid data--conducting inference accurately is not straightforward. In particular, sample averaging, which is used in the family of UCB and Thompson sampling (TS) algorithms, does not provide a good choice as it suffers from bias and a lack of good statistical properties (e.g.  asymptotic normality). Our thesis in this paper is that more sophisticated inference schemes that take into account the adaptive nature of the sequentially collected data can unlock further performance gains, even though both UCB and TS type algorithms are optimal in the worst case. In particular, we propose a variant of TS-style algorithms--which we call doubly adaptive TS--that leverages recent advances in causal inference and adaptively reweights the terms of a doubly robust estimator on the true mean reward of each arm. Through 20 synthetic domain experiments and a semi-synthetic experiment based on data from an A/B test of a web service, we demonstrate that using an adaptive inferential scheme (while still retaining the exploration efficacy of TS) provides clear benefits in online decision making: the proposed DATS algorithm has superior empirical performance to existing baselines (UCB and TS) in terms of regret and sample complexity in identifying the best arm. In addition, we also provide a finite-time regret bound of doubly adaptive TS that matches (up to log factors) those of UCB and TS algorithms, thereby establishing that its improved practical benefits do not come at the expense of worst-case suboptimality. 

Online Multi-Armed Bandits with Adaptive Inference
Maria Dimakopoulou Netflix
Zhimei Ren University of Chicago
m
zmrendstatistics .uciicaoo..ccccoo edu
Zhengyuan Zhou
NYU Stern School of Business zzhou@stern, www.uutttennnuuueee. nyu
Abstract
During online decision making in multi-armed bandits, one needs to conduct inference on the true mean reward of each arm based on data collected far at each step. However, since the arms are adaptively selected-thereby yielding non-i.id. data-conducting inference accurately not straightforward. In particular, sample averaging, which is used in the family of UCB and Thompson sampling (TS) algorithms, does not provide a good choice suffers from bias and a lack of good statistical properties (e.g. asymptotic normality). Our thesis in this paper is that more sophisticated inference schemes that take into account the adaptive nature of the sequentially collected data can unlock further performance gains, even though both UCB and TS type algorithms are optimal the worst case. In particular, propose variant of TS-style algorithms-which we call doubly adaptive Thatha leverages recent advances causal inference and adaptively reweights the terms of doubly robust estimator on the true mean reward of each arm. Through 20 synthetic domain experiments and a semi-synthetic experiment based data from an A/B test ran at Netflix, we demonstrate that using adaptive inferential scheme (while still retaining the exploration efficacy TS) provides clear benefits in online decision making: the proposed DATS algorithm has superior empirical performance to existing baselines (UCB and TS) in terms of regret and sample complexity in identifying the best arm. In addition, we also provide a finite-time regret bound of doubly adaptive TS that matches (up to log factors) those of UCB and TS algorithms, thereby establishing that its improved practical benefits do not come at the expense of worst-case suboptimality.
1 Introduction
Berry and Fristedt 1985 Bubeck and Desa-Bianccil 2012. Sutton and Barto 2018 Lattimore and Szepesvári 2020 is the simplest and most well- established model for sequential decision making, where decision maker needs to adaptively select an arm at each time from set of arms with unknown (but fixed) mean rewards, in the hope of maximizing the total accumulated expected returns over certain time horizon. The existing literature has studied this problem extensively, mainly focusing on developing algorithms that deal with the trade-off, yielding at least two broad classes of algorithms that provide optimal (sometimes up to log factors) regret guarantees in the worst case.
Stochastic nulti-armed bandits Robbins 1952
The first is upper confidence bound (UCB) based algorithms [Lai and Robbins 1985 Agrawal 1995
Auer et al. 2002 Auer 2002 Garivier and Moulines 2011 Garivier and Cappé 2011 Carpentier
al. 2011 Reflecting "optimism in face of uncertainty" UCB algorithms compute confidence bounds of the estimated mean, construct the index for each arm by adding the confidence bound to
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the mean (as the best statistically plausible mean reward) and select the arm with the highest index. The finite-time regret bounds for these algorithss-&(log T) gap-dependent bounds and O (()T) gap-independent nounds-are both optimal, with the latter in the worst-case sense. On the other hand, UCB algorithms are known to be sensitive to
tuning, and are often hard to tune for stellar performance. This stands in contrast to Thompson sampling (TS) based algorithms [Thompson] 1933 Kaufmann et al., 20122, Ghavamzadeh et al. 2015 Russo et al. 2017], an algorithm that does not require much tuning and that achieves exploration through "probabilistic optimism in face of uncertainty". Further, as a result of this more nuanced exploration scheme, TS has been widely recognized to outperform UCB in empirical applications [Scott 2010 Graepel et al., 2010 May and Leslie 2011 Chapelle and Li 2011]. J. However, although an old algorithm [Thompson 1933], its finite-time worst-case regret bound was not known at the time. Consequently, driven by its empirical performance, its theoretical guarantee was raised as open problem in COLT 2012 [Li and Chapelle
2012] and was subsequently settled by (Agrawal and Goyal 2012 2013c which yield the same
minimax optimal regret guarantees (up to log factors) in UCB. These developments both the
UCB/TS algorithms and the theoretical guarantees have subsequently been successfully aapllyy to
contextual bandits"] [Li al. 2010 Filippi al. 2010 Chu et al. 2011 Jun et al.
2017 Li et al.
2017 Agrawal and Goyal| 201 3a b Russo and Van Roy 2014 2016
Agrawal et al.
2017
Despite this remarkably fruitful line of work, searching for better multi-arma bandit algorithms is far from over. For one thing, minimax (i.c., worst-case) optimality is often too conservative a metric, and does not serve useful indicator of practical performance for average problems P In particular, an important weakness in UCB/TS algorithms is that the true mean reward of each arm is estimated using simple sample average, which would work if the data were i..dd. generated. However, the data is adaptively collected and consequently, as pointed out in [Xu et al.
2013 Bowden and Trippal [017] Nie et al.) 2018 Neel and Roth 2018 Hadad al. 2019 Shin et al.
2019 directly using the sample average to estimate the true mean rewards is not guaranteed to be unbiased and asymptotically normal. Intuitively, this is because arms which appear to have worse reward performance than they actually do due to randomness are sampled less often and the downward bias is not corrected. As such, the inferential quality of an estimator-whe treating the underlying data as if they are i..dd-may be poor, thereby constraining the overall online decision making performance
Our goal in this paper is to leverage recent advances in the causal inference literature that tackle the problem of unbiased and asymptotically normal inference from previously collected, offline bandit data (Hadad et al.] 2019 Zhang et al.] 2020 ZZhan et al., [021] Bibaut al.] [021] and obtain practically better online performance by harnessing the strengths of these adaptive inference estimator (originally designed for offline, post-experiment analyses of adaptive experiments) and the effective
balance provided by TS, thereby designing a more effective online sequential decision making algorithm.
1.1 Our Contributions
Our contributions are threefold. First, we pinpoint the issues of the existing bandit algorithms (Section 3.I) and design new algorithm-whie which we call doubly-adaplln Thompson sampling (DATS)-br) by incorporating the adaptively into the online decision making process and making the necessary modifications to the estimated variance of that estimator to render it suitable for the exploration/cxploitttinn trade-off and ensure sufficient exploration. This algorithm mitigates the issues of poor inferential quality inherent in the sample average used in TS/UCB, while retaining the benefits of intelligent exploration (see
doubly robust estimator in (Hadad et al. 2019
Andd to reinforcement learning as well, but contextual bandits and RL are not the focus of this paper. 'The fact that TS performs better in practice than UCB, even though the existing UCB bounds are tighter
(e.g. by log factors) than those of TS, already attests to that. For instance, Audibert et al. 2009 showed that Austanee
a variant of UCB has regret O( / KT) in multi-armed bandits, while the best known regret bound for TS is
O(VKTlog log T) for TS with Beta prior and O(VKT KT log K) for TS with Gaussian prior (Agrawal and Goyal 2017). And for contextual bandits, TS is often at least factor of d (context dimension) worse.
Work concurrent to our paper sheds new light on the arm pulling properties of UCB that results in more balanced data collection under small- gaa regime compared to TS, which drives the estimates from UCB-collected
data towards asymptotic normality in the small-gap gap case [Kalvit and Zeevi 2021]
*Such as the adaptively weighted estimator proposed by [Luedtke and Van Der Laan 2016 in the setting of i.i.d. observational data with multiple optimal policies and later generalized by Hadad et al. 2019 in the aalti- bandit setting.

---

Section 3.2 for more detailed discussion). Previously, inverse propensity weighting (IPW) has been used in bandits (Agarwal al. 2014), motivated, analyzed and evaluated in [Dimakopoulou et al.) 2017 2019] and systematically benchmarked in [Bietti et al. 2018]. However, IPW has very high variance and these works did not use variance stabilizing weights, which can yield poor inferential performance-an as we will see in section 4.2 Second, we validate that the desired benefits in the design of DATS do translate into higher quality decision making. In particular, through 20 synthetic domain experiments and one semi-synthetic experiment, we demonstrate that DATS is more effective than TS and UCB. This effectiveness is shown in two metrics: one is regret, which measures the cumulative performance compared to that of the optimal oracle; the other is sample complexity, which measures how many rounds are needed in order to identify the best arm. Under both metrics, DATS beats all existing bandit algorithms with clear margin (see Section 4 for detailed presentation of results). Finally, to complete the picture, we show that DATS achieves this superior practical performance without giving away the comparable worst-case regret guarantees. In particular, DATS has finite-time regret of (K3/22 log T), which is minimax optimal (up to log factors) in the horizon T, thus matching that of TS (K is the number of arms). Notably, all existing results on adaptive estimators in the inference literature are asymptotic in nature (typically in the style of central limit theorem bounds), whereas our bound is finite in nature and sheds light in the arena of online decision making. rather than offline inference, has focused-to our knowledge. We point out that we do not attempt to be tight in K in our bound, as in the applications we have in mind (e.g. clinical trials, web-service testing). including the one motivating our semi-synthetic experiment, the number of arms is typically a (small) constant. That said, our synthetic empirical results (Fig. D DATS indeed has an optimal O(vK) dependence. We leave tighter analysis on K for future work.
establish that
which all prior work adaptive estimators
on 20 domains (including for large K) demonstrate that
2 Problem Formulation
In stochastic multi-armed bandits, there is a finite set A of arms a E A with |A| = K. At every time t, the environment generates-in in an i.i.d. manner-a reward ree ra) for every arm a E A with expectation [ar] Ma. where Pa is the unknown true reward of arm which is modified by mean-zero noise to generate rz(a). The optimal arm is the arm with the maximum true reward, which is denoted by a" == arg A Ma and is also unknown. When at time / the decision maker chooses arm a,, only the reward of the chosen arm Ti= == rr(a:) is observed.
At every time t, the decision maker employs a policy that maps the history of arms and rewards observed up to that time, H4-1 = (oo, ro..... d ) to a probability distribution over the set of arms A and chooses a; ~ The probability with which arm a is chosen at time t (often referred to as propensity score of arm a at time f) tt,a P(a: = al 1)) The goal of the decision maker is to make decisions adaptively and learn sequence of policies (T (T1..... TT) over the duration of T time periods, so that the expected cumulative regret with respect to the optimal arm selection strategy over T time periods is minimized, where Regret(T, T) == Eim (Ha- - Maewte))
2.1 Baseline Algorithms: UCB and TS
Upper confidence bound (UCB) is an algorithm that balances the exploration/exploottioo trade- off by forming for each arm E A at every time period f an upper bound Ur. that represents the maximum statistically plausible value of the unknown true reward pa given the history H,-1- Then, at time f, UCB chooses the arm with the highest bound, ag = arg maX U2.- Hence, the policy ne of time t assigns probability one to the arm with the highest bound (breaking ties deterministically) and probability zero to all other arms. An example is UCB- -orrmlll for normally distributed rewards [Auer et al. 2002]. where the upper confidence bound of arm a at time is
ara given by Ur, Fr,a + 33 // log(t - 1), where Fr,a is the sample average and o 9.. (ne, is an estimate of the mean reward's variance (qt, is the sum of squared rewards and n4,a is the number of pulls of arm up to time f) while / is an algorithm parameter. Thompson sampling (TS) is another algorithm that balances the exploration/explotttio trade-off by forming for each arm a E A at every time period a posterior distribution P(ua E -i),)),, drawing a sample arg max.cA fr.o- Hence, the
Pr.o from it and choosing the arm with the highest sample, policy n, of time to choose each arm with the probability that it is optimal given the history of observations H4-1, (a) = P(a argmax Fr.al (H)))). An example is the TS-N NS-Normal, in
3

---

which it is assumed that the true reward Ma of arm is drawn from Nioo, a,.)) which plays the role of a prior distribution, and the realized reward of arm at time t, rr(a), is drawn from N (Ha, o²) where fe unknown and a is known. The posterior distribution of arm a at time also
Normal Russo et al. 2017 with mean Pr,a = EljualHeell Fr.u +pi 1.00 /nc. and variance #2-1. +a² /ne,a
62 /na.a
o% Ei(po ( [HH --1.a /02/ The sample average Fr,a of arm's 's a observed rewards up to time & plays a prominent role in UCB and TS, since it is used in U and P(1,, E -1H4211 respectively. However, the observations of a multi-armed bandit algorithm are adaptively collected and, as a result, they are not i.idd,, which makes these sample averages biased.
3 Doubly-Adaptive Thompson Sampling
3.1 Motivation
The issue with the sample average (SA) in the posterior P( E 11H or in the upper confidence bound Ut of arm at time is that the sample average from adaptively collected data has not being guaranteed to be either unbiased or asymptotically normal [Xu et al. 2013, Bowden and Trippa 2017
Nie et al. 2018 Hadad et al. 2019. Shin et al. 2019).
E 1(u, a)r's E.=1 1(a, a)
Q3
Ftaa
Intuitively, as explained in (Nie et al., 2018], this general negative bias of the sample average in the adaptive setting stems from the fact that arms which are "unlucky" and their sample average is lower than their true mean are sampled less and this negative bias is not corrected, while arms which are "lucky" and their sample average is higher than their true mean are sampled more and this positive bias is corrected, accounting for a negative bias of the estimator overall. Very recent work of [alvitt and Zeevi 2021], which is concurrent to our paper, has shown that the arm-pulling properties of TS is much more unbalanced than those of UCB in the small-gap regime, driving the estimates based on data collected by UCB closer to unbiasedness and asymptotic normality and estimates based on data collected by TS former further away from them. Even though UCB has been recently shown to exhibit this favorable inferential property over TS in the small-gap -gp regime, the widespread empirical superiority of TS over UCB motivates even more towards a greater level of sophistication in the estimator design for TS-based algorithms correct for the lack of balanced arm-sampling behavior.
Two approaches to correct the bias are the inverse propensity score weighting (IPW) estimator and the doubly-robust (DR) estimator,
IPW
1(a, a)) Ts:
QDR
1
Σ
1
P. 13-1,a +
1(a, = a0) (r. Fo-1
TT,a
which give an unbiased estimate of arm's 's a true mean reward Ha if the propensity scores Ts,a are accurate. However, inverse propensity score weighting comes at the expense of high variance- particularly when the propensity scores become small-albeit the variance of DR is smaller than the variance of IPW, since the former uses sample average as the baseline and applies inverse propensity score weighting to a shifted reward using the sample average as a control variate. The other issue of IPW and DR-apart from the high-variance-is that they are not asymptotically normal. Intuitively, this lack of asymptotic normality comes from the fact that in an adaptive setting the importance- sampling ratios converge
for the optimal arm diverge to infinity for the sub-optimal arms. As a result, both estimators' variance may either be dominated by their first terms or their last terms depending on the arm. At more theoretical level, in an adaptive setting this violates the classical condition of martingale central limit theorems that the conditional variance of the terms given previous observations stabilizes asymptotically (Hall and Heyde, 2014
An approach that has been proposed in recent literature for performing offline inference from previously collected adaptive data is to use adaptive weights, which are weights that are a function of the history. [Luedtke and Van Der Laan 2016) first proposed adaptive weights for estimating
SSection B. of the Supplemental Material visualizes the shortcomings of sample average, IPW and DR in a toy domain of adaptive data collection introduced in (Hadad et al. 2019

---

the expected reward under the optimal policy when one has access to i.i.d. observational data and multiple optimal policies exist. Subsequently. (Hadad et al. 2019] developed the adaptively weighted method for offline inference on adaptive data, such as the data collected by multi-armed bandit and produced the unbiased and asymptotically normal adaptive doubly-robust estimator (ADR). The approach in [Hadad et al. 2019) modifies the DR estimator by weighing the efficient score
fe == Fe-1,0 + 1a,, = a) (re Fe-1,a)
TTa
of each data point & E [0] := (I,...,(} by a non-uniform weight Ws,a instead of weighing all data points uniformly with weight 1/t. The resulting estimator is weighted average of the efficient scores, which is referred to as adaptive doubly-robust (ADR), since these weights Wa,a are adapted to the history H.,-1 ADR takes the form
E
Ussaf s.a
QADR
Wa,a
The intuition behind ADR is that if the contribution of each term aa.a to the variance of the DR estimator is unequal, then using uniform weights is not as efficient (i.e., results in larger variance) as using weights inversely proportional to the standard deviation of each term s's... Since the data collection time s adapts to the history H via the propensity score a, so does the variance of I' 2.0- As a result, the chosen weight Wa,a is also adaptive to the history H In the i.i.d setting with multiple optimal policies, (Luedtke and Van Der Laan 2016 proposed weighing a, by
Ws.a VT. Subsequently, (Hadad et al. 2019], proposed generalized mechanism for
constructing weights Ws.a in adaptive setting such that the conditions of infinite sampling, variance convergence and bounded moments are satisfied-which are in turn necessary for the resulting ADR estimator be unbiased, have low variance and asymptotically normal distribution- and, among others, retrieved the weighting scheme proposed in [Luedtke and Van Der Laan 2016].
3.2 Algorithm
We propose doubly-adapin Thompson sampling (DATS), which uses as building block
E.=
QADR
E. V 7s,a
In online learning, the decision maker knows exactly the propensity scores in QADR Additionally, in TS-based algorithms, these propensity scores are non-trivial and are bounded away from zero and one-at at least in the initial stages of ceaniig-unllke unlike UCB, in which the propensity score is equal to one for the chosen arm and equal to zero for all other arms. With TS, at any time t the propensity scores via Monte Carlo sampling based on the sampling distribution of
Tia can be computed analytically each arm a and then logged in order to be used for inference in subsequent time steps rather than the need to fit a propensity model in the UCB setting, which may not be accurate. For this reason, our new multi-armed bandit algorithm belongs to the TS class rather than the UCB class.
At each time step & E [T]. where T is the learning horizon, DATS forms a reward sampling distribution for each arm a E A based on the history of observations H;-1 collected so far. The reward sampling distribution of arm at time t is chosen to be normal N ((r,, oZ,o) with mean and variance
Ta a.a
Ei Ta.a [[T s.a i + +1]
ju,a QADR
E.=1
V TTa
(E [ssaa
Note, that the variance in the sampling distribution of DATS has an auxiliary '+1' term compared to the variance (Hadad al. 2019]. This is essentially important for the online setting, as the auxiliary term guarantees a lower bound of the estimated variance, thereby ensuring sufficient exploration in
the initial stages of learning (in contrast to the offline setting in Hadad et al. (2019). ). The derivation of ō..a used by DATS can be found in the Supplemental Material section A. At time the sampling distributions of all arms are used to compute the probability of arm a being chosen, i.e., its propensity
score. Given that TS is probability matching heuristic, i.c., it plays an arm with the probability
5

---

Algorithm Doubly-Adapiive Thompson Sampling
Input: uniform exploration parameter 7 E (0, 1) over non-eliminated arms; sampling parameter K;
for E do
Pull arm and observe reward Tinitial,a- Initialize Fu,a f aimitilla. Au,a 1, Ni,a +- 1/K.
end for A1 AA
for t = 1 to to do
Pull arm de ~ Multinomial (Ac, (Tr,a)EEA)) and observe reward Fr +- rr(a)).
Update sample averages and counts.
L., +1 Bt,a f 1, + and Fz,a <- Ft-1,as De,a &- 14 Va #
Tt,a,
> Update sampling distributions. for A do
I Tea + Fa-1,a + 1(u, =a] -e Vs [[].
Taa
Eim vanaaina Nta Enzi Visaa
Emsr Ro, [fo, - +
E V0,0
end for
Perform arm elimination.
Pitla mina'EA. & (Reaa - ( 02.0 ),a') Ya Ar
Ae+1 As {a E A: Pe+1,a 1/T]
Compute propensity scores.
Ft+1,a ~ (jir,,, =²)) and 1141,a & PP Pa(a= argmaax Fettaa H.). Ya Art1
T4+1,a f (1 - 74411, A/1/ Va A(+1
end for
that it is optimal according to the posteriors, the propensity score of arm time t is equal to the probability with which a single sample tt,a ~ NNrr x o2o2..) from the sampling distribution of arm a is greater than a single sample ar. ~ ( x x²0?, from the sampling distribution of any K² x
other arm a'. Hence, Tr, Paaa argmax ēr,a' H,-1),, where ēr, N These propensity scores can be computed accurately via Monte Carlo simulation.
In order to control the variance of their estimator, Hadad et al. 2019 derived the asymptotic normality of their QADR under the assumption that each arm has non-negligible probability of being chosen, i.e., the propensity score of arm every time lower bounded- this however cannot be assumed in the online setting since otherwise the sub-optimal arms will be pulled for non-trivial fraction of times and yield undesired regret. In order to deal with diminishing propensity scores in the online setting and derive a regret upper bound, DATS performs arm elimination step. To do this, we compute the probability that a sample from the posterior arm a greater than sample from the posterior of arm a'. The difference Da,e' 1 Fa,t Far.t is normally distributed
( i x² (6" t + o)))). So, P(Da.a' 0)
(iee ar. ) //xi/// ////..
/02. + 67.a/
where & denotes the CDF of standard normal distribution. If there exists an arm a' for which P(Da.e'.. > 0) < 1/T (i.e., arm a is dominated by a'), then arm a is eliminated. The set of arms available to the decision maker at the beginning of time step ++ is denoted by Ar+1. Also, DATS maintains a level of uniform exploration 7 among the non-eliminated arms, where 7 is a parameter of the algorithm (default y 0.01) and controls how small propensity scores ge(") Our default choice for the sampling parameter k is 1.
'Note that the presence of this uniform exploration does not yield linear regret, due to the existence of the climination step in our algorithm and the fact that the algorithm applies uniform exploration of magnitude non-eliminated arms. Indeed, in section we prove that the regret of DATS O 3/3 lol T), which is minimax optimal (up to log factors) in the horizon T
ry only over the

---

4 Empirical Evaluation
We now present computational results that demonstrate the robustness of DATS in comparison to baselines, both in terms of regret and in terms of sample complexity for identifying the best arm.
4.1 Synthetic Experiments
First, we present results on synthetie domains with varying number of arms and noise lev- els. as commonly done in literature [Russo] 2016]. We simulate 20 synthetic domains with K 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 where the true mean reward μa of each arm a is drawn randomly from (0, 0.125) in the low signal-to-noise ratio (SNR) setting and from (0, 0.5) in the high SNR setting. while the rewards rt.o are drawn from (H,, 1). The multi-armed bandits run for horizon 7' = 10000. For TS-Normal [Lattimore and Szepesvári 2020). described in section 2.1 we select weak prior ÑO.a 0. oj = -100 for all arms a E A and known noise variance о UCB-Normal [Auer et al. 2002]. described in section 2.1 we tune 3 among values 1, 1.5, 2, 2.5, 3, 4 and select the one with the best performance in each domain. For DATS, we select ? 0.01, = 1. Finally, we also evaluate a simplified version of DATS, called DATS- arm climination and uniform exploration among the non-eliminated arms that DATS introduces to control diminishing propensity scores, DATS-clipping applies TS to modified ADR estimator which replaces s.a in s.a and in the adaptive weights Ws.a by the clipped propensity max(ō, xs,a). Propensity score clipping is a common practice in the offline evaluation literature (Crump et al. 2.09]. but this modified estimator is no-longer unbiased. DATS-clipping uses 6 = 0.001, R 1.
For
instead of
10000
UCB
DMTS DAISS-clipping
DATS
8222
0..5
+
Stoppeng Time
DATS-cllping
Stopakng Time
6030
5000
5555
DATS
DipS-clpping
(a) Average regret and stopping power low SNR. (b) Average regret and stopping power in high SNR.
Figure I: Comparison TS. UCB, DATS and DATS-clipping in terms of average regret vs. VK and stopping power vs. K (for probabilistic algorithms) in 20 synthetic domains (10 arm settings K = 5, ..., 50 and 2 noise settings). Each domain is simulated 64 times and 1 standard error is shown.
We compare TS, UCB, DATS and DATS-clipping in terms of average regret, T ET (pa- Pe. ). as a function of the square root number of arms, VK, shown in the left subplots of laland for the low SNR and the high SNR setting respectively. We also compare the probabilistic bandits-TS, DATS, DATS-clipping-in terms of sample complexity for identifying the best arm with error tolerance = 0.05 (i.e., with 95% confidence) using the Bayesian stopping criterion, which stops at the first time tf when there is an arm at such that its propensity score Tet.a* computed from its posterior P(pa! E 1)) satisfies Tet 2 1 - [Russo] 2016). The right subplots of of Ia and show this stopping time t for each algorithm as a function of the number of arms K for the low SNR and the high SNR setting respectively. Each one of the 20 domains is simulated over 64 simulations and the plots in T the mean and one standard error for both the average regret and the stopping power metric. Both DATS and the DATS-clipping heuristic attain significantly better performance both in terms of average regret (linear dependence on V K with smaller slope than TS and UCB) and in terms of stopping power (identify the best arm with 95% confidence); DATS and DATS-clipping have better sample complexity than TS in all high SNR domains and in the low SNR domains with small K, while being within error from ane-another.
4.2 Semi-Synthette Experiment Based on A/B Test Data
We now evaluate the performance of DATS compared to baselines using data from an A/B test with 6 user-interface (UT) test cells (1 control/production cell and 5 new treatment cells) ran at Netflix.
7

---

AB
3
15
15
120
DATS
T5.01
Oamaratt Re
DATS
15.21
DATS
15:09
DATS clophg
DATS chrping
220
100
42-
100
200
4000
10050
2000
2002
4300
6030
Member
Text Varbber
Namber
(a) High SNR cumulative regret.
(b) Medium SNR cumulative regret.
(c) Low SNR cumulative regret.
10000
18:00
18300
0000
#000
$200
Stoppngg Time
6600
6300
(d) High SNR stopping time.
(c) Medium SNR stopping time.
(f) Low SNR stopping time.
Figure 2: Comparison of A/B test, TS, UCB, TS-IPW, TS-DR, DATS and DATS-clipping in terms of cumulative regret and 95% confidence stopping time (for stochastic algorithms) in high SNR (a = 0.32), medium SNR (a = 0.64) and low SNR (a 1.28) with К = 6 arms. The true reward means and medium SNR a estimated by Netflix's 's A/B test data. Bandits run for horizon T 10000. Results are averaged over 64 simulations and 95% confidence intervals are shown.
For each test member that took part in this A/B test, one of the 6 UI cells was selected uniformly at random was presented to the member throughout the duration of the A/B test. Measures of member satisfaction were collected throughout the A/B test, from which a target reward was defined. From the member-level data collected by the end of the A/B test, we extracted the sample mean of the target reward corresponding to each UI cell relative to the control/production UI cell, [0, -0.05, 0.15, 0.02, 0.28, 0.2), and the sample standard deviation of that target reward across cells, o = 0.64. For reproducibility purposes, we used the above μ and o to simulate a multi-armed bandit domain with K 6 arms and T 10000 observations, where rewards A ((u,a21) (I is the 6 x 6 identity matrix) [
generated from We simulate noise domains: medium SNR with 0.64 (observed in the A/B test); high SNR with 0.32 (halving the observed noise standard deviation) and low SNR with a = 1.28 (doubling the observed noise standard deviation).
We evaluate TS (Ao.. 0, d 10 oracle σ), UCB (3 1.5, 2,5, 3, 4), DATS (7 0.01, k = 1) and DATS-clipping (6 0.001, x = 1). as in section 4.1 Additionally, we benchmark DATS against two more TS- (asbd algorithmss -ieiaams-------P TS-IPW and TS-DR- that replace the biased sample mean with the unbiased but not adaptively weiggtee estimators QIPW and QDR respectively (more details in section 3.1 instead of QDRR in DATS. The rest of the TS-IPW and TS-DR is implemented in DATS (Algorithm 1 with 0.01, k
Figure shows that DATS and DATS-clipping have clear advantage over baselines both in terms of cumulative regret and terms sample complexity for identifying the best arm with 95% confidence in all three noise settings. Interestingly, TS-IPW and TS-DR, although unbiased, have worse regret performance than both TS and UCB, which use the biased sample mean. TS and best-tuned UCB within error from each other. This indicates that using estimators which correct the sample mean bias stemming from the adaptive data collection is not enough if special attention not given to the variance properties of these estimators. Both TS- TS-IPW and TS-DR suffer from high variance due the
7 "The true reward μ., of each and the noise this experiment grounded in real data, hence its characterization as semi-synthetic (unlike Section [.1 where Ho generated at random each arm a.) "Section B.2 of the Supplemental Material explores tuning parameter 7 controlling the uniform exploration over non- non-eiimea arms in TS-IPW. TS-DR. DATS and parameter & clipping the propensities in DATS clipppng.

---

propensity scores in the denominator of their estimator which become small in an online multi- bandit setting" Through the variaanc-stabblizznng property of the adaptive weights. DATS is unbiased with reasonably controlled variance and is able to provide better confidence region for all arms' values, thus improving learning in the online setting.
5 Finite-Time Regret Guarantees
Our main theoretical result concerns an upper bound of the finite-time regret resulting from Algo- rithm [ We present the proof of the two-arm setting in this section, whereas the generalization the K-arm case is deferred to the supplemental material. Theorem foommally shows that for the two-arm stochastic bandit problem the expected regret resulting from Algorithm matches the minimax lower bound (VVT) (up logarithmic factors). We also show a problem-dependee bound Ollog T/A) for our algorithm. Throughout, we assume that the standard deviation of the noise is a, and that there exists M > 0 such that [a)] S M for E [T] and a E A.
Theorem For the two-arm stochastic bandit problem, the expected regret incurred by Algorithm 7 is bounded E[Ar] <OVTlog)))
Without loss of generality, let A = {1,2} and arm 1 be the optimal arm; let A = f4 A2 denote the gap between the two arms. The proof of Theorem T starts from establishing that the estimator Pr.a concentrates around the true mean Naa with high probability; since İt, is a good estimator for Maa, we claim that we are able to recognize the optimal arm fast enough-so that we do not pay too much in the exploration phase-an
are committed to the optimal arm afterwards
To start, we define Mr,a := E.= v (f..a Ma). By construction, {Ma,...2 is martingale w.r.t. the filtration {H.} Let T(a) == minft Pt+1a < 1/T}. Since Pt-1,a is measurable w.r.t. H4 for any E [T. T(a) stopping time w.r.t. the filtration {Hehs1. Consequently,
St == Mr(a)st,a is (stopped) martingale w.r.t. (Hehg11 For any a E A. E [T]. the martingale difference of St,a is given by
Dr. =t, - St-1,a MrtajAt,a Mr = 1fr(a) 2 t} VT, (fr,a - -Ha).
On the event {T(a)= 2 t). the absolute value of the martingale difference DDtaal can be bounded as,
T f. - Mal VTraa Fr-1,0- - taa + 1(A: = a} (r. F. 1.)) < 2M + Vr
2M
Tta
Consequently, Ex Da.al S 4MM. 11M2.11+17) -11+1/ t. On the other hand,
B(D Ho-1) Σ ((((a) 2 23 [[1 T (F.,a 2a)² + o²] [²] S (4M² -2)) .t.
s=1
We then make use of the following lemma to establish the concentration result.
Lemma 1 (Theorem 3.26 of Bercu et al. [2015) Let (Ma]n21 be square integrable martingale Then, for any positive x and y,
w.r.l. the filtration (Fn Falzz such that Mo
P Mn 2 x, Σ (M, 22 Σ E - M, 1 [[-1]()) sv) S scxp (- x²a
2y
Applying Lemma 1 to Se.a we have for any x > 0,
P (S.a 2 2Φ) =P 2=)= St,a 2 x,
E[D2 8,a
1HH & (4M². (4M.. (2-2.22+2/// -02)
5,a
$=1
s=1
2
Sexp (8M2. (2 2/ /T + 1 + +20)
We now consider a "good" E event on which the optimal arm is identified within To O( [og(T)/A²)) pulls, i.c., E == (7(2) < Toj. Lemma 2 whose proof is deferred to Supple- mentary Section A.I guarantees the good event happening with high probability.
TTS-DR has better variance properties than TS-IPW, and thus a bit better performance in the online setting.

---

Lemma 2 The event E happens with probability at least 1 - 2/T - 2(log Ty /T2
On the good event E, the sub-optimal arm is pulled for at most To times, thus incurring a regret at most To A. We can decompose the expected regret as,
E [T, m)] = EE (T, T) 1[E]] + E ReRgret(T, 1 [
7 + TM 2(log T)s = c(M, log(? (T)
2
- To4 TM-
(1)
T
A
where ei ((M,7) is a constant that only depends on M and 7. provides problem-dependent bound. To the problem-independent bound, note that
Regret T. = =f VT
E Regret(T, m))
+1{A2 A (e(M,n) log
E Regret m) S (M((M,))loog(
As a by-product of the proof of Theorem obtain high probability regret bound, which states that with probability at least - 2/7 2 (log (yg / the regret can be bounded as Regret(T, x) = OVTooogT)
Finally, we state the result for the general K-arm case, where consider the case that for each arm the suboptimality gap A. < MVK. In our proof, we consider slightly modified version of the algorithm where we take the sampling parameter to be K 16M for & < 8(1 - VK/7)² log T,
and K2
16yKM M v7
otherwise; we clip the estimated variance हt.a by Cmax v1/(E= / ( where
Cmax can be large constant. The proof of the result can be found in Supplementary Section A.2
Theorem 2 For the K-arm stochastic bandit problem, the expected regret incurred by Algorithm 7 bounded as max SMMK RegrettTT T)] S (K33/2 Volog
6 Conclusions & Societal Impact
Experimentation consumes resources and hence is expensive in the real-world. As such, experimenta- tion methods that achieve better data efficiency would be desirable for our increasingly Al-powered society. Adaptive experimentation holds great promise over traditional A/B tests for real-world domains (e.g. web-service testing, clinical trials etc.), as it aims to maximize the test population's s reward during learning and it effective in reducing the duration by directing test-traffic into actions that are more promising rather than splitting traffic equally among arms. In this work, we advance the field of adaptive experimentation by introducing the idea of reliable inference during online decision making. The adaptive data collection in online multi-armed bandit setting poses an inference challenge that overlooked traditional, provably optimal and widely adopted algorithms such as UCB and TS. We design an online multi-armed bandit algorithm, called Thompson sampling (DATS), which incorporates advances in offline causal inference estimators for adaptive experimental designs and modifies them appropriately in order to render them suitable for the exploration//xplootttio trade-off present in online aamlti-ammed bandits. DATS is shown empirically to improve the test population reward and decrease the test samples required to identify the best arm, while attaining the optimal worst-case regret bound guarantees in terms of time horizon (proven theoretically) and in terms of number of arms (shown empirically). Beyond DATS, the aim for this paper is to motivate a general approach for designing online learning algorithms with more accurate estimation methods that accounts for the biases stemming from the data-collecting mechanism.
7
Acknowledgments
Zhengyuan Zhou would like to gratefully acknowledge the generous support from the NYU Stern Fall 2021 Center for Global Economy and Business research grant and JP Morgan research grant, which played a major role in enabling the rapid development of the results in this paper.
10

---

References
Alckh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning, pages 1638-1646, PMLR, 2014.
Rajeev Agrawal. Sample mean based index policies by ollog n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27( 1054-1088, 1995. doi: 10.2307/1427934,
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pages 39-1. JMLR Workshop and Conference Proceedings, 2012.
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Artificial intelligence and stalistics, pages 99-107, 2013a.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pages 127-135, 2013b.
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Artificial intelligence and statistics, pages 99-107, PMLR, 2013c.
Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1-24, 2017.
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-bandit. arXiv preprint arXiv: 700000077777777 2017.
Jean- Yves Audibert, Sébastien Bubeck, et al. Minimax policies for adversarial and stochastic bandits. In COLT, volume 7, pages 1-122, 2009.
Peter Auer. Using confidence bounds for exploitation-exxloratio trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-2566 2002.
Bernard Bercu, Bernard Delyon, and Emmanuel Rio. Concentration inequalities for sums and martingales. Springer, 2015.
Donald A Berry and Bert Fristedt. Bandit problems: sequential allocation of experiments (monographs on statistics and applied probability). 1985.
Aurélien Bibaut, Antoine Chambaz, Maria Dimakopoulou, Nathan Kallus, and Mark van der Laan. Post-contextual-andiit inference. arXiv preprint arXiv:2106.0044 00418, 2021.
Alberto Bietti, Alekh Agarwal, and John Langford. contextual bandit bake-off. arXiv preprint arXiv:1802.04064, 2018.
Jack Bowden and Lorenzo Trippa. Unbiased estimation estmattion for response adaptive clinical trials. Statistical methods medical research, 26(5):2376-2388, 2017.
Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. arXiv preprint
2012.
Alexandra Carpentier, Alessandro Lazaric, Mohammad Ghavamzadeh, Rémi Munos, and Peter Auer. Upper-confidence- bound algorithms for active learning in multi-armed bandits. In International Conference on Algorithmic Learning Theory, pages 189-203. Springer, 2011.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24:2249-2255 2011.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-21 224, 2011.

---

Richard K Crump, V Joseph Hotz, Guido W Imbens. and Oscar A Mitnik. Dealing with limited overlap in estimation of average treatment effects. Biometrika, 96(1):187-199, 2009.
Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey, and Guido Imbens. Estimation considerations in contextual bandits. arXiv preprint arXhv:1711.07077, 2017.
Maria Dimakopoulou. Zhengyuan Zhou, Susan Athey, and Guido Imbens. Balanced linear contextual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3445-3453, 2019.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, pages 586-594, 2010.
Aurélien Garivier and Olivier Cappé. The kl-uch algorithm for bounded stochastic bandits and beyond. In Proceedings of the 24th annual conference learning theory, pages 359-376. JMLR Workshop and Conference Proceedings, 2011.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In International Conference on Algorithmic Learning Theory, pages 174-188. Springer, 2011.
Mohammad Ghavamzadeh, Shie Mannor, Joelle Pineau, Aviv Tamar, et al. Bayesian reinforcement learning: A survey. Foundations and Trends@ in Machine Learning, 8(5-6):359 483, 2015.
Thore Graepel, Joaquin Quinonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian click-through rate prediction for sponsored search advertising microsoft's bing search engine. In ICML, 2010.
Vitor Hadad, David A Hirshberg, Ruohan Zhan, Stefan Wager, and Susan Athey. Confidence intervals for policy evaluation adaptive experiments. arXiv preprint arXiv: 1911:0091 2019.
Peter Hall and Christopher C Heyde. Martingale limit theory and its application. Academic press, 2014.
Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett, Scalable generalized linear bandits: Online computation and hashing. In Advances in Neural Information Processing Systems, pages 199- 2017.
Anand Kalvit and Assaf Zeevi. A closer look at the worst-case behavior of multi-armed bandit algorithms. arXiv preprint arXiv:2/06.02/ 2021.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory, pages 199-213. Springer, 2012.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematies, 6(1):4-22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandil algorithms. Cambridge University Press, 2020.
Lihong Li and Olivier Chapelle. Open problem: Regret bounds for thompson sampling. In Conference on Learning Theory, pages 43-1. JMLR Workshop and Conference Proceedings, 2012.
Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670 ACM, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In Proceedings of the 34th International Conference on Machine Learning-Volee Volume 70, pages 2071 1-200. JMLR. org, 2017.
Alexander I Luedtke and Mark Van Der Laan. Statistical inference for the mean outcome under a possibly non-unique optimal treatment strategy. Annals of statistics, 44(2):713, 2016.
12

---

Benedict C May and David S Leslie. Simulation studies in optimistic bayesian sampling in contextual- bandit problems. Statistics Group, Department of Mathematics, University of Bristol, 11(02). 2011.
Seth Neel and Aaron Roth. Mitigating bias in adaptive data gathering via differential privacy. In International Conference on Machine Learning, pages 1720-3729. PMLR, 2018.
Xinkun Nie, Xiaoying Tian, Jonathan Taylor, and James Zou. Why adaptively collected data have negative bias and how correct for it. In International Conference on Artificial Intelligence and Statistics, pages 1261-1269. PMLR, 2018.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Sociery, 58(5):527-535, 1952.
Daniel Russo. Simple bayesian algorithms for best arm identification. In Conference on Learning Theory, pages 1417-1418. PMLR, 2016.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4): 2014.
Daniel Russo and Benjamin Van Roy. An information-theoreiicc analysis of thompson sampling. The Journal of Machine Learning Research, 17(1):2442-2471, 2016.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. arXiv preprint
1707.0077000000 a7Xiv:170..02038, 2017.
Steven I. Scott. A modern bayesian look at the multi-armed bandit. Applied Stochastic Models in Business and Industry, 26(6):639 658, 2010.
Jaehyeok Shin, Aaditya Ramdas, and Alessandro Rinaldo. On the bias, risk and consistency of sample means in multi-armed bandits. arXiv preprint arXiv:1902.0077 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
William R Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-294, 1933.
Min Xu, Tao Qin, and Tie- Yan Liu. Estimation bias in multi-armed bandit algorithms for search advertising. Advances Neural Information Processing Systems, 26:2400-2485 24040 2013.
Ruohan Zhan, Vitor Hadad, David A Hirshberg, and Susan Athey. Off-policy evaluation via adaptive weighting with data from contextual bandits. arXiv preprini arXiv:2106.02029, 2021.
Kelly W Zhang, Lucas Janson, and Susan A Murphy. Inference for batched bandits. arXiv preprint 17X1v 2020.
13


Reviews:
[{"review_id": "ih6sKmuxFd", "reviewer": "Reviewer_oqBT", "summary": "This paper considers the multi-arm bandit problem. It starts from the observation (already present in the literature) that classical bandit algorithms such as UCB or TS estimate the mean rewards of the arms by simple empirical averages without taking into account the fact that they are adaptively sampled and are therefore biased. The paper thus proposes to make these estimators unbiased by using importance weighting (inverse propensity score weighting) as well as variance reduction tools (adaptive doubly robust estimator and clipping). Applying it to TS, they empirically demonstrate that their algorithm significantly outperforms classical TS and UCB while maintaining a theoretical worst-case regret bound of order $O(\\sqrt{T})$. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The empirical contribution of the paper is interesting and having bandit algorithms with improved performance is significant. The simulation results in this paper seem compelling to me. While the application of the inverse propensity score is not new in the bandit literature, variance reduction techniques have been shown to perform very well in counterfactual learning and optimization and I am not aware of any previous work applying it to TS or UCB. It is instructive that this also applies to multi-armed bandits. \n\n\nOn the negative side of the paper:\n1. I did not find it so well written. \n\t- Probably because of the page constraint, the heavy use of inline formulas makes the reading sometimes difficult. \n\t- In addition, I would have liked more explanations and informal proofs for some of the claims: why is the standard empirical average biased and what is the bias? I agree that the authors explain that this is due to adaptive sampling and that this has been shown in previous work. But this statement is important to the message of the paper and would make the paper more self-contained. Similarly, a simple formula that shows that the new doubly robust adaptive estimator is indeed unbiased and that its variance is less than that of DR or IPW might help the reader who is not familiar with counterfactual learning. At least the latter claims could probably be illustrated in a figure with synthetic data.\n\n2. Also, the regret bound is suboptimal in the number of arms K (of order $K^2\\sqrt{T}$ instead of $\\sqrt{KT}$). Some parts of the analysis could probably be improved. For example, the upper bound of $N_a$ by $T_a$ in the last equation of p16 seems very suboptimal and gives an extra K factor. Is it not possible to improve this?\n\nOther comments:\n- I agree that the method seems more suitable to TS to compute inverse propensity scores. But do you think that it could also be applied to UCB based algorithm to improve their estimates?\n- I would also write in the main text that you also provide distribution dependent regret bound in $O(\\log T / \\Delta)$\n- For best-arm identification simulations, it could be interesting to show the frequency of success of all algorithms. It is supposed to be approximately 0.95 in theory, but what is it in practice?\n- What motivates the default choice gamma = 0.01 for the algorithm? Doesn't it yield linear regret? Shouldn't it depend on K in practice?\n- TS and UCB are not the standard algorithm for best arm identification. It could be interesting to apply the techniques to best-arm identification algorithms. \n- How is exactly AB implemented in the simulations?\n- I suspect that the regret bound of Thm. 1 should be $\\sqrt{T}log T$ and not $\\sqrt{T log T}$. Indeed, $T_0$ as defined in line 514 is of order $(\\log T / \\Delta)^2$ and not $\\log(T)/Delta^2$ as stated in line 303.\n- Since the bound is of order $\\sqrt{T}$, I do not find Cor. 1 very interesting since it is a straightforward application of Azuma-Hoeffding inequality to Thm. 1. I would replace it with a single-line comment in the text stating that the bound also holds with h.p. \n\n\nTypos:\n- l92: a dot is missing\n- l78: I would define IPW there\n- l307: a T should not be there", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "IbEF9NnqhAc", "reviewer": "Reviewer_wmKw", "summary": "The authors propose a Thompson Sampling (TS) based cumulative regret-minimsation algorithm for stochastic MAB. Their approach pivots on the unbiased estimator of mean using inverse propensity score, and then it applies weighted averaging scheme [Luedtke and Van Der Laan, 2016] to reduce the variance of the estimate. Further, they establish theoretical worst-case upper bound on the expected cumulative regret, and present multiple simulations to show empirical efficiency of their proposed algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "below is the list of strengths ad weaknesses of the paper:\n\nStrengths:\n1) The proposed algorithm is empirically efficient.\n2) Use of propensity score along with weighted averaging for a better estimation of the mean is a god idea.\n\n\nWeaknesses:\n1)  It seems that to hold the proposed approach, the reward distribution of the individual arms has to be Gaussian; however, there is no explicit mention of the same. There is no discussion on the family of sub-gaussian reward distribution.\n2) The scope of this proposed idea for sample averaging by propensity score, does not seem to hold for paradigm like UCB, wherein, given the history, the next arm to be pulled is obtained deterministically.\n3) The problem-independent upper bound on cumulative regret presented in Theorem 2 is far from the optimal rate O(\\sqrt(KT)).\n\nOverall the contribution appears to be marginal.\n\nMinor Comment:\nThere is only a single subsection 1.1 under the section 1.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Mention of limitation of the proposed approach is not apparent.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "H5SQ73-rdN0", "reviewer": "Reviewer_gbUL", "summary": "The paper investigates stochastic MAB algorithms, UCB and Thompson sampling, where the usual choice for estimating the means of arms, importance weighting, is replaced with a \"doubly adaptive\" estimator. This estimator, proposed by Leudtke and Van Der Laan 2016, is self-normalized in that the weight of each sample in the mean estimator is not uniform but rather proportional to the inverse square root propensity weight; it also uses an AIPW-style estimator with these weights.\n\nThe authors claim that this new estimator can have better practical performance, since the variance of the mean estimates is greatly reduced, and this claim is verified with empirical simulations. Additionally, the authors provide an upper bound on the worst case performance of O(K^2 sqrt{T log T}), which captures the correct dependence in T.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a great paper. First, it studies a archetypal NeurIPS problem, the stochastic MAB, and asks an important and very neglected question: what can we say beyond worst-case performance? Second, it brings in powerful and well developed ideas from other literature that are ignored by our community. Third, it is well written, cohesive, and easy to follow. The inclusion of the two-arm upper-bound proof in the main body is appreciated, since it gets the main points of the analysis across without taking up too much space.\n\nThere are a few weaknesses, besides the K^2 term in the upper bound. There is no theory supporting the central hypothesis that DATS can have improved sample complexity. Maybe a particular instance where a gap can be shown between the IPW and a DATS-based algorithm is possible?\n\nWhat is the point of the \\Phi is algorithm 1 (it is monotonic)?\n\npost-rebuttal: my opinion of this paper remains high and my score unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ECJ6MH6hpXQ", "reviewer": "Reviewer_zzib", "summary": "The paper proposes a Thompson Sampling-based online algorithm for the stochastic K-armed bandit problem, which exhibits improved numerical performance in terms of the expected cumulative regret and its variance, and smaller stopping times for best arm identification. The improvement is over the popular UCB and Thompson Sampling baselines common in literature. Although, the improved empirical performance of the proposed algorithm does not translate to provably better regret guarantees vis-a-vis the aforementioned benchmarks (a sub-optimal K-dependent scaling factor is present in the upper bound). The improved numerical performance is primarily attributed to a new estimator for the true arm-means (as opposed to the standard sample-average approximation used by vanilla UCB/TS), which is provably unbiased, and at the same time, offers a better variance control compared to other unbiased estimators popular in ex post (adaptive) causal inference literature. The punchline, in my understanding, is that it is possible to improve and (better) control the numerical performance of bandit algorithms by employing sophisticated estimators from adaptive inference literature, without compromising on rate-optimality in the regret upper bound (order of dependence on the sampling horizon, modulo multiplicative constants). ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written overall with intuitive explanations, and an accessible proof of the main theoretical result. The technical development occurs at the intersection of adaptive inference with the traditional regret viewpoint in the learning literature, and certainly seems to be of practical significance (numerics are promising). Also, extant literature in this space is relatively recent and sparse (to the best of my knowledge), making this work even more appealing. The literature review seems reasonably complete, although the following paper is missing: https://arxiv.org/pdf/2106.02126.pdf. This is a recent paper that answers some long standing open questions regarding the distribution of arm-pulls under UCB, TS and can significantly shape/alter the discussion in the current paper regarding asymptotic-normality (or lack thereof) under vanilla UCB/TS. Cited paper, I think, might be able to provide a more comprehensive and theoretically grounded justification for why it may be advisable to move towards a greater level of sophistication in estimator design in bandit settings.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some broad remarks and minor typographical errors are noted below:\n\n1. Line 34: It should be \"..... uncertainty,\" (the order of \" and , should be flipped). There are other occurrences too.\n\n2. Line 37,38: This is a bit ambiguous; gap-dependent bounds are not the same as \"worst-case\" bounds in standard bandit parlance. \n\n3. Footnote 2: Also state the $O\\left( \\sqrt{KT\\log K} \\right)$ bound for the Gaussian prior-based version of TS from the same reference, for a comprehensive picture (the stated bound corresponds to the Beta prior-based version of TS).\n\n4. Footnote 3: This is not true for UCB. Previously cited paper dispels this myth (Refer to Theorem 1 and 4 therein).  \n\n5. Line 114: Policy-dependence of regret should be made explicit on the RHS. \n\n6. Line 144-145: Same as above, i.e., claim re asymptotic-(non)normality needs to be revisited and corrected for UCB.\n\n7. In Algorithm 1 \"arm elimination step,\" the first update needs to happen for each $a\\in\\mathcal{A}_t$. \n\n8. In Algorithm 1 \"propensity score computation\" step, it should be $\\tilde{r}_{t+1,a}$ after \"argmax.\"\n\n9. Line 200: \"s\" should be \"t,\" and it should be \"a\" in place of $\\tilde{r}_{t,a}$.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three of the four reviewers recommended accepting the paper and I am happy to accept it. I encourage the authors to include in the final version the additional material that they mentioned in the rebuttal.
Decision: Accept (Poster)