Adaptive Experimentation When You Can't Experiment

Authors: yao  zhao
kwang-sung  jun
tanner  fiez
lalit  jain
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-09 08:58:47

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.

Main paper: 
 introduction: 
 In this study, we present a methodology for adaptive experimentation in 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 as average treatment effects (ATE). In this setting, firms are often interested in understanding the treatment with the highest average outcome if presented to all members of the population. However, in many settings firms may not be able to randomize, for example if a feature must be rolled out to all users for various business reasons [30] . In such instances, users may choose to engage with a feature or not based on potentially unobservable preferences. Thus the resulting measured outcome may be correlated with the decision to engage in a 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 1 .A potential solution is for services to employ encouragement designs where users are presented with incentives that encourage users to engage with a specific feature [4, 7, 12 ]. As a concrete example, many online services have introduced membership levels with different offerings and 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 (ITT) 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 a different feature. Hence, the resulting ITT estimate may be a diluted estimate of the ATE [3] . However, all is not lost: if the encouragement presented to a 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 [26, 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. Similar to A/B testing, bandit methods assume users are properly 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.Contributions. In this work, we provide a 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 1.1). 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 suboptimal sampling. The main technical challenge we face is simultaneously improving our estimate of the structural model while designing with inaccurate estimates (Section 3). This approach crucially relies on our development of novel finite-time confidence bounds for two-stage least squares (2SLS) style estimators that may be of independent interest (Section 2.2). 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 E).A confounded pure exploration transductive linear bandits (CPET-LB) instance consists of finite collections of measurement vectors Z ⊂ R d and evaluation vectors W ⊂ R d . At each time t ∈ N, the learner selects z t ∈ Z and observes a pair of noisy responses x t ∈ X ⊆ R d and y t ∈ R generated via the structural equation modelEQUATIONwhere Γ ∈ R d×d and θ ∈ R d are model parameters. 1 We define the history H t-1 = {(z s , x s , y s )} s<t and E t-1 [•] = E[•|H t-1] denoting the conditional expectation under the filtration generated by H t-1 .The noise {η t } ∞ t=1 and {ε t } ∞ t=1 satisfy the following set of assumptions unless otherwise noted. Assumption 1. We assume ε t | H t-1 is 1-sub-Gaussian (and thus E[ε t | H t-1 ] = 0). Furthermore, η t | H t-1 is σ 2 η -sub-Gaussian vectors (and thus E[η t | H t-1 ] = 0), i.e., ∀β ∈ R, max a:∥a∥2≤1E[exp β⟨a, η t ⟩ ] ≤ exp β 2 σ 2 η 2 .Goal. The objective is to identify w * := arg max w∈W w ⊤ θ with probability at least 1 -δ for δ ∈ (0, 1) while taking a minimum number of measurements.In the setting where Γ = I, η = 0 and E t-1 [ε t |x t ] = 0, our setting reduces to the standard pure exploration transductive linear bandit problem [33, 15] . In general, the joint noise process η t , ε t may be dependent across the entries. In particular, we are allowing for the data generating process to be endogenous, meaning that E t-1 [ε t |x t ] ̸ = 0. That is, ε t can affect not just y t , but also x t given a choice of z t . The presence of endogeneity is a key challenge in the CPET-LB problem. Assumption 2 (Exclusion Restriction). We assume that E t-1 [z t ε t ] = 0, or alternatively that z t is uncorrelated with ε t .The variable z t is commonly referred to as an instrumental variable [3] . We consider algorithms for the CPET-LB problem that stop at a H t -measurable time τ ∈ N, and produce a recommendation w ∈ W. The goal is δ-PAC algorithms with efficient sample complexity guarantees. Definition 1.1 (δ-PAC). We say an algorithm is δ-PAC for a CPET-LB problem with W, Z ⊂ R d if for all θ ∈ R d and Γ ∈ R d×d , it holds that P θ,Γ ( w ̸ = w * ) ≤ δ for δ ∈ (0, 1).The CPET-LB feedback model generalizes the classical compliance setting.Compliance as a Special Case. In compliance problems, a decision-maker has access to 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 to a 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, 2, . . . , d}, a decision-maker presents user t ∈ N with an encouragement for a treatment i ∈ A, the user then selects treatment j ∈ A where potentially j ̸ = i, and an outcome y t results.To capture compliance with the CPET-LB framework, we set Z = X = W = {e 1 , • • • , e d } and the parameter Γ captures the probability of accepting a treatment given an encouragement for a potentially different treatment. Specifically, Γ(i, j) = P x t = e i | z t = e j , and a straightforward computation shows that x t = Γ ⊤ z t + η t where E[η t |z t ] = 0 withEQUATIONMoreover, y t = x ⊤ t θ + ε t gives the resulting reward, which is clearly correlated with the user choice so that cov(η t , ε t ) ̸ = 0. Finally, e ⊤ i θ = θ i gives the expected value of treatment i over the population and our goal is to identify w * = arg max ei∈W e ⊤ i θ. 2 Note that when Γ = I, we automatically have that η t = 0 and there is no confounding. This reduces to the standard MAB setting.Motivating Compliance Example. As a motivating compliance example representing the membership level discussion from the introduction, consider a location model that assumes each user t ∈ N arriving online has an underlying unobserved one-dimensional preference u t ∼ N (0, σ 2 u ). If an algorithm presents the user with encouragement z It = e It for I t ∈ A, then the user selects into the membership level given by J t = min j∈A |I t + u t -j| so that x t = e Jt . This process captures a 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 y t = x ⊤ t θ + u t . We conduct an experiment with this problem instance (see Fig. 2 and Appendix B for more details). Specifically, d = 6, θ = 1 -0.95 0 0.45 0.95 0.99 , and σ 2 u = 0.35. Observe that w * = e 1 = arg max w∈W w ⊤ θ. An upper confidence bound (UCB) selection strategy is simulated that maintains estimates of the mean reward of each encouragement i ∈ A, namely µ i,t = t s=1 1{z t = e i }y t , and then pulls the one with the highest UCB. The UCB selection strategy is combined with a pair of recommendation strategies. The UCB-OLS algorithm estimates the mean reward of each treatment using an OLS estimator, namely θ i,t LS = t s=1 1{x t = e i }y t / t s=1 1{x t = e i }, and recommends arg max a∈A θ i,t LS . Moreover, the UCB-IV algorithm uses an instrumental variableestimator (see the next section) that incorporates knowledge of Γ similar to 2SLS to deconfound 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 to identify θ 1 = arg max i∈d θ i 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 z = e i is e ⊤ i Γθ. These values are plotted in orange in Figure 2a . In particular, with some constant probability, UCB zeroes in on arm 6 becauses of the mean estimates on the z's, and as a result fails to give enough samples to learn that arm 1 is indeed the best. In contrast, our proposed method CPEG, Algorithm 1 manages to find the best arm with significantly higher probability.Notation. Let ∆(Z) = {λ ∈ R |Z| : λ ≥ 0, z∈Z λ z = 1} denote the set of probability distributions over the set Z. Given a distribution λ ∈ ∆(Z) and matrix Γ ∈ R d×d , define the operatorA(λ, Γ) := z∈Z λ z Γ ⊤ zz ⊤ Γ. Given Z ∈ R T ×d and Γ ∈ R d×d , define the operator Ā(Z, Γ) := T t=1 Γ ⊤ z t z ⊤ t Γ = Γ ⊤ Z ⊤ ZΓ where z t ∈ R d denotes row t of Z.Given a vector x ∈ R d and a symmetric positive-definite matrix A ∈ R d×d we let ∥x∥ 2 A = x ⊤ Ax. We adopt the standard notation that (a ∨ b) ≡ max{a, b} and (a ∧ b) ≡ min{a, b} for a, b ∈ R. σ min (A), σ max (A) denote the minimum and maximum singular value of a matrix A. We denote by polylog(x 1 , . . . , x n ) any polylogarithmic factors of x 1 , . . . , x n .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 in linear bandits is the RAGE algorithm of [15, 33] . RAGE is nearly instance optimal for linear bandits in the non-confounded setting. Extensions of RAGE to various noise models including logistic and heteroskedastic noise have been considered [35, 20] . Other algorithms for pure exploration linear bandits have been proposedand we leave it for future work to extend the ideas of this paper to those settings [27, 10] .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 demonstrate 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 is 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 ⊤ Γ ⊤ θ in our notation), the highest treatment (arg max w w ⊤ θ), 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 of homogeneous effects across the population, and use an estimate of Γ. Recently [24] 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 [11, 36, 17] considered an online setting where at each time they observe a set {(x t , z t )} where x t is the action of interest and z t is an associated instrument. If action I t is selected, the reward observed is y t = x ⊤ It θ t + ε t , where x t may be endogeneous. Similar to the standard linear bandit setting [1, 26] , the goal is to minimize regret relative to the best action at each time. We remark that this setting is very different from ours. Effectively, we are choosing which instrument to select at each time to learn the best-performing treatment -in particular we can't choose a 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 to intervening (i.e. a "do" operation [31] ) at one or 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 [32] . Though past works have allowed for unobserved confounders in the graph e.g. [29] , their goal is to learn the best performing intervention, which in our setting would be arg max z∈Z z ⊤ Γθ 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 at a grocery store. More recent applications include [4, 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 a 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 1 and for multiple treatments. 
estimators and inference: 
 We now present estimators for the unknown parameter θ and prove the associated statistical properties. The estimators discussed in this section are critical to our algorithmic solution outlined in Section 3.Before describing our solution concept, we quickly review potential options for estimating θ based on a datasetZ T = [z 1 , • • • , z T ] ⊤ ∈ R T ×d , X T = [x 1 , • • • , x T ] ⊤ ∈ R T ×d , Y T = [y 1 , • • • , y T ] ⊤ ∈ R T ,assumed to be generated according to the model in Eq. (1) . Recall that the ordinary-least-squares (OLS) estimator for θ is given byEQUATIONObserve that θ LS is potentially a biased and inconsistent estimator for θ in the presence of endogenous noise since E[ε t |x t ] ̸ = 0. To remediate this problem, we define a general class of estimators that includes several standard estimators. Given an invertible matrix Ψ ∈ R d×d , let XT := Z T Ψ, and consider corresponding estimators termed Ψ-IV estimators of the formEQUATIONWhen Ψ = I we recover the OLS estimator. In the rest of the paper, we will focus on two different potential options for Ψ.Case 1: Oracle. Ψ = Γ. 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 formEQUATIONSince z t is independent of the i.i.d. process η ⊤ t θ + ε t , the least squares estimator which regresses y t onto z ⊤ t Γ is unbiased for estimation of θ and given byEQUATIONThis estimator will be used to design our general solution concept presented in Section 3. Of course in practice we cannot expect to know Γ, but we may be able to estimate it.Case 2: P-2SLS. Ψ = Γ. We consider a setting where Γ is an (unbiased) estimator of Γ, learned using least-squares from an independent dataset 3 That is, Γ = (Z ⊤ T1 Z T1 ) -1 Z ⊤ T1 X T1 and:Z T1 = [z ′ 1 , • • • , z ′ T1 ], X T1 = [z ′ 1 , • • • , z ′ T1 ] collected non-adaptively.θ P-2SLS = ( Γ ⊤ Z ⊤ T Z T Γ) -1 Γ ⊤ Z ⊤ T Y T .We refer to the resulting estimator as a pseudo two stage least squares (P-2SLS) estimator. The main advantage of the P-2SLS estimator over standard 2SLS (given in Appendix C) is easier inference since now {ε t } t≤T of our dataset is independent of the measurements of the first dataset Z T1 , X T1 . In the econometrics literature, such an estimator is referred to as a two-sample 2SLS estimator [19] .In the section that follows, we develop a general algorithmic approach that relies on experimental design aimed at reducing the uncertainty in our estimates of the optimal treatment. To this end, we first develop finite-time confidence intervals for estimators presented in the previous section given data generated according to the model in Eq. ( 1) 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 of results. Lemma 2.1. Under Assumption 1, the noise process ν := η ⊤ θ + ε is σ 2 ν -sub-Gaussian where σ 2 ν = 2(σ 2 η ∥θ∥ 2 2 + 1), specifically when the instance is compliance, σ 2 ν = 2(4∥θ∥ 2 2 + 1).Oracle Confidence Interval. As in the last section, we assume that we have access to a dataset (Z T , X T , Y T ) generated according to Eq. 1 and collected non-adaptively. Given Lemma 2.1, it can be shown that w ⊤ θ oracle is a sub-Gaussian random variable satisfying the following. Lemma 2.2. With probability at least 1 -δ for δ ∈ (0, 1) andw ∈ R d , |w ⊤ ( θ oracle -θ)| ≤ 2σ 2 ν ∥w∥ 2 Ā(Z T ,Γ) -1 log 2/δ ,where σ 2 ν is the sub-Gaussian parameter of the noise ν := η ⊤ θ + ε characterized in Lemma 2.1.The proof of this result is in Appendix G.2. P-2SLS Confidence Interval. We now present a novel finite-time confidence interval for the P-2SLS estimator. As discussed in the previous section with respect to this estimator, we assume access a set of data (Z T1 , X T1 ) generated according to Eq. ( 1) and collected non-adaptively for the purpose of estimating Γ. Moreover, assume access to a separate set of data (Z T2 , X T2 , Y T2 ) generated according to Eq. ( 1) and collected non-adaptively for the purpose of estimating θ.Theorem 2.3. Suppose that Γ = (Z ⊤ T1 Z T1 ) -1 Z ⊤ T1 X T1 and θ P-2SLS = ( Γ ⊤ Z T2 Z T2 Γ) -1 ΓZ ⊤ T2 Y T2 .Then, for any w ∈ W, with probability at least 1 -δ for δ ∈ (0, 1),|w ⊤ ( θ P-2SLS -θ)| ≤ ∥w∥ Ā(Z T 2 , Γ) -1 2σ 2 ν log 4 δ + ∥w∥ Ā(Z T 1 , Γ) -1 ∥θ∥ 2 σ 2 η log Z T1 , δ/4 ,wherelog(Z T , δ) := 8d ln 1 + 2T L 2 z d(2 ∧ σ min (Z ⊤ T1 Z T1 )) + 16 ln   2•6 d δ • log 2 2 4 2 ∧ σ min (Z ⊤ T1 Z T1 )   .The proof is presented in Appendix G.3. Observe that the first term in the P-2SLS estimator confidence interval given by 2σ 2 ν ∥w∥ 2 Ā(Z T 2 , Γ) -1 log 4/δ matches the Oracle estimator confidence interval in Lemma 2.2 when Γ = Γ. The second term scaling like O(∥w∥Ā(Z T 2 , Γ) -1 ∥θ∥ 2 σ η d + log 1/δ ),is an upper bound on the approximation error w ⊤ ( Γ -1 Γ -I)θ for any w ∈ R d , assuming that Γ is learned from an OLS estimator (see Theorem G.3 for details).We will see that the form of this confidence interval is particularly convenient for our algorithmic approach given in Section 3. In particular, the form of the variance ∥w∥ 2 Ā(Z T 2 ,Γ) -1 on the first term only depends on a 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, (Z T1 , X T1 ) to be collected from either a 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. Γ) [9] . Our result matches the existing literature on the asymptotic variance of two sample 2SLS estimators (e.g., Theorem 1 of [19] ). Remark 2.5. The asymptotic variance of standard 2SLS is known to involve a factor σ 2 ε , instead of σ 2 ν as we have [18] . Recent work by [11] shows a variance involving dσ 2 ε . However, it's unclear how to use the form of their confidence interval directly for experimental design. In addition, their work is not sufficiently general to handle the general forms of noise that we consider in Lemma 2.1. 
