Adaptive Experimentation When You Can't Experiment
Authors: Yao Zhao
Kwang-Sung Jun
Tanner Fiez
Lalit K Jain
Venue: NeurIPS 2024 poster (2024)
Keywords: Experimental Design
multi-armed bandit
Primary area: bandits

Abstract: This paper introduces the confounded pure exploration transductive linear bandit (CPET-LB) problem. 
As a motivating example,  often online services cannot directly assign users to specific control or treatment experiences either for business or practical reasons. In these settings, naively comparing treatment and control groups that may result from self-selection can lead to biased estimates of underlying treatment effects. 
Instead, online services can employ a properly randomized encouragement that incentivizes users toward a specific treatment. 
Our methodology provides online services with an adaptive experimental design approach for learning the best-performing treatment for such encouragement designs. 
We consider a more general underlying model captured by a linear structural equation and formulate pure exploration linear bandits in this setting. Though pure exploration has been extensively studied in standard adaptive experimental design settings, we believe this is the first work considering a setting where noise is confounded.  Elimination-style algorithms using experimental design methods in combination with a novel finite-time confidence interval on an instrumental variable style estimator are presented with sample complexity upper bounds nearly matching a minimax lower bound. Finally, experiments are conducted that demonstrate the efficacy of our approach.

Adaptive Experimentation When You Can't Experiment
Yao Zhao University of Arizona yaozoarizona.co edu
Kwang-Sung Jun University of Arizona kjunccs arizona. edu
Tanner Fiez
Amazon
Fleztann@amazon.com
Lalit Jain University of Washington Balitjeur edu
Abstract
This paper introduces the confounded pure exploration transductive linear bandit (CPET-LB) problem. As motivating example, often online services cannot directly assign users to specific control or treatment experiences either for business or prac- tical reasons. In these settings, naively comparing treatment and control groups that may result from self-selection can lead to biased estimates of underlying treatment effects. Instead, online services employ properly randomized encouragement that incentivizes users toward a specific treatment. Our methodology provides online services with an adaptive experimental design approach for learning the best-performing treatment for such encouragement designs. We consider more general underlying model captured by linear structural equation and formulate pure exploration linear bandits in this setting. Though pure exploration has been ex- tensively studied in standard adaptive experimental design settings, we believe this is the first work considering setting where noise is confounded. Elimination-styy algorithms using experimental design methods in combination with novel finite- time confidence interval on instrumental variable style estimator are presented with sample complexity upper bounds nearly matching a minimax lower bound. Finally, experiments are conducted that demonstrate the efficacy of our approach.
Introduction
In this study, we present a methodology for adaptive experimentation scenarios characterized by potential confounding. Online services routinely conduct thousands of A/B tests annually (23). In most online A/B/N experimentation, meticulous user-level randomization is essential to ensure unbiased estimates of treatment effects at the population level, commonly known average treatment effects (ATE). In this setting, firms are often interested in understanding the treatment with the highest average outcome if presented all members of the population. However, in many settings firms may not be able to randomize, for example a feature must be rolled out to all users for various business reasons (30]. In such instances, users may choose engage with feature not based potentially unobservable preferences. Thus the resulting measured outcome may be correlated with the decision engage in specific feature. I.e. the underlying characteristics of the user confound the relationship between the decision to use the feature being evaluated and the effect of the feature. Thus, naively comparing the average outcome for users who engage with a feature with those who do not suffers from a (selection) bias. This setting is captured in Figure
A potential solution is for services to employ encouragement designs where with incentives that encourage users to engage with a specific feature [4] 7 12]. As concrete example, many online services have introduced membership levels with different offerings and
presented
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