adaptive experimental design algorithms: 
 We now present adaptive experimental design algorithms for the CPET-LB problem. Our main insight utilizes Eq. 1 by plugging the model for x into the top equation resulting in the relationshipy = z ⊤ Γθ + θ ⊤ η + ε.When Γ is known, by Eq. 5, we see that CPET-LB reduces to a standard pure exploration transductive linear bandit problem where the measurement set is given by {Γ ⊤ z} z∈Z ⊂ R d , the evaluation set is W ⊂ R d , and the feedback model is given by y = v ⊤ θ + ν where the noise ν = θ ⊤ η + ε is sub-Gaussian and as before the goal is to identify arg max w∈W w ⊤ θ. An existing approach to this problem is given by the RAGE algorithm [15] , which we use as the basis of our approach. Addressing the case of unknown Γ 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 Γ is known.Algorithm 1 assumes a parameter L ν , which acts as an upper bound on the sub-Gaussian constant of the noise ν = θ ⊤ η + ε. In each round k, an active set of potentially optimal vectors W k ⊂ W is maintained. CPEG aims to sample in such a way that reduces the uncertainty of the estimates on the gaps (w -w ′ ) ⊤ θ for each pair w, w ′ ∈ W k maximally each round. In any given round the algorithm takes N k samples Z N k , the confidence interval of Lemma 2.2 shows that the error in estimating (w -w ′ ) ⊤ θ scales with ∥w-w ′ ∥ 2 (Γ ⊤ Z ⊤ N k Z N k Γ) -1. This motivates utilizing an experimental design approach where we choose a distributionλ k ∈ ∆(Z) to minimize max w,w ′ ∈ W k ∥w -w ′ ∥ ( z∈Z λzΓ ⊤ zz ⊤ Γ) -1 .The number of resulting samples taken from this design N k is chosen to guarantee that the confidence interval of Lemma 2.2 is less than 2 -k . Then, the elimination step in Line 8 guarantees that all w ∈ W such that (w * -w) ⊤ θ > 2 • 2 -k are then eliminated from the active set by round k + 1 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(ω).Sample Complexity Guarantee. The sample complexity of Algorithm 1 depends on the following problem-dependent quantity ρ * (γ) that captures the underlying hardness of a problem instance in terms of (W, Z, Γ, θ), when γ = 0, we abbreviate ρ * (0EQUATION)Theorem 3.1. Algorithm 1 is δ-PAC and terminates in at most c(1 + ω)L ν ρ * log 1/δ + cr(ω) samples, where c hides logarithmic factors of ∆ := min w ⟨w * -w, θ⟩ and |W|, as well as constants.The proof of this result is in Appendix H.1. In the unconfounded case when Γ = I and η = 0, E t-1 [ε t |x t ] = 0 this matches the sample complexity of [15] . In particular, for the case where Z = X = W, the problem further reduces to a standard multi-armed bandit, and if ε is 1-sub-Gaussian noise, [33] shows that ρ * = O(d i=2 (θ 1 -θ i ) -2)), which is the optimal sample complexity of best-arm identification for multi-armed bandits. The following lemma shows that the conditioning of Γ can have a strong impact on the resulting sample complexity.Lemma 3.2. For the compliance setting, we have min λ∈∆ d max j,j ′ ∥e j -e j ′ ∥ 2( d i=1 λiΓ ⊤ eie ⊤ i Γ) -1 ≤ d max j,j ′ ∥Γ -1 (e j -e j ′ )∥ 2 2 . Furthermore, ρ * ≤ dσ 2 min (Γ) -1 ∆ 2 min .Algorithm 1 CPEG:Confounded pure exploration with Γ1: Input Z, W, Ψ = Γ, δ, Lν ≥ σ 2 ν , ω, 2: Initialize: k = 1, W1 = W, ζ1 = 1 3: Set f (w, w ′ , Γ, λ) := ∥w -w ′ ∥ 2 ( z∈Z λz Γ ⊤ zz ⊤ Γ) -1 4: while |W k | > 1 do 5: λ k = arg min λ∈∆(Z) max w,w ′ ∈W k f (w, w ′ , Γ, λ). 6: ρ(W k ) = min λ∈∆(Z) max w,w ′ ∈W k f (w, w ′ , Γ, λ) 7: N k := ⌈2(1 + ω)2 2k ρ(W k )Lν log 4k 2 |W|/δ ⌉ ∨ r(ω) 8: Pull arms in ZN k = ROUND(λ k , N k ) and observe YN k . 9: Compute θ k Γ = Z ⊤ N k ZN k Γ -1 Z ⊤ N k YN k 10: W k+1 = W k \{w ∈ W k |∃w ′ ∈ W k , ⟨w ′ -w, θ k Γ ⟩ > 2 -k }, k ← k + 1 11: end while 12: Output: w ∈ W kTo further illustrate the impact of Γ, imagine an extreme setting where Γ = (1 -ε)/d11 ⊤ + εI and ε ≈ 0, i.e. Γ is a perturbation of 1/d11 ⊤ . It's straightforward to show that the upper bound in the first display of Lemma 3.2 is of the order O(dε -2 ) (this is also a lower bound -see Appendix K.1). In particular, the upper bound on the sample complexity is of the form dε -2 /∆ 2 min . This is in sharp contrast to the linear bandit case, when Γ = I and we are guaranteed a sample complexity of no more than d/∆ 2 min samples. To gain some intuition, regardless of the choice of λ,i≤d λ i Γ ⊤ e i e ⊤ i Γ ≈ Γ.As a result, ρ * → ∞ as ε → 0. Intuitively in the limit, regardless of which instrument i ≤ d 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 an estimate of θ. This is a phenomenon which does not arise in the standard multi-armed bandit case with unconfounding.Remark 3.3. We also consider a setting where instead of given Γ directly, we are given an estimate Γ of Γ based on offline data. We discuss such an adaptation of Algorithm 1 to this setting in Appendix I and provide a sample complexity which reflects the error in Γ (scaling with ρ * (γ) for γ > 0). We remark that this result is subsumed by the approach of Section 3.2 and so we omit it in the main text.Lower bound. Due to the noise model from confounding and the dependence of the noise θ ⊤ η + ε, the instance-dependent lower bounds of [15] do not immediately apply. We develop a 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 2 compared to the standard transductive linear bandit problem in the most general setting where entries of η are sub-Gaussian, but not necessarily independent nor bounded. Due to space limit, we defer it to Appendix D.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 Γ and θ simultaneously. Our algorithm, built upon Algorithm 1, is summarized in Algorithm 3. At its core, each phase of the algorithm is divided into two sub-phases, for estimating Γ and θ respectively. Specifically, the second sub-phase is essentially same as Algorithm 1 with Γ k in place of Γ where Γ k is 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 Γ. 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 bothD 2 := max w,w ′ ∥w -w ′ ∥ 2 Ā(Z T 2 , Γ k ) (error from θP-2SLS ) and D 1 := max w,w ′ ∥w -w ′ ∥ 2 Ā(Z T 1 , Γ k )(error from Γ k ) to be below the target error O(ζ 2 k ) at each phase (ignoring unimportant factors for discussion). Controlling D 2 is trivial, which is done in the second sub-phase as we described above.However, for D 1 , a similar strategy cannot be done because the estimate Γ k is computed directly by sampling arms in Z T1 . That is, the ideal design, based on which we will collect data points z 1 , . . . , z n , requires access to the random matrix Γ k that can only be computed after sampling z 1 , . . . , z n ,. This Algorithm 3 CPEUG: Confounded pure exploration with with unknown ΓInput Z, W, δ, Lν ≥ σ 2 ν , Lη ≥ σ 2 η , ω, γmin ≤ λmin(Γ), λE, κ0 Initialize: k = 1, W1 = W, Γ0 =⊥, ζ1 = 1 Define f (w, w ′ , Γ, λ) := ∥w -w ′ ∥ 2 ( z∈Z Γ ⊤ λz zz ⊤ Γ) -1 , M := 32Lη γ 2 min σ min( A(λ E ,I)) ∨ 1, δ ℓ := δ 4ℓ 2 while |W k | > 1 do Γ k = Γ -estimator W k , Γ k-1 , ζ k , δ/k 2 , ω, λE, M, Lη ▷ Step 1: update Γ θ k P-2SLS = θ -estimator W k , δ/k 2 , ζ k , Γ k , ω, Lν ▷ Step 2: update θ W k+1 = W k \ w ∈ W k | ∃w ′ ∈ W k , s.t., w ′ -w, θ k P-2SLS > ζ k ▷ Step 3: elimination k ← k + 1, ζ k = 2 -k end while Output: W kcreates 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 to compute the design based on Γ k from the previous phase. We then perform a doubling trick where we double the sample size (while following the computed design) until D 1 becomes smaller than the target error O(ζ 2 k ). The intuition is that in later phases the estimate Γ k 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.Algorithm 2 θ -estimator Input W, δ, ζ, Γ, ω, Lν λ = arg min λ∈∆(Z) max w,w ′ ∈W f (w, w ′ , Γ, λ) ρ(W) = min λ∈∆(Z) max w,w ′ ∈W f (w, w ′ , Γ, λ) N2 = 2(1 + ω)ζ -2 ρ(W)Lν log 4|W| δ ∨ r(ω) get N2 samples per design λ denoted as {Z2, X2, Y2} ▷ via ROUND update θP-2SLS = ( Γ ⊤ Z ⊤ 2 Z2 Γ) -1 Γ ⊤ Z ⊤ 2 Y2 Output: θP-2SLSOur algorithm additionally employs the so-called E-optimal design to ensure that the covariance matrix of the collected data used to estimate Γ is well-conditioned. This conditioning is required to ensure that Γ k concentrates fast enough to Γ as shown in the analysis. The E-optimal design is a well-known design objective in experimental design that aims to maximize the smallest singular value:λ * E := arg min λ∈∆(Z) σ max (V -1 (λ)), where V = z∈Z λ z zz ⊤ . We denote κ -1 0 := σ max (V -1 (λ * E )) = σ -1 min (V (λ * E ))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 Γ, the sample complexity scales with the key problem difficulty ρ * almost matching the sample complexity of Algorithm 1 which relies on knowledge of Γ. Theorem 3.4. Algorithm 3 is δ-PAC and terminates in at most(1 + ω)((L ν log 1/δ + L η ∥θ∥ 2 2 (d + log 1/δ ))ρ * + (d + log 1/δ )(L η ∥θ∥ 2 2 ρ 0 + M ))pulls, ignoring both of the additive and multiplicative logarithms of ∆, |W|, ρ * , ρ 0 , M , whereρ 0 = max w∈W\{w * } ∥w * -w∥ 2 ( z∈Z λ E,z Γ ⊤ zz ⊤ Γ) -1 , and M = 32L η γ 2 min σ min A(λ E , I) ∨ 1.Note that ρ 0 does not get hurt by ⟨w * -w, θ⟩, (ρ * does). It comes from the fact that in the first phase, we initialize that algorithm with E-optimal design.The challenge of the analysis can be summarized in two-fold. First, since the concentration result in Theorem 2.3 is w.r.t. Γ k , we need to analyze how the random matrix Γ k concentrates around Γ and how this impacts the sample complexity. For this, we develop a novel concentration inequalityAlgorithm 4 Γ -estimator Input W, Γ, ζ, δ, ω, λE, M, Lη Define Stop(W, Z, Γ, δ) := max w,w ′ ∈W w -w ′ Ā(Z,Γ) -1 ∥θ∥ 2 Lηlog(Z, δ) Initialize ℓ = 1, N0,0 = 0 ▷ doubling trick initialization if Γ =⊥ then while ℓ = 1 or Stop W, Z 0,ℓ , Γ ′ , δ ℓ > 1 do get 2 ℓ-1 r(ω) ∨ 2 κ 0 samples denoted as {Z 0,ℓ , X 0,ℓ , Y 0,ℓ } per design λE ▷ via ROUND Update Γ ′ by OLS on {Z 0,ℓ , X 0,ℓ }, ℓ ← ℓ + 1 end while else λ = arg min λ∈∆(Z) max w,w ′ ∈W f (w, w ′ , Γ, λ) N ′ = 4gdM ln 1 + 2M d + L 2 z + 2M 2gdM + 8M ln 2•6 d δ ∨ r(ω) while ℓ = 1 or Stop W, Z 0,ℓ ∪ Z 1,ℓ , Γ, δ ℓ > ζ do N 1,ℓ = 2 ℓ N ′ ▷ doubling trick update get N 1,ℓ samples per λ denoted as {Z 1,ℓ , X 1,ℓ , Y 1,ℓ } ▷ via ROUND N 0,ℓ = 2gdM ln M d + N 1,ℓ + L 2 z + 4M ln 2•6 d δ ℓ ∨ r(ω) ∨ 2 κ 0 get (N 0,ℓ -N 0,ℓ-1 ) samples per λE augmented to {Z 0,ℓ-1 , X 0,ℓ-1 } and get {Z 0,ℓ , X 0,ℓ } Update Γ ′ by OLS on {Z 0,ℓ ∪ Z 1,ℓ , X 0,ℓ ∪ X 1,ℓ }, ℓ ← ℓ + 1 end while end if Output: Γ ′that relates the confidence width involving Γ from Theorem 2.3 with the same quantity involving Γ in place of Γ. Second, our algorithm creates a long-range error propagation, which is highly nontrivial to analyze. To see this, the quality of Γk is affected by the design objective function max w,w ′ f (w, w ′ , Γk-1 , λ), which depends on the error of the estimate Γk-1 from the previous phase. This error is, in turn, affected by the error of Γk-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 a 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 our key novelty in the analysis. Remark 3.5. Our algorithm requires knowledge of a lower bound γ min of λ min (Γ). The knowledge of γ min is for simplicity only as one can obtain such a lower bound that is at least half of the true value λ min (Γ) via an efficient sampling procedure that we describe in Appendix K.Experiments. We provide experiments for the instance of Section 1.2 in the Appendix E. The experiments show that our approach is more sample efficient than natural passive baselines (e.g. A/B testing), or naively applying existing Pure-Exploration linear bandit methods and performs similarly to the oracle complexity. 
conclusion: 
 This work introduces the CPET-LB problem in which the learning protocol is characterized by a linear structural equation model governed by parameters Γ and θ. 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 a number of directions for future work including considering situations where the d z ̸ = d x , analysis to improve the dependence on the underlying noise variance, and the pursuit of a tight information-theoretic instance-dependent lower-bound. We hope that this line of work motivates increased discussion of the real impact of confounding on applicability of adaptive experimentation.  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: the paper poses no such risks, no such data or model involved.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 use any existing assets.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: This work is algorithmic and not tied to a particular application that would have immediate negative impact.We now present an illustrative experiment that highlights the challenges of 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 1, consider that a service has d membership options given by the set A = {1, . . . , d}. Let the set Z = {e 1 , • • • , e d } represent encouragements (incentives or advertisements) for the corresponding membership options given by W= X = {e 1 , • • • , e d }.We consider a location model that assumes each user t ∈ N arriving online has an underlying unobserved one-dimensional preference u t ∼ N (0, σ 2 u ). If an algorithm presents the user with encouragement z It = e It for I t ∈ A, then the user selects into the membership level given by J t = min j∈A |I t + u t -j| so that x t = e Jt . For a visual depiction, see Figure 3a . This process captures a 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 y t = x ⊤ t θ + u t . This problem instance is a specific compliance instance. For this experiment, we take d = 6, let θ = 1 -0.95 0 0.45 0.95 0.99 and σ 2 u = 0.35. Observe that the optimal evaluation vector is w * = e 1 = arg max w∈W w ⊤ θ.We simulate a UCB strategy which maintains estimates of the average reward of each of the possible d incentives, namely µ i,t = t s=1 1{z t = e i }y t and then pulls the one with the highest upper confidence bound. This models current practice of using a bandit algorithm to select which incentive to show a user. Our results averaged over 100 simulations are in Figure 3d . At each round we estimate the average reward of each level using an OLS estimator, i.e. θ OLS i,t = t s=1 1{x t = e i }y t / t s=1 1{x t = e i }, and check whether it matches the true value (denoted as UCB-OLS). We also consider an instrumental variable-estimator (see the next Section) which incorporates knowledge of Γ similar to 2SLS to deconfound our estimate (UCB-IV). As the plot demonstrates, UCB-OLS completely fails to identify θ 1 = arg max i∈d θ i (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 z = e i is e ⊤ i Γθ. These values are plotted in orange in Figure 3c . In particular, with some constant probability, UCB runs on the empirical rewards from pulling z's zeroes in on arm 6, and as a result fails to give enough samples to learn that arm 1 is indeed the best. In contrast, our proposed method CPEG, Algorithm 1 manages to find the best arm with significantly higher probability (the algorithm was run with δ = .1) in the given time horizon.Consider Ψ = Γ 2SLS = (Z ⊤ T Z T ) -1 Z ⊤ T X T .In this setting, we recover the standard two-stage-leastsquares (2SLS) estimator,θ 2SLS = (X ⊤ T Z T (Z ⊤ T Z T ) -1 Z ⊤ T X T ) -1 X ⊤ T (Z ⊤ T Z T ) -1 Z ⊤ T Y T = (Z ⊤ T X T ) -1 Z ⊤ T Y T .Note that the 2SLS estimator is a biased, but consistent estimator of the parameter θ [3, 18] . Note that in particular, the asymptotic variance of 2SLS is known to be σ [18] . Recent work by [11] provides a confidence interval of the form |w2 ε ∥w∥ ( Γ ⊤ 2SLS Z ⊤ T Z T Γ2SLS) -1⊤ ( θ 2SLS -θ)| ≤ O(dσ 2 ε ∥w∥ ( Γ ⊤ 2SLS Z ⊤ T Z T Γ2SLS) -1log T /δ ). However, it's unclear how to use the form of their confidence interval directly for experimental design due to the dependence of Γ2SLS on the random quantity X. In addition, their work is not sufficiently general to handle the general forms of noise that we consider in Lemma 2.1.Due to the noise model from confounding and the dependence of the noise θ ⊤ η + ε, the instancedependent lower bounds of [15] 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 a specific non-adaptive algorithm A that has access to the matrix Γ governing the structural equation model.In particular, suppose that the non-adaptive algorithm A is allowed to select a sequence of T measurements {z I1 , . . . z It . . . , z I T } to query prior to collecting any observations, where I t represents the index of the vector z ∈ Z chosen at time t ∈ {1, . . . , T }. Then, given the observations {y 1 , . . . , . . . y t , . . . , y T } generated by the environment, a candidate optimal vector w ∈ W is returned by the algorithm. We are interested in the necessary number of observations T that must be collected in order to ensure P( w ̸ = w * ) ≤ δ for some δ ∈ (0, 1). Thus, it is natural that the optimal non-adaptive algorithm A using the estimator θ oracle forms a recommendation rule such that w = arg max w∈W w ⊤ θ oracle . We now state our lower bound result with respect to the non-adaptive oracle algorithm. This chart shows that the optimal evaluation vector is w * = e 1 = arg max w∈W E[y|x = w], while e 6 = arg max w∈W E[y|z = w] and consequently estimation based on this quantity is problematic. (d) The probability of identifying w * = e 1 for a collection of algorithms on the CPET-LB instance described in Section B. Standard optimistic sampling approaches in combination with an ordinary least squares estimator leads to faulty inferences. Given an instrumental variable estimator, these experimental designs eventually give high probability identification but do so inefficiently compared to our proposed approach (see Section 3).W ⊂ R d , Z ⊂ R d , Γ ∈ R d×d ,and θ ∈ R d . Assume Γ is known, θ is unknown, and the noise process is jointly Gaussian and defined by γ := η ε ∼ N (0, Σ) where Σ ∈ R (d+1)×(d+1) is an arbitrary correlation matrix. For δ ∈ (0, 0.05], if the non-adaptive oracle algorithm acquires T ≤ σ 2 ρ * log 1/δ /2 samples on the problem instance where The proof of Theorem D.1 is in Appendix F.1. Notably, the result is reminiscent of lower bounds for the standard pure exploration transductive linear bandit problem without confounding [15, 22] when given the measurement set {Γ ⊤ z} z∈W , evaluation set Z, and parameter θ.σ 2 := v ⊤ Σv and v := θ 1 ∈ R d+1 , then P( w ̸ = w * ) ≥ δ.W ⊂ R d , Z ⊂ R d , Γ ∈ R d×dNotably, the upper bounds for our algorithms nearly match the lower bound of Theorem D.1. However, it is interesting to observe that the sample complexity incurs an additional factor of d 2 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 a tight lower bound. In particular, it is a lower bound with respect to a non-adaptive algorithm that uses the particular choice of estimator. We leave improved lower bounds to future work.We now present experiments a collection of experiments on CPET-LB problem instances. The experiments demonstrate that our approach produces efficient designs for inference and estimation.The baselines that our approaches are compared with are discussed below. We run experiments both when Γ is known and when Γ is fully unknown.E.1.1 Known Γ.To standardize the experiments, the baselines considered run in rounds mirroring the structure of Algorithm 1. Specifically, in round k ∈ N a sampling algorithm selects a design λ k ∈ ∆(Z), collects N k samples from the design, and forms a Ψ -IV estimate of θ with Ψ = Γ that is combined with a confidence interval (Lemma 2.2 to either eliminate evaluation vectors or validate a stopping condition. The number of samples N k taken in round k ∈ N by any of the algorithms is given byN k = ⌈2(1+ω)ζ -2 k ρ(W k )L ν log 4k 2 |W|/δ ⌉∨r(ω) where ρ(W k ) = max w,w ′ ∈W k f (w, w ′ , Γ, λ) for design λ k ∈ ∆(Z)and an active set of evaluation vectors W k . The round sample count guarantees that given any experimental design, all vectors w ∈ W such that (w * -w) ⊤ θ > 2 • 2 -k can be determined to be suboptimal by the end of round k. The sampling methods we consider are now described.• Static Oracle. This design selects λ k = arg min λ∈∆(Z) max w∈W\{w * } f (w * , w ′ , Γ, λ).• Static XY-Optimal. This design selects λ k = arg min λ∈∆(Z) max w,w ′ ∈W f (w, w ′ , Γ, λ).• Static Uniform. This design selects λ k,z = 1/|Z| ∀ z ∈ Z.• Adaptive Uniform (SE). This design selects λ k,w = 1/|W k | ∀ w ∈ W k . Note that this algorithm is effectively an adaption of action-elimination [14] .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 Γ.For this set of experiments, we compare Algorithm 3 against a collection of variations of the sampling procedures. Specifically, we compare against methods that either replace only the experimental design for estimating Γ, or only the experimental design for estimating θ, or both with uniform sampling. We label the approaches as N -N , where N represents the sampling approaches (XY or uniform) for Γ and θ respectively. Moreover, to make our approach more practical, we modify the algorithm so that log(Z T , δ) = 4d + log 1/δ . The step of incrementally adding more E-optimal design samples is also removed, so we collect E-optimal design samples only once in the beginning of Algorithm 4. We find that even with these modifications to the algorithm, correctness is maintained empirically.We first return back to the location model of Section B. Recall thatZ = W = X = {e 1 , • • • , e d }.For this experiment, we take d = 6, let θ = 1 -0.95 0.45 0.45 0.95 0.45 and σ 2 u = 0.275. The results of the experiment are shown in Figure 4a for the case of known Γ. We see that Algorithm 1 performs much better than the baselines and nearly matches the oracle design. Delving into the approach, it is able to quickly eliminate all but w 1 and w d-1 and then puts more mass on z 1 and z d-1 to reduce the uncertainty on w 1 and w d-1 . For the case of unknown Γ, the results are shown in Figure 4d , where θ 5 is reduced to 0.9 so that all approaches could finish. 4b for ε ∈ {1, 0.9, 0.8, 0.7} with Γ known. Note that Static-XY and Uniform overlap, and SE and CPEG overlap. We see that Algorithm 1 and the adaptive uniform strategy 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 if 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 Γ → 1 d 1 ⊤ d /d. Note that the identity matrix could be replaced with a permutation matrix, in which case uniform sampling with elimination becomes highly suboptimal. The results for the case of Γ unknown are shown in Figure 4e with ε = 0.99. This shows the value that comes from the experimental design for estimating both Γ and θ.To demonstrate the superiority of our algorithm over SE, we also consider that Γ := (1-ε) d 1 d 1 ⊤ d +εI p d , where I pd is a permutation matrix as follows,I p d =     0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0     .All other settings remain the same as in the previous interpolation instance. The results for the known Γ case, shown in Figure 4c , indicate that SE exhibits significant underperformance due to its sampling rule not accounting for the permutation effect in Γ. In contrast, CPEG consistently achieves near-optimal performance. Note that Static-XY and Uniform still overlap. Figure 4f presents the results for the unknown Γ case, where we can notice that, comparing with Figure 4e , estimating different permutation matrices (with the identity matrix as a special case) does not affect problem difficulty.F Proofs of the lower bound 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 to query prior to collecting any data. Let I t represent the index of the vector z ∈ Z chosen at time t ∈ {1, . . . , T }. The noise process for the instance under consideration is assumed to be jointly Gaussian and defined by γ t := η t ε t ∼ N (0, Σ) where Σ ∈ R (d+1)×(d+1) is an arbitrary positive semidefinite matrix. Defining xIt := Γ ⊤ z It , v := θ 1 ∈ R d+1 and ν t := v ⊤ γ t , the feedback model can be described as follows:y t = x t θ + ε t = (Γ ⊤ z It ) ⊤ θ + η ⊤ t θ + ε t =: (Γ ⊤ z It ) ⊤ θ + v ⊤ γ t =: x⊤ It θ + ν t .Observe that the noise is independent and identically distributed as ν t ∼ N (0, σ 2 ) where σ 2 := v ⊤ Σv since γ t ∼ N (0, Σ). Moreover, the noise process is exogeneous withE[ν t |x It ] = 0 since xIt is deterministic given the index choice I t .Let {z It } T t=1 , {x It } T t=1 , and {y t } T t=1 denote the observations collected by the non-adaptive oracle algorithm A and define Z T ∈ R T ×d , XT ∈ R T ×d , and Y T ∈ R T to contain the respective stacked observations. Algorithm A obtains an estimate θ oracle by minimizing the sum of squares as follows:θ oracle := arg min θ∈R d T t=1 (y t -xIt θ) 2 = ( X⊤ T XT ) -1 X⊤ T Y T = (Z ⊤ T Z T Γ) -1 Z ⊤ T Y T .Given θ oracle , the non-adaptive oracle algorithms A returns a recommendation defined by w = arg max w∈W w ⊤ θ oracle . Note that since θ oracle is obtained by least squares with exogeneous, independent and identically distributed mean-zero Gaussian noise, it is straightforward to verify the estimator is distributed asEQUATIONwhereĀ(Z T , Γ) := T t=1 Γ ⊤ z It z It Γ = X⊤ T XT = Γ ⊤ Z ⊤ T Z T Γ.Proof by Contradiction. To begin, recall thatρ * := min λ∈∆(Z) max w∈W\{w * } ∥w * -w∥ 2 A(λ,Γ) -1 ⟨w * -w, θ⟩ 2 .Suppose for the sake of contradiction that the number of samples collected by the non-adaptive oracle algorithm A is T ≤ σ 2 ρ * log 1/δ /2 and P( w ̸ = w * ) < δ for δ ∈ (0, 0.05]. To reach a contradiction, we analyze the distribution of (w -w * ) ⊤ θ for some w ̸ = w * and show that with probability at least δ it is positive. We remark that this proof follows similar techniques to that of the proof of Theorem 3 of [22] .Let λ ∈ ∆(Z) represent the empirical sampling distribution of the algorithm A, which is defined such thatλ z = 1 T T t=1 1{z It = z} for each z ∈ Z. Moreover, define ρ * (λ) := max w∈W\{w * } ∥w * -w∥ 2 A(λ,Γ) -1⟨w * -w, θ⟩ 2 and w ∈ arg maxw∈W\{w * } ∥w * -w∥ 2 A(λ,Γ) -1 ⟨w * -w, θ⟩ 2 .Note that ρ * (λ) ≥ ρ * and observe by definition,A(λ, Γ) -1 T := ( z∈Z λ z Γ ⊤ zz ⊤ Γ) -1 T = T t=1 Γ ⊤ z It z It Γ -1 := Ā(Z T , Γ) -1 .Thus, by Eq. ( 8),θ Oracle -θ ∼ N 0, σ 2 • A(λ, Γ) -1 T ,and( w -w * ) ⊤ ( θ Oracle -θ) ⟨w * -w, θ⟩ ∼ N 0, σ 2 • ∥w * -w∥ 2 A(λ,Γ) -1T • ⟨w * -w, θ⟩ 2 . Furthermore, by the definition of ρ * (λ), the assumption T ≤ σ 2 ρ * log 1/δ /2, and the fact ρ * (λ) ≥ ρ * , we obtainEQUATIONNow, consider a random variable W ∼ N (0, 1). Proposition 2.1.2 of Vershynin [34] gives an anti-concentration result showing that for all ζ > 0,EQUATION)We apply this result to the quantity ( w -w * ) ⊤ ( θ Oracle -θ)/⟨w * -w, θ⟩ to conclude that ( ww * ) ⊤ θ Oracle > 0 with probability at least δ. Toward doing so, let c ∈ (1, 1.15] be a constant and define Observe that W ∼ N (0, 1). The following analysis holds for δ ∈ (0, 0.05] given that c ∈ (1, 1.15] as assumed:EQUATIONEQUATION3 c 3 log 1/δ 3 1 √ 2π δ c 2 /4≥ δ. The final inequality can be verified computationally. Thus, with probability at least δ for δ ∈ (0, 0.05], we obtain( w -w * ) ⊤ θ Oracle ≥ c(w * -w) ⊤ θ + ( w -w * ) ⊤ θ = c(w * -w) ⊤ θ -(w * -w) ⊤ θ = (c -1)(w * -w) ⊤ θ > 0.Observe that the final inequality holds since c > 1 and (w * -w) ⊤ θ > 0 by definition.This result directly implies that with probability at least δ for δ ∈ (0, 0.05], the vector w returned by algorithm A is not w * . This is a contradiction, so we conclude that if the non-adaptive oracle algorithm A acquires T ≤ σ 2 ρ * log 1/δ /2 samples, then P( w ̸ = w * ) ≥ δ for δ ∈ (0, 0.05]. Note that the correlation of η i with itself for i ∈ {1, . . . , d} is σ 2 ηi = ζ ηi,ηi = 1 and similarly the correlation of ε with itself isσ 2 ε = ζ ε,ε = 1.The correlation matrix Σ is then given byEQUATION,whereΣ θ =      1 ζ η2,η1 • • • ζ η d ,η1 ζ η1,η2 1 • • • ζ η d ,η2 . . . . . . . . . . . . ζ η1,η d ζ η2,η d • • • 1      ∈ [-1, 1] d×d and ζ η,ε =      ζ η1,ε ζ η2,ε . . . ζ η d ,ε      ∈ [-1, 1] d .Moreover, we use the notation Σ ⊤ θ,i ∈ R d to denote the i-th row of Σ ⊤ θ , or equivalently the i-th column of Σ θ , for any i ∈ {1, . . . , d}.Lower Bounding Noise Variance. Given the above notation, we now work toward lower bounding σ 2 := v ⊤ Σv. Observe that by algebraic manipulations,v ⊤ Σv := θ 1 ⊤ Σ θ ζ η,ε ζ ⊤ η,ε 1 θ 1 = θ ⊤ Σ ⊤ θ,1 + ζ η1,ε θ ⊤ Σ ⊤ θ,2 + ζ η2,ε • • • θ ⊤ Σ ⊤ θ,d + ζ η d ,ε θ ⊤ ζ η,ε + 1 θ 1 = θ ⊤ d i=1 Σ ⊤ θ,i θ i + d i=1 ζ ηi,ε θ i + θ ⊤ ζ η,ε + 1 = θ ⊤ Σ θ θ + 2θ ⊤ ζ η,ε + 1.Since Σ θ is a real symmetric matrix, an eigendecomposition exists such that Σ θ = QΛQ ⊤ where Λ = diag(λ 1 , . . . , λ d ) ∈ R d×d is a diagonal matrix containing the eigenvalues of Σ θ and Q ∈ R d×d is an orthogonal matrix with columns corresponding to the eigenvectors of Σ θ . Let q i := Q ⊤ i denote column i of the matrix Q for i = {1, . . . , d}, which is equivalently eigenvector i of Σ θ for i = {1, . . . , d}. Without loss of generality, assume that the eigenvectors are of unit length so that ∥q i ∥ 2 = 1 for all i = {1, . . . , d}.Given this information, suppose that the parameter θ in the instance is equal to a scalar multiple of the eigenvector of Σ θ corresponding to the maximum eigenvalue. Note this is equivalent to the statement that θ is equal to some scalar multiple of the column q * ∈ R d of the matrix Q where q * is the eigenvector of Σ θ corresponding to the maximum eigenvalue λ * . Thus, we take θ = c • q * for some c ∈ R and observe that ∥θ∥ 2 = c. Toward quantifying the value of v ⊤ Σv for the problem instance, we begin by characterizing θ ⊤ Σ θ θ for the choice of θ. Consider the following analysis:θ ⊤ Σ θ θ = θ ⊤ QΛQ ⊤ θ := (cq * ) ⊤ QΛQ ⊤ (cq * ) (θ := cq * ) = ∥θ∥ 2 2 q ⊤ * q 1 • • • q * • • • q d Λ q 1 • • • q * • • • q d ⊤ q * = ∥θ∥ 2 2 0 • • • ∥q * ∥ 2 2 • • • 0 diag(λ 1 , . . . , λ * , . . . , λ 1 ) 0 • • • ∥q * ∥ 2 2 • • • 0 ⊤ (q ⊤ i q j = 0 ∀i ̸ = j) = ∥θ∥ 2 λ * . (∥q * ∥ 2 = 1)Thus, in general for this choice of θ,v ⊤ Σ θ v = ∥θ∥ 2 2 λ * + 2θ ⊤ ζ η,ε + 1.To conclude, take Σ θ := 1 d 1 ⊤ d where 1 d represents the d-dimensional vector of all ones. Since this is a rank-1 matrix, the maximum eigenvalue is λ * = 1 ⊤ d 1 d = d and the remainder of the eigenvalues are zero. Observe that q * = 1 d /d is an eigenvector corresponding to the maximum eigenvalue since1 d 1 ⊤ d q * = dq * . Thus, v ⊤ Σ θ v = ∥θ∥ 2 2 λ * + 2θ ⊤ ζ η,ε + 1 := ∥θ∥ 2 2 λ * + 2∥θ∥ 2 1 ⊤ d 1 d / √ d + 1 (θ := cq * := ∥θ∥ 2 1 d / √ d = and ζ η,ε := 1 d ) = d∥θ∥ 2 2 + 2 √ d∥θ∥ 2 + 1 ≥ max{d∥θ∥ 2 2 , √ d∥θ∥ 2 }.This completes the proof since we have shown that there exists a parameter θ and correlation matrix Σ such that σ 2 := v ⊤ Σv ≥ max{d∥θ∥ 2 2 , √ d∥θ∥ 2 }, which by Theorem D.1 allows us to make the stated conclusion.The first statement is an immediate consequence of Lemma G.2 and the second statement is proven in Lemma G.1.Lemma G.1. In the compliance model, the noise η ⊤ θ + ε follows a 8∥θ∥ Let us figure out the sub-Gaussian parameter of the random vector η. Fix any unit vector a. First, we have E[⟨η, a⟩] = 0. Second, we haveη ⊤ a ≤ ∥η∥ 2 (Cauchy-Schwarz inequality) ≤ x -P e 1 | z , • • • , P e d | z ⊤ 2 ≤ ∥x∥ 2 + P e 1 | z , • • • , P e d | z ⊤ 2 ≤ 1 + P e 1 | z , • • • , P e d | z ⊤ 1 (x ∈ {e 1 , • • • , e d } and ∥x∥ 2 ≤ ∥x∥ 1 , ∀x) = 2.Thus, η ⊤ a is bounded and zero-mean and thus 2 2 -sub-Gaussian. This implies that ∀β, maxa:∥a∥≤1 E[exp β⟨η, a⟩ ] ≤ exp β 2 2 2 2 .and thus η is a 2 2 -sub-Gaussan random vector. Then,η ⊤ θ is (2∥θ∥) 2 -sub-Gaussian.Using Lemma G.2, we have that η ⊤ θ + ε is 2(4∥θ∥ 2 + 1)-sub-Gaussian.Lemma G.2. Let A and B random variables that are each σ 2 A -and σ 2 B -sub-Gaussian but are correlated. Then,A + B is 2(σ 2 A + σ 2 B )-sub-Gaussian.Proof. By definition of sub-Gaussian, we have for any γ ∈ R,E exp γ(A + B) = E exp(γA) exp(γB) ≤ E exp(2γA) E exp(2γB) (Cauchy-Schwarz) ≤ exp 2γ 2 σ 2 A exp 2γ 2 σ 2 B ≤ exp 2γ 2 (σ 2 A + σ 2 B ) . G.2 Proof of Lemma 2.2Lemma 2.2. Suppose that T observations are collected non-adaptively from the structural equation model in Eqs. (1) and Γ ∈ R d×d is known. Then, with probability at least 1 -δ for δ ∈ (0, 1) andw ∈ R d , |w ⊤ ( θ oracle -θ)| ≤ 2σ 2 ν ∥w∥ Ā(Z T ,Γ) -1 log 2/δ .where σ 2 ν is the sub-Gaussian parameter of the noise process ν := η ⊤ θ + ε as characterized in Lemma 2.1.Proof. Given the knowledge of Γ, we have the oracle 2SLS estimatorθ oracle =   T t=1 z s Γ ⊤ z s ⊤   -1 T t=1 z s y t =   T t=1 z s z ⊤ s Γ   -1 T t=1 z s y t .Note thaty t = x ⊤ t θ + ε t = Γ ⊤ z t ⊤ θ + η ⊤ t θ + ε t .Denote ν t := η ⊤ t θ + ε t . For any w ∈ W, we haveθ oracle -θ, w =   T t=1 z s z ⊤ s Γ   -1 T t=1 z s y t -θ, w =   T t=1 z s z ⊤ s Γ   -1 T t=1 z s z ⊤ s Γθ + ν t -θ, w =   T t=1 z s z ⊤ s Γ   -1   T t=1 z s z ⊤ s Γθ + T t=1 z s ν t   -θ, w =   T t=1 z s z ⊤ s Γ   -1 T t=1 z s ν t , w = t q=1   T t=1 z s z ⊤ s Γ   -1z q , w ν q .By Lemma G.1, the noise ν t is σ 2 ν -sub-Gaussian, we have  T t=1 z s z ⊤ s Γ   -1 z q , w ν q is T t=1 z s z ⊤ s Γ -1 z q , w 2 σ 2 ν -sub-Gaussian. Thus P      θ oracle -θ, w ≥ 2 t q=1   T t=1 z s z ⊤ s Γ   -1 z q , w 2 σ 2 ν log 1 δ      ≤ δ.Concisely,EQUATIONThus,P      θ oracle -θ, w ≥ 2w ⊤   Γ ⊤   T t=1 z s z ⊤ s   Γ    -1 wσ 2 ν log 1 δ      ≤ δ.We can further write it asP   θ oracle -θ, w ≥ 2∥w∥ 2 Γ ⊤ ( T t=1 zsz ⊤ s )Γ -1 σ 2 ν log 1 δ   ≤ δ.By taking a union bound over, we have the confidence interval for the absolute value as in the statement of the lemma.Theorem 2.3. Suppose that Γ is estimated through a design matrix Z T1 ∈ R T1×d and θ P-2SLS is estimated through a design matrix Z T2 ∈ R T2×d . Then, for any w ∈ W, with probability at least 1 -δ,|w ⊤ ( θ P-2SLS -θ)| ≤ ∥w∥ Ā(Z T 2 , Γ) -1 2σ 2 ν log 4 δ + ∥w∥ Ā(Z T 1 , Γ) -1 ∥θ∥ 2 σ 2 η log Z T1 , δ/4 .where σ 2 ν is the sub-Gaussian parameter of the noise ν := η ⊤ θ + ε, σ 2 η is the sub-Gaussian parameter of the noise η, andlog(Z T , δ) := 8d ln 1 + 2T L 2 z d(2 ∧ σ min (Z ⊤ T1 Z T1 )) + 16 ln   2•6 d δ • log 2 2 4 2 ∧ σ min (Z ⊤ T1 Z T1 )   Proof.For the pseudo 2SLS estimator, we haveθ P-2SLS -θ =   T2 t=1 z It z ⊤ It Γ   -1 T2 t=1 z It y t -θ =   T2 t=1 z It z ⊤ It Γ   -1 T2 t=1 z It z ⊤ It Γθ + ν t -θ =   T2 t=1 z It z ⊤ It Γ   -1   T2 t=1 z It z ⊤ It Γθ + T2 t=1 z It ν t   -θ =   T2 t=1 z It z ⊤ It Γ   -1 T2 t=1 z It ν t + Γ -1 Γ -I θ.For any w ∈ W, we haveEQUATIONWe upper bound the first term and the second term separately. For the first term, by Lemma 2.1, we know ν t is σ 2 ν -subGaussian, we haveT2 q=1 T2 t=1 z It z ⊤ It Γ -1 z Iq , w ν q is T2 q=1 T2 t=1 z It z ⊤ It Γ -1z Iq , w 2 σ 2 ν -subGaussian. Thus by the concentration inequality of sub-Gaussian random variables, we haveP      T2 q=1   T2 t=1 z It z ⊤ It Γ   -1 z Iq , w ν q ≥ 2 T2 q=1   T2 t=1 z It z ⊤ It Γ   -1 z Iq , w 2 σ 2 ν log 2 δ      ≤ δ 2 .By similar calculation as (11), we have with probability at leastEQUATIONThus with probability at least 1 -δ 2 ,θ P-2SLS -θ, w ≤ ∥w∥ Ā(Z T 2 , Γ) -1 2σ 2 ν log 2 δ + Γ -1 -Γ -1 Γθ, wBy Theorem G.3, we have with probability at least 1 -δ 2 ,EQUATIONCombining ( 13) and ( 14), we have with probability at least 1 -δ, for any w ∈ W,θ P-2SLS -θ, w ≤ ∥w∥ Ā(Z T 2 , Γ) -1 2σ 2 ν log 2 δ + ∥w∥ Ā(Z T 1 , Γ) -1 ∥θ∥ σ 2 η log Z T1 , δ/2 .By a union bound, we have the confidence interval for the absolute value of the inner product,|w ⊤ ( θ P-2SLS -θ)| ≤ ∥w∥ Ā(Z T 2 , Γ) -1 2σ 2 ν log 4 δ + ∥w∥ Ā(Z T 1 , Γ) -1 ∥θ∥ σ 2 η log Z T1 , δ/4 .Theorem G.3. Suppose that the least square estimator Γ is estimated through a design matrix Z T1 ∈ R T1×d , then it satisfies, with probability at least 1 -δ,Γ -1 -Γ -1 Γθ, w ≤ ∥w∥ Ā(Z T 1 , Γ) -1 ∥θ∥ σ 2 η log(Z T1 , δ)for any w ∈ W.Proof. Define V = Z ⊤ T1 Z T1 , S ∈ R T1×d as the matrix with i-th row being η ⊤ i , the stacked noise, i.e., the data collection process of the design matrix Z T1 is X = Z T1 Γ + S. Then we haveΓ -1 -Γ -1 Γθ, w =w ⊤ Γ -1 -Γ -1 Γθ =w ⊤ Γ + V -1 Z ⊤ T1 S -1 V -1 Z ⊤ T1 SΓ -1 Γθ (Lemma J.12) =w ⊤ Γ -1 V -1/2 V -1/2 Z ⊤ T1 Sθ ≤ w ⊤ Γ -1 V -1/2 V -1/2 Z ⊤ T1 Sθ ≤∥w∥ Ā(Z T 1 , Γ) -1 V -1/2 Z ⊤ T1 S op ∥θ∥ ≤∥w∥ Ā(Z T 1 , Γ) -1 ∥θ∥ σ 2 η log(Z T1 , δ), where the last inequality is due to Lemma G.4.Lemma G.4. Suppose we have z 1 , . . . , z T ∈ R d and η1 , . . . , η T ∈ R d such that η T | z 1 , η 1 , . . . , z T -1 , η T -1 , z T is σ 2η -sub-Gaussian vector (defined in Assumption 1). Let Z, S ∈ R T ×d be matrices whose t-th row is z ⊤ t and η ⊤ t respectively. Suppose ∥z t ∥ ≤ L z , ∀t. Let V = Z ⊤ Z. Then, ∀δ ∈ (0, 1), we have, with probability at least 1 -δ,V -1/2 Z ⊤ T S op ≤ σ η 8d ln 1 + 2T L 2 z d(2 ∧ σ min (V )) + 16 ln 2•6 d δ • log 2 2 4 2 ∧ σ min (V ).We abbreviate log(Z T , δ) := 8d ln 1 +2T L 2 z d(2∧σmin(V )) + 16 ln 2•6 d δ • log 2 2 4 2∧σmin(V ). Proof. By the definition of operator norm, we haveV -1/2 Z ⊤ T S op = sup {x|∥x∥ 2 =1} V -1/2 Z ⊤ T Sx 2 = sup {x|∥x∥ 2 =1} x ⊤ S ⊤ Z T V -1 Z ⊤ T Sx = sup {x|∥x∥ 2 =1} Z ⊤ T Sx V -1 .Considering a fixed w ∈ R d , by Lemma G.5, we have with probability at least 1 -δ,Z ⊤ T Sx V -1 ≤ √ 2σ η d ln 1 + 2T L 2 z d(2 ∧ σ min (V )) + 2 ln 2 δ • log 2 2 4 2 ∧ σ min (V ).By Lemma G.6 and a union bound, for the ε-covering C ε , we have the following event happens with probability no more than δ:E :=      ∃x ∈ C ε , Z ⊤ T Sx V -1 ≥ √ 2σ η d ln 1 + 2T L 2 z d(2 ∧ σ min (V )) + 2 ln 2|C ε | δ • log 2 2 4 2 ∧ σ min (V )      . We abbreviate log(Z T , δ) := √ 2 d ln 1 + 2T L 2 z d(2∧σmin(V )) + 2 ln 2|Cε| δ • log 2 2 4 2∧σmin(V )When E does not happen, we haveV -1/2 Z ⊤ S op = sup {x|∥x∥=1} Z ⊤ T Sx V -1 = sup {x|∥x∥=1} min {y|y∈Cε} Z ⊤ T S(x -y + y) V -1 ≤ sup {x|∥x∥=1} min {y|y∈Cε} Z ⊤ T S(x -y) V -1 + Z ⊤ T Sy V -1 ≤ sup {x|∥x∥=1} min {y|y∈Cε} V -1/2 Z ⊤ S op ∥x -y∥ 2 + σ η log(Z T , δ) ≤ ε V -1/2 Z ⊤ T S op + σ η log(Z T , δ).Thus,V -1/2 Z ⊤ T S op ≤ σ η 1 -ε log(Z T , δ).By choosing ε = 1 2 and Lemma G.6, we haveV -1/2 Z ⊤ T S op ≤ σ η 8d ln 1 + 2T L 2 z d(2 ∧ σ min (V )) + 16 ln 2•6 d δ • log 2 2 4 2 ∧ σ min (V ).Lemma G.5. [Self-Normalized Bound for Vector-Valued Martingales] Suppose we have z 1 , . . . , z t ∈ R d and η 1 , . . . , η t ∈ R d such that η t | z 1 , η 1 , . . . , z t-1 , η t-1 , z t is σ 2 η -sub-Gaussian vector (defined in Assumption 1). Let Z, S ∈ R t×d be matrices whose s-th row is z ⊤ s and η ⊤ s respectively. Suppose ∥z s ∥ ≤ L z , ∀s. Let V t = Z ⊤ Z. Then, ∀b ∈ R t , δ ∈ (0, 1), we have, with probability at least 1 -δ,∀t ≥ 1, Z ⊤ Sb V -1 t ≤ √ 2∥b∥ 2 σ η d ln 1 + 2tL 2 z d(2 ∧ σ min (V t )) + 2 ln 2 δ • log 2 2 4 2 ∧ σ min (V t ).Proof. Since each row of S is a σ 2 η -subGaussian vector, we have that (Sb) i /∥b∥ is σ 2 η -subGaussian. Using Lemma G.7 with ε s = (Sb) i /∥b∥ completes the proof.C ε ⊂ R d with |C ε | ≤ 3 ε d such that for any x ∈ x | x ∈ R d , ∥x∥ 2 = 1 , there exists a y ∈ C ε such that ∥x -y∥ 2 ≤ ε. Lemma G.7. Let z 1 , z 2 , . . . ∈ {z ∈ R d : ∥z∥ 2 ≤ L z } and ε 1 , ε 2 , . . . ∈ R be random variables such that ε k | z 1 , ε 1 , . . . , z t-1 , ε t-1 , z t is σ 2 ε -sub-Gaussian. Let V t = t s=1 z s z ⊤ s . Then, 1 -δ ≤ P   ∀t ≥ 1, t s=1 z s ε s V -1 t ≤ √ 2σ ε d ln 1 + 2tL 2 z d(2 ∧ σ min (V t )) + 2 ln 2 δ • log 2 2 4 2 ∧ σ min (V t )   Proof. Let Z t ∈ R t×d be the design matrix and define ε t := (ε 1 , . . . , ε t ) ⊤ ∈ R t . Let us omit the subscript t from Z t , ε t and V t . Note that∥Z ⊤ ε∥ V -1 = ∥Z ⊤ ε∥ ( 1 2 V + 1 2 V ) -1 ≤ ∥Z ⊤ ε∥ ( 1 2 V + 1 2 σmin(V )I) -1 ≤ √ 2∥Z ⊤ ε∥ (V +σmin(V )I) -1It remains to bound ∥Z ⊤ ε∥ (V +σmin(V )I) -1 . 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 λ k = 2 -k+1 for k ≥ 1. Then,1 -δ ≤ P   E :=    ∀k ∈ N + , ∀t ≥ 1, ∥Z ⊤ ε∥ (V +λ k I) -1 ≤ σ ε d ln 1 + tL 2 dλ k + 2 ln (π 2 /6)k 2 δ      Under the event E, we have two cases:• σ min (V ) ≥ 1: choose k = 1. Then, ∥Z ⊤ ε∥ (V +σmin(V )I) -1 ≤ ∥Z ⊤ ε∥ (V +I) -1 ≤ σ ε d ln 1 + tL 2 d + 2 ln (π 2 /6) δ • σ min (V ) < 1: choose k = ⌈log 2 (2σ min (V ) -1 )⌉ ≥ 2, which is the k that satisfies λ k ≤ σ min (V ) < λ k-1 . Then, ∥Z ⊤ ε∥ (V +σmin(V )I) -1 ≤ ∥Z ⊤ ε∥ (V +λ k I) -1 ≤ σ ε d ln 1 + tL 2 dλ k + 2 ln (π 2 /6)k 2 δ ≤ σ ε d ln 1 + tL 2 dσ min (V )/2 + 2 ln (π 2 /6)⌈log 2 (2σ min (V ) -1 )⌉ 2 δ . (λ k = 1 2 λ k-1 > 1 2 σ min (V ); def'n of k) Altogether, we have ∥Z ⊤ ε∥ (V +σmin(V )I) -1 ≤ σ ε d ln 1 + tL 2 (1 ∨ 2σ -1 min (V )) d + 2 ln (π 2 /6)(1 ∨ ⌈log 2 (2σ -1 min (V ))⌉ 2 ) δ .We conclude the proof by simplifying the RHS.H.1 Proof of Theorem 3.1Algorithm 5 Confounded pure exploration with known ΓInput Z, W, Γ, δ, ε, L ν ≥ σ 2 ν Initialize: k = 1, Ŵk = W Define f (w, w ′ , Γ, λ) := ∥w -w ′ ∥ 2 ( z∈Z Γ ⊤ λzzz ⊤ Γ) -1while Ŵk > 1 do λ k = arg min λ∈∆(Z) max w,w ′ ∈W k f (w, w ′ , Γ, λ) ρ(W k ) = min λ∈∆(Z) max w,w ′ ∈W k f (w, w ′ , Γ, λ) ζ k = 2 -k N k = 2(1 + ω)ζ -2 k ρ(W k )L ν log 4k 2 |W| δ ∨ r(ω) Z N k = ROUND(λ k , N k ) Pull arms in Z N k and observe Y N k Compute θ k oracle = Z ⊤ N k Z N k Γ -1 Z ⊤ N k Y N k W k+1 = W k \ w ∈ W k | ∃w ′ ∈ W k , s.t., w ′ -w, θ k oracle > ζ k k = k + 1 end while Output: W kθ k oracle -θ, w -w * ≤ ∥w -w * ∥ Γ ⊤ N k s=1 z I t z ⊤ I t Γ -1 2σ 2 ν log 4k 2 |W| δ ≤ √ 1 + ω∥w -w * ∥ (Γ ⊤ λzzz ⊤ Γ) -1 √ N k 2σ 2 ν log 4k 2 |W| δ ≤ √ 1 + ω∥w -w * ∥ (Γ ⊤ λzzz ⊤ Γ) -1 2(1 + ω)ζ -2 k ρ(W k )L ν log 4k 2 |W| δ ∨ r(ω) 2σ 2 ν log 4k 2 |W| δ ≤ ζ k .Define a good event E k,w for each k and W k asE k,w = θ k oracle -θ, w -w * ≤ ζ k .We claim that with probability at least 1 -δ, the event ∞ k=1 w∈W k E k,w holds. It can be proved by a union bound.EQUATIONwhere the last step is by the fact that∞ k=1 1 k 2 = π 2 6 < 2.Under the event ∞ k=1 w∈W k E w,k , to show that the best arm is never eliminated, it suffices to show that for any sub-optimal arm w ∈ W k ,w -w * , θ k oracle = w -w * , θ k oracle -θ + ⟨w -w * , θ⟩ ≤ w -w * , θ k oracle -θ ≤ ζ k .Thus the best arm w * never satisfies the elimination condition. Next we show that at the end of stage k, any suboptimal arm w that satisfies ⟨θ, w * -w⟩ ≥2ζ k is eliminated. To show this, we need to show that w satisfies the elimination condition,max w ′ ∈W k θ k oracle , w ′ -w ≥ θ k oracle , w * -w = θ k oracle -θ, w * -w + ⟨θ, w * -w⟩ ≥ -ζ k + 2ζ k =ζ k .This implies that with probability at least 1 -δ, w * always survives.Define S k = w ∈ W | ⟨w * -w, θ⟩ ≤ 4ζ k . Thus with probability at least 1 -δ, we have k {W k ⊆ S k }. This implies the following is true with probability at least1 -δ for all k ρ(W k ) = min λ∈∆(Z) max w,w ′ ∈W k w -w ′ 2 ( z∈Z Γ ⊤ λzzz ⊤ Γ) -1 ≤ min λ∈∆(Z) max w,w ′ ∈S k w -w ′ 2 ( z∈Z Γ ⊤ λzzz ⊤ Γ) -1 = ρ(S k ).Define ∆ to be the minimum gap between w * and any other w ∈ W, i.e., ∆ := min w∈W\{w * } ⟨w * -w, θ⟩. Then for k ≥ log 4∆ -1 , we have S k = {w * } with probability at least 1 -δ. The total sample complexity is the summation of the number of samples in each round,EQUATION)On the other hand, we haveEQUATIONwhere the last inequality is by the triangle inequality, i.e., maxw,w ′ ∈S k w -w ′ 2 ( z∈Z Γ ⊤ λzzz ⊤ Γ) -1 ≤ max w,w ′ ∈S k ∥w -w * ∥ ( z∈Z Γ ⊤ λzzz ⊤ Γ) -1 + w * -w ′ ( z∈Z Γ ⊤ λzzz ⊤ Γ) -1 2 ≤4 max w∈S k ∥w -w * ∥ 2 ( z∈Z Γ ⊤ λzzz ⊤ Γ) -1 .Combining ( 16) and ( 17), we havelog(4∆ -1 ) k=1 N k ≤ c(1 + ω)L ν log 4∆ -1 log   log 4∆ -1 2 |W| δ   ρ * + log 4∆ -1 r(ω).Algorithm 6 Confounded pure exploration with known ΓInput Z, W, Γ, δ, ε, L ν ≥ σ 2 ν , L η ≥ σ 2 η Initialize: k = 1, Ŵk = W, calculate γ using (18) Define f (w, w ′ , Γ, λ) := ∥w -w ′ ∥ 2 ( z∈Z Γ ⊤ λzzz ⊤ Γ) -1 while ∃w, w ′ ∈ W k , s.t., w ′ -w, θ k oracle > 4γ or ζ k > γ do λ k = arg min λ∈∆(Z) max w,w ′ ∈W k f (w, w ′ , Γ, λ) ρ(W k ) = min λ∈∆(Z) max w,w ′ ∈W k f (w, w ′ , Γ, λ) ζ k = 2 -k N k = 2(1 + ω) ζ -2 k ∧ 1 γ 2 ρ(W k )L ν log 4k 2 |W| δ ∨ r(ω) Z N k = ROUND(λ k , N k ) Pull arms in Z N k and observe Y N k Compute θ k P-2SLS = Z ⊤ N k Z N k Γ -1 Z ⊤ N k Y N k W k+1 = W k \ w ∈ W k | ∃w ′ ∈ W k , s.t., w ′ -w, θ k P-2SLS > ζ k + γ k = k + 1 end while Output: any w ∈ W kTheorem I.1. Suppose that we have Γ that is an OLS estimate from an offline dataset {Z T , X T } collected non-adaptively through a fixed design ξ and the efficient rounding procedure ROUND,as well as T ≥ 4σ 2 η σmin(A(ξ,Γ)) log Z T , δ/2 . Algorithm 6 guarantees that with probability at least 1 -δ, a 6γ-good arm is returned, whereEQUATION)Also, the algorithm terminates in at mostc(1 + ω)L ν log 1/δ ρ * (γ) + c(1 + ω) 2 L ν log 1/δ σ 2 η log(Z T , δ) σ min A(ξ, Γ) ρ(ξ, γ) T ∨ cr(ω)samples, where c hides logarithmic factors of ∆ and |W| and γ.ρ(λ, γ) := maxw∈W\{w * } ∥w * -w∥ 2 A(λ,Γ) -1 ⟨w * -w, θ⟩ 2 ∨ γ 2 and ρ * (γ) = min λ∈∆(Z) max w∈W\{w * } ∥w * -w∥ 2 A(λ,Γ) -1 ⟨w * -w, θ⟩ 2 ∨ γ 2 .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 ⟨θ, w * -w⟩ ≥ 2ζ k + 2γ is eliminated.• The stopping condition is met in finite time.• When the stopping condition is met, there are only 6γ-good arms left.• 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 -δ 2k 2 |W| , for any k and w ∈ W k ,θ k P-2SLS -θ, w -w * ≤ ∥w -w * ∥ Ā(Z N k , Γ) -1 2σ 2 ν log 4k 2 |W| δ + γ ≤ √ 1 + ω∥w -w * ∥ A(λ k , Γ) -1 √ N k 2σ 2 ν log 4k 2 |W| δ + γ ≤ √ 1 + ω∥w -w * ∥ A(λ k , Γ) -1 2(1 + ω)ζ -2 k ρ(W k )L ν log 4k 2 |W| δ ∨ r(ω) 2σ 2 ν log 4k 2 |W| δ + γ ≤ ζ k + γ.Define a good event E k,w for each k and w ∈ W k asE k,w = θ k P-2SLS -θ, w -w * ≤ ζ k + γ .By the same calculation as (15) , we claim that with probability at least 1 -δ, the event ∞ k=1 w∈W k E k,w holds. Under the event ∞ k=1 w∈W k E w,k , to show that the best arm is never eliminated, it suffices to show that for any sub-optimal arm w ∈ W k ,w -w * , θ k P-2SLS = w -w * , θ k P-2SLS -θ + ⟨w -w * , θ⟩ ≤ w -w * , θ k P-2SLS -θ ≤ ζ k + γ.Thus the best arm w * never satisfies the elimination condition.Step 2: At the end of stage k, any suboptimal arm w that satisfies ⟨θ, w * -w⟩ ≥ 2ζ k + 2γ is eliminated.To prove this, we show that such arm w must satisfy the elimination condition,max w ′ ∈W k θ k P-2SLS , w ′ -w ≥ θ k P-2SLS , w * -w = θ k P-2SLS -θ, w * -w + ⟨θ, w * -w⟩ ≥ -ζ k -γ + 2ζ k + 2γ =ζ k + γ.Thus the arm w is eliminated.Step 3: The stopping condition is met in finite time.Step 2 and the fact that ζ k is an exponentially decreasing sequence, we know that all of the arms w satisfying ⟨θ, w * -w⟩ > 2γ will be eliminated in finite time. This means that only the arms w satisfying ⟨θ, w * -w⟩ ≤ 2γ will remain. We need to show that ∀w, w ′ ∈ W k , w ′ -w, θ k P-2SLS ≤ 4γ can be achieved in finite time. When ζ k ≤ γ, (which will happen in finite time),w ′ -w, θ k P-2SLS = w ′ -w + w * -w * , θ k P-2SLS = w * -w, θ k P-2SLS + w ′ -w * , θ k P-2SLS = w * -w, θ k P-2SLS -θ + θ + w ′ -w * , θ k P-2SLS -θ + θ = w * -w, θ k P-2SLS -θ + ⟨w * -w, θ⟩ + w ′ -w * , θ k P-2SLS -θ + w ′ -w * , θ ≤ζ k + γ + 2γ + ζ k + γ =4γ.Step 4: When the stopping condition is met, there are only 6γ-good arms left.For any w ∈ W k , we have⟨w * -w, θ⟩ = w * -w, θ -θ k P-2SLS + w * -w, θ k P-2SLS ≤ζ k + γ + 4γ =6γ.Step 5: The upper bound of the sample complexity. EQUATION)Note that the factor of min λ∈∆(Z) max w,w ′ ∈S k ∥w -w ′ ∥ 2 A(λ,Γ) -1 has the underlying true Γ in it, while the algorithm uses the plugged-in Γ. We need to relate it to ρ(S k ) := min λ∈∆(Z) max w,w ′ ∈S k ∥w -w ′ ∥ 2 A(λ, Γ) -1 . By Lemma J.9, and defining λ * z (S k ) as the optimal design for S k , i.e.,EQUATION)where the last inequality is due tow -w ′ 2 A(λ ′ k ,Γ) -1 ≤ w -w ′ 2 A( 1 2 λ * k + 1 2 ξ,Γ) -1 ≤ w -w ′ 2 A( 1 2 λ * k ,Γ) -1 =2 w -w ′ 2 A(λ * k ,Γ) -1, as well as, by Lemma J.11, when T ≥ 4σ 2 η σmin(A(ξ,Γ)) log Z T , δ/2 , we have, with probability at least 1 -δ/2, we havemax w,w ′ ∈S k (Γ -⊤ -Γ -⊤ ) w -w ′ 2 A(λ ′ k ,I) -1 ≤ 4σ 2 η log Z T , δ/2 σ min A(λ ′ k , Γ) max w,w ′ ∈S k w -w ′ 2 A(ξ,Γ) -1 1 T ≤ 4σ 2 η log Z T , δ/2 σ min A(αλ * k + (1 -α)ξ, Γ) max w,w ′ ∈S k w -w ′ 2 A(ξ,Γ) -1 1 T ≤ 8σ 2 η log Z T , δ/2 σ min A(ξ, Γ) max w,w ′ ∈S k w -w ′ 2 A(ξ,Γ) -1 1 T .We can lower bound ρ * (γ) byEQUATIONGiven ( 19), ( 20) and ( 21), we havek * k=1 N k ≤ c(1 + ω)L ν log 1/δ ρ * (γ) + c(1 + ω) 2 L ν log 1/δ σ 2 η log(Z T , δ) σ min A(ξ, Γ) ρ(ξ, γ) T + cr(ω),where c hides logarithmic factors of ∆ and |W| and γ.Algorithm 7 Optimal design with unknown ΓInput Z, W, δ, L ν ≥ σ 2 ν , L η ≥ σ 2 η , ω, γ min ≤ λ min (Γ), λ E , κ 0 Initialize: k = 1, W 1 = W, Γ 0 =⊥, ζ 1 = 1 Define f (w, w ′ , Γ, λ) := ∥w -w ′ ∥ 2 ( z∈Z Γ ⊤ λzzz ⊤ Γ) -1 , M := 32Lη γ 2 min σmin(A(λ E ,I)) ∨ 1, δ k,ℓ := δ 4k 2 ℓ 2 while |W k | > 1 do Γ k = Γ -estimator W k , Γ k-1 , ζ k , δ, k, ω, λ E , M, L η ▷ Step 1: update Γ θ k P-2SLS = θ -estimator W k , δ, ζ k , Γ k , ω, L ν , k ▷ Step 2: update θ W k+1 = W k \ w ∈ W k | ∃w ′ ∈ W k , s.t., w ′ -w, θ k P-2SLS > ζ k ▷ Step 3: elimination k ← k + 1, ζ k = 2 -k end while Output: W kThe algorithms of Γestimator and θestimator we present below are 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 W k , Γ k-1 , ζ k , δ, k, ω, λ E , M, L η Define Stop(W, Z, Γ, δ) := max w,w ′ ∈W w -w ′ Ā(Z,Γ) -1 ∥θ∥ 2 L η log(Z, δ) Initialize ℓ = 1, N k,0,0 = 0 ▷ doubling trick initialization if k = 1 then while ℓ = 1 or Stop W k , Z k,0,ℓ , Γ k , δ k,ℓ > 1 do get 2 ℓ-1 r(ω) ∨ 2 κ0 samples denoted as Z k,0,ℓ , X k,0,ℓ , Y k,0,ℓ per design λ E ▷ via ROUND Update Γ k by OLS on Z k,0,ℓ , X k,0,ℓ , ℓ ← ℓ + 1 end while else λk = arg min λ∈∆(Z) max w,w ′ ∈W k f (w, w ′ , Γ k-1 , λ) N ′ = 4gdM ln 1 + 2M d + L 2 z + 2M 2gdM + 8M ln 2•6 d δ k,1 ∨ r(ω) while ℓ = 1 or Stop W k , Z k,0,ℓ ∪ Z k,1,ℓ , Γ k , δ k,ℓ > ζ k do N k,1,ℓ = 2 ℓ N ′ ▷ doubling trick update get N k,1,ℓ samples per λk denoted as Z k,1,ℓ , X k,1,ℓ , Y k,1,ℓ ▷ via ROUND N k,0,ℓ = 2gdM ln M d + N k,1,ℓ + L 2 z + 4M ln 2•6 d δ k,ℓ ∨ r(ω) ∨ 2 κ0 get (N k,0,ℓ -N k,0,ℓ-1 ) samples per λ E augmented to Z k,0,ℓ-1 , X k,0,ℓ-1 and get Z k,0,ℓ , X k,0,ℓ Update Γ k by OLS on Z k,0,ℓ ∪ Z k,1,ℓ , X k,0,ℓ ∪ X k,1,ℓ , ℓ ← ℓ + 1 end while end if Output: Γ k Algorithm 9 θ -estimator Input W k , δ, ζ k , Γ k , ω, L ν , k λ k = arg min λ∈∆(Z) max w,w ′ ∈W k f (w, w ′ , Γ k , λ) ρ(W k ) = min λ∈∆(Z) max w,w ′ ∈W k f (w, w ′ , Γ k , λ) N k,2 = 2(1 + ω)ζ -2 k ρ(W k )L ν log 4k 2 |W| δ ∨ r(ω) get N k,2 samples per design λ k denoted as Z k,2 , X k,2 , Y k,2 ▷ via ROUND update θ k P-2SLS = ( Γ ⊤ k Z ⊤ k,2 Z k,2 Γ k ) -1 Γ ⊤ k Z ⊤ k,2 Y k,2 Output: θ k P-2SLSLemma J.1. Algorithm 3 and N k,1,ℓ , N k,0,ℓ guarantees three properties:• Property 1: N k,1,ℓ ≥ N k,0,ℓ . • Property 2: 1 2 N k,0,ℓ + N k,1,ℓ ≤ N k,0,ℓ-1 + N k,1,ℓ-1 .• Property 3:N k,1,1 8d ln 1+ N k,1,1 L 2 z d +16 ln 2•6 d k 2 δ ≤ M ln(dM ).Proof. For Property 1, recall that N k,0,ℓ and N k,1,ℓ are defined asN k,0,ℓ =     2gdM ln M d + N k,1,ℓ + L 2 z + 4M ln 2•6 d δ k,ℓ ∨ r(ω)     and N k,1,ℓ = 2 ℓ     4gdM ln 1 + 2M d + L 2 z + 2M 2gdM + 8M ln 2•6 d δ k,1 ∨ r(ω)     .We prove the result by induction. For the result for ℓ = 1, note that N k,1,1 is of the form N k,1,1 = 2a + 2b ln(1 + 2c + 2bd) and N k,0,1 is of the form N k,0,1 = a + b ln(c + dr), where• a = 4M ln 2•6 d δ k,1 • b = 2gdM • c = M d + L 2 z • d = M • r = N k,1,ℓ .By the contraposition of Lemma K.5, we haver > 2a + 2b ln(1 + 2c + 2bd) =⇒ r > a + b ln(c + dr).Thus we have N k,1,1 ≥ N k,0,1 . Now we assume the result holds for ℓ, i.e., N k,1,ℓ ≥ N k,0,ℓ and prove that it holds for ℓ + 1. We haveN k,1,ℓ+1 = 2N k,1,ℓ ≥ 2N k,0,ℓ .It suffices to prove that2N k,0,ℓ ≥ N k,0,ℓ+1 .We have2N k,0,ℓ =2     2gdM ln M d + N k,1,ℓ + L 2 z + 4M ln 2•6 d δ k,ℓ ∨ r(ω)     ≥2gdM ln M 2 d + N k,1,ℓ + L 2 z 2 + 8M ln 2•6 d ℓ 2 δ k,1 ∨ r(ω) ≥2gdM ln M 2 d + N k,1,ℓ + L 2 z 2 + 8M   ln 2•6 d δ k,1 + 2 ln(ℓ)   ∨ r(ω) ≥2gdM ln M 2 d + N k,1,ℓ + L 2 z 2 + 4M   ln 2•6 d δ k,1 + 2 ln(ℓ + 1)   ∨ r(ω)(2 ln ℓ ≥ ln(ℓ + 1) for ℓ ≥ 2)≥2gdM ln M d + 2N k,1,ℓ + L 2 z + 4M ln 2•6 d (ℓ + 1) 2 δ k,1 ∨ r(ω) =N k,0,ℓ+1 .For Property 2, it suffices to prove that1 2 N k,0,ℓ ≤ N k,0,ℓ-1 .This is equivalent to prove that1 2 a + b ln(c + 2dr) ≤ a + b ln(c + dr).We have1 2 a + b ln(c + 2dr) ≤ a + b ln(c + dr) ⇐⇒ 1 2 b ln(c + 2dr) ≤ 1 2 a + b ln(c + dr) ⇐⇒ b ln √ c + 2dr ≤ 1 2 a + b ln(c + dr) ⇐= √ c + 2dr ≤ c + dr ⇐⇒ c + 2dr ≤ c 2 + 2cdr + d 2 r 2 ⇐⇒ dr(dr + 2c -2) + c 2 -c ≥ 0.The last inequality holds because c = M > 1.For Property 3, we have,4dM ln 1 + 2M d + L 2 z + 2M dM + 8M ln 2•6 d k 2 δ 8d ln 1 + N k,1,1 L 2 z d + 16 ln 2•6 d k 2 δ ≤ 4dM ln 1 + 2M d + L 2 z + 2M dM 8d ln 1 + N k,1,1 L 2 z d + 16 ln 2•6 d k 2 δ + 8M ln 2•6 d k 2 δ 8d ln 1 + N k,1,1 L 2 z d + 16 ln 2•6 d k 2 δ ≤ M ln 1 + 2M d + L 2 z + 2M dM 2 ln (1 + M L 2 z ) + M 2 (loosely apply N k,1,1 ≥ dM )≤M ln(dM ).Theorem J.2. Algorithm 3 guarantees that with probability at least 1 -δ, the best arm is returned, and the algorithm terminates in at most(1 + ω) L ν log 1/δ + L η ∥θ∥ 2 2 d + log 1/δ ρ * + d + log 1/δ L η ∥θ∥ 2 2 ρ 0 + Mpulls, ignoring both of the additive and multiplicative logarithms of ∆, |W|, ρ * , ρ 0 , M , whereρ * = min λ∈∆(Z) max w∈W\{w * } ∥w * -w∥ 2 ( z∈Z λzΓ ⊤ zz ⊤ Γ) -1 ⟨w * -w, θ⟩ 2 ,andρ 0 = max w∈W\{w * } ∥w * -w∥ 2 ( z∈Z λ E,z Γ ⊤ zz ⊤ Γ) -1 ,andM = 32L η γ 2 min σ min A(λ E , I) ∨ 1.Note that ρ 0 does not get hurt by ⟨w * -w, θ⟩. It comes from the fact that in the first phase, we initialize that algorithm with E-optimal design.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 (12) .θ P-2SLS -θ, w = T2 q=1   T2 t=1 z It z ⊤ It Γ   -1 z Iq , w ν q + Γ -1 -Γ -1 Γθ, w .Given Γ, for a w ∈ W, with probability at least 1 -δ 2 the first term satisfiesT2 q=1   T2 t=1 z It z ⊤ It Γ   -1 z Iq , w ν q ≤ ∥w∥ Ā(Z T 2 , Γ) -1 2σ 2 ν log 4 δ .For any w ∈ W, with probability at least 1 -δ 2 , the second term satisfiesΓ -1 -Γ -1 Γθ, w ≤ ∥w∥ Ā(Z T 1 , Γ) -1 ∥θ∥ 2 σ 2 η log Z T1 , δ/4 .Note that by Lemma G.4, the above inequality holds for all w ∈ W, and the RHS is essentially a result ofV -1/2 Z ⊤ T S op ≤ σ 2 η log Z T , δ/4 .In the vanilla form of the confidence of P-2SLS, we can define good events as• for the first term, for any w ∈ W,T2 q=1   T2 t=1 z It z ⊤ It Γ   -1 z Iq , w ν q ≤ ∥w∥ Ā(Z T 2 , Γ) -1 2σ 2 ν log 16k 2 |W|/δ .• for the second term,V -1/2 Z ⊤ T S op ≤ σ 2 η log Z T , δ/4 .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 as the samples from each doubling trick iteration satisfies the self-normalized concentration inequality of Lemma G.4.We define the good event for ℓ-th doubling trick iteration in the first sub-phase of phase k asE 1 k,ℓ = V -1/2 k,ℓ Z ⊤ k,ℓ S k,ℓ 2 op ≤ σ 2 η log Z k,ℓ , δ 4k 2 (ℓ + 1) 2 ,whereZ k,ℓ = Z k,0,ℓ ∪ Z k,1,ℓ , V k,ℓ = Z ⊤ k,ℓ Z k,ℓand S k,ℓ is stacked noise matrix during collecting samples Z k,ℓ per the model X = ZΓ + S. By a union bound, we haveP      ∞ k=1 ∞ ℓ=1 E 1 k,ℓ   c    ≤ ∞ k=1 ∞ ℓ=1 P E 1 k,ℓ ≤ δ/2.For the second sub-phase in phase k, we define the good event for the second sub-phase in phase k and w ∈ W asE 2 k,w =      N k,2 q=1   N k,2 t=1 z It z ⊤ It Γ   -1 z Iq , w ν q ≤ ∥w∥ Ā(Z k,2 , Γ) -1 2σ 2 ν log 16k 2 |W|/δ     .By a union bound, we haveP      ∞ k=1 w∈W k E 2 k,w   c    ≤ ∞ k=1 w∈W P E 2 k,w ≤ δ/2.Under the good event∞ k=1 ∞ ℓ=1 E 1 k,ℓ ∞ k=1 w∈W k E 2 k,w, we have with probability at least 1 -δ, for all k and w ∈ W,θ k P-2SLS -θ, w -w * ≤ ζ k .The rest of proof is same as the proof of Theorem 3.1.Recall that λ E = arg max λ∈∆(Z) σ min z∈Z λ z zz ⊤ is the E-optimal design to maximize the minimum singular value of z∈Z λ z zz ⊤ and κ 0 = max λ σ min ( z∈Z λ z zz ⊤ ) is the maximum minimum singular value of z∈Z λ z zz ⊤ . At the beginning of first sub-phase in phase k, the algorithm first samples N k,0,0 arms according to λ E .Before we proceed to the main proof of the sample complexity, we first address a minor technique issue to avoid cumbersomeness. For the logarithmic term that appears in the algorithm and confidence interval,log(Z T , δ) := 8d ln 1 + 2T L 2 z d(2 ∧ σ min (Z ⊤ T Z T )) + 16 ln   2•6 d δ • log 2 2 4 2 ∧ σ min (Z ⊤ T Z T )   , when 2 ∧ σ min (V ) = 2, it is equivalent to log(T, δ) := 8d ln 1 + T L 2 z d + 16 ln 2•6 d δ .Our algorithm design guarantees that 2 ∧ σ min (V ) = 2 is always true whenever we need to use the logarithmic term log(Z T , δ), given that the samples of our interest always includes the E-optimal design samples Z k,0,ℓ and the number of samples from the E-optimal design Z k,0,ℓ is always larger than 2 κ0 . So for the remaining part of the proof, we will use log(N, δ) instead of log(Z T , δ). Denote the samples of E-optimal design that mixed into the samples from ℓ-th doubling trick iteration in the first sub-phase of phase k as Z k,0,ℓ and Z k,0,ℓ = N k,0,ℓ . By Lemma J.3, our choice of N k,0,ℓN k,0,ℓ ≥ 64gdσ 2 η σ min A(λ E , Γ) ln 32gσ 2 η σ min A(λ E , Γ) d + N k,1,ℓ L 2 z + L 2 z + 128gσ 2 η σ min A(λ E , Γ) ln 2•6 d δ ,is a sufficient condition to guaranteeEQUATIONMultiply both sides of ( 22) byN k,0,ℓ +N k,1,ℓ N k,0,ℓand we haveN k,0,ℓ + N k,1,ℓ ≥   4gσ 2 η log N k,0,ℓ + N k,1,ℓ , δ k,ℓ σ min A(λ E , Γ) ∨ r(ω)   N k,0,ℓ + N k,1,ℓ N k,0,ℓ .By Property 1 of Lemma J.1, we have α k,ℓ :=EQUATIONThese condition on N k,0,ℓ and N k,0,ℓ + N k,1,ℓ are needed for the proof.Denote the total number of doubling trick iterations as L k for phase k. In the case of L k = 1, 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 isN k,0,1 + N k,1,1 ≤2N k,1,1 (Property 1 of Lemma J.1) ≤8gdM ln 1 + 2M d + L 2 z + 2M 2gdM + 16M ln 2•6 d δ k,1 ∨ r(ω).In the case ofL k > 1, for ℓ ∈ {1, • • • , L k }, denote Γ ℓas the estimate of Γ at the end of the ℓ-th doubling trick iteration. With these notations, we have• At the end of L k -th doubling trick iteration, the stopping condition is satisfied, i.e., maxEQUATIONWe short log N k,0,ℓ + N k,1,ℓ , δ k,ℓ = log k,ℓ .• At the end of (L k -1)-th doubling trick iteration, the stopping condition is not satisfied, i.e., maxEQUATIONDenote ξ L k as the empirical distribution of Z k,0,L k ∪ Z k,1,L k . Then above two conditions imply that the number of samples for L k -th and (L k -1)-th doubling trick iterations respectively satisfyEQUATIONandEQUATIONNote that by Property 2 of Lemma J.1,1 2 N k,0,L k + N k,1,L k ≤ N k,0,L k -1 + N k,1,L k -1 .ThusEQUATIONFor any ℓ ∈ {1, . . . , L k }, by Lemma J.7, the factor of max w,wEQUATIONWe will upper bound the three terms in the RHS of (29) separately.For the first term, by Lemma J.6,EQUATION)where λk is the optimal design for W k in the first sub-phase of phase k -1 (based on the last doubling trick iteration), i.e., λk = arg minλ∈∆(Z) max w,w ′ ∈W k w -w ′ 2 A(λ, Γ L k-1 ) -1 .Then for any λ,EQUATIONwhere for (b 1 ), we plug inλ ′ k := α * k λ E + (1 -α * k )λ * k , with α * k ≤ 1/2will be defined later and λ * k is the optimal design for W k given Γ, i.e.,λ * k = arg min λ∈∆(Z) max w,w ′ ∈W k w -w ′ 2 A(λ,Γ) -1 .(b 2 ) is due to the fact that α * k ≤ 1/2. For the second term in the RHS of (31) , given the condition (23), i.e.,N k-1,0,L k-1 + N k-1,1,L k-1 ≥ 4gL η log k-1,L k-1 σ min A(ξ L k-1 , Γ)by Lemma J.11 we have,EQUATIONwhere for (b 1 ), we use the condition (22) on N k-1,0,L k-1 , and (b 2 ) is due to Lemma J.5. Plug (32) into (31) , we haveEQUATIONPlug ( 33) into (30) , we have the first term in the RHS of ( 29) can be upper bounded byEQUATIONwhere for the last inequality we use the fact that the stopping condition is satisfied at the end of (L k-1 )-th doubling trick iteration for phase k -1 per (26) .For the second term in the RHS of (29) , by Lemma J.10, when the condition ( 23) is satisfied, i.e., whenEQUATIONwhere the last inequality is due to Lemma J.5.For the third term in the RHS of (29) , by Lemma J.11, when the condition ( 23) is satisfied, i.e., whenEQUATIONwhere (b 1 ) is due to (26) , (b 2 ) is due to (22) . Plug ( 34), ( 35) and ( 36) into (29), we haveEQUATION)With ℓ = L k -1 and the fact that g > 24 whose exact value will be set later, we can rearrange (37) asEQUATION)Note that the LHS of above can be lower bounded by (28) ,EQUATION)Rearrange the terms in (39) and (38) and setting g to be larger enough and using the fact thatζ k = ζ k-1 /2, we have N k,0,L k + N k,1,L k ≤ 576 ζ 2 k ∥θ∥ 2 2 L η log k,L k -1 max w,w ′ ∈W k w -w ′ 2 A(λ * k ,Γ) -1 + 72 g log k,L k -1 log k-1,L k-1 (N k-1,0,L k-1 + N k-1,1,L k-1 ).Note that by definition log k,L k -1 < log k,L k , thusN k,0,L k + N k,1,L k ≤ 576 ζ 2 k ∥θ∥ 2 2 L η log k,L k max w,w ′ ∈W k w -w ′ 2 A(λ * k ,Γ) -1 + 72 g log k,L k log k-1,L k-1 (N k-1,0,L k-1 + N k-1,1,L k-1 ).Denote D k := N k,0,L k + N k,1,L k and divide both sides of above by log k,L k , we haveD k log k,L k ≤ 576 ζ 2 k ∥θ∥ 2 2 L η max w,w ′ ∈W k w -w ′ 2 A(λ * k ,Γ) -1 + 72 g D k-1 log k-1,L k-1 .In the case of L k = 1, by Property 3 of Lemma J.1, we haveD k log k,L k = N k,1,1 8d ln 1 + N k,1,1 L 2 z d + 16 ln 2•6 d k 2 δ ≤ M ln(dM ).Thereby we haveEQUATION)Taking a summation over k on both sides of (40), we haveEQUATIONThus by setting g = 72 × 2 and rearranging the terms, we haveEQUATION)For D 1 , which corresponds to the first sub-phase where we use E-optimal design with doubling trick, we have the stopping condition,max w,w ′ ∈W1 w -w ′ 2 Ā(Z 1,0,L 1 , Γ L 1 ) -1 ∥θ∥ 2 2 L η log 1,L1 ≤ ζ 2 1 .This implies that when the stopping condition is metEQUATIONandEQUATIONSince we use E-optimal design for the first phase, the factor of w -w ′ 2 A(ξ L 1 -1 , Γ L 1 -1 ) -1 can be upper bounded byEQUATIONPlug ( 48) into (47), and use the fact that 2N 1,0,L1-1 = N 1,0,L1 , ζ 1 = 1, we haveEQUATION)Thus we have,D 1 log 1,L1 ≤ 2N 1,0,L1 log 1,L1 ≤ 48∥θ∥ 2 2 L η max w,w ′ ∈W1 w -w ′ 2 A(λ E ,Γ) -1 =: ρ 1 .By the same calculation as ( 17) and ( 19), we have∥θ∥ 2 2 L η K * k=2 1 ζ 2 k max w,w ′ ∈W k w -w ′ 2 A(λ * k ,Γ) -1 ≤ c∥θ∥ 2 2 L η K * ρ * =: ρ 2 ,where c is an absolute constant. Next we lower bound the left hand side of (45). To do this, we first upper bound log k,L k asEQUATIONwhere the inequality above uses the fact that L k is the index of the last doubling trick iteration for phase k, by the design of the doubling trick, we haveL k ≤ log 2 D k d . K * k=1 D k log k,L k = K * k=1 D k 8d ln 1 + D k L 2 z d + 16 ln 2•6 d k 2 L 2 k δ ≥ K * k=1 D k 32d ln 1 + D k L 2 z d + 16 ln 2•6 d K * 2 δ (due to (50)) ≥ K * k=1 D k 32d ln 1 + K * k=1 D k L 2 z d + 16 ln 2•6 d K * 2 δ = 1 32d ln 1 + K * k=1 D k L 2 z d + 16 ln 2•6 d K * 2 δ K * k=1 D k .Denote ρ 3 := K * M ln(dM ), looking back at (44), we haveK * k=1 D k ≤   32d ln 1 + K * k=1 D k L 2 z d + 16 ln 2•6 d K * 2 δ   (ρ 1 + ρ 2 + ρ 3 ).By Lemma K.5, we haveEQUATIONSample complexity for second sub-phaseThe design for the second sub-phase of phase k is based on Γ L k , the estimate of Γ at the end of the L k -th doubling trick iteration in the first sub-phase of phase k,λk = arg min λ∈∆(Z) max w,w ′ ∈W k w -w ′ 2 A(λ, Γ L k ) -1 .Then for any λ, by Lemma J.7 we havemax w,w ′ ∈W k w -w ′ 2 A( λk , Γ L k ) -1 ≤3 max w,w ′ ∈W k w -w ′ 2 A(λ,Γ) -1 + 2 max w,w ′ ∈W k (Γ -⊤ -( Γ L k ) -⊤ ) w -w ′ 2 A(λ,I) -1We plug inEQUATIONwhere the last inequality is due to the fact that α * k ≤ 1/2. For the second term in the RHS of above, by Lemma J.11 we have,EQUATIONwhere for (b 1 ), we have N k,0,L k ≥ 4gLη log k,L k σmin(A(λ E ,Γ)) , and (b 2 ) is due to Lemma J.5. Plug (53) into (52), we haveEQUATIONwhere the last inequality is due to (26) . According to the algorithm design, the number of samples in the second sub-phase of phase k is defined asN k,2 =     2(1 + ω)ζ -2 k ρ(W k )L ν log 4k 2 |W| δ     ∨ r(ω), with ρ(W k ) = min λ∈∆(Z) max w,w ′ ∈W k ∥w -w ′ ∥ 2 A(λ, Γ L k ) -1 .Then we have, by setting g ≥ 4,N k,2 ⪅ (1 + ω)ζ -2 k L ν max w,w ′ ∈W k w -w ′ 2 A(λ * k ,Γ) -1 log 4k 2 |W| δ + (1 + ω)(N k,0,L k + N k,1,L k ),where '⪅' hides logarithmic factors of |W| for the second term and constants for simplicity. Plug (54) into the above inequality. Also note that by Lemma 2.1, we can always set L ν = 2(∥θ∥2 2 L η + 1). Thus, K * k=1 N k,2 ⪅(1 + ω) K * k=1 ζ -2 k L ν max w,w ′ ∈W k w -w ′ 2 A(λ * k ,Γ) -1 log 4k 2 |W| δ + (1 + ω) K * k=1 (N k,0,L k + N k,1,L k ) ⪅(1 + ω)K * L ν ρ * log 4K * 2 |W| δ + (1 + ω) K * k=1 (N k,0,L k + N k,1,L k ).This essentially means that the sample complexity for the second sub-phase N k,2 can be upper bounded by summation of the sample complexity we pay for Algorithm 1 and the sample complexity of the first sub-phase 51) and (55), we conclude the result.K * k=1 (N k,0,L k + N k,1,L k ). Combine (Lemma J.3. Denote log N k,0 , δ k,0 = 8d ln 1 + N k,0 L 2 z d + 16 ln 2•6 d δ .A sufficient condition forEQUATION)to hold isN k,0,ℓ ≥ 16gdσ 2 η σ min A(λ E , Γ) ln 8g σ min A(λ E , Γ) d + N k,1,ℓ L 2 z + L 2 z + 32gσ 2 η σ min A(λ E , Γ) ln 2•6 d δ . Proof. Given log N k,0,ℓ + N k,1,ℓ , δ k,ℓ = 8d ln 1 + (N k,0,ℓ + N k,1,ℓ )L 2 z d + 16 ln 2•6 d δ .By Lemma J.4, for the formulaX ≥ A ln (D + BX) + C we have • A = 8gdσ 2 η σmin(A(λ E ,Γ)) , • B = L 2 z d , • C = 16gσ 2 η σmin(A(λ E ,Γ)) ln 2•6 d δ , • D = 1 + N k,1,ℓ L 2 z d .Thus a sufficient condition for the inequality to hold isN k,0,ℓ ≥ 16gdσ 2 η σ min A(λ E , Γ) ln   8gdσ 2 η σ min A(λ E , Γ) 1 + N k,1,ℓ L 2 z d + L 2 z d   + 32gσ 2 η σ min A(λ E , Γ) ln 2•6 d δ = 16gdσ 2 η σ min A(λ E , Γ) ln 8gσ 2 η σ min A(λ E , Γ) d + N k,1,ℓ L 2 z + L 2 z + 32gσ 2 η σ min A(λ E , Γ) ln 2•6 d δ . Lemma J.4. Let X ≥ 1, A, B ≥ 0, then a sufficient condition for X ≥ A ln (D + BX) + C is X ≥ 2A ln(AD + AB) + 2C.Proof. The proof is motivated by Gales et al. [16] . Let f ∈ (0, 1), thenX ≥ A ln (D + BX) + C ⇔X ≥ A ln f X A + A ln A f D X + B + C ⇐X ≥ A f X A -1 + A ln A f D X + B + C (since ln(x) ≤ x -1) ⇐X(1 -f ) ≥ A ln A 2f D X + B + C ⇔X ≥ 1 1 -f A ln A 2f D X + B + c 1 -f .Set f = 1/2 and by the fact X ≥ 1, we have X ≥ 2A ln(AD + AB) + 2C.Lemma J.5. Suppose that we have a data set {Z T , X T }. Denote the empirical distribution of Z T as ξ. The number of samples satisfiesT ≥ 8σ 2 η σ min A(ξ, Γ) log(Z T , δ) ∨ r(ω). Γ is the OLS estimate of Γ based on {Z T , X T }. Then ∥w∥ 2 A(ξ,Γ) -1 ≤ 6∥w∥ 2 A(ξ, Γ) -1 .Proof. By Lemma J.7, we have∥w∥ 2 A(ξ,Γ) -1 ≤3∥w∥ 2 A(ξ, Γ) -1 + 2 (Γ -⊤ -Γ -⊤ )w 2 A(ξ,I) -1 ≤3∥w∥ 2 A(ξ, Γ) -1 + 1 2 ∥w∥ 2 A(ξ,Γ) -1 ,where the last inequality is due to Lemma J.10 with g = 2. Rearranging the terms, we have∥w∥ 2 A(ξ,Γ) -1 ≤ 6∥w∥ 2 A(ξ, Γ) -1 .Lemma J.6. Suppose that we use ROUND to sample N 0 arms according to λ E denoted as Z 0 , and N 1 arms according to λ 1 denoted as Z 1 , with N 1 ≥ N 0 . Denote the empirical distribution of all the collected samples as ξ, then∥w∥ 2 A(ξ,Γ) ≤ 4∥w∥ 2 A(λ1,Γ) -1 .Proof. Denote the empirical distribution of Z 0 as ξ 0 , and the empirical distribution of Z 1 as ξ 1 , then we have∥w∥ 2 Ā(Z0∪Z1,Γ) -1 =w ⊤   z∈Z0∪Z1 Γ ⊤ zz ⊤ Γ   -1 w =w ⊤   z∈Z0 Γ ⊤ zz ⊤ Γ + z∈Z1 Γ ⊤ zz ⊤ Γ   -1 w =w ⊤   N 0 z∈Z ξ z,0 Γ ⊤ zz ⊤ Γ + N 1 z∈Z ξ z,1 Γ ⊤ zz ⊤ Γ   -1 w = 1 N 0 + N 1 w ⊤   N 0 N 0 + N 1 z∈Z ξ z,0 Γ ⊤ zz ⊤ Γ + N 1 N 0 + N 1 z∈Z ξ z,1 Γ ⊤ zz ⊤ Γ   -1 w ≤ 1 N 0 + N 1 w ⊤   N 1 N 0 + N 1 z∈Z ξ z,1 Γ ⊤ zz ⊤ Γ   -1 w ≤ 2 N 0 + N 1 w ⊤   z∈Z ξ z,1 Γ ⊤ zz ⊤ Γ   -1 w (N 1 ≥ N 0 ) ≤ 4 N 0 + N 1 w ⊤   z∈Z λ 1 Γ ⊤ zz ⊤ Γ   -1 w = 4 N 0 + N 1 ∥w∥ 2 A(λ1,Γ) -1 .The result follows by noting that∥w∥ 2 Ā(Z0∪Z1,Γ) -1 = 1 N 0 + N 1 ∥w∥ 2 A(ξ,Γ) .Lemma J.7. Suppose that we have an estimate Γ that is invertible, for any x ∈ R d and covariance matrix V , we haveEQUATIONProof. Suppose we have an estimate Γ. Then,∥x∥ 2 (Γ ⊤ V Γ) -1 = ∥x∥ 2 ( Γ ⊤ V Γ) -1 + ∥x∥ 2 (Γ ⊤ V Γ) -1 -∥x∥ 2 ( Γ ⊤ V Γ) -1 .Lemma J.10. Suppose that we have Γ that is an OLS estimate from an offline dataset {Z T1 , X T1 } collected non-adaptively through a fixed design λ and the efficient rounding procedure ROUND. Let V = Z ⊤ T1 Z T1 . Then, for any x ∈ R d and g ≥ 1, we have, with probability 1 -δ,EQUATION)where p is the cardinality of support of λ.Proof. We first show thatEQUATION(Lemma J.13:EQUATION.We can upper bound the the termEQUATION=: V by noticing that it appears in both of a 1 , a 2 above. Thus we have the inequalityV ≤ Γ -1 V -1 Γ -⊤ op V -1/2 Z ⊤ T1 S 2 op V -1/2 Γ -⊤ x 2 2 + V .By rearranging the terms, we haveEQUATION.By Lemma G.4, with probability 1 -δ, we haveV -1/2 Z ⊤ T1 S 2 op ≤ σ 2 η log(Z T1 , δ).Thus, with probability 1 -δ, we haveV ≤ 1 1 -Γ -1 V -1 Γ -⊤ op σ 2 η log(Z T1 , δ) Γ -1 V -1 Γ -⊤ op σ 2 η log(Z T1 , δ) V -1/2 Γ -⊤ x 2 2 .To further upper bound V, we first find a sufficient condition on T 1 such thatΓ -1 V -1 Γ -⊤ op σ 2 η log(Z T1 , δ) ≤ 1 2g , g ≥ 1. By Lemma J.14, when T 1 ≥ 2p, Γ -1 V -1 Γ -⊤ op σ 2 η log(Z T1 , δ) ≤ 2σ 2 η T 1 σ min z∈Z λ z Γ ⊤ zz ⊤ Γ log(Z T1 , δ).To upper bound the right hand side by 1 2g , we needEQUATIONWith this condition (58), we have with probability 1 -δ,EQUATION)Lemma J.11. Suppose that we have Γ that is an OLS estimate from an offline dataset {Z T1 , X T1 } collected non-adaptively through a fixed design λ and the efficient rounding procedure ROUND. Let V be any positive definite matrix. Then, for any x ∈ R d , we have, with probability 1 -δ,(Γ -⊤ -Γ -⊤ )x 2 V -1 ≤ 2 Γ -1 V -1 Γ -⊤ op σ 2 η log(Z T1 , δ)∥x∥ 2 Ā(Z T 1 ,Γ) -1 , when T 1 ≥ 4σ 2 η σ min A(λ, Γ) log(Z T1 , δ) ∨ 2p,where p is the cardinality of support of λ.Proof.EQUATION(Lemma J.13:(A + B) -1 = A -1 -(A + B) -1 BA -1 ) a2 ≤ Γ -1 V -1 Γ -⊤ op V -1/2 Z ⊤ T1 S 2 op V -1/2 Γ -⊤ x 2 2 + V -1/2 Γ -⊤ V -1 Z ⊤ T1 S ⊤ Γ + V -1 Z ⊤ T1 S -⊤ x 2 2 .Given the condition (58) holds, we have with probability 1 -δ,(Γ -⊤ -Γ -⊤ )x 2 V -1 a1 ≤ Γ -1 V -1 Γ -⊤ op V -1/2 Z ⊤ T1 S 2 op V -1/2 Γ -⊤ x 2 2 + V -1/2 Γ -⊤ x 2 2 =2 Γ -1 V -1 Γ -⊤ op V -1/2 Z ⊤ T1 S 2 op V -1/2 Γ -⊤ x 2 2 ≤2 Γ -1 V -1 Γ -⊤ op σ 2 η log(Z T1 , δ)∥x∥ 2 (Γ ⊤ V Γ) -1, where (a 1 ) is due to (59) and setting g = 1.Lemma J.12. For a least square estimate Γ that is estimated through a design matrix Z and Γ is invertible, we haveΓ -1 -Γ -1 = -Γ + V -1 Z ⊤ S -1 V -1 Z ⊤ SΓ -1 .Proof. Since Γ is a least square estimator, we have Γ = Γ + V -1 Z ⊤ S. By Lemma J.13, we haveΓ -1 -Γ -1 = Γ + V -1 Z ⊤ S -1 -Γ -1 = -Γ + V -1 Z ⊤ S -1 V -1 Z ⊤ SΓ -1 .Lemma J.13. For two invertible matrixes A, B ∈ R d×d , we have(A + B) -1 = A -1 -(A + B) -1 BA -1 .Proof. We have(A + B) -1 = A -1 + (A + B) -1 -A -1 = A -1 + (A + B) -1 A -I A -1 = A -1 + (A + B) -1 A -(A + B) A -1 = A -1 -(A + B) -1 BA -1 .Lemma J.14. Suppose that we have a design matrix Z T that is sampled from a distribution λ ∈ ∆ Z , with the efficient rounding procedure ROUND. Let p represent the cardinality of support of λ. We have, if T ≥ 2p,Γ ⊤ Z ⊤ T Z T Γ -1 op ≤ 2 T σ min z∈Z λ z Γ ⊤ zz ⊤ Γ .where σ min (•) is the smallest singular value of a matrix.Proof. Suppose that each arm z ∈ Z is sampled t z times, the empirical distribution of Z T is ξ := tz T z∈Z . Thus, we haveΓ ⊤ Z ⊤ T Z T Γ -1 op = 1 σ min Γ ⊤ Z ⊤ T Z T Γ = 1 σ min T z∈Z ξ z Γ ⊤ zz ⊤ Γ = 1 T σ min z∈Z ξ z Γ ⊤ zz ⊤ Γ . By Fiez et al. [15, Proposition 2], we have z∈Z ξ z Γ ⊤ zz ⊤ Γ ⪰ α z∈Z λ z Γ ⊤ zz ⊤ Γ,where α ∈ [ T T +2p , 1] when T ≥ 2p. Given the fact that both of z∈Z ξ z Γ ⊤ zz ⊤ Γ and z∈Z λ z Γ ⊤ zz ⊤ Γ are positive definite, we have σ min z∈Z ξ z Γ ⊤ zz ⊤ Γ ≥ ασ min z∈Z λ z Γ ⊤ zz ⊤ Γ . Thus, we haveΓ ⊤ Z ⊤ T Z T Γ -1 op ≤ 1 αT σ min z∈Z λ z Γ ⊤ zz ⊤ Γ .When T ≥ 2p, we have α ≥ 1/2, which implies the result.In this section, we introduce a simple adaptive procedure that finds a high probability lower bound on γ * min := λ min (Γ) that is sufficiently accurate (i.e., within a constant factor of γ * min ). For simplicity, we assume ∥z t ∥ ≤ 1, ∀t in this section.Our algorithm leverages confidence bounds to adaptively determine how many samples we like to take. Let Γt := (Z ⊤ Z) -1 Z ⊤ X be the least square estimate of Γ after sampling t times to obtain {(z s , x s )} t s=1 where Z ∈ R t×d and X ∈ R t×d are the design matrices. Let V t := t s=1 z s z ⊤ s . We define the lower and upper confidence bound for γ * min as follows:LCB(t) := λ min ( Γt ) - ψ t t , UCB(t) := λ min ( Γt ) + ψ t twhereψ t = σ -1 min 1 t V t • 8d ln 1 + 2t d(2 ∧ σ min (V t )) + 16 ln 2•6 d δ • log 2 2 4 2 ∧ σ min (V t ).and LCB(0) := -∞ and UCB(0) := ∞.The following lemma shows that LCB(t) and UCB(t) form a valid anytime confidence bound for γ * min . Lemma K.1. (Correctness of the confidence bounds)1 -δ ≤ P(∀t ≥ 1, LCB(t) ≤ γ * min ≤ UCB(t))Equipped with the confidence bounds, we are now ready to describe our algorithm for learning γ * min (see Algorithm 10) . Since the tightness of the confidence bounds depends on the smallest eigenvalue of V t , 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 λ * E and κ 0 is the smallest singular value achieved by λ * E . We take in a rounding procedure for the E-optimal design ROUND E (λ, t) that takes in t samples and design λ and outputs integer sample count assignments {N z } z∈Z so that if we sample according to these counts then we haveσ -1 min ( 1 t V t ) ≤ (1 + ω)κ -1 0 (60)After determining the base sample counts {m z } z∈Z by ROUND(λ * E , ⌈r(ω)⌉, ω), we start doubling the sample size until we satisfy the condition LCB(t) > 1 2 UCB(t). 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 j-1 ⌈r(ω)⌉. Once the loop stops, we return LCB(t) as the claimed lower approximation of the γ * min . Let N w be the total number of samples we used in Algorithm 10. Then, the next theorem shows that the estimate returned by our algorithm is both a valid lower bound to γ * min and sufficiently accurate.Algorithm 10 Learning λ min (Γ)Input: Arm set Z, rounding procedure ROUND E for the E-optimal design, rounding accuracy ω Initialize: j = 1, t = 0.Compute the E-optimal design λ * E for Z. Compute {m z } z∈Z by ROUND E (λ * E , ⌈r(ω)⌉). while LCB(t) ≤ 1 2 UCB(t) do t ← 2 j-1 ⌈r(ω)⌉. For each arm z ∈ Z, sample 2 j-1 m z -1{j ̸ = 1} 2 j-2 m z times. Estimate Γt using all samples collected so far (total t data points) j ← j + 1. We remark that Allen-Zhu et al. [2] provides a rounding procedure with r(ε) = O(d/ε 2 ).Proof of Lemma K.1. Note that Γ = Γ + V -1 t Z ⊤ S where Z, S ∈ R t×d is the design matrices with s-th row being z ⊤ s and η ⊤ s respectively. Using Lemma G. Proof of Theorem K.2. We assume ∀t ≥ 1, LCB(t) ≤ γ * min ≤ UCB(t), which happens with probability at least 1 -δ. Then, it is trivial to see that LCB(N w ) ≤ γ * min . For the other inequality, we use the fact that the stopping condition was satisfied with N w :LCB(N w ) > 1 2 UCB(N w ) ≥ γ * min 2 .This concludes the proof. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).We assume throughout that Γ ∈ R d×d is an invertible matrix.Our setting differs slightly from the traditional compliance setting based on a potential outcomes framework[3]. 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 θi and the local average treatment effect (LATE) on compilers are the same.Formally, we say that a set of data (ZT , XT , YT ) generated via the model in Eq. (1) is collected nonadaptively from an experimental design if zt is H0 measurable for all 1 ≤ t ≤ T . 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: My concerns are largely around two things: 
1. 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. 

2. 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.
questions: 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: limitations: See above.
paper_summary: paper_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.
strength_weakness: strength_weakness: The authors could enhance their study by conducting additional experiments to verify the robustness of their results.

Furthermore, there should be a more detailed discussion of the p-values and confidence intervals to strengthen the statistical analysis.
questions: questions: How to think of p-values/confidence intervals as it is important in an experimentation setting.
limitations: limitations: The authors adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1.	The 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. 
2.	The 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. 
3.	The authors might want to reconsider the title. The title, from my perspective, is a bit confusing and misleading.
questions: questions: 1.	Could 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: limitations: See above.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. No real-data demonstration of the proposed method.
questions: questions: N.A.
limitations: limitations: N.A.

Comments: comment: Thank you for your answers and clarifications to my questions/concerns. I will leave my score unchanged, but appreciate the points raised by the authors.
Dear reviewer Y9pp,

As we approach the end of the rebuttal period, we sincerely appreciate this last opportunity to further engage with the reviewer and clarify any outstanding questions or concerns. We thank the reviewer again for acknowledging the novelty of our problem formulation and the thorough analysis throughout. If our rebuttal has adequately addressed the points raised, we would kindly request that the reviewer re-evaluate the score accordingly. We remain open to any additional feedback.
Thank you for addressing my questions on the confidence interval. I will keep my score unchanged.
I have read the rebuttal carefully. Thanks for the clarification. I really appreciate your efforts!