prices available to all users. Given a set of membership level options, the service is interested in knowing the counterfactual of which level has the optimal outcome (e.g., total revenue) if every user chooses to join that membership level. In this setting, encouragements could be coupons or trials for corresponding membership levels. In these settings, the firm can use intent-to-treat (TTT) estimates for the treatment effect which naively compare the average outcomes between the groups given different encouragements. In practice, given an encouragement a user may not engage with the corresponding feature choosing either the control or different feature. Hence, the resulting ITT estimate may be diluted estimate of the ATE [3]. However, all is not lost: the encouragement presented to user is properly randomized, and the service guarantees that the encouragement only affects the outcome through the choice of user treatment, then the encouragement acts as an instrumental variable. Standard analysis from the econometrics and compliance literature show that two-stage least squares (2SLS) estimators can then be used to provide consistent estimates of treatment effects.
At the same time, firms are also increasingly utilizing adaptive experimentation techniques, often known as pure exploration multi-armed bandits (MAB) algorithms 226 15] to accelerate traditional A/B/N testing. Pure exploration MAB techniques promise to deliver accurate inferences in a fraction of the time and cost as traditional methods. Sim- ilar to A/B testing, bandit methods assume users are prop- erly randomized and can fail to learn the optimal treatment if naively used and may be sample inefficient if they fail to take the confounded structure into account.
Z Encouragement
User Chvice
Chitoome
Confomdder
Figure 1: Causal graph of the model.
Contributions. In this work, we provide methodology for experimenters seeking to use adaptive experimentation in settings with confounding where encouragements are available. We formulate this work in the more general and novel setting of confounded pure exploration transductive linear bandits (CPET-LB) (Section I.I). We present algorithms using experimental design for the CPET-LB problem and analyze the resulting sample complexity. As we demonstrate, even in the simple multi-armed bandit setting described above, computing an effective sampling pattern requires using the machinery of linear bandits. Without knowledge of the underlying structural model, existing linear bandit approaches could lead to sub- optimal sampling. The main technical challenge we face is simultaneously improving the structural model while designing with inaccurate estimates (Section (3. This approach crucially relies our development of novel finite-time confidence bounds for two-stage least squares (2SLS) style estimators that may be of independent interest (Section Moreover, we provide worst-case sample complexity lower bounds that are nearly matched by our sample complexity upper bounds (Appendix D). Though the goal of this work is primarily theoretical, we empirically show the efficacy of our method over existing solutions (Appendix
estimate of
1.1 General Problem Formulation
confounded pure exploration transductive linear bandits (CPET-LB) instance consists of finite collections of measurement vectors Z C IRd and evaluation vectors W C Rd. At each time i E N, the learner selects 2, Z and observes pair of noisy responses 24 X C Rd and yt E R generated via the structural equation model
It I + Te.
Vi = x. +
where I' E Rdxd and 0 e IRd are model parameters We define the history H4-1 = [(,, Ez. yo (a)} Jost and E,-1l- = El 1 denoting the conditional expectation under the filtration generated by H4-1- The noise {ne _ and {e satisfy the following set of assumptions unless otherwise noted.
Assumption 1. We assume E Hi-1 is I-sub-Gaussian (and thus Els, H4-1l = 0). Furthermore, me H4-1 is o,.-uu- -----Gaaaasinnn vectors (and thus Blye H.-1] = 0), i.c.,
Pog
V3 E R, max E(exp(B(a. exp 1l
2
'e assume throughout that I' ddd is invertible matrix.

---

Goal, The objective is to identify w' := arg maX w with probability at least 1 - 8 for 8 E (0, 1) while taking minimum number of measurements.
In the setting where r = 1 = O and ( = O, our setting reduces to the standard pure exploration transductive linear bandit problem [33 15 In general, the joint noise process [7/,, 6x] may be dependent across the entries. In particular, we are allowing for the data generating process to be endogenous, meaning that E, [x * O. That is, E, can affect not just yt, but also given choice of 24. The presence of endogeneity a key challenge in the CPET-LB problem.
Assumption 2 (Exclusion Restriction). We assume that E, [2 = 0, or alternatively that 2, is uncorrelated with E.-
The variable 24 is commonly referred to as an instrumental variable 3
We consider algorithms
for the CPET-LB problem that stop at Hl.-masurable time т E N, and produce recommendation @ E W. The goal is 5-PAC algorithms with efficient sample complexity guarantees.
Definition 1.1 (Ó-PAC). We say algorithm is 6-PAC for CPET-LB problem with W, 2 TR if for all 0 E IRd and E Rdxdd it holds that pe.r aar(fe F w*) s 5 for 5 E 1).
1.2 Encouragement Designs
The CPET-LB feedback model generalizes the classical compliance setting.
Compliance a Special Case. In compliance problems, decision-maker has access a set of treatment that can be offered to users, while the users themselves have the option to accept the treatment they are presented or instead opt-in different treatment. The goal is to identify the treatment with the optimal average outcome if all users were to accept it. Specifically, given a finite set A = {1, ......... d). a decision-maker presents user & N with an encouragement for a treatment i E A, the user then selects treatment j E AA where potentially + i, and an outcome Ye results. To capture compliance with the CPET-LB framework, we set Z X W fei, , Ce) and the parameter I' captures the probability of accepting treatment given an encouragement for potentially different treatment. Specifically, [(i,j) = P(x,, = e, | ã = ej), , and a straightforward computation shows that Tt- = D 2t + 7/8 where B(na 22] = 0 with
= x₁ (P =,..... ,P(ea 24)
(2)
Moreover, 3/ = xx] E, gives the resulting reward, which is clearly correlated with the user choice so that cov(N): Ee) * O. Finally, e, 0 = 0; gives the expected value of treatment over the population and our goal is to identify w' arg max s.ew e, 0. Note that when I I, we automatically have that 7/+ = 0 and there is no confounding. This reduces to the standard MAB setting.
Motivating Compliance Example. As motivating compliance example representing the mem- bership level discussion from the introduction, consider a location model that assumes each user t E N arriving online has an underlying unobserved one- mi-dimensional preference un ~ (0, a.). If an algorithm presents the user with encouragement 21, = er, for I, E AA, then the user selects into the membership level given by J, minijeA 1/, + U, jl so that ,,, e.,,- This process captures user being more likely to opt-in to membership levels that are closer to the encouragement that they were presented. The outcome is then given by V1 xx, 0 + U4-
We conduct an experiment with this problem instance (see Fig. and Appendix for more details). Specificallyy, d = 6, 0 =
0.95 0.99 and a = 0.35. Observe that w" = e arg max_ew w: To. An upper confidence bound (UCB) selection strategy is simulated that maintains estimates of the mean reward of each encouragement E AA, namely fu., =E 1f2z = e Jv, and then pulls the one with the highest UCB. The UCB selection strategy is combined with a pair of recommendation strategies. The OCS algorithm estimates the mean reward of each treatment using an OLS estimator, namely 0-3 = E'= 1fx = eJy./ E 1(2, = e. and recommends arg max 0is Moreover, the UCB-IV algorithm uses an instrumental variable- estimator (see the next section) that incorporates knowledge of similar to 2SLS to deconfound
-0.95
0.45
"Our setting differs slightly from the traditional compliance setting based on potential outcomes frame- work 33] Our setting is equivalent to one where we assume that there is a constant treatment effect. See Chapter 4 of 3 for further discussion of the differences. Thus in our setting, learning 6 and the local average treatment effect (LATE) on compilers are the same.
3

---

6/9
e.ro
1.00
Mentificattoo Probability
0.75
0.30
0.25
6.0
Valle
0.00
00225
-0.50
-0.75
-1.00
29020
40020
60000
50000
Evaluation Index
Time Index
(a) w and w 10 for w E eal
P w² for the instance
Figure (a) bar chart showing Elylæ w w 0 and Elyl= = w| = = = arg max Bly la = w), while eu = arg max wew Elylz = w] and consequently estimation based on this quantity is problematic. (b) for collection of algorithms on the CPET-LB instance from Section 1.2
E W.
This chart shows that the optimal evaluation vector is w
The probability of identifying w"
estimates of the mean rewards of each treatment and recommends the treatment with the maximum estimate. The results over 100 simulations are shown in Fig. 2 UCB-OLS completely fails identify 0 = arg m 0 due to a biased estimate, whereas BCB-VV does better. However, UCB-IV methods seem have a constant probability of error. To see why, note that the expected reward from pulling C; is e. T8. These values are plotted in orange in Figure 2a In particular, with some constant probability, UCB zeroes in on arm becauses of the mean estimates on the z's, and as a result fails to give enough samples to learn that arm is indeed the best. In contrast, our proposed method CPEG, Al Algorithm|] manages to find the best arm with significantly higher probability.
Notation. Let A(Z) {A E R : A 2 E.E d = =1} denote the set of probability dis- A(Z) and matrix I E Rdxd, define the operator A(A, = E.ez Ar 22 T.. Given Z E RT'xd and T Rdxd define the operator A(2,1) = Σ l 22
tributions over the Z. Given distribution
2 ZT ZT where E Rd denotes row t of Z. Given vector E R and symmetric positive-definit matrix A E Rdxd we let | = xx' Axx We adopt the standard notation that (a b)) = max(a, (a, 6] and (a min(a, b) for a, R. mmnn(A), max (A) denote the minimum and maximum singular value of matrix A. We denote by polylog(11,. Tn) any polylogarithmic factors of I1,...,fa.
1.3 Related Works
Our work is at the intersection of several parallel tracks of literature, pure exploration linear bandits, causal bandits, and econometrics. The most relevant work on pure exploration linear bandits the RAGE algorithm of [15] 33 RAGE is nearly instance optimal for linear bandits in the non-confounded setting. Extensions of RAGE various noise models including logistic and heteroskedastic noise have been considered [5 20). Other algorithms for pure exploration linear bandits have been proposed [0].
and we leave it for future work to extend the ideas of this paper to those settings
Confounding in bandits was first considered in the regret minimization setting by 5 They introduces the Multi-armed bandit with unobserved confounders (MABUC) problem. They empirically demon- strate traditional bandit algorithms can have linear regret in this setting and provide an algorithm that effectively employs observed intuition. The early work of (21) also assumes there an additional unobserved latent class at each time that determines confounding in a compliance setting. They provide novel notions of regret, relative to the instrument with the highest reward (arg max Z TTr in our notation), the highest treatment (arg max w' 0), regret relative to the best latent class at each time, and regret on the set of "compliers". They discuss the suitability of these various notions of regret, and discuss when sublinear regret is possible. We remark that their approach is similar to ours in the sense that they assume a form homogeneous effects across the population, and use an estimate of T. Recently (4 also consider the problem of compliance, however they don' 't take explicit non-confounding into account and assume an explicit parametric model that determines the non-compliance. This is analogous to the Heckman selection model considered in econometrics [18).

---

The recent works of [IT] 36 17 considered an online setting where at each time they observe set {(2,, 2+]} where x2 is the action of interest and 2, an associated instrument. If action 1, is selected, the reward observed is yt z i, 0r + Et, where Ia may be endogeneous. Similar to the standard linear bandit setting [66).. the goal is to minimize regret relative to the best action at each time. We remark that this setting very different from ours. Effectively, we are choosing which instrument to select at each time to learn the best- best-performing treatment in particular we can't 't choose particular intervention. In their setting, they are choosing an intervention at each time and using the instrument purely for de-confounding the result. Experimental design for instruments to have more effective estimation has been considered by [8]
In the causal bandit problem, an underlying causal graph between a set of interventions and a reward value is assumed. Actions correspond intervening (i.e. a "do" operation (3T) at
more specific nodes in the causal graph and then observing the corresponding value at the reward node. Causal bandits have been studied extensively in the regret setting [25] 28 6 and the pure exploration setting (3). Though past works have allowed for unobserved confounders in the graph e.g. [29], their goal is to learn the best performing intervention, which our setting would be arg m TØ instead of w..
Encouragement designs have been considered in many applications in online and offline settings. One of the earliest works on encouragement designs is (7). which considers the problem of using encouragements to determine the impact of coupons
grocery store. More recent applications 30, 13 all in the context of online services and treatments that are required to be served to all users. Most of these works consider a small number of treatments and heterogeneous treatment effect- hence are interested in LATE estimator. As far as we are aware, we are the only work that considers adaptive encouragement design in the context of the model given in Equation T and for multiple treatments.
include 4
2
Estimators and Inference
We now present estimators for the unknown parameter 0 and prove the associated statistical properties. The estimators discussed in this section are critical to our algorithmic solution outlined in Section 3
2.1 Estimators
Before describing our solution concept, we quickly review potential options for estimating 0 based on a dataset Zr = ..., 2T] E TR. xd Xr = [21.... FT)
T E R. gxxdd Yr = [y,..... yr) R.T.
assumed to be generated according to the model in Eq. I Recall that the ardinary-least-sppe (OLS) estimator for is given by
0 arg mingeg" Ei x 0) = xx) = 0 0 (X
(3)
Observe that OLS is potentially a biased and inconsistent estimator for 0 the presence of endogenous noise since [[er| & O. To remediate this problem, we define a general class of estimators that includes several standard estimators. Given an invertible matrix Vi E Rdd let Xq == Zr and consider corresponding estimators termed IV estimators of the form
0y = Xr) X, YT (v T ZT YT Yr (Z) -ト
When V/ = / we recover the OLS estimator. In the rest of the paper, we will focus on two different potential options for V.
Case 1: Oracle. V = r. To begin, observe that the structural equation model from Eq. 1 can be combined by substituting the second equation into the first to obtain the reduced form
Y1 2 T + 1)( 0 + St-
(5)
Since 2; is independent of the i.i.d. process 77. 0 + Es. the least squares estimator which regresses yr onto 2, T is unbiased for estimation of f and given by
Oaracla = (8 x - (2777))
This estimator will be used to design our general solution concept presented in Section 3 Of course in practice cannot expect to know I', but may be able to estimate it.
5

---

Case 2: P-2SLS. V = f. We consider a setting where is an (unbiased) estimator of r. learned using squaresuuares from an independent dataset ZT; = [24,- 24, IT,
2 o collected
non-adaptively That is, I (Z7, Zı, 77, X1, and:
0p-28Ls (f 2 (イ 2T
We refer the resulting estimator pseudo stage least squares (P-2SLS) estimator. The main advantage of the P-2SLS estimator over standard 2SLS (given in Appendix ( is casier inference since now {EI of our dataset independent of the measurements of the first dataset ZT, XT. In the econometrics literature, such an estimator is referred to as two-sample 2SLS estimator [9]
2.2 Confidence Intervals
In the section that follows, develop general algorithmic approach that relies experimental design aimed at reducing the uncertainty in our estimates of the optimal treatment. To this end, we first develop finite-tima confidence intervals for estimators presented in the previous section given data generated according to the model Eq. ①I and collected from non-adaptive designs.
We begin by characterizing the properties of the noise structure in the combined model of Eq. (5) with the following set results.
the noise process == == is o3--uu--Garr Bub-Gaussian where of 200, + 1). specifically when the instance is compliance, o 1 + 1).
Lemma 2.1. Under Assumption !
Oracle Confidence Interval. As in the last section, assume that have access dataset (ZT, XT, YT) generated according to Eq. [ and collected non-adaptively. Given Lemma 2. it can be shown that w Foracie is sub-Gauue Gaussian random variable satisfying the following. Lemma 2.2. With probability at least 1 - for E (0, and w E R4,
w T (foracie - 0) S 20 w/ 1(2 log (2/6).
where o is the sub-Gaussian parameter of the noise y= n + characterized in Lemma 2.1
The proof of this result is in Appendix G.2
P-2SLS Confidence Interval. We now present novel finite-time confidence interval for the P-2SLS estimator. As discussed the previous section with respect this estimator, we assume access set of data (ZT, XT,) generated according to Eq. (T] and collected non-adaptively for the purpose of estimating Г. Moreover, assume access to a separate set of data (ZT,, XT,, Yr;) generated according to Eq. I and collected non non-adanaa aonaaaativelly for the purpose of estimating O.
Theorem 2.3. Suppose that î (ZT, - XT, and 0p-25Ls- (f' Zr, (T, P Yrs Then, for any W, with probability least 1 f 8 (0,
4 + | A(ZT, ((2r, 110112 Voglog ,5,;5/19
|w (0p-28LS 8) S F)) 20 log 8
where
23 (1+ d(2 A mmin (2,, ZT,))
2-6
4 2 A Tmin (Z ZT,
log( (T, Sid
+ 16 In
log3
The proof is presented in Appendix G.3 Observe that the first term in the P-2SLS estimator confidence
interval given by 220 w|
A(Zr, - log( 4/8) matches the Oracle estimator confidence interval
in Lemma 2.2 when f = r. The second term scaling like O A(2r,, - 100120, d log (0gg(1)) (1/5)). an upper bound on the approximation error (f- I)@ for any w E Rdd, assuming that f is leamned from an OLS estimator (see Theorem G.33 for details).
Formally, we say that set of data (Zr, Xr, Yr) generated via the model in Eq. is collected non- adaptively from experimental design if is Ho measurable for all 1t S.

---

We will see that the form of this confidence interval is particularly convenient for our algorithmic approach given in Section In particular, the form of the variance || 2 A(Zr, ,')-1 on the first term only depends on design over instruments. Thus, we can choose an experimental design over Z's which reduces this variance optimally.
Remark 2.4. In practice we expect the first stage of samples, (ZT,, XT, to be collected from either burn-in period or from existing historical data. We remark that assuming two stages of samples is common in the orthogonal and double machine learning for estimating nuisance parameters in the data generating process (e.g. I'' 19]. Our result matches the existing literature on the asymptotic variance of two sample 2SLS estimators (e.g., Theorem of [1)).
Remark 2.5. The asymptotic variance of standard 2SLS is known to involve a factor o². instead of of as we have (18). Recent work by [II] shows variance involving do However, it's unclear how to use the form of their confidence interval directly for experimental design. addition, their work is not sufficiently general to handle the general forms of noise that consider in Lemma 2.1
3 Adaptive Experimental Design Algorithms
We now present adaptive experimental design algorithms for the CPET-LB problem. Our main insight utilizes Eq. Ty plugging the model for into the top equation resulting in the relationship
y r + 0 E.
When I is known, by Eq. 5
that CPET-LB reduces to standard pure exploration transductive linear bandit problem where the measurement set is given by {I' =}eez C RR, the evaluation set W C R4, and the feedback model is given by y = v 0 + V where the noise v = 8 17 + is Sau-Gansiin and as before the goal is to identify arg wa w 9. An existing approach this problem is given by the RAGE algorithm [15), which we use as the basis of our approach. Addressing the case of unknown I is our major algorithmic contribution, where we develop solutions to improve our estimate of and learn w" simultaneously. As a warm-up to this approach, we first consider the setting when I' is known.
3.1 Warm-Up: Known Structural Model
Algorithm Jssumes a parameter L,, which acts as an upper bound on the nub-Gaussian constant of the noise v Tn v) + e. In each round i an active set of potentially optimal vectors We C & is maintained. CPEG aims sample in such a way that reduces the uncertainty of the estimates on the gaps (wr - w for each pair w. w/ E Wi maximally each round. In any given round the algorithm takes N₂ samples ZN,, the confidence interval of Lemma 2.2 shows that the error in estimating (w w²) scales with ||-=w'] [1 27, 2x, TD-1 This motivates utilizing an experimental design approach
where choose distribution d E A(2) minimize max max || w/ 11 AT s= TT)-- The number of resulting samples taken from this design Ng. is chosen guarantee that the confidence interval of Lemma is is less than 2 Then, the elimination step in Line 8 guarantces that all E W such that (w- w) > 2- 2-2- are then eliminated from the active set by round + of the procedure. To actually choose our samples, as is common in this literature (15). we use an efficient rounding procedure, ROUND that requires a minimum number of samples r(w).
Sample Complexity Guarantee. The sample complexity of Algorithm depends on the following quantity (>() that captures the underlying hardness of a problem instance in terms of (W, TJ, when = 0, we abbreviate p² (0) p",
|w0 - w/ll (w- w. 0)2
p² (7)
min max XEA(Z) WEW)("")
(7)
Theorem 3.1. Algorithm 7 iis 5-PAC and terminates in at most c(1 + w) L.p log (1/8) + cr(w) samples, where hides logarithmic ftcttor of A min,, (w= - w.0) ) and [W], as well as constants.
The proof of this result is in Appendix H.I In the unconfounded case when I' = / and = 0, E E [r] 0 this matches the sample complexity of (15). In particular, for the case where 2 - X = W. the problem further reduces to standard multi-armed bandit, and if e is 1-sub- Gaussian noise,
33 shows that p" O(E - -2)) which is the optimal sample complexity
7

---

of best-arm identification for aelli-armed bandits. The following lemma shows that the conditioning of I' can have strong impact on the resulting sample complexity.
Lemma 3.2. For the compliance setting, we have min max lle, eg ee AI - S
d max oy ||r (eg (ey- - - Furthermore, p² I da (T)=
A
To further illustrate the impact of T, imagine an extreme setting where
Algorithm 1 CPEG:Confounded pure exploration with I
T (1-e)/d11 T + e and x 0, i.c. I' a perturbation of 1/d11".
1: Imput 2, W, = Lv 2 o
2: Initialize: k = 1, W1 W.
It's straightforward to show that the upper bound in the first display of Lemma 3.2 is of the order 3)
3: Set f(e w', w',T,,,,,., .T, = ||
EEEE TT)
4: while [W& do
5: A arg min)ea(2) Wn [wu, w', mo'.T,M AJ)
(this is also lower bound- see Ap- pendix K.I). In particular, the upper bound on the sample complexity is of the form d min- This is in sharp contrast to the linear bandit case, when r = I and we are guaranteed a sample complexity of no more than d/Amin samples. To gain some in- tuition, regardless of the choice of X, ATr e,e I x Г. As a result, p² + as E + O. Intuitively in the limit, regardless of which instrument i < is being pulled, the resulting distribution on the treatments is uniform (the instruments are weak). Thus, it is impossible to deconfound the measurement noise, and recover estimate of 0. This is a phenomenon which does not arise in the standard multi-armed bandit case with unconfounding.
6: p(W) = minxe max WeW f(u, w' .I,))
7: N2 : [2 + w2 p(W)))L log [4k² (11661 V r(w)
8: Pull arms in ZNz = ROUND()E, Nk) and observe YN..
9: Compute 0f
I ZN.T)
ZN,YNa
10: WA+1 = War(w E WallBw E We,, (w- w. O0)
2-*), k < +
11: end while
12: Output: w E Wi
We also consider a setting where instead of given directly, we are given an estimate f of I based on offline data. We discuss such adaptation of Algorithm to this setting in Appendix []] and provide a sample complexity which reflects the error in I (scaling with p (7) for y > 0). We remark that this result is subsumed by the approach of Section 3.2 and so omit in the main text.
Remark 3.3.
Lower bound. Due to the noise model from confounding and the dependence of the noise AT 7 E. the instance-depender lower bounds of [15] do not immediately apply. We develop lower bound tailored for the confounding setting that nearly match the upper bounds of our algorithms. What's more, our lower bound illustrates the additional difficulty that arises from confounding by an additional factor of d² compared to the standard transductive linear bandit problem the most general setting where entries of are sub- Gaussian, but not necessarily independent nor bounded. Due to space limit, we defer to Appendix D
3.2 Fully Unknown Structural Model
We now consider the setting where is fully unknown. The difficulty of this setting is that the data collection process needs to support both estimation of I and @ simultaneously. Our algorithm, built upon Algorithm [ is summarized in Algorithm 3 At its core, each phase of the algorithm is divided into two sub-p 1o0--pases, for estimating I' and 0 respectively. Specifically, the second sub-phase is essentially same as Algorithm 1 with F'x in place of I' where I' estimated from the first sub-phase. The main novelty of our algorithmic design lies in the first sub-phase, which resolves the challenge of performing the optimal design for estimating I'. To explain this challenge, the confidence interval for P-2SLS estimators of Theorem 2.3 indicates that one should pull arms so that we control both || w/] 112
D2 := max
A(Zr, f.)) (error from 2p-25LS) and Dj == max || - w'll A(Zr, .2a)
(error from (1)) to be below the target error O(C2) at each phase (ignoring unimportant factors for discussion). Controlling D2 is trivial, which is done in the second sub-phase as we described above.
However, for Di, similar strategy cannot be done because the estimate I's is computed directly by sampling arms in Zr,- That is, the ideal design, based on which we will collect data points 21, Zn. requires access to the random matrix I'v that can only be computed after sampling 21,..., .... En.. This
8

---

Algorithm 3 CPEUG: Confounded pure exploration with with unknown
Input 2,W,6, 6, by 2 oi bn 2 " Ymin Amin (T), Ag,
Initialize: == 1, W, To =1,51 =1
Define f(w, w/; [,,) = || w o'lli [iez IT
Asax Tr) M
32h, Janon Mwin (1(2g.1)
V1, 8e ==
4 122
while [W > do
F r estimator (Wis, F --1 Sha 6/k2, S//h,an we XE, M, Min)
Step I: update T
0 02- 0 - estimator (We, 6/h², " Sks I'K Loo)
D Step 2: update
We+1 WAl { wE W/ F'o E Wa,sll (w' (2.288)) St
Step 3: elimination
+ + 1, Cu =
end while Output: We
creates a cycle that seems impossible to resolve. Such an issue, to our knowledge, has not been seen in existing work on pure exploration, and thus resolving it is our key technical contribution.
Our solution is compute the design based on F&g from the previous phase. We then perform doubling trick where we double the sample size (while following the computed design) until Di becomes smaller than the target error O( The intuition is that in later phases the estimate I&g from the previous phase will be accurate enough to ensure that the design is efficient. Note that this novel algorithm induces extra randomness in how many samples we end up collecting in the first sub-phase, which remains random even after conditioning on the history, unlike the second sub-phase. This makes the analysis challenging, which we describe after the main result.
Our algorithm additionally employs the so-called E-optimal design to ensure that the covariance matrix of the collected data used to esti- mate is well-conditioned. This conditioning is required to ensure that Fw concentrates fast enough to I' as shown in the analysis. The E-optimal design is well-known design objective in experimental design that aims to maximize the smallest singular value: Xg = arg mi))) max (Vnxx(-1(A)) where = ExEz A=22T. denote --1 == maax (V-
Algorithm 2 8 estimator
Input W, <, R.F. La
Ā arg minxe max of e'ew (w, w', ,T,A) p(W) minxea(2)) max w/ ew f(w, w/ {.A)
N₂ 2(1 + w){ (wwpw)((())_))))) P(W) log
4WW1
Vr(w)
get N₂ samples per design Ā denoted as {Zz, X2, Y23 & via
ROUND update 0p-
( 737 -2 7
Output: Op-29Ls
We =
amin (V (Xg)) as the smallest singular value achieved by the E-optimal design.
We present our analysis result Theorem 3.4 where we show that, even without knowledge of r, the sample complexity scales with the key problem difficulty p² almost matching the sample complexity of Algorithm| [ which relies knowledge of T.
Theorem 3.4. Algorithm 3 is 5-PAC and terminates in at most
(1 ([L, (1/6) (1) + log(1/6)))p* + (d (o=) + M)) pulls, ignoring both of the additive and multiplicative logarithmss of A, [W Pu, M, where
32Lg
Po
max WEW'
wlli AE. 22 and M
11.
Tiin Twii (A()E:1))
Note that Pa does not get hurt by (w" w. f), (p" does). comes from the fact that the first phase, initialize that algorithm with E-optimal design.
The challenge of the analysis can be summarized in two-fold. First, since the concentration result Theorem 2.3 w.r.t. Pr, we need to analyze how the random matrix Π. concentrates around and how this impacts the sample complexity. For this, we develop novel concentration inequality

---

Algorithm 4 . estimator
Input W, (, M, lnn
Define (W, (. www. w 111 -ewp///wwwlxxzx---1111
L,,log( Z, 8)
Initialize ( = Noo.
b doubling trick initialization
iff =1 then
while / = or Stop W, Zo .5t) > do
get 2 2 ng
samples denoted as (Z X Yo,e) per design Ae Update F' by OLS on {Z Xoct. 1+1
via ROUND
end while else
x min)e w'EW [ww, w', P.A))
N'
AgdM In
[ 1 2M d L?)) 2M2gdM1 8M In (2g*) v vr(w)
while 1 or Stop W, T U 71,,, F,,)) > < do
N1.e 2' N"
b doubling trick update
get N..e samples per Ā denoted as [Z,, X1.e, Vi.e}
via ROUND
No. 2ydM In M (M (d+ Ni. LZ) 4M In 2:64 V Vr(w)
get (No.e No,c-1) samples per As augmented to (Zo,z-1, Xo.c-13 and get (Z, Xo,e3
Update I'd by OLS (Zo.e Xo. X1.)). 1- e+1 end while
end Output: fM
that relates the confidence width involving I from Theorem 2.3 with the same quantity involving in place of f. Second, our algorithm creates long-range error propagation, which is highly nontrivial to analyze. To see this, the quality f& is affected by the design objective function max [w, w', , A), which depends on the error of the estimate f from the previous phase. This error is, in turn, affected by the error of i'x-2 2 by the same mechanism. This is repeated all the way back to the first phase. Thus, any abnormal behavior from the first iteration will have cumulative impact to even the end. In our analysis, we successfully analyze how the error is propagated from the previous iterations, which forms a complicated recursion. Resolving this recursion is key novelty in the analysis.
Remark 3.5. Our algorithm requires knowledge of a lower bound Tmin of Amin The knowledge of Ymii is for simplicity only as can obtain such lower bound that is at least half of the true value Amiu (T) via an efficient sampling procedure that we describe in Appendix
We provide experiments for the instance of Section 1.2 in the Appendix The experiments show that our approach is more sample efficient than natural passive baselines (e.g. A/B testing). or naively applying existing Pure-Expe Eipp-orrtortoon linear bandit methods and performs similarly the oracle complexity.
Experiments.
4 Conclusion
This work introduces the CPET-LB problem in which the learning protocol is characterized by linear structural equation model governed by parameters I' and 0. We provide a general solution that simultaneously estimates the structural model while optimally designing to learn the best-arm. The key ideas behind our approach are based on linear experimental design techniques, an instrumental variable estimator whose variance can be controlled by the design, and novel finite-time confidence intervals on this estimator. This paper presents number of directions for future work including considering situations where the d, + d., analysis to improve the dependence on the underlying noise variance, and the pursuit of tight iiftrmmtioonthhoreete instance-dependee hope that this line of work motivates increased discussion of the real impact of confounding on applicability of adaptive experimentation.
lower-bound. We
10

---

Acknowledgements
Kwang-Sung Jun and Yao Zhao were supported in part by the National Science Foundation under grant CCF-2327013.
References
[1] Abbasi-Yadkorfs Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Allen-Zhu, Z., Li, Y., Singh, A., and Wang, Y. Near-optimal discrete optimization for experi- mental design: A regret minimization approach. Mathematical Programming, 186:439 478, 2021.
[3] Angrist, D.D Imbens, G. W., and Rubin, D. B. Identification of causal effects using instrumental variables. Journal of the American Statistical Association, 91(434):444-455 1996.
[4] Bakshy, E., Fckles, D., and Bernstein, M. S. Designing and deploying online field experiments. In International Conference on World Wide Web, pages 283-292, 2014.
[5] Bareinboim, E., Forney, A., and Pearl, J. Bandits with unobserved confounders: A causal approach. Advances in Neural Information Processing Systems, 28, 2015.
[6] Bilodeau, B., Wang, L., and Roy, D. Adaptively exploiting d-separators with causal bandits. Advances in Neural Information Processing Systems, 35:20381-20092, 2022.
[7] Bradlow, E. Encouragement designs: an approach to self-selected samples in an experimental design. Marketing Letters, 9:383-391, 1998.
[8] Chandak, Y., Shankar, S., Syrgkanis, V., and Brunskill, E. Adaptive instrument design for indirect experiments. arXiv preprint arXiv:2312.02438 2023.
[9] Chernozhukov, V., Chetverikov, D., Demirer, M., Duflo, E., Hansen, C., Newey, W., and Robins, J. Double/debiased machine learning for treatment and structural parameters, 2018.
[10] Degenne, R., Ménard, P., Shang, X., and Valko, M. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432-2442. PMLR, 2020.
[11] Della Vecchia, R. and Basu, D. Online instrumental variable regression: Regret analysis and bandit feedback. arXiv preprint drXiv:2302.09355,,200 2023.
[12] Elbers, B. Encouragement designs and instrumental variables for a/b test- ing, August 2023. URL aste::://engiheerriggaatttttpp atspotiff. cow 2023//223//// /08 nncouragement.o weegeeenntdeiinneeee
desidnssign..... gns- and mnstrumenntall-vriaallee.. for b-sttingg//// Accessed: 2024-05-19.
[13] Engineering. S. Encouragement designs and instrumental variables for a/b testing, 2023. Accessed: December 26, 2023.
[14] Even-Dar, E., Mannor, S., Mansour, Y., and Mahadevan, Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
[15] Fiez, T., Jain, L., Jamieson, K. G., and Ratliff, L. Sequential experimental design for transductive linear bandits. Advances in Neural Information Processing Systems, 32, 2019.
[16] Gales, S. B., Sethuraman, S., and Jun, K.-S. Norm-agnostic linear bandits. In International Conference Artificial Intelligence and Statistics, pages 73-91. PMLR, 2022.
[17] Gong, X. and Zhang, J. Dual instrumental method for confounded kernelized bandits. arXiv preprint arXiv:2209.032224 2022.
[18] Greene, W. H. Econometric analysis. Pearson Education India, 2003.

---

[19] Inoue, A. and Solon, G. Two-sample and Statisties, 526)):55--561, 2010.
instruummntttttt instrumental variables estimators. The Review of Economics
[20] Jun, K.-S., Jain, L., Mason, B., and Nassif, H. Improved confidence bounds for the linear logistic model and applications to bandits. In International Conference Machine Learning, pages 5148-5157. PMLR, 2021.
[21] Kallus, N. Instrument-armed bandits. Algorithmic Learning Theory, pages 529-546. PMLR, 2018.
[22] Katz-Samuels, J., Jain, L., Karnin, Z., and Jamieson, K. G. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. In Advances in Neural Information Processing Systems, volume 33, pages 10371-10382, 2020.
[23] Kohavi, R., Tang, D., and Xu, Trustworthy online controlled experiments: A practical guide to a/b testing. Cambridge University Press, 2020.
[24] Kveton, B., Liu, Y., Kruijssen, J. M., and Nie, Y. Non-compliant bandits. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pages 1138- 1148,114,, 2023.
[25] Lattimore, F., Lattimore, T., and Reid, M. Causal bandits: Learning good interventions via causal inference. Advances in Neural Information Processing Systems, 29, 2016.
[26] Lattimore, T. and Szepesvári, C. Bandit algorithms. Cambridge University Press, 2020.
[27] Li, Z.,, Jamieson, K., and Jain, L.. Optimal exploration is no harder than thompson sampling. arXiv preprint arXiv:23/0.06006 2023.
[28] Lu, Y., Meisami, A., Tewari, A., and Yan, W. Regret analysis bandit problems with causal background knowledge. In Conference on Uncertainty in Artificial Intelligence, pages 141-150. PMLR, 2020.
[29] Malek, A., Aglietti, V., and Chiappa, S. Additive causal bandits with unknown graph. In International Conference on Machine Learning, 2023.
[30] Mummalaneni, S., Yoganarasimhan, H., and Pathak, V. V. Producer and consumer engagement on social media platforms. SSRN 4173537,
[31] Pearl, J. Causality. Cambridge university press, 2009.
[32] Sen, R., Shanmugam, K., Dimakis, A. G., and Shakkottai, S. Identifying best interventions through online importance sampling. In International Conference on Machine Learning, pages 3057-3066. PMLR, 2017.
[33] Soare, M., Lazaric, A., and Munos, R. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
[34] Vershynin, R. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[35] Weltz, J., Fiez, T., Volfovsky, A., Laber, E., Mason, B., Nassif, H., and Jain, L. Experimental designs for heteroskedastic variance. arXiv preprint arXiv:2310.04390, 2023.
[36] Zhang, J., Chen, Y., and Singh, A. Causal bandits: Online decision-making in endogenous settings. arXiv preprint (tt::2211.086442 2022.
12

---

Appendix
Table of Contents
A Broader Impacts
13
Iulstrtitv Example
13
Standard 2SLS estimator
14
D
non-inferactive lower bound
E
Experiments
16
E.1
Comparison Algorithms
16
E.2 Experiment I: Jump-Aroume Around Instance
16
E.3
Experiment 2: Interpolation Instance
17
F
Proofs of the lower bound
18
Proof Theorem
18
Proof Corollary D.2
20
G Proofs of the confidence interval
21
Proof of Lemma 2.
21
Proof of Lemma 2.2
22
G.3
3
Proof of Theorem 2.3
24
Proofs of sample complexity when given
28
Proof of Theorem|3.1
28
Proofs sample complexity when given
31
Proofs sample complexity with unknown
35
K
Estimating Amin (T)
54
Proof of Lemma
57
lemma for solving x less than In(x)
57
A Broader Impacts
This work is algorithmic and tied to particular application that would have immediate negative impact.
B Illustrative Example
We now present an illustrative experiment that highlights the challenges endogenous noise and the insufficiency of standard experimentation approaches used in the absence of confounding.
Instance Definition. Toward connecting back to membership example in Section I consider that service has d membership options given by the set A = {1...., d). Let the set 2= fei.-... .e] represent encouragements (incentives or advertisements) for the corresponding membership options given by W = X' {er..... } We consider location model that assumes each user / E N arriving online has an underlying unobserved one-dimensional preference 14 ~ (N(0, If an algorithm presents the user with encouragement 21, e,, for 1, A, then the user selects into the
13

---

membership level given by Jr = minjes + u -j] so that 2; CJ,, For visual depiction, see Figure Bal This process captures a user being more likely opt-in to membership levels that are closer to the encouragement that they were presented. The outcome is then given by y/: x; 0 + ut- This problem instance is a specific compliance instance. For this experiment, we take d 6, let 0 0.45 0.95 0.99 and of 0.35. Observe that the optimal evaluation vector is wt 61 arg waw wTd
0= =
0.95
We simulate UCB strategy which maintains estimates of the average reward of each of the possible incentives, namely Fi., = E. 2
ej and then pulls the one with the highest upper confidence bound. This models current practice of using bandit algorithm to select which incentive to show a user. Our results averaged over 100 simulations are Figure 3d At each round we estimate the average reward of each level using an OLS estimator, i.e.
0 = Σ.= 1fx =
/ Ei- 1(r, e;}, and check whether it matches the true value (denoted as UCB-OLS). We also consider an instrumental knowledge of I similar to 2SLS to deconfound our estimate (UCB-IV), As the plot demonstrates, UCB-OLS completely fails to identify 01 arg maxied 0g (this line is hard to see it is at 0) due to a biased estimate, whereas UCB-IV does better. However, UCB-IV methods seem to have a constant probability of error. To see why, note that the expected reward from pulling = = is e T8. These values are plotted in orange in Figure [cc In particular, with some constant probability, UCB runs on the empirical rewards from pulling z' zeroes in arm 6, and result fails to give enough samples to learn that arm is indeed the best. In contrast, our proposed method CPEG, Algorithm| manages to find the best arm with significantly higher probability (the algorithm was run with ó in the given time horizon.
(see the next Section) which incorporates
C Standard 2SLS estimator
Consider v/ f 2SLs = - Xy. In this setting, we recover the standard two-stage-least
squares (2SLS) estimator,
0ZLLS = (r Zr) xx,
(Z,
Note that the 2SLS estimator is a biased, but consistent estimator of the parameter 0 18
Note that in particular, the asymptotic variance of 2SLS is known to be o2
(f [ [f aas)
18
Recent work by 11 provides a confidence interval of the form Iw (#2sis
0)
(T)5)). However, it's unclear how to use the form of their con-
fidence interval directly for experimental design due to the dependence of PISLS on the random quantity X. In addition, their work is not sufficiently general handle the general forms of noise that we consider in Lemma 2.1
D A non-interactive lower bound
Due to the noise model from confounding and the dependence of the noise OJ + e, the instance- dependent lower bounds of [5] do not immediately apply. In this section, we develop a lower bound tailored for the confounding setting.
Toward characterizing the optimal sample complexity, we develop a lower bound for specific non-adaptive algorithm A that has access to the matrix I' governing the structural equation model. In particular, suppose that the non-adaptive algorithm A is allowed to select a sequence of T measurements {-1,.... 21, ...,, Z1, } to query prior to collecting any observations, where I, represents the index of the vector E chosen time E {l..... T).. Then, given the observations {Vi,.... (V1............................. Ut,........ yr) generated by the environment, candidate optimal vector ã E W is returned by the algorithm. We are interested in the necessary number of observations that must be collected in order to ensure P(w # w*) < ö for some ö E 1). Thus, it is natural that the optimal non-adaptive algorithm A using the estimator Ooracto forms a recommendation rule such that ă arg max w Doracle- We now state our lower bound result with respect to the non-adaptive oracle algorithm.
14

---

Pix
ci2 c:)
0.07
0.00
0.00
0.00
0.07
0.85
0.08
0.00
0.00
0.00
0.00
0.07
0.85
0.08
0.00
0.00
0.00
0.00
0.08
0.85
0.08
0.00
Jr
+
U1
1
0.00
0.00
0.00
0.07
0.85
0.08
0.00
0.00
0.00
0.07
0.93
2
3
5
==
(a) Depiction of the problem instance.
Heat-map of T.
e/re
UCB-OLS
UCB-IV
1.00
Iddettif Iattaaatio Prohabsiity
0.78
0.30
Value
0.28
0.00
-0.25
-0.50
-0.75
-1.00
20020
40000
60000
ED000
Evaluation Index
Time Index
(c) w To and us TT for fei,...,,eal
P( (1. w²) for the instance
Figure 3: (a) A visual depiction of the problem instance from Section B The user is presented with encouragement I E A and the user choice given by Je where Jj minje 14 + 2e -jl and 24 ~ (0, ).). b) A heat-map showing the structural parameter I' for the problem instance from TO for all w W. This chart shows that the optimal evaluation vector is w* = = arg wEW E[y[æ = w). while 66 = arg max Ely|2 w| and consequently estimation based on this quantity problematic. for collection of algorithms the CPET-LB instance described in Section B Standard optimistic sampling approaches combination with an ordinary least squares estimator leads to faulty inferences. Given instrumental variable estimator, these experimental designs eventually give high probability identification but do so inefficiently compared to our proposed approach (see Section 3).
Section B (c) A bar chart showing Eyyy w] w 0 and [E[yl = w]
(d) The probability of identifying w"
Theorem D.1 by W C Rdd Z C IRd, E' Idddd, and E Idd, Assume I' is known, 0 is unknown, and the noise process is jointly Gaussian and defined by := ( E| ~ N E) where E E [id-1)x(d++)) is arbitrary correlation matrix. For 8 E (0, 0.05). if the non-adaptive oracle algorithu acquires T < a2p" p" log (1/8) 1/8) / samples on the problem instance where x² == T Tuu and u := 1] TRo+1
Oracle Lower Bound). Consider problem instance characterized
then P( + w )²= 2 6.
Corollary D.2. There exists a problem instance chargcterized by W Rd Z Rdd, I E pdxd and i E TR. with noise process satisfying Assumption such that if the non-adaptive oracle algorithm acquires T I max(d]]0] /d[10l12pp* log (1/5) samples, then P(w + w²) 2 8 for E (0, 0.05].
The proof of Theorem D.I is in Appendix F.
Notably, the result is reminiscent of lower bounds for the standard pure exploration transductive linear bandit problem without confounding [5] 2 when given the measurement set {T' 2e2e,, evaluation set 2, and parameter 9.
Notably, the upper bounds for our algorithms nearly match the lower bound of Theorem D.I However, interesting to observe that the sample complexity incurs an additional factor of d" relative to the standard transductive linear bandit problem in the most general setting where entries of are sub-Gaussian, but not necessarily independent nor bounded. This illustrates the additional difficulty that arises from confounding. We point out that this is not likely to be tight lower bound. In
15

---

particular, it a lower bound with respect to non-adaptive algorithm that uses the particular choice of estimator. We leave improved lower bounds future work.
E
Experiments
We now present experiments collection of experiments on CPET-LB problem instances. The experiments demonstrate that our approach produces efficient designs for inference and estimation.
E.1
Comparison Algorithms
The baselines that approaches compared with are discussed below. We experiments both when P is known and when fully unknown.
E.1.1 Known
To standardize the experiments, the baselines considered in rounds mirroring the structure of Algorithm I Specifically, in round & E N sampling algorithm selects design X E A (22, collects Nù samples from the design, and forms a V/
estimate of 9 with V/ I that is combined with confidence interval (Lemma 2.2 to either eliminate evaluation vectors or validate stopping condition. The number of samples Ne taken in round & E N by any of the algorithms is given by WW/6) Vr(w) where p(W); max w'E max f(w, w', A) for design A E (()) and active set of evaluation vectors Wμ. The round sample count guarantees that given any experimental design, all vectors E W such that (w* w) T > 2 2- can be determined be suboptimal by the end of round The sampling methods we consider are now described.
NA [2(1+w)<G p((W)) Lu log (4k" log(4k*
Static Oracle. This design selects d arg (in)) max f(w", w' V,, A).
Static XY-Optimal. This design selects λ = arg min XEA(Z) wa fww, w', N.,.A)) A).
Static Uniform. This design selects A 1/1 V 2.
Adaptive Uniform (SE). This design selects AR = 1//W V V E We. Note that this
algorithm is effectively an adaption of oction-eliminatio
The static designs are independent of the round and simply terminate when all evaluation vectors can be eliminated except for a recommended optimal vector w.
E.1.2 Unknown T.
For this set of experiments, compare AlgorithmB 3 against collection of variations of the sampling procedures. Specifically, we compare against methods that either replace only the experimental design for estimating I, only the experimental design for estimating 0, both with uniform sampling. We label the approaches as - N, where N represents the sampling approaches (XY or uniform) for I and 0 respectively. Moreover, to make that log( also removed, so we collect E-optimal design samples only once the beginning of Algorithm We find that even with these modifications to the algorithm, correctness is maintained empirically.
modify the algorithm so = 4d log( (1/5). The step of incrementally adding more E-optimal design samples
approach more practical,
E.2 Experiment 1: Jump-Around Instance
We first return back to the location model of Section Recall that = e.) For this experiment, we take d 6, let [1 0.95
0.45
0.45
0.95 0.45] and 0 0.275.
The results of the experiment are shown in Figure 4a for the case of known I. We see that Algorithm
performs much better than the baselines and nearly matches the oracle design. Delving into approach, it is able to quickly eliminate all but wi and W2-1 and then puts more mass on #1 and =d-1 to reduce the uncertainty on wi and w 1- For the case of unknown r, the results are shown in Figure 4d where 0g is reduced to 0.9 that all approaches could finish.
16

---

Oracle
CPEG
Uniform
Static-XY
2.0
(a) Experiment Known
(b) Experiment 2: Known F, iden- tity
(c) Experiment Known I, per-
mutation
XX-XY
Uniform-XY XY
XY-Uniform
Uniform-Unffomm
(d) Experiment Unknown r
(c) Experiment 2: Unknown r,
(f) Experiment 2: Unknown r,
identity
permutation
Figure 4: Sample complexity for algorithms on CPET-LB problems. Our approach is consistently competitive across the experiments.)
E.3 Experiment 2: Interpolation Instance
Let 2 = W = X fe..... ed] define the measurement, evaluation, and observation sets. We first consider that r == -111 1a1] æTa for parameter (0, 1) where is d-dimensional vector of I's and La is the d-dimensional identity matrix. For this experiment, we take d = 4 and let = [0.5 0.583 0.67 0.75]. As all compliance instances, 1/: 2, - 2,, and in this simulation f = 0.4%, vr, where 1 /,/ / and 0g ~ NO, La). The results of the experiment shown in Figure for & E {1, 0.9, 0.8, 0.7} with I' known. Note that Static-XY and Uniform overlap, and SE and CPEG overlap. We see that Algorithm perform similarly and near optimally. This is to be expected since the most efficient way to gather observations for treatments is to encourage that treatment, given that the encouragement is not followed each of the alternatives is equally likely and provides no additional information of interest. Moreover, as discussed earlier, the problem gets more challenging as T + 12 /d. Note that the identity matrix could be replaced with permutation matrix, in which case uniform sampling with elimination becomes highly suboptimal. The results for the case of unknown are shown Figure with 0.99. This shows the value that comes from the experimental design for estimating both I and 0.
| and the adaptive uniform strategy
To demonstrate the superiority of our algorithm over SE, we also consider that P := (1-6) 1al] +
where 73 is permutation matrix as follows,
1
0
0
0
1
0
0
0
0
0
0
All other settings remain the same as in the previous interpolation instance. The results for the known I' case, shown in Figure 4c] indicate that SE exhibits significant underperformance due its sampling rule not accounting for the permutation effect in I'. In contrast, CPEG consistently achieves near-optimal performance. Note that Static-XY and Uniform still overlap. Figure 4f presents results for the unknown I' case, where we can notice that, comparing with Figure 4e estimating different permutation matrices (with the identity matrix as special case) does not affect problem difficulty.
17

---

Proofs of the lower bound
E1 Proof of Theorem D.1
Theorem D.1 Consider problem instance characterized by W R. Z C CR I''.' gdxd and 0 E Rd. Assume I is known, is unknown, and the noise process is jointly Gaussian and defined b 7= in E] ~ No(,)) Σ) where Σ E R(d+1)x(d+1) is an arbitrary correlation matrix. For E (0, 0.05], if the non-adaptive oracle algorithm acquires 7 S a² log (0g(1/8)/)) /2 samples on the problem instance where o² := v Eu and v : [0 1] R then P( + w=)) 8.
Proof. We begin by recalling the framework of the non-adaptive oracle algorithm and discussing the properties of its estimator for the noise structure described in the statement of the result.
Non-Adaptive Oracle and Instance Definition. The non-adaptive oracle algorithm A selects T measurements query prior to collecting any data. Let I represent the index of the vector Z chosen at time t {1...., T}. The noise process for the instance under consideration is assumed to be jointly Gaussian and defined by % = | Et] ~ _/ 2) where E E R(d+1)x(d-1) is an
arbitrary positive semidefinite matrix. Defining TT, == P 21, v = 0 1 E Rd+1 and == v 7.
the feedback model can be described as follows:
y/ r40 Et
(T 21,) + 11. T + Et
=: (T 2 + N
=: =,, Vt.
Observe that the noise is independent and identically distributed as i ~ N( o²) where o² := v Ev since "i (0, E). Moreover. the noise process exogeneous with E/p,|e1,] since FT, is deterministic given the index choice 4,
Let (z,, VT YE and {ye )T denote the observations collected by the non-adaptive oracle algorithm A and define Zr E Rxxx XT E Rxxd and YT E IR. to contain the respective stacked observations. Algorithm A obtains estimate 0 Ooracle by minimizing the of squares follows:
Ooracle == arg min DER E (v: 2,, 0) 2 -
(Z YT.
Given foraclo, the non-adaptive oracle algorithms A returns recommendation defined by T arg max w" GoracIe. Note that since Porecie is obtained by least squares with exogeneous, independent and identically distributed mean-zero Gaussian noise, it is straightforward to verify the estimator distributed as
Ocracio 0 ~ NN(0. (A(T))))()
(8)
where
A(Zr, = Σ r 2T, = XT = r 2 ZT1.
Proof by Contradiction. To begin, recall that
||" w -11 A(
min max AEA(2) (w") (w+ - w. 0)
Suppose for the sake of contradiction that the number of samples collected by the non-adaptive oracle algorithm is T' < o²p² log (1/8 and P( & w²) 8 for (0, 0.05). To reach contradiction, we analyze the distribution of (w
(w- - w²) 0 for some * w" and show that with probability at least it is positive. We remark that this proof follows similar techniques that the proof of Theorem 3 of (22].
18

---

Let Ā E A(2) represent the empirical sampling distribution of the algorithm A, which is defined 2} for each 2. Moreover, define
such that X= Ei= 11 (2,,
||0 - = A( and W E arg max (WW)(
1|w0 w A(2,1)-1
p²(A) = max
we NeWif"")
(w> w. 0)2
(w" w; 0)2
Note that p (²) 2 p and observe by definition,
1(
ExE2 XrT 22 --)
T
21, 21, 1)
= A(ZTT
T
T
1=1
Thus, by Eq. (8)
Oxxacie - 0 ~ 0 -V(0,02. A(T.T)
T
and
1
w²) (Boracle - 0)
. N(1,002
1 --ll ((2.1)-1
(w* W.
T. fw² ūū 0,2
Furthermore, by the definition of p" (A), the assumption T S 0²pp log (1/6)/2, and the fact p² (A)) p", we obtain
2
w²) (foracta - 0 0²
1 T 2 A(A,)) == (²(2)
2
(9)
(w* w. 0)
T. (w" w.0. 0,2
T
log(1/6)
Now, consider a random variable W ~ .N(0, 1). Proposition 2.1.2 of Vershynin 34 gives an anti-concentration result showing that for all <>
P(W ( 2 ( ( 2tT
-2/2
(10)
We apply this result to the quantity (w- w²) T(Orrccee 0)/(w² w 0) conclude that (w
w*) Ouracia > O with probability at least 8. Toward doing so, let (1, 1.15) be a constant and define
W ~ C log (166)
W
and W
and 7
2/log(116)
v log((1 (1/)
Observe that W N0 1). The following analysis holds for d (0, 0.05) given that e (1, 1.15] as assumed:
10- w²) (foracle 0) 2 2c) 2 P(W 2 c)
P
(By Eq.
(w- w. 0)
W
2/ (2/1)
2/ log (1/8)
= P(W 2 7)
1
72
(Proposition 2.1.2 Vershynin 34
73
2TT
V2
V22
1
8/
c loggo(11) (1/8)
\ogg(1/6)
1/TT
8.
The final inequality can be verified computationally. Thus, with probability at least 8 for 8 E (0. 0.05). we obtain
(w- - w²) Ofracte 2 =(ww -
To c(ww" -w) 0 (w* w) To
-w)To 0 -w)
+ (w -w")= To
(c- - 1)(w² - w) To
> 0.
19

---

Observe that the final inequality holds since > 1 and (w" - -w) T >
0 by definition.
This result directly implies that with probability least for å (0. 0.05], the vector t returned by algorithm A is not w". This is contradiction, so we conclude that the non-adaptive oracle algorithm A acquires T S d²p" log(1/5) samples, then PP * w") 2 8 for d 0.,0.
F.2 Proof of Corollary D.2
Corollary D.2 There exists problem instance characterized by W c R Z c R r E Rdxd and 0 E 12d with a noise process satisfying Assumption such that if the non-adaptive oracle algorithm acquires T max(d]]0122. vd 0 0|22p"" log(1/0) samples, then [P o w*) for (0, 0.05].
Proof. To begin, consider the specifications of Theorem D.I and its result. That is, problem an arbitrary instance characterized by W Fd C Rd T Raxd and 0 E ER where the noise process is jointly Gaussian and defined by 7 : [ E] NO 2 where 2 (xd++))((+1)) is an arbitrary correlation matrix. Observe that the noise process defined by satisfies Assumption [ The result states that if the non-adaptive oracle algorithm acquires T o²p= log log(1/0)/2 samples on the problem instance where o² := Ev and == [ 1] E Rd+1, then P( * w 2 6 for d E (0, 0.05]. From this point, we show that there exists a parameter 0 and correlation matrix such that ²² == T Ev 2 max max(d]|0 ] in order to reach the stated conclusion.
Notation. Let Sm.. E [-1, denote the correlation between and ε for E {I,.... (h....,d, d}. Similarly, let Sm,y Soy.m [-1, denote the correlation between fi: and πy for # E {1.....d) Note that the correlation of 7/ with itself for E {l....,d d} is o. = Sm..
and similarly the correlation with itself is o² = Ee.= = 1. The correlation matrix Σ is then given by
1
Sma.
Sna.m Sna.ma
Sa.m Se
Smine
Eg Spe
Snie 1
E
Smiona 6m.5
Sma-ns Snz.e
Seyns
Sna.
where
1
Sma.m
Smann
Smie Sya.e
Smima
1
Smarra
Eg
E 11-1, and
Sape
E E[-1,114
Snioa
Snama
Snais
Moreover, we use the notation E.. E Rd to denote the i-th row of EJ or equivalently the i-th column of Lg for any i E {1, [l.
Lower Bounding Noise Variance. Given the above notation, we work toward lower bounding 22 == 0 Ev. Observe that by algebraic manipulations,
0
Eg
Sa.e
U Ev =
Sm,s
0 TTTT + Somee T Sn + +1] 0
T TTTT Smi
0T BT + Sop.
0
Σ Eg
Em Sm OT Sn. +1
i=1
= 0 Σg0 20 Sn,s +1.
Since Eg a real symmetric matrix, an eigendecomposition exists such that Σ. = QAQT where A diag diag(Ai..... Ai.... >a) [dxdd is diagonal matrix containing the cigenvalues of Eg and Q E dddd
20

---

is an orthogonal matrix with columns corresponding to the eigenvectors of Eg. Let qi := Q denote column of the matrix Q for = .......d d}. which equivalently eigenvector of Σ. for i == -1,,... d}. Without loss of generality, assume that the eigenvectors are of unit length so that ||g:l12 for all ......
Given this information, suppose that the parameter in the instance is equal to a scalar multiple of the eigenvector of Eg corresponding to the maximum eigenvalue. Note this is equivalent the statement that is equal to some scalar multiple of the column q- E R2 of the matrix Q where q. the eigenvector of Eg corresponding to the maximum eigenvalue A² Thus, we take 0 q- for some E IR and observe that ||0]|2 c. Toward quantifying the value of v Ev for the problem instance, we begin by characterizing 0 EgA for the choice of 0. Consider the following analysis:
A Ege T QTQQAT
= (cq-)" "QQQ (cq+)
(8 = cq.)
|101/g. [92
q.
qa] Agn
g.
qd] 4.
||01
0j diag(A1.....
X . 11) 00
11 1
T]
(g: = 0 vi * j)
|10||2>*.
(14- = 1)
Thus, general for this choice of 0,
Egv |1012>> -0
Sn. + 1.
To conclude, take Eg == 1e17 where 1a represents the d-dimensional vector of all ones. Since this is a rank-1 matrix, the maximum eigenvalue is X 1, 1a d and the remainder of the eigenvalues zero. Observe that g. 1a/ / is eigenvector corresponding to the maximum eigenvalue since 1x1 q. dg.. Thus.
T Evv |1013>> + 20 Sn.5 +1 = |1012x +
(0 = cq. = 100121a/Val and Sn.s := 1a)
dll011 + 2vd +1
2 max(d]10113 Vd (112).
This completes the proof since we have shown that there exists parameter and correlation matrix I such that x² == v Ev 2 max(d] V010 which by Theorem D.1 allows us to make the stated conclusion.
G Proofs of the confidence interval
G.1 Proof of Lemma 2.1
The first statement is an immediate consequence of Lemma G.2 and the second statement is proven in Lemma G.I
Lemma G.1. In the compliance model, the noise o) 6 follows (810112 + 2) -ss--suuuus Gaussian distribution.
Proof. In compliance, we have 2, x E (e eej, and
") (P((1 ()) ,P(e,, =
21

---

Let us figure out the sub-Gaussian parameter of the random vector Fix any unit vector a. First, we have B a)] O. Second, we have
"
17122
(Cauchy-Schwarz inequality)
(P(e1) z). P((uull,)))))))) /|,
W
| + (P(e1 ,((aa P(ea 1z) (1.)
1+ ((e1 (P(e1 12),.. P(ea =)) Tl.)
(x: fer, ,ed) and ||01|2 $ || Va)
= 2.
Thus, 17 a'aa is bounded and zero-mean and thus 2-ssub-Gaussian. This implies that
vB, Elexp (3())((())))))) - exp 8822 a:|||||
and thus 1) is 22-sub-Gaussan random vector. Then, 17 0 is Subbl)=-uu Using Lemma G.2 we have that 17 To + e is 2 + 1)-sub-Gaussinn
L
Lemma G.2. Let A and B random variables that are each 0'2- and P2-sub-GGaussiee but are correlated. Then, A + B 2 + -ts-ss--Gaassiin
Proof. By definition of sub-Gaussian, we have for any Y E R
E <exp(>(A+ B)) [ex B)]
< v [[ex)(27AA] E[eex(27BB)
(Cauchy-Sehwarz)
(exp(2?20)) (exp(27208)
s exp (27 + +
G.2 Proof of Lemma 2.2
Lemma 2.2 Suppose that T' observations are collected non-adaptively from the structural equation
model in Eqs. ( and Iddxd is known. Then, with probability at least - 8 for & E (0, 1) and
W E Rdd
w T T(Ooraacte 0)| < 20 - log (2/()
where o² is the sub-Gaussian parameter of the noise process = T1 + as characterized in
Lemma 2.1
Proof. Given the knowledge I',, I', we have the oracle 2SLS estimator
T
①
Ooracte
23
r Zg
Za
Σ
20 T
r
Zallt.
1=1
[=1
Note that
21 = x2 +
(TT
0 11 TT 0
22

---

Denote v/ := :=77 0 +
For any w E W, we have
-1
0 Oracll - 0, Q.
2 r
Σ
24 8, w
T
2 I T
Σ
T 2, L0 + v1)
-0, w
1=1
-1
T
Σ 2 T
Σ 2
Tr +
Σ zz
0, w
T Σ
Σ A T
t=l
r
2g. w
Uq
q=
By Lemma G.1 the noise vs is oz Se--uu--ausssan we have
T
Σ
2522
r
Zig V4
2
is ((EE) 2525T
Zgg w)
oZ-sub-Gaussian. Thus
T
P
(oracle - 00, -0,w) (/
2 T
Zy. w
oZ log
S 8.
8
9=1
(=1
Conciscly,
7)
T
T
Σ
2 5
I
Eqg w
= T
Σ Zz r
Σ
2q a
Σ
I
w
9=1
t=1
T
w --1
Σ
2
I
I
w
T
TT
Σ
I
W.
(11)
Thus,
-1
T
P (Doracio - w 2
2w T
rT
Σ
T
r
wo log
1
1
S
t=1
We can further write it as
IP (Pareato - 0..) 2 $1 221101
(I
-10 log
1 (
6.
23

---

By taking union bound over, we have the confidence interval for the absolute value as in the statement of the lemma.
G.3 Proof of Theorem 2.3
Theorem 2.3 Suppose that I is estimated through a design matrix Zr, E i and 0p-2sLs is estimated through a design matrix ZT₃ E R2xx Then, for any w E W, with probability at least 1 6,
Iw (0p-23LS 0) S ||||| ((zr,
4 [ 20 log
+ || ā(Zr, .i- 1 / oflog ,04)
where of is the Gaussin parameter of the noise v 17 T 0 + E, of is the sub- Gaussian parameter of the noise 17. and
2T d(2 A min (Z,, Zr.))
2-6" 5
4 A miin (2,,2r,)
log(Zr, 6) = 8d 1+
+ 16
logē
Proof. For the pseudo 2SLS estimator, we have
T2 T
T2 -
0p. 02.28L. - 0 =
21,21
21,0t
0
1=1
1=1
-1
T2
T2
T
TO + v1)
21, 21
21,
T3
21, 21
21, 2 L0 + Σ
21,41
- 0
1=1
-1 T2
T1
Σ
21, 2
Tf
Σ t=1
M +
(f- -f- -1)0.
1=1
For any w W, we have
-1
T2
T2
O0p288L5 - -,w0 =
Σ
21 r
4 V4 +
(f-lr- - -1)0,u w
1=1
-1
T2
T3
Σ
2 I T
+ +(f-1T-- -1)0, w0
21, Ve, w
21 , w U4 + ((--r-1)) - w
21, 21,2111 2,T
-1
T2
21, 21
Tf
21 w V4
+
(f-1 p-1 re, (f-11-r1)re
( w.
(12)
We upper bound the first term and the second term separately. For the first term, by (Ein
Lemma 2.1. we know ve is subsuSasns,, we have Σn (E 2122T.T) 21, w vo is
2 21,: w o subGaussian. Thus by the concentration incquality of sub- (>>²) To I1, =T
-1
24

---

Gaussian random variables, we have
-1
T2
T2
T2
T2
16 on
Σ 21,21,
T.P
21g w
4/
2
21,
21,21,
f
219 w
o log
IA
q=1
q=1
By similar calculation as
11
we have with probability at least
2
T2
21, 21
T
21g
Vu I
Tw
FT
21,
r
wo? log
==1
/=1
1=1
S
21120|1 12
-)- 1 log
2112
2
(13)
Thus with probability at least 1 2
( (0e.28Ls- 0, w S || A(2,, Py 203 log
+ (
By Theorem G.3 have with probability at least -
((-1-r-1)ro) - | alla D- 1101 oz ( (T, 8/2)
(14)
Combining [3) and (1), we have with probability at least 1 - 5, for any w E W.
2 _1
002-2015 0,w) || A(Zry, -)-1
203 log
||l|| (,z, i 1101| ofooo Zn, 5/2).
By union bound, we have the confidence interval for the absolute value of the inner product,
()) + ||w +1|00/ 11211 ofTog( (Zo, Zz,, 5/4).
Iw (fp- 0) S ||l||| ||u/lx(20,, 203 log
Theorem G.3. Suppose that the least square estimator I' is estimated through a design matrix iT, 1R then it satisfies, with probability at least 1-
((-1-r~)) ro, w S [| A(Zz, A1 1101l (T,,
for any w E W.
Proof. Define V - ZT, E TRTid as the matrix with i-th row being 17 the stacked noise, i.e., the data collection process of the design matrix Z7, is X Z7, I + S. Then we have
(f-1---1) 10, w
A r - r0
= T
[++V 2T,55 [-+V-1Z7,5) V V-1
-T
(Lemmal D.12
11-1-- 1/2 1/2 SB
1 1 1/2 -=1||| 11/22 2Tz s0
<|1w|l f2-1
|| S op
||011
S1ww|| <|Iw|| Py- 101|
ofoloi ZZT, 8),
where the last inequality is due to Lemma
G.4
25

---

Lemma G.A. Suppose we have 21...., E R and ....... dr F such that Tr
21: "........... -1: 2T is oz -og-sub-Gind Gaussian vector (defined Assumption 7 Let 7,5 & R be matrices whose 1-th row is =t and ne respectively. Suppose =| S b,, VL. vō E (0, 1), we have, with probability at least 1-
Let V Z Z. Then,
2T
2-6d
4 2 T (V)
V V- 1/25T S o
8n
1+
In
..og2
d(2 A minn (V))
We abbreviate log (T 6) 8d (1+
2T a(2A0min(V)))
+ 16
2.0d. logg (2nomia())) )
4
Proof. By the definition of operator norm, we have V 7 5
V-1/2 1/2 1-11/22 Z7 Sx
sup op {
sup {all 1
TT Zr Z7 Sx
Z7 Sz
sup
f=1|=1=-1)
V-1
Considering a fixed w E Rd, by Lemma G.5 we have with probability at least 8,
2TL3
Z Sx 4-1 S v2 dln 1+
2
Logg
d(2 A m (V))
2 2 J (V)
By Lemma G.6land a union bound, for the s-covering Cz, we have the following event happens with probability no more than 5:
3 = Er E Ce. 2 2 2 v20mg dln 1+
2T
In
2/Ca 5
log2
d(2 A Jmin (V))
2 A Triin
We abbreviate log( (Tr 8) = v dln (1+
2TL2
+ 2 In
21 log
2(2h0min (V]J
When & does not happen, we have
V 1/22 T
2 Sz
sup
{_]|=||=11
V-1
77 y y+ w/1
sup min { (NivECt) }
min {uiveC,} (|27,S(= - w/| + 1| Sy (--1)
sup
[a]||||=1]
(|V-11/27 s
x sup
min {uIvEC.}
|| - 2ll2 + a Tog 7or, 6)
< --1 / S
+ t, 2T,88)
Thus,
V-1/2 2T s
5
og
log ZT, 8).
op
1
By choosing E = ] and Lemma G.6 we have
V-1/2 op
s song
8d 1+
2T
+ 116h
2-6d
log
4
d(2 ouin (V))
5
2 A Tmin (V)
26

---

Lemma G.5. /Seff-Normalized Bound Vector-Valuee Martingales| Suppose we have 21...., 24 E E and Th... .......7 ht R such that Tr. ,,.............................. 1, 2t is of -us-uu--Guussian Gaussian vector (defined in Assumption D. Let Z, S E Rtxd be matrices whose s-th row is 2 and n, respectively. Suppose | S Lin Va. Let Ve - 2 Then, vb E IR' ,8 E (0, 1), we have, with probability at least
Vt 1, n Sb v. I V21lb1l20m dln (1
2LL2 d(2 ^ miin (V))
(2
21n
logg
2 A min (V))
Proof. Since each row of S is - -uubGassiin vector, we have that (Sb):/|| is o SubGaussiin. Using Lemma G.7 with e, (Sb);/ / | completes the proof.
Lemma G.6. [2emmaa 20.1| There exists a set Ce C Rd with |Cel S ( such that for any I E {z E Rd, ||1|| = 1}. there exists y E Ce such that || 2112 S
Lemma G.7. Let 21, ... E {z E IR ||=1|2 || S Lz} and E1, E1,82,... E IR be random variables such that EK
- is -f--sb---aaaa -sub-aassiann Let V₁ = > 202 Then,
1-85P
VI 2 1,
Σ 2
S V20rg dln (1+
21L2
2 log2
2
d(2 A min (V))
2 O (V))
Proof. Let Z, Rixd be the design matrix and define e, (e1,..., E() R Let us omit the subscript from Ze Et and V., Note that
_ =lllv--1 = || Z Ell ell $ I1 (
S 2 +
It remains bound | el (V)2) We use union bound with the standard self-normalized
inequality of Lattimore and Szepesvári 26 Theorem 20.4 and Note 20.2]. Specifically, let A
2 -++1 for k 2 1. Then,
LL2 ddv. + 21nn (T22 26)/2)22
- 8 < TP 8:=
Ak 4 22 -ll S Sagg dln (1+
8
Under the event E, we have two cases:
Tmin (V) 1: choose & Then.
| El| Ell(V+omm (V) $ 1 E
LL2
(T2/6)
S Soc dln (1
+ 2ln
d
Omin (V) < 1: choose k [log (20 (V)-1) Omin (mi < A4-1- Then,
2, which is the ie that satisfies λ 5
|Z ell(v+tom (V)))) S 1T Ell El((++
tI?
(m²2 /6)/2)
$ $0 dln
[1+
+2
ddv
dln (1+
112
(20 (V) (V)-1)12
S soep
2m
do
(V)/2)
(Ax
2
mmnn (V); def of k)
Altogether, have
||zT e S ds dln I 1T v 20 (V))
(n2/6) (2g min (V))]2)
+ 2l
d
8
We conclude the proof by simplifying the RHS.
27

---

H Proofs of sample complexity when given r
H.1 Proof of Theorem 3.1
Algorithm 5 Confounded pure exploration with known I
Input 2, W, T, 6, e, Ly 2 0
Initialize: k = 1, M4 = =W
||l w/ (Exez 1 T)= Define f(w,, w/, A)
while W 1 do
A arg m2 w' f(w, w', A)
p(W))) min wa [(w, w/, (T,))
Ca 2-
N 2(1 + W L, log
4k [
v Vr(w)
ZN = ROUND(A:: N₂)) Pull arms ZNZ and observe YN=
Compute Oo = (MM ZNeI)
N YNz
WK+1 = WWA E Wi Bu' E Wk, ( (w' - w, 0 Ooracio) > Sk
++
end while Output: Wi
Theorem 3.1
Algorithm [
8-PAC for the CPET-LB problem and terminates in most c(1
Lup log 1/8) + cr(w) samples, where hides logarithmic factors of A and [W].
Proof. Part 8-PAC
By the confidence interval in Lemma 2.2 we have, with probability least 1
2
(0t oracla -0, 0, w0'
41.2 W|
< || w'll
(IT (E 21, s1,27)) V
20 log
8
vI w||le w w² ||
(IT A, T1)=
4k:2 W|
20 log
VNx
V1 + ++www w" ((TT (T)
203 log
8
2(1 + PL log (mmiin
vr(w)
< CR-
Define good event E w for each & and W3 as
{ - 0,w w. wn) ssa)
En
28

---

We claim that with probability at least 1 ò, the event a union bound.
20 Nww., Ek holds. It can be proved by
P
n
Ew
1,,00
k= wEW
R= WEWB
21 W
WEW
00
2
<6
(15)
where the last step by the fact that Σx=1 R7 6 2. Under the event N==1 O wew, Ew to show that the best arm is never climinated, suffices to show that for any sub-optimal arm w E Wk.
x²
w w" 0c
10 w. 0t oracle
+ (w wt , 00)
W w", 0 Poracle 0
Thus the best arm w" never satisfies the elimination condition. Next show that at the end of stage k any suboptimal arm w that satisfies
(0, :"' w) 225B
climinated. To show this, we need to show that w satisfies the climination condition,
Poractor w - -w)
2 0 Crraceer w" -w)
max wr NEW
( 0, w² w) (0, wn w)
Ck + 2Ck
Sk.
This implics that with probability at least 1 8, w" always survives.
Part 2 sample complexity
Define Sk {w E W|| (w- w, < 4Gx)- Thus with probability at least 5, we have Nie (W& C S.). This implies the following is true with probability at least - å for all k
p(W)) min
ww w II2
(EEez PT TT)
XEA(Z) uan EWW
< min max XEA(Z) ESt
||l w P (T
P(S)).
Define A to be the minimum gap between w" and any other w E W, i... A = min (w" - wr 0). Then for 2 [oog( 4A { we have S (w*) with probability
29

---

at least 1 - 5. The total sample complexity is the summation of the number of samples in each round,
[10 b)
Σ
N
)
Σ
4(1+ 2 L, log
v vr(ao)
8
1=1
[1o((4 191
4k-1
Σ
8(1 + w22 pw log
v vr(w)
8
Tog((1 42 1)]
4121
Σ
((1+w)22) Ly p( log
r((w)
(16)
On the other hand, we have
Iw w 10
S2 1T AAA22TTT
min
(2)(2) WEW
(w* w. 0)2
100 w/| 3 12i.ez (TA222TT)
min max max (EA(2) weSt
(w* w. 0/2
[oR(4>-1)]
Iw" w/l (Σ 2e IT A TT)
1
llog(4 (4A =1]
min AEA(Z)
max weS
(w* w. 0)2
k=1
[oo[44 44 1)
22k
min
max
||w w|l? [.Ez Ag==TT)
16 log (4A [
XEA(Z) WESt
Log( (os()s-1)]
Σ
2 min
||w w11 18 IiEz IT TT)=
64 (4A (19(44-11)
AEA(2) w.
[og(44 (0(44--1)
Σ
22k p(Sk),
(17)
64| (40 -
where the last inequality is by the triangle inequality, i.c..
max || w/ w/ (EEE PTAAsTTT)
max wo w. ES₁
||l w0 "I Aeaz Try T I|w" w/ a' A
wi," ES
max wESt
[ w01l "1 T))-
Combining (16) and (17). we have
log( 11 [
1og(1A-1))(M) p² + +log (44 10og(1--111 (14-1)
No < c(1 L) log loggoog10 (4A-1) log
30

---

I Proofs of sample complexity when given /
Algorithm 6 Confounded pure exploration with known f
Input 2, W, T, 6, e, b, 2 oz In 2 d Initialize: & 1, W3- W, calculate 7 using (18
Define f(w,, w/, I1, A) = w|l w w'11
[> EE r Au==
while Ew, w E Wk. s.t., ( w' w, Ooaciia) > 4y or Sk > do
A arg min mE w'W,, fwU, w/, {)
p(W)) min max [(w, w', (.))) SA 2-
N - 2(1 + w)
Sx (<
# p()))) log ( ) V vr(w)
NN = ROUND(AR;
Pull arms in INZ and observe YN2
Compute 06 02-2815 = (N ZNee)
Zh YNZ
WK+1 = W io E We Fwl E 8.L. (w' w. 0p-2L88 > Sa +7
k k++ end while
Output: any w W4
Theorem L1. Suppose that we have I' that is an OLS estimate from an offline dataset {Zr, Xr collected non-adaptively through fixed design & and the efficient rounding procedure ROUND,as
1o², well as T > Tmin (Agg.T)) log ZT, 8/2). Algorithm 6 guarantees that with probability at least 1 8,
Gry-good arm is returned, where
max w - w (A(Zn,)) 1001l Lo,,o 10,00 EW
(18)
Also, the algorithm terminates in at most
o log (llog(ZZ,)) OT
p(E,7)
+ + c(1 +cl L. log log(1/5) miin (A(E.T)
V cr(w)
T
samples, where hides Oogarithmiccaatonn of A and I and 7.
ww" w/ 3 A( 1 p(),7) wWW)( fw" w. 0)2 g
and
||l - w/13 A(A,T)
(7()) = min AEA(2) weW (wr)
max
(wo w. 0)2 V V
Proof. The proof can be divided into four steps:
The best arm w is never eliminated.
At the end of stage k, any suboptimal arm w that satisfies (0, w- - -w) 2 2Cr + 2y is
eliminated.
The stopping condition is met in finite time.
When the stopping condition is met, there only -o-g arms left.
31

---

The upper bound of the sample complexity.
Step 1: The best arm w" is never eliminated.
By the confidence interval in Theorem 2.3, we have, with probability at least 1 and WK.
2 for any k
4k2 4
(0-2eLs w w0
< 1/00 w" AlIN,, (1ww-wllAtz,,,
20 log
Y
v1 w
w" wolwwwwwaaaam 1)
203
log log
VN.
VI ww+ w0 w" [I
20 log
+
2(1 + w)sk P(WW) ((WW) log(
( 4egwi) vr(w)
$ ck +
Define good event ε for each & and w W₁
Ek - ={ 0, w w²) s Sc to.
By the same calculation 15 we claim that with probability at least - 5, the event Ni= new,, Ek, holds. Under the event o Twew, Euck show that the best arm is never eliminated, suffices to show that for any sub-optimal arm WE.
w w", 0.0 0) + (ww -=,
w", p-2SL
=
< w", Op PSLS
0)
< C4 +
Thus the best arm w² never satisfies the elimination condition.
Step 2: At the end of stage k; any suboptimal arm w that satisfies (0, n- - w) 2 2Cr + 27 is eliminated.
To prove this, we show that such arm w must satisfy the elimination condition.
2SLS w' - w) 2 2(0222155 P-2SS w" - w
max W'WW
-(0% 00-28LLS 0, w² w) (0, w= w)
2 CA + 2Cr + 2n
Sb + 7.
Thus the arm is eliminated.
Step 3:
The stopping condition met in finite time.
Given the result in Step and the fact that Çe is an exponentially decreasing sequence, we know that all of the arms w satisfying (0, w² w) > 2y will be eliminated in finite time. This means that only the arms w satisfying (0, w - w) < 2y will remain. We need to show that Vw, w' E
We: (w'' w. 03 201))
< 47 can be achieved in finite time. When Sa S 7. (which will happen in
32

---

finite time),
(w'' w, 0g p-2LL
10 1 + w² w", 0p-28LL)
w w, Op PP22LL ) + ww' w² 00-228L3
10 w, Op P-2SLS - 0 + 0) + (w'' lu' - -w", 0p--8LL - -0+0)
w0 w, O 2S1B - 0) + (w" - w. 0) w'' -w= 0.8 0) + +(u² - w² .0
S( + 7 + 27 + CK +
47
Step 4: When the stopping condition is met, there are only 6y-good arms left.
For any WR, we have
(w0 w. = w" w.
8
+ (w" w. 0p-28L8
7-233
S(k + + 47
-67.
Step 5: The upper bound of the sample complexity.
Define W(2 as the set of 2-y-good arms, i.c., W(27) {we W| w0 (0) S 227]. Then the best arm in the set (())((2) has suboptimality gap min (0, n² w). We de- fine Amin(27) = min W www (0, wt - w) 2y. By the result in Step 2, we know that
after h- == log 44 (2
stages, all of the arms in W(W(2)) are eliminated. De-
fine Sy {w E W/ (w" w. 0) < 4Gx 2y)- Thus with probability at least ō, we have Ne (Wa S.).
The sample complexity of the algorithm is the total number of samples pulled, which is
N
1 p(WW)) log
2(1 w)
6o 2 73
rr(w)
1
4k-|
3(1 + w)
22h 1/2
p(W))L. log
vr(w)
8
3(1 + ww)
22h
T/2
1 p(Ss)lw log log
4k2
vr(w)
(19)
Note that the factor of minxe max || w 1'112 has the underlying true I in it, while the algorithm uses the plugged-in f. We need to relate p(Se)
minxea(2) max 1/w - w/1l2 o By Lemma I.9 and defining (5())) as the optimal
design for St, i.c.
\ arg min max |w w/ w1113 11
xEA(Z) w.w'ES.
33

---

Define X/4 = 1/2 + 225 we have
|| - w' u F)
max w,w'
min max AEA(Z) u. EW2
||W w' w'll A(A.F))
S min
max
||00 w' 1|(
(Z) t0 ES
3 31Bw w 12 + max
-P-TTP-T)- - w²)l A(--)) -
< min (EA(2) E.
max
w.w'ES,
< max 3/|W w w0 11 A(x +2 max w,w'ES ES
-T-T-f- (w w') 1|3
W.
A(X
160 (ZT, (Tr,
< max w. E.
6| w/ l 11((2..)=-
max ES
|| w (A(e.T) -7 (20)
min (A(
where the last inequality is due
| w'll
w'll
S | w/ l (EAA++
=110: |/0 w/ l' (+(a..)))
-2 w w'll 11
as well as, by Lemma J.11 when T
log( Zr. Zr, 8/2), we have, with probability at least
aman (A(E.T))
1 - -/22, we have
(r -f - - -w') 12 1(X
max w,w ESa
,o,,og| Zr, 5/2)
max ||u0 w TAAE. 'T
mmin
(A(X,, 1'))
1o (ZT (02)
|W - w 1 A((..r)-1 T
max
min
(A(a2i (1 a)g,T)
u. ES₁
80 1og ZT, 5/2)
|| w/ 1
max
m ( (A(g.T))
w.w ESt
We can lower bound p² p²(7) by
| - w1l2 -
(7) = min max AEA(Z) (w") (w" w, w,0)2 V 72
||0" - -w113 1112(22.))
max (2A(2) h DESAY(W'
min
max
(w* w. 03,2 V V22
||00 w/ 1
min h XEA(2)
max
( (w* w. 0)2 V?
2 A
min
max
-w112
16k
72
XEA(Z) wES+((
1
1
22k
min xEA(2)
max || w/ w''1aaa..))11 1.
(21)
64k
72
m.
Given
19
20
and 21
we have
o (r, plE,7)
No c - w)J (1/0)p (1) + c(1 + 2)2 L, log(1/8)
+ cr(w),
mmin (A(E,T)) T
where c hides logarithmic factors of A and [W] and 7.
34

---

J Proofs of sample complexity with unknown r
Algorithm 7 Optimal design with unknown I'
Input 2, 2,W, Lu 2 o. Ly 2 o W, Tmin Amin (T), XB, No
Initialize: h = 1, W/ = W. -11G
Define f(w, w/, ;) == ||w0 w/ "' PEce A M ==
32L
V V1, òz ==
Juin anin (A(Ag.13)
while [ do
Fh = I' - est tisttotorrioo WWi k-1 Sc, o, XE, M, ME,,,, kn)
Step I: update î
0F 7-2LL 0 - estimator We: d. Cky Tky Tuus
Step 2: update 0
Wk+1 Wal w We Bw' S., ( (w' - -w, O22S5 2SLS
St }
D Step elimination
+ k 5$ h
end while
Output: We
The algorithms of r estimator and 0 eatimator present below slightly different from the one in the main text. In the main text, we omit the phase index k in the algorithm for simplicity.
Algorithm 8 estimator
Input We. Ve. 8, l λE M, Lyj
Define Stop(W, 2,1, == max - w' - |Z12
L, (Z,6
Initialize f = 1, Nx.0.0 =
doubling trick initialization
if k then
while e = 1 or Stop Wk. Zk.o,e, Tx. 6n.c) > 1 do
get 2 2 (r(w)) 2 samples denoted as ZZ..uee Xk.o.e Yk,0,} per design Ag b via ROUND
Update F& by OLS Zk,,0 Nk.o l 1+ end while
else
A = arg minxee(2)) max f(w, w', 1x-1,
N' = AgdM1n (1 (1+ (d + 1.2) + 2M 2M2gdM 8M In
226d 8
V r(w)
while é = 1 or Stop Wn, Zz. 0 U IR I' Sk.e) > Co do
N N7
doubling trick update via ROUND
get N.. samples per d denoted as {ZK,1 Xx,1, YE.Le
NR.0.E = 2gdM In (M NR. + L2)) + 4M In
2.0d 0z,1
v Vr(w) 2
get (Na,0.E - Nk.0.e11) samples per dØ augmented to { 1 Xx and get
Zk.o.e; X
Update A& by OLS on { ZZ,, Za,,ee Xx Xx1e). 1+1+1 end while
end
Output:
35

---

Algorithm 9 estimator
Input We, 6, Sk. P W, Lugh k
X arg mi)) w'w (w, w', .x. 2)
p(W{)) mi))ea(2) max flu, w' Tx, 2)
Nx. = 2(1 Wh p(W)) log
V Vr(w)
get Ne. samples per design d denoted { Xk.2 V4.2] update 0p-2LL - (TT Zx, - 2,,22,2 V22
via ROUND
I..
Output: 07-25LS
Lemma J.1. Algorithm 3 and NK,,, Nk.0.t guarantees three properties:
Property NK.1,e 2 NE,0.e-
Property 2: 1/2 (Nu.o No.1.e) S NK.0,-1 N1,1,8-1-
Property 3:
N1.1
M In(dM).
8d
N 1-
+16 2.0d422
Proof. For Property 1, recall that Nk.o,e and NK.1, are defined as
2gdMIn In M (a((+ Nx.1 1.,)
2.6a
Nk
4M In
vr(w)
ôx.e
and
Nk.1,
2 AgdM In (1+2M
2M dd I?)) 2M2gdM)
8MM
2.6
r((w)
8
prove the result by induction. For the result for l = 1, note that NK. is the form Ng, 2a + 26 In(1 11 2c 2bd) and Na.o,1 is of the form Nx.0,1 + b Illnc + dr), where
4M
2.6" de,1
2gdM
== M(d+ + 1.2)
d= M
r= N
By the contraposition of Lemma K.5 we have
2a 26 In
2c 2bd)
a bln(c dr).
Thus we have NE.1,11 > NA.0111 Now we assume the result holds for ic.. No.1 2 Nk and prove that it holds for & + 1. We have
No.1.+1 2N 2 2Nr.0.
suffices to prove that
2Nx.0.2 2 NN.0411-
36

---

We have
2Nx,0.8
=2 2gdMinn in (M (M((+ NE.. + 12)) + 4M
2.6d
V Vr(w)
in (MP(a+ Ne,, + 12) 12)²) + 8M In
2-6
(D((+NNe.e
Vr(w)
8k,1
2gddM in Codd+Na.,0 + 1.) 13)² + 8M
2-6d
In
+ +2In(e)
v vr(w)
ōz,1
inddM'n ( Ne)e++))) + 4M
NeLe+
In
2.6d
+ 21n +1) v Vr(w)
8x,1
(2ln22 (n(e+1) for f 2)
Mn
M (d 2N + 1?))
add+2Neue
+ +4Mh In
(e+
v Vr(w)
6k
=Ns,0,e+1-
For Property 2, it suffices to prove that
2 No.u. S Nk.0,e-1-
This is equivalent to prove that
2 (a blu(ccl S a bln(c dr).
We have
(a + bln(c + 2dr)) S a + blu(c + dr)
bll(c + 2dr) s 50 + bln(c dr)
1
bln (V++ 2dr
s 2
+ bln(c + dr)
vc+ 2dr S 4 dr
c 2dr < 2 + 2edr + d2,2
dr(dr + 2c - 2) + c² 2 O.
The last inequality holds because M > For Property 3, we have,
4dM In 1 2M (d (3) + 2MdMM
+ 8M In
2.0*k²
8d1n (1+ N + 161m
2.60122
4dM In
(1+ 2M (d + L2) + 2MdM)
8M In
2.0012
8d
+ Ne.Lul2 ) + 16 2.0012
8d (1
Ne.
+ In
2.0:/
0
M
(1 + 2M (d + 12) 2MdM
M
+
(loosely apply N 2 dM)
2l (1 + ML2)
2
IndMM...
37

---

Theorem J.2. Algorithm 3 guaranteess that with probability at least 6, the best arm is returned, and the algorithm terminates in at most
(1 + w) ((Ln)oo(1/0) L,,101 log (1161) 9- (d+ (L, 101120000000000 + m))
pulls, ignoring both of the additive and multiplicatiie logarithms of A, [W], H", Po. M, where
I|2 w | A, 2=
0
min XEA(2) wEW
mBx
(w- w, 0)2
and
||0" -wll ( an
P0
max WWW\f
and
32
M
V1.
min minn (A()E,1))
2
Note that po does not get hurt by (we w. 0). It comes from the fact that in the first phase, initialize that algorithm with E-optimal design.
Proof. Part 1: correctness of the algorithm
The idea of the proof is similar to the proof of Theorem 3.1
Recall that the confidence interval of P-2SLS can be break down into two terms (2
T2
T2
0p-28Ls - -0,
Σ
TP
) uy + ((--) ro,
21,
21, w
1=1
Given F, for a w E W, with probability at least 1 - the first term satisfies
4
Σ
21, 2 TT
#1, po ||ull .D- P--1 20 log
t=1
For any w E W, with probability at least - 4 Z. the second term satisfies
(f-l-r-)
ro, w
S
oolog (T, 5//4)
Note that by Lemma G.4 the above inequality holds for all w E W, and the RHS is essentially a result of
v 1/2 op
In the vanilla form of the confidence of P-2SLS, can define good events
for the first term, for any w E W,
Σ 21, 21. T
214 w yo S || 1y-1 2og (166211118)
for the second term, |-1122
< oo Zr, 5/4).
op
38

---

For our algorithm design, since we use the doubling trick for the first sub-phase, we need to define the good event for the first sub-phase the samples from each doubling trick iteration satisfies the self-normalized concentration inequality of Lemma G.4
We define the good event for l-th doubling trick iteration in the first sub-phase of phase as
E
{
|
2
2 op s ooij Zn.b 4k2 1)3
8
where ZR.e- Zu,o,e U I.R. Vk.e Z and Sk. is stacked noise matrix during collecting samples Zu per the model X = 'T" + By union bound, we have
P
nn
(Eke)) S 8/22.
k=1
k=
t=1
For the second sub-phase in phase ki we define the good event for the second sub-phase in phase and W as
Na.a
N
Ek
21,
|1
wwlla((aa...)- / 20 log (66(16)2))100)
By union bound, we have
( k,
$ 8/22.
k
1=1 WEW,
k= wEW
Under the good event (n Eke) (N 1 8, for all and w E W,
k Nwews 22.0) we have with probability at least
(0p_ P-2SL
0, w w²) S Sr.
The rest of proof is same as the proof of Theorem 3.1 Part 2: sample complexity of algorithm
Sample complexity for first sub-phase
Recall that A = arg maxxca(2)) Omin Esez )=zz T is the E-optimal design to maximize the minimum singular value of E35z Agaz and Ko = maxa min E AgazT) is the maximum minimum singular value of Σ Eeez A= At the beginning of first sub-phase in phase k, the algorithm first samples Nx,0,0 arms according to Ag.
Before we proceed to the main proof of the sample complexity, we first address minor technique issue avoid cumbersomeness, For the logarithmic term that appears in the algorithm and confidence interval.
2TL2
2-6d
Tog Zr, 5) == 8dIn
+ 16
log
d(2 A miin (Z, Zrl)
2 A T (2,7 ZT)
when 2 amin (V) 2, it is equivalent
TT2
2.6d
log (T, 8d 1+
+ 16
8
Our algorithm design guarantees that 2 A mmn (V) 2 is always true whenever we need to use the logarithmic term log(Zr,6 8). given that the samples of our interest always includes the E-optimal
39

---

design samples uu, and the number of samples from the E-optimal design Zk,0.e| is always larger than 2. So for the remaining part of the proof, we will use log(NN 6) instead of log(Zr, 6). Zr,
Denote the samples of E-optimal design that mixed into the samples from E-th doubling trick iteration in the first sub-phase of phase l: as Zr, and Za,0.e Nk.0.e. By Lemma J.3 our choice of Nk.0.
64gdož Omin (A(AE.1))
32go
(d+ N 1:)
12890
2-6
Nk.0,e
In
+
In min (A(AE,1))
min (A()E,1) 1"))
8
is a sufficient condition to guarantee
log Nu,o.e + No,1,, V Vr(w).
Nk.o,e
(22)
Omin (A()E,
Multiply both sides of [22 by No..NNN and we have
Nk.o.t
Ago (No.0, + No.L,,ōudd Vr(w)
Nu.o Nu.oe- NN,1E Nk.0.
Nv.o.t N
Jmin (((x,T))
By Property of Lemma J.1 we have are == No..
No..
1/2, then
Agožlog( (Nu,,, + N,,1,,,0u,))
No + N4.1 2 ank
v vr(w)
mmin (A(AE,T)
Agot)og( (No,0 + Nk.1,0
V r(w)
Jmin (A(ar,edE.T)
Morflog(NN.o.) + Ne.1,e,
V Vr(w).
(23)
Omin AA(aL,dE + (1 (1- (x,,,,))d...))
These condition on NE.,, and Ng.0. + NE.1, are needed for the proof.
Denote the total number of doubling trick iterations Lg for phase k. In the of T the samples from the first doubling trick iteration satisfies stopping condition of the first sub-phase already, and the algorithm will not enter the second doubling trick iteration. Thus the total number of samples for the first sub-phase is
No.0,1 + NE.1, 22Nx,1.1
(Property 1 of Lemma I.1
<8gdMIn (1+2M d 12)) + 2M2gdM + 16M In
2-6d
v Vr(w).
ŌR.1
In the case of La 1, for é {1,... Lx). denote I as the estimate of I at the end of the f-th doubling trick iteration. With these notations, we have
At the end of La -h doubling trick iteration, the stopping condition is satisfied, i.c..
|| --wwli w/'l 1 UZh.. F26 fle
log 1og (Nv.o,L, + Nk, Sk,La) S c.
max w.w
(24)
We short log(NN. + Nk, Sp.e) logk,e
the end of (L+ - 1) doubling trick iteration, the stopping condition not satisfied, i.c.,
w w w/ll2 ( u. UZz 110 log,, -1 > C2.
max w. EW,
(25)
40

---

Denote EL2 as the empirical distribution of Zk U LR Then above two conditions imply that the number of samples for Lg-th and (Lx- 1) doubling trick iterations respectively satisfy
1o C
||w w/ wollAtee, (AAELL FaN)-1
N. + Nk 2
max w. w,w'EWw
(26)
and
10112
LOBR,L 22
L1 + L1-1
max w.w'EW
|| w' |AASE 1.f40-1--1- (27)
Note that by Property 2 of Lemma
2 NN + NN,,, S N1.0,12-1 + N.
Thus
2110 Loggkk. Lx-1
NE. + NL,1L <
max w.w E.W
|| - w' LACELE 1
(28)
For any E {l...., Lij. by Lemma J.7 the factor max 1/w - will (a can be upper
bounded by
||w - w' 1 (
max W.W'EW
|w w/ 11 |1ArE 1)-1 +
- (f 1)- (ww) |
max w.W'EW
max
w. W.W.
(E, T)
-T-T- (fe)-T) [) w/ 1//
[w- w/ ||A(E +2
max w. w.w'EW:
max w W.W'EW
( T
+
max 20, EWW
- - (f
(T w')
(29)
[, ErazT)
We will upper bound the three terms in the RHS of (29 separately.
For the first term, by Lemma J.6
max N0 EW,
||w w/ " ( S
max
|I w/'l w'll31
(30)
where d is the optimal design for W/ in the first sub-phase of phase k (based on the last doubling trick iteration), i.e.,
d arg min max ||10 - w' 11 14 AEA(Z) w, EW;
Then for any X,
[w w/l 2 A(2,, 116-13-1
max
w,we EW
[w - woll 1 [1( +2
- - -( (w w') A(1.1)
<3 max EW
max w. w.w'eW.
(Lemma 1.7
b
| - w/'l w ( +2
| (ora--))T((us- w²) |
- (Pbx-1)
max w,ww EW/
max
w. EW:
(E. X
(w - w'll w 11
|T-- - (f -T -owwww)) w/)) 1|
max 10.0 EW
+ 2
max ww
(I. ((sT)-1
(31)
where for (bi), we plug in N²== = atAE (1- with at S 1/2 will be defined later and A₁. is the optimal design for Wj given I", i.e.,
X arg min max || w/ 1 1
AEA(Z) w. WWW
41

---

b2 is due to the fact that og - 1/2. For the second term in the RHS of (31), given the condition
i.e.,
1gL,,logk 1,14
11 + N
Jmin (A(ELe-1)
by Lemma J.11 we have,
(T- (FlZ-1)- w²) w/|l ( ; \
21,1108k-1,1es
Mmin (A(X,, 11-110, + NK-111,0-11 100 w'll 1 A 17-
21, log 1,6x1
N
$ 11- mla (A(X,.T))
I w/ dellA
N
2L logh
N8-1.0.2-11
1 - w/ 1 ((E
11,, min AA
2I, logh
|w- - w' I (1(
(set o = -0k-1)
1.0 mmin (A (A(AETT)
| w/ "'((A 1)
4g
bg
||00 w'
|
(32)
Ag
where for (b1). we use the condition into (3T. we have
22 on N,, and (b2) is due to Lemma J.S Plug
32
max 1|1e w/l 11 F 1)-1
I 6 max
w - 12 A
max w.w' eW:
||
w
AlAcEL, F' 1)-1"
w.w' E.W
w.w' E
(33)
Plug (33 into 30
we have the first term in the RHS of 29 be upper bounded by
w w 10'133
max EWW
A (4R-1)
12
24
max
||w w/
A(A
max
||W
w/1
l Frx 1)-1
w.
9
w.w'E w.w'EW
< 24 max W,w'EWW
[wwwwll w Tl
+
12
G-1
(Ns-1,0, + NE-111L--1): (34)
9 |10|
1,
where for the last inequality we use the fact that the stopping condition satisfied at the end of (h doubling trick iteration for phase k - per 266
For the second term in the RHS of 29). by Lemma J.10 when
when the condition 23 is satisfied, i.c..
4g IOBR.E mmin (A(Ee, r))
No.0. Ne.1
we have
max w.we EWW |1-T- - ((') w²) 2
||W - w' w/ A(
max
(I. Se20 )-1
w.to W.W
|/ w/ 2
max w. W.W
(35)
where the last inequality is due to Lemma J.5
42

---

For the third term in the RHS of (29 by Lemma J.11 when
when the condition
23 is satisfied, i.e.,
4gg,, - 1,4
1,0 + NR- 1,1,
Jmin (A(ELr-11
have
- -PLAa-1)- ww) 1|
max we E\W
(En (E, (12ST)=
2o, 1,1x-1 (A(Ee, I)) NK- 1,-,,, - www W.W
||00 w/ I A
max
Mmin
2Lyploga-1,44
|| w/ W pL--1)
max w.wnn
Mmin (A(asdE,1)) NK-100 N 11-1,1,1-1
N NE,LE
210gk-1,Le-1 (NK-110, + Nk-1,1,
G
NE..
11-100 + NN--11,L1- Mmi (A()F:T))
1101/1081-1.0 1,
NE. + NE.2
2
22-1
NK.OE.
mmin (A(AE, D))
11012
NE. Ne.1,
22-1
(36)
log,,
|1011
where (bi) is due to (26). (b2) is due to
22
Plug
34
35
and
36
into
29
we have
||u- w' 2 F9)-1
max w.w'EW,
72 max 10,00 W,
|w w/ w0'l3 (1A
36
(N + NK-1,1,E0-1)
9
1101__,,logA_11110
12 max ||w w w al
Nk.0.et1 + NE.11111
G2-1
+
(37)
w.w EW
I,gloga,
|1012
With l La I and the fact that g > 24 whose exact value will be set later, we can rearrange (37 as
||l w/ wIll21Ee 1.8-1-1)-1
max 10,00 WWW
<144 max waw EW:
||w w' (
+
72
L
(N + NN-111
g
1011 L log, -
1 NK.LLE NK.1,L Gh-1
(38)
9 L,glgg,Au-1
1001
Note that the LHS of above can be lower bounded by (28)
(Na.0.14 + N..
max w.we EW.
||w w/ w'll3 -A
(39)
21 Log
Rearrange the terms in Sa Sk-14/155 1/2, we have
39 and 38 and setting to be larger enough and using the fact that
576 NK.0.L. NN.1.
72 loga, (No- + -N-111
|0
1o
L2
max ||w w w'|l2
( +
2
w0,10
g logg 1,
Note that by definition loga, logg, thus
576
72 logg,Lt (Na-1,0, + -N-1,1,
No.0.Le + No.1 -
|10
Ly
La
max
ww w/ll w'll +
w. EWL
logg- 1,6
43

---

Denote D& == N.. + NE, and divide both sides of above by logs, I. we have
Dx
S
576
1012T
max w, eW,
I| w'
wl'l (A
72 DE-1
Lo
ck
logk:
1,1
In the case of Lμ L, by Property of Lemma J.I we have
Dk
NR.
MIn(dM).
8d [ No.1112 12 + 16 In
2-64k
d
Thereby have
576 { Min(aN),
DE S max
1111211,
max 1|m- w' ('1A((A.TT)
72
Dk-1
2
+
logx,12 Lx
w,w eW
9
logg- 1,,0k-1
(40)
Taking a summation over on both sides of 40 have
D&
D1
DR
(41)
Log
log1.
loga,Ta Tuk
2=2
K
1og1.L1
D1
max
576 M In(dM),
Ch
101
max u. EWW
||
w w0ll 1'
+
72
logs 1.bb-1
D
2=
(42)
D1
576
72
DK-1
M (n(dM) +
||0|
Ln
max
||0- w/ A((g).))
1081,L1
C%
an,00 EW,
logk 1,-6-1
k=
(43)
K
K"
D1
MIndMM)
+
576
1101
Ln
max w.w EW.
|/ - w 1AAAA
+
72
Dk-1
log1.
logg 1,Tx
k=2
k=
(44)
Thus by setting g 72 x 2 and rearranging the terms, we have
Dj
2D1
576 Σ
+2 Σ M (dM) +
1 Ln
||
w ('llAigg
max u0 EWW
Logg,Lt
10g1,L1
(45)
For D,, which corresponds to the first sub-phase where we use E-optimal design with doubling trick, we have the stopping condition,
||u- - w BAlziaz, p'1) L, S St.
max EWi
This implies that when the stopping condition is met
NI,, 2
|| - w w'll2 I1 P(1) 1-
(46)
SP
and EW,
and
NL
2110112
10
max EW;
|| w will331e -1---
(47)
7
44

---

Since E-optimal design for the first phase, the factor of ||0 w w -1 can be upper bounded by
| w' w
-16
S3 [ w/ll - -(, + +2 (1 hoo-ww)li (1-37
(Lemma J.7
<3/l w/ |1 A(A + +2 - w''l'(A
(Lemma 0.10
<6 w w/|l 1 A(AA,T)--"
(48)
Plug 48 into 447 and use the fact that 2NV1,0,L1-1 N1,0,L1, = have
N1,0, S
max u. WWW
J w [AiAnn S 24,101
max u.ar WW
| - w 2'llA(Ae.TT
(49)
Thus we have,
D
2N
< 18
|| - w'l --'ll = MI-
max w,w'EM EWEW
1og1,
log
By the same calculation as and
19 we have
K'
|00|
2 Tm
max W.
|| w - S 1. =: P2:
where is absolute constant. Next we lower bound the left hand side of 45 To do this, first upper bound Lo as
D&L2
2-
loga.t
Sd In
1 d
+ 161n
8
1+ D&L2 d
2.
<8d ln
+ 32 (L,) 166n
Dz
Dx
k.
<8d hn
1 d
+ 32 In
loga
16
5
D&L2 1
k2
<32dIn
16
(50)
5
where the inequality above uses the fact that Lç is the index of the last doubling trick iteration for phase k. by the design of the doubling trick, we have Lt S logz
Da
D
DR
8d 1 Dul3
+ 16
(26
5
Dr
(due to 50
k= 32d In
(1 DeL?
+ 161n
2-B
d
K*
Dp
DK. DeL?
2266k
k=1 32d In
1
16
K*
D
32d
1 K*
D&
+ 161n
2.64
45

---

Denote P3 = KM In(dM), looking back at (44 we have
K²
Ei= D
2-6 K22 2
DE
S
32d1n
1+
161n
(01 (0) + +2 ps).
d
k=1
By Lemma
K.5
we have
K
2.6
2L
Σ k=1
Dj - 32 + p2 + ps) In
+ 64d(pi + P + pz) 3 (pi + + + p3)
d
(51)
Sample complexity for second sub-phase
The design for the second sub-phase of phase k is based on 14x the estimate of at the end of Ly-th doubling trick iteration in the first sub-phase of phase k
d arg min
max Iw w w'll 1 AEA(Z) w.W'EW
Then for any X, by Lemma 1.7 we have
w w/))
w'll Fl), )
max EW
(r-T (f wi W
||0 w/ 11((A.9-11 +
max WAN EW2
max w. NW''
We plug in X = a AE + (1 (1- af with a S 1/2 will be defined later and A is the optimal design for Wk.
max w.w EW2
w
w/ll wl'1 1l F'a)-
|| w/ 1 I1
|[-- - -(Flk)-T) - -w'') ||
<3
max W. w.w W.W.
ATA
+2
max
w. w.we EWW,
(E, x===T)-
<6 max W.W
||
w' w A
max +2
(T-T (f [w ww))
?
(E. ((==T)=-11 (52)
EW;
where the last inequality is due to the fact that or S 1/2.. For the second term in the RHS of above, by Lemma I.11 we have,
(r-T-(fuu) (f-2) w') ? (E. X(=I))
(E.
40y1ogg.
1110 w 1110-w1122zaazz A(Z
(A(X)
Mmin
4Lylogg
NN.
|| w w (la(EL) D)
NK.0,Ly Jmin (A(X,, NK NK.
4ly
No
||u w w'll'a ('l
NE.O.L Mmin (A(aīdE,T)) NE.0, + NR
NR.0.La amin (A()E; r)) || w/ 1 "A
(set o = =..)
| - w/ w (l
by 1
11 w/ w/ llACELL f2e)--1
(53)
46

---

4gl,,,o8n..y and (bg) is due Lemma J.5 Plug 53 into 52
awin (A(AE.T))) where for (b1), we have N2
have ||00 w'll W,
2 max
max
26 max ue,a EW,
|w- w ('AlA(AZ-))>
| w lasasss, 14R)-1
9 w. EW,
<6
max u, WWW
|w w w (112(1221)--
2
(Nu,0,ta + N..1.
9 |101 I, Logg.
(54)
where the last inequality is due to (26) According the algorithm design, the number of samples in the second sub-hhase of phase k is defined as
4h2 4h21w))
Nx.2 = 2(1 w) P(WE) ((W))L log
V Vr(w),
with p(Wa)) = minxes(2) max wow.llww- w/l1 A(2,F4a)-1"
Then we have, by setting g 2 4,
4
N & (1 + W Lu max || w w' IlAAA. log
+ (1+ ()+ N,,,,,.))
N.w'EW.
5
where ' hides logarithmic factors of [W] for the second term and constants for simplicity. Plug we can always set L, = 2[1 01 1).
(54 into the above incquality. Also note that by Lemma 2.1
Thus,
4k2|W)
Σ NR. (1 +w)
Σ
Sk
Ly
max
|| - wlll3 ('11((( log
+ (1 + w
Σ (Ne,0,L. NKK,,Le)
w,w EW2
8
WI
K
( +W) log
+ (1+ Σ
(Nv.0.tx + Nx.1,te).
This essentially means that the sample complexity for the second sub sub-phase Σ Ne.2 be upper bounded by summation of the sample complexity we pay for Algorithm | and the sample complexity of the first sub sub-phase K (Nv.0,Le LNN,1,L2). Combine (51 and 55 we conclude the result.
Lemma J.3. Denote
No.02
2.6d
log(N (No,, 0k.0) 8dln 1+
+ 16
d
A sufficient condition for
goglog ( (Nu,0. + Nk.e) vr(w).
Nk.
(55)
Jmin (A(AE,1))
to hold is
16gdo
8g Omin (A(Ag,
(d+ NR, +1²)+
32go
2-6d
Nk.o.t
In
In
Omin (A(AE:T))
mmin (A(AE, I')
8
Proof. Given
(
1+ (Nu.ee + N
2.6d
oN + NK.1, 6x.e) = 8d In
+ 16 In
d
By Lemma [4 for the formula
X > Al BX) +C
we have
47

---

8 Ouin A(AE:)))
1.2
d
169a
2.6
C
In
miiu (A(Ag.T)
1= 1oL
Thus a sufficient condition for the inequality to hold is
16gdo 1
S
12
32g0
2.6
Nk,0,t2
In
1
) +
+
In
Omin (A(XE, r))
Amin (A()E:T)
d
min (A()E: r))
16gdo
8go
32g0 ?
2.6d
7
In
( Nu. 12)
1)
In
Mmin (A()g,
Min (A(AE.T))
min
(A(AE,
6
Lemma J.4. Let X 2 1, 2 0, then sufficient condition for X 2 Aln AD BX) C is
X 2 2AIn(AD + AB) 2C..
Proof. The proof is motivated by Gales et al. 16 Let (0, then
X 2 In (D + BX) +C
[X
A A xx x
*x 2 Aln
Aln
+
fX
XX> A
-1)
+ Alm
f { (x+B +C
(since In(x) S x 1)
A (2
eX(1 f) Aln
2f x B) +C
4 T-
1
Aln
25 x +
A D
T-
Set / = 1/2 and by the fact X > 1, we have
X 2AIn(AD AB) 2C.
Lemma J.5. Suppose that we have a data set {Zr, XT). Denote the empirical distribution of Zz as The number of samples satisfies
80 min (A(E.T)
T
log LI, V(w)..
i is the OLS estimate of based on (Zr, Xr). Then
| < 61]w|| -
Proof. By Lemma J.7 have
|| <3||w/ 1 F + +2
1(E,))-
1 ( + [1
<31|001
48

---

where the last inequality is due to Lemma 0.10 with 2. Rearranging the terms, we have
|| S A(
Lemma J.6. Suppose that we use ROUND to sample No arms according to Xg denoted as Zo. and Ni arms according to A denoted as Z,, with Ni 2 No. Denote the empirical distribution of all the collected samples as E, then
[ S 4 4|1
Proof. Denote the empirical distribution of Zo as Eo. and the empirical distribution of Zi as E1, then have
-1
|
2
A(Z.UZZ,))
=
Σ r
TTzzTT TT
ZEZuUZ
Σ
T 22 r Σ
P 22 T
w
w
2EZ1
-1
No Σ
ET,O 22 T N1 Σ
E 2z
TI
w
ZE2
zEZ
No + N1 w T
1
No Σs,or
22 T
N₂
ET.I 22 TT
No N
No Ni
#E2
#E2
-1
1
Ni
22
Σ
2T
w
Ny + N1
No + N1
SEZ
2
w T
Σ TT 22 TT
(N1 2 No)
No + N1
8EZ
-1
4
Σ TTr 22 T
w
w
No + N
FEZ
4
No + N
The result follows by noting that
| 2 AIZZUUZZZ..)-
1 No + N1
|
Lemma J.7. Suppose that we have an estimate T that is invertible, for any x E Rdd and covariance matrix V. we have
| U S 3| + -
(56)
Proof. Suppose we have an estimate r. Then,
|| ( |el| + | ||
49

---

Note that
= - -
Thus,
|| (ry--
+ - -- )x
(1-1- ---))-----
- |
| ||||||||||- ||0 [1- - - )x3
+
(I-T -
r- )zz
V-1 (
V-1
< | + 2 | + p-
-
1o
+ 2
1
(r- - D0)
2
V-1 + 1
+2
V-1
(AM-GM)
This implies that
/ s / + +2 -
F-T)x -
V-1
Lemma J.8. Suppose Ny argmin f(A) and >9 arg g(A) and f(2) & g(A) + h(A), then
f(As) ((>g) + h(2g).
Proof.
f(A)) S min(((()nn))n)))))()))( + n(2)) S { h(22).
Lemma J.9. Define Xr and Nz
x= arg min max
w|w w adl12(20.11
AEA(Z) w.w EW
and
A arg min max || w' 11.x.. (EA(Z) w. ew
as the optimal design regarding I and that regarding its estimate I' respectively. Then, have
max | w' I 1 S max 3|1u- w' 11 w,10' EWW
2
- F- F-T)(w w/) 12 [I, --1
+ max
wow' EW
a, w.w'EW"
Proof. By Lemma J.7 for any w, w' W and \ E Az.
| ||- w/ 1i-w'l2aa..m 1 S 3||w w w'l -T-T-- wd)l
[, Neaa \ --11
Thus
2 - w/) 1
max [ w A
5 max www ew
3111- w 1'A + on an EW
max
By Lemma J.8
w w/ 2
3/1u w' 12 1
TT - F w²) w²)l 12
max W.
& max W. EW
+ max w.w ew
[, N5x0
50

---

Lemma J.10. Suppose that we have I that is an OLS estimate from an offtine dataset ( Xx,, 3 collected ton-adaptively through a fixed design X and the efficient rounding procedure ROUND. Let V = 7,, 7., Then, for any E IRe and g 2 1, we have, with probability 5,
Ja 2 [T- f- Ja)
V S -111lla2z .1)
when
4go
T 2
log Zr, 6) V 2p.
(57)
min (A(A,1))
where p the cardinality of support of
Proof. We first show that
(T - r- )x
p- T S Zm v (T -- 2
(Lemma J.12
11
([Aa1|² || Ar ?
V r- ST Zn, V
[T V-1 5)
( + v-- -1, 9) T 2
V
21/2
(|Ar|| - || |>|||
ST ZT,
(T' V-1 -,, s) ST,,)))Tz(]
<IABB op S || Bllpp)
1/2 27, 5
V- 1/2 r + -7,
(IIAT A All up = ||Al
1-1 1 V 1-2 (V-12T 5) T (r++ - -T
1/2 1/11//2/1 S
(Lemma J.13 (A + B) A- BB -BBAB 'BA'1)
(1V- V-1// - + V-1/2p-T (v-1 (I+ (I+V-12J,,) -2,55) 2
12)
1/2 27, S
op
-T 2
We can upper bound the the term V 1/2 (v-Iz7,)) (
x
20 by
2
noticing that it appears in both of a1; a2 above. Thus we have the inequality
1/-1/27,, s $1
(11--1er Txr
2
2
T
V- 1/2 2,,
+
By rearranging the terms, we have
27- <
1/2
5
V
1/2
T
T,
--1----
V 1-1/22 5
0p
op
op
op
By Lemma G.4
with probability - 5, we have
12 op
< Eolog(ZTT,
Thus, with probability - 8, we have
,g LT, /001lvV 111121
27
2o ZT, 8)
2
51

---

To further
upper bound 21 we first find a sufficient condition on Ti such that
--V
op 1p og ZT, 8) S 2g 2 1. By Lemma
lg
J.14 when Ti 2 2p,
20
lo ZT, 0)
log(Zr,, ZT. 0).
Tiomin
Exeg A=[T==TT)
1 To upper bound the right hand side by
we need
2n"
4go 1
T
logí log(Zz;,1) .).
(58)
22 TT 6 min Ezez A.
With this condition (58). we have with probability
1, 6,
27 <
10 Zr; 6) 1-11/pp-1
[
V -
-
of llog( ZT,
op
1
5
1/2
1
2g
2g
V 1/-1/22-11
(59)
Lemma J.11. Suppose that we have I that is an OLS estimate from an offline dataset {ZT,, XT,) collected non-adaptively through fixed design X and the efficient rounding procedure ROUND. Let V be any positive definite matrix. Then, for any Rdd, have, with probability 1 1-66 5.
[T- - f Joo
< 2
log 5) 51 .I) 1.
5)1
V-1
when
40
T
log (T,, 5) V 2p.
0 min
(A(A,1")
where p is the cardinality of support of X.
Proof.
-T-T- -f-
p- T S Zm [[++-=1,,T)-- v-1
(Lemma J.12
V 1 1 TT 2, V 1 (T' V-1 5) S)
([Ax1] || | Ar ?
V ( + v- 9) TT 2
1/ ST 2T,
-x0 x112 ( + -- 5)
(|Ar|l < || |
1 11 2 ST ZT,
(IABI - || B Bl
1/2 12 5
V- 1/2 ( + -2,
-T
(IIA A All op = 1111
0P
1-2 1 V 1/2 (v- ZT, T (r+V~ -T
1/2 1/2 s
(Lemma J.13
(A + B) -1 A-1 (A+ -A+
(2)
1/2 27, s
1/2 TT + V 11 (V--((((zTs) ([++--125s)) 2
0p
op
52

---

Given the condition
58
holds, we have with probability 1 1 6,
r
1/2
S
V-1/2T-
-0- V V- 1/2 1-
1012
op
op
2
2
r
V-1/2 /2 7,
8
1/2
op
log Zr, 8) 0)|
where (a1) due to (59 and setting g = 1.
Lemma J.12. For least square estimate that is estimated through design matrix Z and I is invertible, we have
P---r--= = -arr-=-(r-tt -ar----(+-- -00---= V
Proof. Since I is least square estimator, we have
f= V V
By Lemma J.13
we have
f-1 --1-r-1-0 [ V 2T -r-1
=- -- -- -
-1
Lemma J.13. For two invertible matrixes A, B E RRaxd we have
BA- (A+ B) A (A BA
Proof. We have
A-1 = AA- (A++B) 1) A-1
= A +
= A- + (A+ B) (A (A- (A+ B))
A- (A B) BA
Lemma J.14. Suppose that have design matrix Zr that is sampled from distribution X Az. with the efficient rounding procedure ROUND. Let represent the cardinality of support of X. We have, if 2 2p,
(r 2Tl
Tomin EvEz X 22 22
ATTT22
where mmin(-) the smallest singular value of a matrix.
Proof. Suppose that each arm z E Z is sampled t times, the empirical distribution of Zr is E : (4) Thus, we have
Tmin (I' Z ZrI')
mmin T T TT
To Exee (2TT
53

---

By Fiez et al. [15 Proposition 2}, we have
EEr
22 T a Σ 22
:E2
2EZ
where (742p:1) 1] when T 2 2p.
Given the fact that both of Col
and Exez ArT ATT T are positive definite,
we have Omin [Eee E. 22 T2 2
m07 211E2d0 del 22 2xTT2x=1) r) Thus, we have
( 77 ( (+)))
aT EvEzz 2z
op
When T' 2p, we have 2 1/2, which implies the result.
K
Estimating Amin (T)
In this section, we introduce simple adaptive procedure that finds a high probability lower bound on Ymin == Amin (T) that is sufficiently accurate (i.e., within a constant factor of min) ). For simplicity, we assume || < 1, Vt in this section.
Our algorithm leverages confidence bounds adaptively determine how many samples like to take. Let f (Z Z) ZT X be the least square estimate of I after sampling times to obtain 2.)) where Z IR gxd and X Igtxd are the design matrices. Let V == > Re2g We define the lower and upper confidence bound for min as follows:
LCB(() = Amin (f+)
W -V
UCB(() = Amin (f+) +
tt
t
where
1/. min (:): vi)
In (1+ d(2 A minu (V)))
2t
2-6
4
+ 16
log2
8
2A Tuuin (V))
and LCB(O) == oo and UCB(0) == cc.
The following lemma shows that LCB(t) and UCB(t) form a valid anytime confidence bound for Tmin
Lemma K.1. (Correctness the
the confidence bounds)
1 < IP(VI LC)(((I S Vinn UCB(I)
Equipped with the confidence bounds, we are now ready to describe our algorithm for learning Tiin (see Algorithm| TO). Since the tightness of the confidence bounds depends the smallest eigenvalue of V4, it is natural to use the E-optimal design as defined in Section 3.2 Recall that the solution of the E-optimal design is Xlg and Kg the smallest singular value achieved by A We take in rounding procedure for the E-optimal design ROUND & (A, 1) that takes in / samples and design À and outputs integer sample count assignments {Na)ee that we sample according these counts then have
1 Vi) S W
min 7
(60)
After determining the base sample counts (m=)zes by ROUND(A; 1w))), we start doubling the sample size until we satisfy the condition LCB(t) > UCB(()). Note that the sampling scheme in the while loop is designed such that the total number of samples collected up to (and including) j-th iteration is 2 [r(w]] Once the loop stops, we return LCB(t) () as the claimed lower approximation of the 7mm..
Let N,, the total number of samples we used Algorithm TO Then, the next theorem shows that the estimate returned by algorithm is both valid lower bound to x and sufficiently accurate.
54

---

Algorithm 10 Learning Amin (T)
Input: Arm set 2, rounding procedure ROUND for the E-optimal design, rounding accuracy Initialize: j 1, f =
Compute the E-optimal design A for Z. Compute {m= ) by ROUNDE (A [r(w]]).
while (C - UCCB(() do
1. 4- [)-"(((w]]
For each arm 2, sample 2 11 2/-2mm times.
Estimate F using all samples collected so far (total data points)
j 1.
end while Output: LCB(()
Theorem K.2. (Correctness of Algorithm TOl The total number of samples denoted by Now used in
Algorithm 10 satisfies that, with probability at least 1 d,
1min
ICB(NN))
min
We next analyze the sample complexity of the algorithm, which essentially shows the scaling of (oain P2m even if the algorithm does not need knowledge "
Theorem K.3. (Sample complexity of Algorithm TO Then, with w we have, with probability at least 1 8,
N 0 (T(1) + (1imin)
(daii)))""".. (dpooylog((?mmnn)> m + In (n(16)))
We remark that Allen-Zhu et al.
2 provides a rounding procedure with r(E) = O(d/s²).
Proof of Lemmal K.1 Note that = VV--+V 2TS
where Z, S E Rxtd the design matrices with s-th row being 2, and 112 respectively. Using Lemma G.4
have, with probability at least 6,
Vt 1, [.
IVV ZT $
IV, 1/2
lpp
2
IV, 1/2 1/2 TT Slopp
2
1/2 1/2 IT_ s
to (2)
2t
2-6d
8n in 1
+ 16
log
to min
(2)
d(2 A Jmin (V:))
2 7.iini
[Lemma
G.4
1 E
The well-known Weyl's theorem implies that max; (f, - xx - - where x (A) is the k-th largest singular value of the matrix A. Choosing k = d and combining it with the display above conclude the proof.
We assume Vt 2 L,LC)(t) < Yiin < SCC((t) which happens with proba- bility at least 1 Then, it is trivial to see that LCB(Nw) S Yiin
Proof of Theorem K.2
For the other inequality, we the fact that the stopping condition satisfied with N..:
LCB(N.)) UCB(NN)) >
7ina
2
This concludes the proof.
55

---

Proof of Theorem K.3 We assume V 2 1,LCB(t) & (T) - UCB(t), which happens with probability at least 5. In this proof, we let Mmin := Amin (I N.) and Ymin := Amin (I') for brevity,
N [r(1]], then there is nothing to prove. Otherwise, the loop in the algorithm was iterated more than once. Then, since the stopping condition was satisfied with Nw. we have that in the previous iteration where t /2
2 the stopping condition was not satisfied. Thus,
2L /2) < UCB(Nw/2)
Using the following two inequalities:
v N
VN /2
2LCB(NN 2 Imnin
2
Ymin 2
Nw /2
Nw
1/Nw1/2
UCB(NNu/22 $ Imin +
S Mmin +2
/2
Nw
have
WNN/2 12
72
Mmin
6
Nw/22
N S
(Tinin )2
On the other hand, with the rounding procedure, we have
2424 N
N
2
N max
((
N
Σ 2t
(1+
2
since w Using this and the fact that Nw 2 d, it is easy to see that there exists an absolute constant сj such that
ON ci dd (d No + kō¹) In ( 2
Then, there exists absolute constant 02 such that
No S (mminn) 222 (d (1+ No + NTO) + In
We have No, on both sides. invoke Lemma K.5 with r = + No to obtain
( 5 )))
N I 1 + 202 202() - d'In (dln(1+ [1+ 2n (1 + cod(nmii)) 2-) + In
Lemma K.4. Let A.T E Baxd where A is symmetric positive semi-defnitte Then,
Omin (rT (TTAT) 2 amin (T)² Tmin 2 (A)
Proof.
(amin (T (TT)))
||| 11- 1pp
||| 11 ||A 11 | - lop
(submultiplicity of the operator norm)
mnin (I') " (A)
Taking the inverse both sides concludes the proof.
56

---

K.1
Proof of Lemma 3.2
Define A - Ae,e, i.. the diagonal matrix with on the diagonal.
Note that
(T
k.j)
min m (TAT -- -ci min max
d
k=
So for an upper bound, we consider À 1/d1,
min max(e
(lee--e) eg) d 1 eg)l
6J
43
The result about p² follows immediately.
When = (1- c)/d1/ + =T, a computation using Sherman-Morrison shows that [ = 1/e (1 -1-8) [l==)/d Thus
min max(e, - T (TAAT)-- - -=)===" min max(e; - (e ce) 1
min max e TA- + ej -
i
2 min max & TA E + ej 1
5- min max e TA TA-Le, e;
= = 22
where the last line follows from the Kiefer- Wolfowitz Theorem 226
K.2 lemma for solving less than In(x)
Lemma K.5. Let a, b, c, d > 0. Then, for every
r bln(c dr)
r 2a 2bIn(1 + 2c + 2bd)
Proof. If dr S e, then
S a +bn((2(22)) aa Sa+bla(f + 2c)
If dr > c. then,
r S a bl((2dr
2d r-
a + bln
-28
26
< <a+b
r
In (4bbd)
(I((x) S x
26
(1
< 2a 2h In
c
< 2a 26 l2bdd)
Either case, we have
5 2a 26 26lnn(1111111111111111111 + 2c) v 26d) s 2a + 26266ln + 2c + 2bd)
Lemma K.6. Let oe, > 0. Then, for any r,
S aln(1 + +r) + = + 2a
In(e 5 a) +
57

---

Proof.
r S aln
r(= + 1) +
<an ln
r
2a
1
+ 1)
+ 3
2a
aa
r
+
In
2al 1
+ ( + B
(Vr,I Sx 2x -1) 1)
20
p
r S 2a In
-a(
( + 11 +
r S 20, then there is nothing to prove. If r > 20, then r S 2a 2a + a) + 23. Either case, we
have r S 2a In(e + a) 23.
58

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Abstract and introduction summarize our main theorems.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
For example, we explain our limitations on lower bound.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
59

---

The assumptions are given is the beginning of the paper and referred later when necessary.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Details on the experiment setup are given. It is mainly theoretical paper. Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
60

---

Answer:
[Yes]
Justification:
is mainly theoretical paper. We attach the code used for the simulation.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https Cooeeeoodeesssseeeeee 7/nips.com / casssnnnnccccyyc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: is mainly a theoretical paper with some simulations appendix. No deep learning other complicated training involved. But attach our code for reference.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Error bar is reported, e.g., Fig 2b.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
61

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: It is mainly a theoretical paper. Some simulations are given in the appendix. No need for heavy computation resource.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
This paper conforms all the code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: we discuss it in the appendix. It is mainly a theoretical and algorithmic paper, without any sensitive data, very unlikely to have negative impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
62

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses no such risks, no such data or model involved.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do not any existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
63

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not produce any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not use anything like crowdsourcing.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do use anything like crowdsoureing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
64


Reviews:
[{"review_id": "b7wEX8srcF", "reviewer": "Reviewer_Y9pp", "summary": "This paper addresses the problem of pure exploration bandits in the setting of encouragement designs. The authors describe the problem in terms of online instrumental variable regression. Toward this end, the authors derive a finite time confidence interval. Using this as the main tool, the authors then describe a pure exploration transductive bandit. Algorithms are provided for optimizing the pure exploration problem. A number of theoretical results are provided describing the entailed sample complexity of the proposed approach. Empirical results are provided which show strong performance against other baselines.", "questions": "Throughout an E-optimal design is also employed. My main question is whether the choice of E-optimality is done as a matter of convenience, or if it is motivated by aspects of the problem that would favor this criterion over other choices.", "limitations": "See above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a problem that has practical relevance in both industrial and social scientific settings. The task, to my knowledge, is novel in its formulation, and the authors do a nice job of delineating this work from prior art. The authors do a nice job of presenting algorithms and analysis in both the settings of a known and unknown structural models. Further, there is thorough analysis of each of the proposed procedures' properties.", "weaknesses": "My concerns are largely around two things: \n1. There is a fairly limited experimental evaluation here. It would be helpful if the authors provided a more thorough evaluation of the proposed approaches' behavior across a wider range of settings. \n\n2. The text is a little meandering at times and as a result was a little hard to follow on first read. I would suggest a round of editing in order to improve the narrative and organization of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the novelty of our problem formulation and the thorough analysis throughout. \n\nConcern on limited experimental evaluation: \n\nOur work is primarily theoretical and to provide an initial solution, which makes the surprising connection between encouragement designs and pure exploration linear bandits. This highlights an area that the adaptive experimentation / bandits community has largely overlooked. We have included experiments in the Appendix to demonstrate the impact of confounding and the effectiveness of our solution. We acknowledge that more experiments can be conducted and hope our work inspires further study in this area. We will update our conclusion to reflect this.\n\nConcern on readability of results:  \n\nWe will undertake additional rounds of editing and polishing to enhance readability. The camera-ready version will allow us to add one more page, which will help us improve clarity. \n\nRegarding the question:\n\nThank you for your question. We chose the E-optimal design to ensure the covariance matrix of the collected data is well-conditioned by maximizing the minimal eigenvalue, a requirement not necessarily met by other objectives. \nThis well-conditioning is crucial for efficiently meeting the stopping condition of the $\\Gamma$ estimation phase. \nThat said, we believe E-optimal design is sufficient but may not be necessary -- perhaps a more sophisticated design could be more useful, which remains to be a future direction.\nA significant algorithmic analysis contribution is determining the number of samples for E-optimal design to maintain these properties without significantly increasing sample complexity.", "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": "", "extra_scores": {}}, {"review_id": "clKrcSNyxF", "reviewer": "Reviewer_oap7", "summary": "This paper addresses the issue of adaptive experimentation using \"encouragement\" rather than \"compulsion instruction,\" a scenario commonly encountered in industrial applications. The proposed solution integrates linear bandit algorithms with instrumental variables regressions. The authors provide rigorous theoretical guarantees for their method and demonstrate its superior performance compared to traditional A/B testing and conventional linear bandit algorithms.", "questions": "How to think of p-values/confidence intervals as it is important in an experimentation setting.", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The scenarios examined by the authors are well-motivated. In practice, numerous situations exist where only encouragement can be employed to influence user decisions. Considering the shift in industry from traditional A/B testing to adaptive experimentation, the study presented here has the potential for significant industry impact.\n\nIn addition, the proposed algorithm is intuitive, and the theoretical guarantees provided are robust.", "weaknesses": "The authors could enhance their study by conducting additional experiments to verify the robustness of their results.\n\nFurthermore, there should be a more detailed discussion of the p-values and confidence intervals to strengthen the statistical analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are happy to see the reviewer likes our work and find its strong practical value.\n\nRegarding your comment on additional experiments:\n\nOur work is primarily theoretical and to provide an initial solution, which makes the surprising connection between encouragement designs and pure exploration linear bandits. This highlights an area that the adaptive experimentation/bandits community has largely overlooked. We have included experiments in the Appendix to demonstrate the impact of confounding and the effectiveness of our solution. We acknowledge that more experiments can be conducted and hope our work inspires further study in this area. We will update our conclusion to reflect this.\n\nRegarding the question on p-values and confidence intervals in an experimentation setting: \n\nthey correspond 1-to-1. For example, we can construct a confidence interval by considering the set of $\\theta$ that are not rejected under the null hypothesis for a given $p$-value. A good reference is Johari, Ramesh, et al. \"Always valid inference: Continuous monitoring of a/b tests.\" Operations Research 70.3 (2022): 1806-1821. Thus our confidence intervals in Section 2 could be used to provide inference. We will add a small discussion of this correspondence to the final draft.", "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": "", "extra_scores": {}}, {"review_id": "oIQKRcjyk7", "reviewer": "Reviewer_4vBb", "summary": "The paper introduces the confounded pure exploration transductive linear bandit (CPET-LB) problem, which addresses the challenges of conducting adaptive experimentation in environments where direct randomization is not possible. From my understanding, the paper studies the best arm identification problem under linear structural model with non-compliance. The paper proposes the algorithms with nearly optimal sample complexity guarantee.", "questions": "1.\tCould you please elaborate a bit more on why the confidence interval in Section 2.2 is novel? I know the traditional 2SLS always using asymptotic normality to construct CI. Is non-asymptotic or asymptotic the key difference?", "limitations": "See above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe paper provides a thorough theoretical analysis, including proofs of finite-time confidence intervals for the estimators and sample complexity bounds. The theoretical contributions are significant and appear to be solid.\n2.\tThe problem is practical-relevant and important.", "weaknesses": "1.\tThe connections with two streams of the literature should be more clearly stated. The basic problem set up is very classical econometric setting where the non-compliance exists. The analysis framework and some of the tools are very standard in transductive linear bandit problem. \n2.\tThe presentation of Section 1 is not easy to follow. I feel the authors try to manage the terminology from causal inference and pure exploration. For example, in Line 78, “measurement” and ”evaluation” are new terminology of the paper and a bit hard to connect with the example proposed in introduction. \n3.\tThe authors might want to reconsider the title. The title, from my perspective, is a bit confusing and misleading.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging our thorough theoretical analysis, noting its significance and solid foundation, as well as the strong practical value of our work.\n\nRegarding your comments on weaknesses, we appreciate your detailed concerns:\n\n1. As the reviewers kindly pointed out, we did take on the challenge of connecting fairly disparate settings in the literature. We addressed these aspects in the introduction, page 3 footnote, and the related work section of the appendix. We will conduct another round of editing to more clearly delineate the two streams of topics.\n\n2. Thank you for this very insightful comment.\" We will link the terminology back to the example proposed in the introduction, where $Z$ refers to  encouragement and $X$ refers to treatment. The terms \"measurement\" and \"evaluation\" come from the transductive linear bandit literature. We will clarify this further in the revision.\n\nThanks for your question:\n\nNon-asymptotic confidence intervals are one of our key novelties. While asymptotic intervals for the 2SLS estimator are known, they are not useful for algorithm design because they do not allow for identifying and eliminating bad treatments in the non-asymptotic regime with a precise correctness guarantee.\n\nOur second novelty addresses the limitations of the only other known non-asymptotic interval, which requires simultaneous control over Zs and Xs, this is challenging as X is a random result of Z. Our confidence interval solves this by using data splitting in two phases. This discussion is included in the paper.", "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": "", "extra_scores": {}}, {"review_id": "zXU023R0rz", "reviewer": "Reviewer_byyL", "summary": "This article studies the pure exploration transductive linear bandit problem in the presence of instrumental variables. The authors assume a linear structural equation model on the instrument, treatment and outcome. The proposed method attempts to estimate the parameters in the structural model while optimally designing to learn the best arm (i.e. treatment).  The paper is mainly theoretical, but some simulations are provided to demonstrate the method.", "questions": "N.A.", "limitations": "N.A.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The combination of instrument variables and pure exploration appears novel.\n2. The proposed method is guided by finite-time confidence bounds for two-stage least squares. The lower and upper bounds of sample complexity  are provided in the paper.\n3. The method outperforms the standard methods UCB-OLS and UCB-IV.", "weaknesses": "1. Section 3 is very dense. The authors can consider shortening the content before Section 2.2 and use more room to explain Section 3.\n2. No real-data demonstration of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the novelty of our problem setting and ideas, as well as our theoretical contributions.\n\nRegarding your comments:\n\n1. We agree that Sec 3 is dense, making this paper a heavy lift with many theoretical results. We appreciate the suggestion to shorten the content. The camera-ready version allows an additional page, giving us the opportunity to make these improvements.\n\n2. We would have loved to examine our approach on real data and compare it against alternative methods. Unfortunately, to the best of our knowledge, there is no public dataset available for this specific problem.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for providing insightful comments. As the strengths of our paper, 
reviewers Y9pp, oap7, and 4vBb have acknowledged the practical relevance and importance of the problem we introduced, and reviewers Y9pp and byyL acknowledged that our formulation is novel.
Finally, reviewer Y9pp, oap7, and 4vBb have mentioned that our analysis is through and solid.

Meta-review: I concur with the reviewers' positive view of the submission and think the paper would makes a nice addition to the nascent literature on this topic. However, I find deferring all discussion of related work to the appendix to be very inappropriate. Remarking that there are "only a handful of works in the multi-armed bandit literature that even consider confounding" is not informative of the works and how their technical content relates to the present paper -- the number of works is not relevant. I therefore ask the authors to discuss the relevant related works in the main text and to even prioritize this over technical details or considering different settings (eg Sec 3.1 and 3.2). It is ok to have an even more extended discussion of tangentially related work in the appendix, but directly related works studying the same problem such as [5,21,24,11,36,17] must be discussed in full to properly set up the context for the work and its contribution, especially as there are close similarities such as remarked on line 497 ("We remark that their approach is similar to ours ..."). I trust that the authors can undertake this appropriately within the preparation of a camera ready version as this mostly involves moving content around from/to the appendix.
Decision: Accept (poster)