Adaptive Instrument Design for Indirect Experiments
Authors: Yash Chandak
Shiv Shankar
Vasilis Syrgkanis
Emma Brunskill
Venue: ICLR 2024 poster (2024)
Keywords: instrument variable
experiment design
indirect experiments
adaptive design
Primary area: causal reasoning
TL;DR: We take the initial steps towards enhancing sample efficiency for \textit{indirect} experiments by adaptively designing a data collection policy over instrumental variables.

Abstract: Indirect experiments provide a valuable framework for estimating treatment effects in situations where conducting randomized control trials (RCTs) is impractical or unethical. Unlike RCTs, indirect experiments estimate treatment effects by leveraging (conditional) instrumental variables, enabling estimation through encouragement and recommendation rather than strict treatment assignment.  However, the sample efficiency of such estimators depends not only on the inherent variability in outcomes but also on the varying compliance levels of users with the instrumental variables and the choice of estimator being used, especially when dealing with numerous instrumental variables.  While adaptive experiment design has a rich literature for \textit{direct} experiments, in this paper we take the initial steps towards enhancing sample efficiency for \textit{indirect} experiments by adaptively designing a data collection policy over instrumental variables.  Our main contribution is a practical computational procedure that utilizes influence functions to search for an optimal data collection policy, minimizing the mean-squared error of the desired (non-linear) estimator. Through experiments conducted in various domains inspired by real-world applications, we showcase how our method can significantly improve the sample efficiency of indirect experiments.

Published as a conference paper at ICLR 2024
ADAPTIVE INSTRUMENT DESIGN FOR INDIRECT EXPERIMENTS
Yash Chandak
Shiv Shankar UMass Amherst
Vasilis Syrgkanis Stanford University
Emma Brunskill Stanford University
Stanford University
ABSTRACT
Indirect experiments provide a valuable framework for estimating treatment ef- fects in situations where conducting randomized control trials (RCT's is impracti- cal or unethical. Unlike RCTs, indirect experiments estimate treatment effects by leveraging (conditional) instrumental variables, enabling estimation through en- couragement and recommendation rather than strict treatment assignment. How- ever, the sample efficiency of such estimators depends not only on the inherent variability in outcomes but also on the varying compliance levels of users with the instrumental variables and the choice of estimator being used, especially when dealing with numerous instrumental variables. While adaptive experiment de- sign has rich literature for direct experiments, in this paper we take the initial steps towards enhancing sample efficiency for indirect experiments by adaptively designing a data collection policy over instrumental variables. Our main contri- bution is practical computational procedure that utilizes influence functions search for an optimal data collection policy, minimizing the mean-squared error of the desired (non-linear) estimator. Through experiments conducted in various domains inspired by real-world applications, we showcase how our method can significantly improve the sample efficiency of indirect experiments.
INTRODUCTION
Advances in machine learning, especially from large language models, are greatly expanding the potential of Al to augment and support humans in an enormous number of settings, such as help- ing direct teachers to students unproductively struggling while using math software (Holstein et al., 2018), providing suggestions to novice customer support operators (Brynjolfsson al., 2023), and helping peer volunteers learn to be more effective mental health supporters (Hsu et al.. 2023). AI- augmentation will often (importantly) provide autonomy to the human, who may consider infor- mation or suggestions provided by an AI, before ultimately making their own choice about how to proceed (we provide examples of more use-cases in Appendix B). In such settings it will be highly informative be able to separate estimating the strength of the intervention choices, as well as the actual treatment effects (the outcomes the human chooses to follow the treatment of interest), instead of estimating only intent-to to-ttttt effects. This estimation problem be- comes more challenging given the likely existence of latent confounders, that may influence both whether person is likely to uptake particular recommendation (such following large language model's 's recommendation of what to say to a customer). and their downstream outcomes (on cus- tomer satisfaction). Fortunately, if the AI intervention satisfies the requirements of an instrumental variable (Hartford et al., 2017; Syrgkanis et al., 2019), it is well-known when and how consistent estimates of the treatment effect estimates can be obtained.
humans" treatment
In this paper. we consider how to automatically learn data-efficient adaptive instrument-selection decision policies. in order to quickly estimate conditional average treatment effects. While adaptive experiment design well-studied when direct experimentation is feasible (Murphy, 2005; Xiong et al., 2019; Chaloner & Verdinelli, 1995; Rainforth et al., 2023; Che & Namkoong, 2023; Hahn et al., 2011; Kato et al., 2020; Song et al., 2023), it remains largely unexplored in situations where direct assignment to interventions is impractical, unethical or undesirable, such as for the real-time Al support of teachers, customer support agents, and volunteer mental health support trainees. Some work has considered adaptive data collection to minimize regret when using instrument variables (Kallus, 2018; Della Vecchia & Basu, 2023), which also relates to work in the multi-armed bandit literature. Other work has considered when user compliance may be dynamic, and shaped

---

Published as a conference paper at ICLR 2024
In randomized control trials (direct ex- periments), there is no unobserved confounding, iee, the value of the treatment the same as that of the instrument, Using adaptive experiment de- sign strategy of RCTs naively for indirect experi-
Figure 1:
Binary Instrument Treatment
Percent of MSE of Uniformm
1.2
1.0
Adaptive
RCT
ments, i.e., when confounding does exists, can re-
0.9
DIA
sult in performance worse than the uniform sam- pling strategy. In contrast, the proposed algo-
Uniform
0.7-
Oracle
rithm for designing instruments adaptively (DIA)
0.6
more effective for indirect experiments.
0.5
Confounder Strength x10
time (Ngo et al., 2021). In contrast, our work focuses on estimating treatment effects through the use of adaptive allocation of instruments, but the impact of those instruments is assumed to be statie, though unknown. As Figure demonstrates, we will shortly show that is possible to create adaptive instrumental strategies that far outperform standard uniform allocation. In particular, our paper address this challenge of adaptive instrument design through two main avenues:
1. A general framework for adaptive indirect experiments: We envision modern scenarios where available instruments could be high-dimensional, even encompassing natural language (e.g,, personalised texts encourage participation in treatment control groups). This necessitates mod- eling the sampling procedure with rich function approximators. Taking the first steps towards this goal, do restrict ourselves to relatively small synthetic and semi-syntheric experiments but prior- itize understanding the fundamental challenges of creating such a flexible framework.
In Section 3 we introduce influence functions estimators for black-box double causal estimators and a multi-rejection sampler. These tools enable us to perform a gradient-based optimization of data collection policy æ. Importantly, the proposed method is flexible support ı that modeled using deep networks, and is applicable to various -tone-linear (conditional) IV estimators.
Balancing sample complexity and computational complexity: Experiment design is most valuable when sample efficiency is paramount as data is relatively costly in terms of time or re- sources compared to computation. Therefore, we advocate for leveraging computational resources to enhance the search for an optimal data collection strategy x. Our framework is designed to mini- mize the need for expert knowledge and can readily scale with computational capabilities.
Perhaps the most relevant is the work by Gupta al. (2021) for enhancing sample efficiency for specific (linear) IV estimator by learning a sampling distribution over a few data sources, where each source provides different moment conditions. This is complementary the problem of adaptive sampling, even within single data source, and using potentially non-linear estimators. Therefore, detailed related work discussion is deferred to Appendix A.
work consider
BACKGROUND AND PROBLEM SETUP
U
Let X E X' the observable covariates, U E U be the unobserved confounding variables, Z E Z be the instruments, A E A be the +
actions/treatments, and Y E R be the outcomes. Let т A be an instrument sampling policy, and II be the set of all such policies. Let D, = {S, } ) data sample S, = (X,, Ze, A., Yi} is collected using (potentially different) policy x; E ПI. With the model given in Figure 2, we assume that the causal relationship can be represented with the following structural model:
Z
A
be a dataset of size n, where each
de
Figure 2: Causal graph.
Y (x)(AAA) UU, E[U] = EUUA, + 0,
(1)
where g is an unknown (potentially non-linear) function. Importantly, note that the variable U can affect not only the outcomes Y but also and A. We consider treatment effects to be homogenous across instruments, i.e., the CATE matches the conditional LATE (Angrist et al., 1996).
Following Newey Powell (2003) and Hartford et al. (2017), we define the counterfactual predic- tion f(x, a) g(z + [[U]x], where E(U [z] corresponds the fixed baseline effect across all treatments a E A, for a given covariate x E X. This definition f is useful, as it can be identified (discussed later) and can also be used to determine the effect of treatment an A compared to
2

---

Published as a conference paper at ICLR 2024
another treatment 02 E A as f(z - f(z, 02) g(z, a1) g a2). Further, in the simpler setting, U T1 X, then f(z, = g(z, a).
In the supervised learning setting (which assumes U A, X), the prediction model estimates E| [r, a). however, this can result in a biased (and inconsistent) treatment effect estimate as E|y [r, aj = g(z, a)+BUUla, l al + f( a). This issue can often be alleviated using instruments. For Z to be valid instrument, Z should satisfy the following assumptions (red arrows in Fig 2).
Assumption 1. (a) Exclusive: Z IL YIX, A, i.e., instruments do not effect the outcomes directly. (b) Relevance: Z JL A|X, i.e., the action chosen can be influenced using instruments. (c) Inde- pendence: Z IL U|X, i.e., the unobserved confounder does not affect the instrument.
Under Assumption 1, an inverse problem can be designed for estimating f. with the help 2,
B| =| = Elg(2, a))a, B[U|2] = (i,(2, = [xx (2x)a)dP((az
(2)
However, identifiability of using 2 depends on specific assumptions. In the simple setting where f is linear and E = 0, Angrist et al. (1996) discuss how two-stage least-squares estimator (2SLS) can be used to identify ʃ. In contrast, if f non-linear (or non-parametric), exact recovery of f may not be viable as equation 2 results in an ill-posed inverse problem (Newey & Powell, 2003; Xu al., 2020). Different techniques have been proposed to mitigate this issue (Newey & Powell, 2003; Xu et al., 2020; Syrgkanis et al., 2019; Frauen & Feuerriegel, 2022); see Wu et al. (2022) for a survey. These methods often employ a two-stage procedure, where each stage solves set of moment conditions. We formalize these below.
Let X'x x A + R be parametrized using O E O, where θ is the set of all parameters. Let 6g E θ be the true parameter for f. Let q(S;;) and m(S;; 0, ø) be the moment condition for nuisance parameters 6 and parameters of interest 0, respectively, for each sample S. Let Mn and Qn be the corresponding sample average moments such that,
Mn (0.0)
1 n
n Qn(d)= = n (S;
m 6,
(3)
where is the solution to (n( = o, and the estimated parameters of interest / are obtained as a solution to (0, 6) = O. For example, in the basic 2SLS setting without covariates X; (Pearl, 2009), first stage moment ((S;; Φ) = V Vo(Zo - A,)² and the second stage moment m(S;; f. ④) == Vo(A,0 - Yj)2, where Å; = 7,0. Similarly, to solve 2 in the non-linear setting with deep networks, Hartford al. (2017)
((S;;)) 6) = ~ log Pr(A,[X,, Ze Φ) estimate density dP,A,)X., Z;; Φ) using a neural density estimator, and subsequently define mS,,; 0, Φ) = [ f(,,, a; P X,, Z; 2))² where f is also a neural network parametrized by
To make the dependency of the estimated parameters of ff on the data explicit, we denote the esti- mated parameter ((,,.) Further, assume that the ((D,) is symmetric in Dn, i..., ((D,,) is invariant to the ordering of samples in the dataset D,.- This holds for 2SLSS, DeepIV (Hartford et al., 2017), and most other popular estimators (Syrgkanis al., 2019; Wu et al., 2022). We also consider (DD)) to be deterministic for given Dn. In Appendix H.2, we discuss how the proposed algorithm can be used as-is for the setting where ((D,) is also stochastic given D,..
Problem Statement: While these estimators mitigate the confounder bias in estimation of f, they often subject to high variance (Imbens, 2014). In this work, we aim to develop an adaptive data collection policy that can improve sample-efficiency of the estimate of the counterfactual prediction f. Importantly, aim to develop an algorithmic framework that can work with general (non) two-stage estimators. Specifically, let X, A ~ Pz,a be samples from a fixed distribution over which the expected mean mean-squared error is evaluated,
((T) = E (MSE(((D,))) and MSE(O) = Ex.A Da
-(x,)))))((
(4)
To begin, we aim to find a single policy "' E arg min [(T) for the most sample-efficient estimation of 0. In Section 3.3, we will adapt this solution for sequential collection of data.
3

---

Published as a conference paper at ICLR 2024
3 APPROACH
As Figure illustrates, selecting instruments strategically to generate a dataset can have a substantial impact on the efficiency of indirect experiments. Importantly, as [(x) a function of both the data Dn, and the estimator f(; 0), an optimal π not only depends on the data-generating process (c.g., heteroskedasticity compliances Z|X and outcomes Y, even given specific covariate X) but also on the actual procedure used to compute an estimate of the parameter of interest 8, such as 2SLS, etc. In Appendix C, we present simple illustrative case of linear models for the conditional average treatment effect (CATE) estimation, where each aspect can be observed explicitly.
Now we provide the key insights for general gradient- gradient-based optimization procedure to find an instrument selection decision policy x¹ that tackles all of these problems simultaneously. A formal analysis of the claims and the algorithmic approaches we make, and how they contrast with some other alternate choices, will be presented later in Section 4.
As our main objective to search for x", we propose computing the gradient of L(T), which we can express the following using the popular REINFORCE approach (Williams, 1992), a log ग (Z,(),) Ōn
(LT = E MSF(O(D..) log Pr(Dn; m) DANT
(a)
E
MSE(O(D,.)
(5)
DA
where (a) follows because Pr(Dni x) is the probability of observing the entire dataset Dn.
Pr(Dns II (X) (r) U, 2,) Pr(Y) P(X)) A.).
(6)
The gradient in is appealing as it provides an unbiased direction to update æ, and encapsulates properties of both the data-generating process and the estimators black-box in MSE(O((D)). However, using V (T)) for optimization is impractical due to two main challenges:
Challenge 1: As we will state more formally in Section 4, the variance of sample estimate of VL(T) can be (n)) i.e., it can grow linearly in the size of Dn. This can make the optimization process prohibitively inefficient as we collect more data.
Optimization using 5 will also require evaluating V ((T)) for a π different from N' that was used to collect the data. If off-policy correction is done using importance weighting (Precup, 2000), then the variance might grow exponentially with n.
Challenge 2:
To address these two issues we now demonstrate how influence functions and multi-rejection impor- tance sampling can be used to leverage the structure in our indirect experiment design setup to not only significantly reduce the variance of the resulting gradient estimate, but also do in a compu- tationally practical manner that is compatible with deep neural networks. The pseudocode for our algorithm approach is shown Appendix H.
3.1 INFLUENCE FUNCTIONS FOR CONTROL VARIATES
To address challenge I, common approach reinforcement learning and other areas is introduce control variates, that reduce the variance of estimation without introducing additional bias. In partic- ular, we observe that for our setting, using the MSE computed using all other data points Day (i.e., all of D,,, except the sample S; used in the log x ((z (X:) term) serves as a control variate,
log (x,1x,) (MSE(0(D.)) MSE (DDn)))) ÔT
cV L(T)
(7)
As we illustrate in Figure and formalize in Section 4. this immediately results in a substantial variance reduction over the originally proposed gradient (5). However, the computation required for estimating 5 ((T) can be prohibitively expensive as now for each V log x (Z,)x,) in 7, an entire separate re-training process is required to estimate the control variate MSE()(D,;)).
To be efficient in terms of both the variance and the computation, we now show that MSE(O(D,.) MSE (Dava)) can be estimated using influence functions (Fisher & Kennedy, 2021). As discuss below, this requires only single optimization process for estimating MSE(O(D..)
(SE(((D))))) across all i's, and thus preserves the best of both Gov [(T) and L
4

---

Published as a conference paper at ICLR 2024
X10
X10->
Figure Bias-variance of different gradient estimators, for given policy π, when using a 2SLS estimators un- der model-misspeciication Observe the scale on the y-axes.
Variance
PcV
Samples x10
Samples K10?
Let ITD he the distribution function induced by the dataset Dn. and with slight overload of notation,
we let 0( P.,) = A(TD). Let ID, == (1 - <)D + c5(), be a distribution perturhed the direction of S, where 5()) denotes the Dirac distribution. Note that for c = -1 1/n, distribution ID,,, corresponds to the distribution function without the sample St, i.e., the distribution induced by Dny, From this perspective, MSE( corresponds a functional of the data distribution function D, and thus we can do Von Mises expansion (Fernholz, 2012), i.e., distributional analog of the Taylor expansion for statistical functionals, to directly approximate MSE(O((D;..) terms of MSE()(DD) as
MSE(O(D,..)) = MSE(O(D))
(b) MSE (S,),
(8)
E!
where (k) (2015) accessible introduction to influence functions). Therefore, when all the higher order fluence function exists, we can use 8 to recover an estimate of MSF((( (D.)) MSF(0(D,, (D(D))))) with- out re-training. In practice, approximating with K-th order expansion often suffices, which per- mits gradient estimator 7 ((T) that avoids any re-computation of the mean-square-error,
MSE is the k-th order inftuence function (see the work by Fisher & Kennedy (2021); Kahn
Ölog T (Z, IM,)(S.), where, IMSE (S.) = Ôπ
T ('T((
MSE (S.).
(9)
In fact, illustrate in Figure and state formally in Section 4, when using finite K terms, the bias of the gradient in 9 is of the order n - while still providing significant variance reduction. This en- ables the bias to be neglected even when using K 1. Intuitively, for le 1, MMIE operationalizes the concept of the first-order derivative for the functional MS)( i.e., it characterizes the effect on MSE when the training sample S; is infinitesimaly up- seiieithted during optimization,
d MSE (0 (0( - t)D t5(S.)) t=
MSE (S.) = dt
(10)
key contribution is to derive (Theorem in Appendix D) the following form for (S.).
d MSF(() (S:))
(S:)
(11)
where, (S)) aM, -1 (0, ②)) m(S)) Os
aM,
aQQ -1 (o)a(S, 3)
(0.
Φ)
(12)
a0
Note that these expressions generalize the influence function for standard machine learning estima- tors (e.g., least-squares, classification) (Koh & Liang, 2017) to more general estimators (e.g., IV estimator, GMM estimators, double machine-learning estimators) that involve black-box estimation of nuisance parameters & alongside the parameters of interest 6, as discussed in 3.
In Appendix H we show how (S.) can be computed efficiently, without ever explicitly storing or inverting derivatives of M,, or Qn. using Hessian-vector products (Pearlmutter, 1994) readily available in auto-diff packages (Bradbury al., 2018: Paszke et al., 2019). Our approaches are inspired by techniques used to scale implicit gradients and influence function computation to models with millions (Lorraine et al., 2020) of parameters. In Appendix H. we also discuss how Zz!" (Sc) can be further re-used to partially estimate [(3) (S;), thereby making IMSE(S;) more accurate.
3.2 REJECTINN SAMPLING FOR DISTRIBUTION CORRECTION
Recall from Challenge 2 that gradient based search of x" would require evaluating gradient at n' using data collected from * w'. A common technique in RL to address this is by using importance
5

---

Published as a conference paper at ICLR 2024
Figure (Left) Change in did not impact the optima as the orderings were preserved.
x10*
MSE Estimate
10a
Variance
2
(Right) variance of rejection
RS
sampling (RS) vs importance
10-1
15
sampling (IS). See Figure 8 for
the plot with log-scale. Ob-
10-2
serve the scale the y-axes.
0.75
0.5
a for k=
Samplesx10*
sampling (IS) (Precup, 2000; Thomas, 2015). Unfortumately, the effective importance ratio, when using IS in our setting, will be a product of the importance ratios for all the data points (see Equation 165 in Appendix F). This can result in the variance of gradient estimates being exponential in the number of samples n, in the worst case. We illustrate this in Figure 4 and discuss formally in Appendix F.
We now introduce multi-rejection importance sampling approach to estimate the gradient under a decision policy different from that used to gather the historical data. In contrast, unlike in RI., in our setting, the estimator
0( (D,) can considered symmetrie for most of the popular estimators as the order of samples in Dr, does not matter. Therefore, instead of performing importance sampling over the whole prior data, we propose creating a new dataset of size & by employing rejection sampling. Critically, the importance ratio used to select (or reject) each sample S; to evaluate a new policy x' depends only on the importance ratio p(s) for that single sample 8, instead of the product of those ratios over the entire dataset:
S: { Accept if &. S p(S:) Reject Otherwise.
Pr(SaTT Pr(SsTT)
(Z, T XX)
((S.)
(13)
where ç, ~ Uniform(0, 1) and Pmax == max, p(s). Note that 13 allows simulating samples from the data distribution governed by n', without requiring any knowledge of the unobserved con- founders U.. As we will prove in Section 4, this ensures that the variance of the resulting dataset scales with the worst single sample importance ratio, instead of exponentially over the entire dataset size n. This process can therefore be used to generate a smaller k sized dataset with the same distribution data as sampling from the desired policy x'.
As we illustrate in Figure 4 and discuss formally in Appendix F.4, it is reasonable to consider that instrument-selection policy ordering (in terms of their MSE) is robust to the dataset size, i.., E, (MSE(((((DD))) 2 Ex, (ISE(((D,.)) implies that E, (MS{(((()))] 2 E,r (M))( where k < n. In addition, as we will state formally in Property 4, if k = o(n), then the probability of the failure case, where the expected number of samples n Rs accepted by rejection sampling is less than the desired i samples, decays exponentially.
This insight is advantageous as we can now directly obtain datasets D3 from n², albeit of size n, to evaluate n', as desired. We implement this by first running the rejection process for all samples, yielding a set of samples of size ne Rt that are drawn from म, and then selecting a random subset of size k from the n accepted samples. For the sub-sample Dr, analogous to the true MSE in 4 we calculate an estimate of the MSE using X; and A, drawn from a held-out dataset with M samples from P,
M MSB(O(Da)) = M
(14)
Note that in general, our historical data may be a sequence of decision policies, as we adaptively deploy new instrument-selectee
decision policies. In this setting, a straightforward application of rejection sampling will require the support assumption which necessitates (2,2((,,) > 0 if x' r', > 0 for all i E {1,...,n) This may restrict the class of new instrument-selection policies that can be deployed. Instead we propose the following multi-rejection sampling strategy:
Acceppt if & S ((S.) Pmax Reject
ा 7'(Z,
S,
p(S,) = bo (2
(15)
Otherwise.

---

Published as a conference paper at ICLR 2024
where Pmax max, p(s). As show in Appendix G, this relaxes the support assumption enforced for every π, to support assumption over the union of supports of { while still ensuring that the accepted samples follow the distribution specified by x². For e.g., if the initial data collected or available used a uniform instrument-selection decision policy, then subsequent policies can be arbi- trarily deterministic and the multi-rejection procedure can still all the data and remain valid. This makes it particularly well suited for our adaptive experiment design framework. In Appendix G, we further prove that the expected number of samples n MMS accepted under multi-rejection will always be more than or equal to n RS obtained using rejection sampling, irrespective of {x; 1
3.3 DIA: DESIGNING INSTRUMENTS ADAPTIVELY
Using influence functions and multi-rejectton sampling we addressed both the challenges about high variance. Leveraging the flexibility offered by the proposed gradient- basse procedure, we readily extend the idea for sequential collection of data. To do so, propose using parameterization of π to account for data already collected, which is important during adaptive instrument-selection policy design.
Let be the size of the dataset D,= {S+ collected so far, and let N be the budget for the total number of samples that can be collected. At each stage of data collection, DIA searches for a policy Te, parameterized using şe such that when the remaining D {S; ) ] samples are collected using Ti, the combined distribution DN := Dn L.UDDD N would approximate the optimal distribution for estimating 0. Let T operationalize DN, if DN were to be collected using Tip.
"1(1 Σ (m(elz)) = N
off (2|xx) T
1 ) T=(x)x)
(16)
Let I MISE (S:) be the influence function similar to 9, where the MSE is replaced with its proxy 14, and let {5:) in the following be the samples for क. obtained using multi-rejection sampling in 15. Then for the first batch, Tp is designed to be a uniform distribution, and for the later batches we leverage 9 and 14 to update Tie using
(Zc)( a log "
4 ((
I MSE (S.).
(17)
04p
We use T. to collect the next batch of data and then update T. again, as discussed above, to ensure that the final distribution Dx ) approximates the optimal distribution, for estimating 0, as closely as possible. Intuitively, this technique is similar to receding horizon control, where the controller is planned for the entire remaining horizon of length N n, but is updated and refined again periodically. A pseudo-code for the proposed algorithm is provided in Appendix H.
4 THEORY
We provide theoretical statements about the impact of the algorithmic design choices, over alternatives, in terms of their benefit on the variance. Proofs and more formal detailed statements of the theorems are deferred Appendix E. We first state that variance of the naive gradient can scale poorly with the dataset size:
Property 1 (Informal). If MSE(((D,)) is leave-one-out stable and ml[MSE(((D.)))1. ((a(n)) = (1), we have Var Var(v((()) = M(a(n)) (c.f. Theorem 3 in Appendix).
In many cases, we would expect that the mean squared error decays at the rate of n n1/2 (unless we can invoke a fast parametric rate of 1/n, which holds under strong convexity assumptions); such cases, we have that a(n) = w(1) and Var(VL(TT) can grow with the sample size. Moreover, the mean squared error does not converge to zero, due to persistent approximation error, local optima in the optimization, or if is ill-posed when dealing with non- non-parametric estimators, then the variance can grow linearly, i.e. a<n) O(n). See Figure 3. In contrast, the variance of the gradient of the loss with MSE covariates 7 is often independent of the data set size:
Property 2 (Informal). B[V)([(T) = VL(T). Further, if MSE(O(Da)) is leave-one-out stable then Var(("<((T)) O(1) (c.f. Theorem 4 in Appendix).
7

---

Published as a conference paper at ICLR 2024
Percent of MSE of Unitorm
I
Percent of MSE of Uniformm
Conditional IV
Percent of MSE Uniferm
TripAdvisor
2.00-
1.20
1.0
0.75
0.8
0.52-
0.50
0.4
9.25
0.25
0.4
3 Samples
0.00
62
0.4
0.6 Samples
0.
1.5
Samples
x1o
Oracle
DIA-5 DIA-10 DIA-20 DIA.40
Unifarm
Figure 5: Performance gains when considering a different number of instrumental variables, with total of 5 re-allocation. First allocation (1000 samples) is done using uniform sampling, and thus all methods have the same performance initially. DIA-X refers to the application of the proposed algorithm to the domain setting where the number of instruments is X. Note that since MSE under uniform distribution also keeps increasing, a saturating or increasing trend of the ratio does not imply that the MSE is increasing. (Left) Results for the IV setting (using closed- Dotted lines correspond to the oracle estimate for the respective number of instruments. (Middle) Results for the conditional IV setting (using logistic regression based estimator). (Right) Results for the TripAdvisor domain (Syrgkanis et al., 2019) (using neural network based estimator). Error bars correspond to one stderr.
linear estimator).
Unlike Property 1, Property holds irrespective of (n), thus providing reliable gradient estimator even if the function approximator is mis-specified, optimization is susceptible to local optima, or ill-posed when dealing with non-parametric estimators. Further, our loss using influence functions 9 can also yield similar variance reduction, at much lower computational cost:
Property (Informal). the Von-Mises expansion in 8 exists, "E[ [(x)] VL(m) + O(n -K). If (/M.)))( is leave-one-out stable then Var( 1F [(x)) 0(1) (c.f. Theorem Appendix).
We then prove how rejection sampling can impact the MSE, enabling variance that has an expo- nential reduction in variance compared to importance sampling, whose variance can depend on pmax (c.f. Theorem in Appendix), at the expense of only bounded failure rate of not producing the desired number of samples k. For this result, let MSE be the estimate of MSE computed using the mean of MSE( ())x)) across all the subsets D3 from the n RS accepted samples.
Property 4 (Informal). Let E, (MSE(((D)))) = a(k)) then Var (MSEE = ((a(k))kkpumx/// (n)) and Bias Bias(MSF,
( -1/ v /a(n)). Further, the failure probability is bounded as < <k S e (n/((ppao)) (c.f. Theorem 8 in Appendix).
Pr(n RS
We also show in the Appendix fc.f. Corollary 1) that the above theorem, together with further regu- larity conditions, can used to argue that ranking policies based on MSE leads to approximately optimal policy decisions, with respect to E[MSE((((n)) in strong approximation sense.
5 EXPERIMENTS
In this section we empirically investigate the flexibility and efficiency of our approach. We provide the key takeaway points here, and more experimental details are deferred to Appendix I.
A. Flexibility of the proposed approach: One of the key benefits of DIA that can be used as- is for variety of estimators (linear and non-linear) and settings (unconditional and conditional IV setting). Drawing inspiration from real-world use cases, consider binary treatment settings, where only have access plethora of instruments that be used to encourage (e.g., using different types of notifications, emails, etc.) treatment uptake. Specifically, we consider three regimes:
IV: This simulator is a basic IV setting with homogenous treatment effects and which thus permits closed-form solution using the standard two-stage least-squares procedure (Pearl, 2009). This do- main has heteroskedastic outcome noise and varying levels compliance for different instruments. Figure (left) presents the results for this setting.
8

---

Published as a conference paper at ICLR 2024
Percent MSE of Uniform
IV
MSE Uniform
Conditional
1.0
1.0-
0.8
0.8
0.8
0.6
0.2
0.2
0.0
0.0
Number of Re-allocations
Number of Re-allocations
DIA-5
DIA-10
DIA-20
DIA-40
Uniform
Figure 6: DIA-X refers to the application the proposed algorithm to the domain setting where the number of instruments is X. The plots illustrate the percent of MSE of uniform, after all the 5000 samples are collected, with the given number of re-allocations. Error bars correspond to one stderr.
Second we consider the important setting where instrumeentxeencuuraeemntt can be allocated in context-dependent way, and the objective is to estimate the conditional average treatment effect. Our simulator has covariates containing a mix of binary and continuous- features, and heteroskedastic noises and compliances, across instruments and outcomes, for every covariate. We solve the counterfactual prediction ʃ in 2 using the two-stage moment conditions in involving logistic regression and this estimator does not have closed-form solution. Figure (middle) presents the results for this setting.
Conditional IV:
TripAdvisor: We use the simulator built from TripAdvisor customer data (Syrgkanis al., 2019). The goal is to estimate the effect revenue if customer becomes subscribed member. The original setup had instruments corresponding to easier/promotional sign-up options, but to provide ablation studies spond to demographic data about the customer, and their past interaction behavior on the website. For this setting, we use the estimator by Hartford al. (2017) and model all the functions f. dP (from 2), and æ,, using neural networks. Figure 5 (right) presents the results for this setting.
consider larger, synthetically augmented, set of instruments. Covariates corre-
B. Understanding the performance gains: In order to simulate a realistic situation where de- ployed policy can be updated only periodically, we consider a batched allocation setting. To measure the performance gain, we compute the relative improvement in MSE over uniform allocation strat- egy, i.e., a metric popular direct experiment design literature (Che & Namkoong, 2023) (lower is better). In the IV setting, in Figure (left), we also provide comparison with the oracle ob- tained using brute force search. To assess the robustness of our method, we also consider varying the number of available instruments and the number of batch re-allocations possible.
Across all the domains, we observe that DIA can provide substantial gains for estimating the coun- terfactual prediction by adaptively designing the instruments for indirect experiments (Figure 5). Performance gains are observed even as we vary the number of instruemnts present in the domain. Importantly, DIA achieves this across different (linear and non-linear) estimators, thereby illustrat- ing its flexibility. In addition, in general there is a benefit to increasing the number of times the instrument-design policy is updated (Figure 6).
It is worth highlighting that DIA can improve the accuracy of the base estimator by factor of 1.2x 10x: equivalently, for some desired target treatment effect estimation accuracies, DIA needs only 80% to an order-of-
less sample data.
Our results also suggest a tension behind the amount of data and the complexity of the problem, creating "U'-trend (see e.g. Figure 6). With larger number of instruments, there is more potential advantage of being strategic, especially when for many contexts, most instruments have a weak influence. However, learning the optimal strategy to realize those gains also becomes harder when there are so many instruments (and the sample budget is held fixed). the middle regime gains are substantial and the method can also quickly learn effective instrument-selection design

---

Published as a conference paper at ICLR 2024
6 CONCLUSION
The increasing prevalence of human-AT interaction systems presents important development. However, as Al systems can often only be suggestive and not prescriptive, estimating the effect of its suggested action necessitates the development of sample-efficient methods to estimate treatment effect merely through suggestions, while leaving the agency of decision to the user. This work took the initial step lay the foundation for adaptive data collection for such indirect experiments. We characterized the key challenges, theoretically assessed the proposed remedies, and validated them empirically
domains inspired by real-world settings. Scaling the framework to settings with natural language instruments, and doing inference with adaptively collected data (Zhang et al., 2021; Gupta al., 2021) remain exciting future directions.
7
ACKNOWLEDGEMENT
We thank Stefan Wager, Jann Spiess, and Art Owen for their valuable feedback. Earlier versions of the draft also benefited from feedback from Jonathan Lee and Allen Nie. This work was supported in part by 2023 Amazon Research Award.
REFERENCES
Karim Abou-Moustafa and Csaba Szepesvári. An exponential efron-stein inequality for l_q stable learning rules. In Algorithmic Learning Theory, pp. 31-63. PMLR, 2019. [Page(s): 27]
Ahmed Alaa and Mihaela Van Der Schaar. Validating causal inference models via influence func- tions. In International Conference on Machine Learning, pp. 191-201. PMLR, 2019. (Page(s): 17, 25]
Ahmed Alaa and Mihaela Van Der Schaar. Discriminative jackknife: Quantifying uncertainty in deep learning via higher-order influence functions. International Conference on Machine Learning. pp. 165-174. PMLR, 2020. [Page(s): 17]
Joshua D Angrist, Guido W Imbens, and Donald B Rubin. Identification of causal effects using instrumental variables. Journal of the American statistical Association, 91(444):444455, 1996.
[Page(s): 2.3,
Susan Athey and Stefan Wager. Policy learning with observational data. Econometrica, 89(1): 133-161, 2021. [Pago(s): 17]
Juhan Bae, Nathan Ng, Alston Lo, Marzyeh Ghassemi, and Roger B Grosse. If influence functions are the answer, then what is the question? Advances in Neural Information Processing Systems, [Page(s): 24.46, 46]
35:17953-17967 2022.
Samyadeep Basu, Philip Pope, and Soheil Feizi. Influence functions in deep learning are fragile. arXiv preprint arXiv:2006. 14651, 2020. [Page(s): 46]
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//qithub. com/ gwtgl//cogeeeooeo jax. [Page(s): 5]
Patrick Breheny. Statistical functionals and influence functions. Technical report, The University of 2011/nots//
Iowa, 2020. hittps:/mmyweer oww.a. edu http////beeee/////teeeeeeeeeeeee [Page(s)::4] 24]
Erik Brynjolfsson, Danielle Li, and Lindsey R Raymond. Generative ai at work. Technical report, National Bureau of Economic Research, 2023. [Pagets): I]
Brian S Caffo, James G Booth, and AC Davison. Empirical supremum rejection sampling. Biometrika, 8944)775--75, 2002. [Page(s): 45]
Ricardo Cao. Bootstrapping the mean integrated squared error. Journal of Multivariate Analysis, 45 (1):137-160, 1993, (Page(s): 17)
Alain Celisse and Benjamin Guedj. Stability revisited: new generalisation bounds for the leave-one- out. arXiv preprint arXiv: 1601166618..22... 2016. [Pagets): 271
Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: review. Statistical science, pp. 273-304, 1995. [Pagois): 17,47]
10

---

Published as a conference paper at ICLR 2024
Ethan Che and Hongseok Namkoong, Adaptive experimentation at scale: Bayesian algorithms for flexible batches. arXiv preprint arXiv:2303.11582, 2023. (Pago(s): 1, 1,9. 17]
Yen-Chi Chen. Introduction to resampling methods. lecture 5: Bootstrap. Technical report, Uni-
versity of Washington. 2017a. https: /faculty.... washington, httpi//gtt...aaee/ecce//////// paf. (Page(s): 17]
Yen-Chi Chen. Introduction to resampling methods. lecture 9: Introduction to the bootstrap the-
ory. Technical report, University of Washington, 2017b,
washington.
http:/yenchicc17$pp.. -030_/4400_//0 Lecc__heorry pdf.. [Page(s):
Yen-Chi Chen. Stat 512: Statistical inference. lecture 10: Statistical functionals and the bootstrap. Technical report, University of Washington, 2020. https: ffaulty..... washington. edu/
http://000___attt1eeeeeeeeeeeae httpeeeccoo_uuciionaaaa..ae__... pdf. [Page(s): 17]
Paul Clarke and Frank Windmeijer. Instrumental variable estimators for binary outcomes. Journal of the American Statistical Association, 107(500):1638--162) 2012. [Page(s): 17]
R Dennis Cook and Sanford Weisberg. Residuals and influence in regression. New York: Chapman and Hall, 1982, [Page(s): 24)
Alicia Curth, Alihan Hüyük, and Mihaela van der Schaar. Adaptively identifying patient populations with treatment benefit in clinical trials. arXiv preprint arXiv:2208 05844, 2022. [Page(s): 17]
Michiel Debruyne, Mia Hubert, and Johan AK Suykens. Model selection in kernel based regression using the influence function. Journal of machine learning research-Cambrrdge Mass., 9:2377- 2400, 2008 [Pagelst: 17]
Riccardo Della Vecchia and Debabrota Basu. Online instrumental variable regression: Regret anal- ysis and bandit feedback. arXiv preprint arXiv:2302.09335 2023. [Pagets): i]
Ozkan Eren and Daniel Henderson. The impact of homework on student achievement. The Econo- metrics Journal, 11 (22):326 (2):326-348, 2008. [Page(s): 18]
Yingying Fan, Jinchi Lv, and Jingbo Wang. Dnn: two-scale distributional tale of heterogeneous treatment effect inference. Available at SSRN 3238897, 2018. [Page(s): 31,41]
Luisa Turrin Fernholz. Von Mises calculus for statistical functionals, volume 19, Springer Science & Business Media, 2012. (Page(s): 5]
Johannes Ferstad, Priya Prahalad, David M Maahs, Emily Fox, Ramesh Johari, and David Scheinker. 1009-p: The association between patient characteristics and the efficacy of remote patient moni- toring and messaging. Diabetes, 71(Supplement 1), 2022. (Page(s): 18]
Aaron Fisher and Edward H Kennedy. Visually communicating and teaching intuition for influence functions. The American Statistician, 75(2):62--17, 2021. (Page(s); 4,
Dennis Frauen and Stefan Feuerriegel. Estimating individual treatment effects under unobserved confounding using binary instruments. arXiv preprint arXiv:2208.0855 08544, 2022. (Page(s): 31
Charles J Geyer. 5601 notes: The subsampling bootstrap. Unpublished manuscript, 2006. URL
https: http://wwwwwsttt stw...ttt.................. umn edu/ gegggeeyerr110 /tt///oot///eeeeeeo sub. IPagets): 17]
Roger Grosse, Juhan Bae, Cem Anil. Nelson Elhage, Alex Tamkin, Amirhossein Tajdini, Benoit Steiner, Dustin Li, Esin Durmus, Ethan Perez, et al. Studying large language model generalization with influence functions. arXiv preprint arXiv:2308.0322 2023. [Page(s). 45]
Shantanu Gupta, Zachary Lipton, and David Childers. Efficient online estimation of causal effects by deciding what to observe. Advances in Neural Information Processing Systems, 34:20995- 21007, 2021. [Puge(s): 2. 10]
Jinyong Hahn, Keisuke Hirano, and Dean Karlan. Adaptive experimental design using the propen- sity score. Journal of Business & Economic Statistics, 29(1):96-108, 2011. [Pagets): 17]
Peter Hall. Using the bootstrap to estimate mean squared error and select smoothing parameter in nonparametric problems. Journal of multivariate analysis, 32(2): 177-203, 1990. (Pagecer 17]
Peter Hall. Methodology and theory for the bootstrap. Technical report, University of California, Davis, 2016. https: / anson. uedavis. ieddavii.eduuue edt.//etteteeett/tta5..... pdf. [Page(s):
bootstrrap-

---

Published as a conference paper at ICLR 2024
Jason Hartford, Greg Lewis, Kevin Leyton-Brown, and Matt Taddy. Deep iv: A flexible approach for counterfactual prediction. In International Conference on Machine Learning, pp. 1423-1423.
PMLR, 2017. [Pagels): 1, 2, 484
James J Heckman and Sergio Urzua. Comparing iv with structural models: What simple iv can and cannot identify. Journal of Econometrics, 156(1):77-37, 2010. [PagoG): 17]
Oliver Hines, Oliver Dukes, Karla Diaz-Ordaz, and Stijn Vansteclandt. Demystifying statistical
learning based on efficient influence functions. The American Statistician, 76(3):992-304, 2022.
[Pagota:: 1?]
Wassily Hoeffding. A class of statistics with asymptotically normal distribution. The Annals of Mathematical Statistics, 19(3):293-325, 1948. [Pago(s): 31]
Kenneth Holstein, Bruce M McLaren, and Vincent Aleven. Student learning benefits of mixed- reality teacher awareness tool in ai-enhanced classrooms. In Artificial Intelligence in Education: 19th International Conference, AIED 2018, London, UK, June 27-30, 2018, Proceedings, Part I 19, pp. 154-168. Springer, 2018. [Page(s): 1)
Shang-Ling Hsu, Raj Sanjay Shah, Prathik Senthil, Zahra Ashktorab, Casey Dugan, Werner Geyer, and Diyi Yang. Helping the helper: Supporting peer counselors via ai-empowered practice and feedback. arXiv preprint arXivv2330.088900 2023. [Page(s): I]
Hidehiko Ichimura and Whitney K Newey, The influence function of semiparametric estimators. Quantitative Economics, 13(1):29-61. 2022. [Puge(s): 17, 24]
Guido Imbens. Instrumental variables: an econometrician's perspective. Technical report, National
Bureau of Economic Research, 2014. (Page(s): 3]
Guido W Imbens. Better late than nothing: Some comments on deaton (2009) and heckman and urzua (2009). Journal of Economic literature, 48(2):399-422 2010. (Page(s): 17]
Jay Kahn. Influence functions for fun and profit. Ross School of Business, University of URL http://j-kahu jjkkaann..... cow/files///ecccccccccccccceclee Seiilesinnfuunneee http///nnnnennnttiiiio ionssnnttiiioooii.i iff..
Michigan, 2015.
(Puge(s): 19,24, 24,24,40
Nathan Kallus. Instrument-armee bandits. In Firdaus Janoos, Mehryar Mohri, and Karthik Sridha- ran (eds.). Proceedings of Algorithmic Learning Theory. volume 83 of Proceedings of Machine Learning Research, pp. 529 129.-46. PMLR, 07-09 Apr 2018. URL mlr. wetres//v3/kaae
8a. html. [Page(s): If
Maximilian Kasy. Semiparametrically efficient estimation of conditional instrumental variables pa- rameters. The International Journal of Biostatistics, 5(1), 2009, [Pagets): 171
Maximilian Kasy and Anja Sautmann. Adaptive treatment assignment in experiments for policy choice. Econometrica, (9(1):113-13)) 2021. [Page(s): 17)
Masahiro Kato, Takuya Ishihara, Junya Honda, and Yusuke Narita. Efficient adaptive experi- mental design for average treatment effect estimation. arXiv preprint 200::2002.003088 2020. [Pago(s): 1. 17]
Michael Kearns and Dana Ron. Algorithmic stability and sanity-check bounds for leave-one-out cross-validation. In Proceedings of the tenth annual conference on Computational learning the- ory, pp. 152-162, 1997. [Puge(s): 27)
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1885-1894, PMLR, 2017. (Page(s): 5, 24]
Wouter Kool, Herke van Hoof, and Max Welling. Buy REINFORCE samples, get a baseline for free! In Deep Reinforcement Learning Meets Structured Prediction, ICLR 2019 Workshop, New Orleans, Louisiana, United States, May 6, 2019. ReenRevie,.net, 2019. URL https: / opoeneeview... wwt. fote://ommmm/// waa.mddddrllggGGSee.. [Page(s):
Steven George Krantz and Harold R Parks. The implicit function theorem: history, theory, and applications. Springer Science& & Business Media, 2002. [Page(s): 24]
Zhaobin Kuang, Frederic Sala, Nimit Sohoni, Sen Wu, Aldo Saalova-Pallmera,, Jared Dunnmon, James Priest, and Christopher Ré. Ivy: Instrumental variable synthesis for causal inference. In International Conference on Artificial Intelligence and Statistics, pp. 398-410. PMLR, 2020.
[Pages): 1?]
12

---

Published as a conference paper at ICLR 2024
Harrison Hi and Art B Owen. Double machine learning and design in batch adaptive experiments.
arXiv preprint arXiv:2309. Sttt22309..2297, 15297, 2023, (Page(s): 17]
Pierre Liotet, Francesco Vidaich, Alberto Maria Metelli, and Marcello Restelli, Lifelong hyper- policy optimization with multiple importance sampling regularization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7525-7533, 2022. [Page(s): 17)
Hao Liu, Yihao Feng, Mao, Dengyong Zhou, Jian Peng, and Qiang Liu. Action-depedent con- trol variates for policy optimization via stein's identity. arXiv preprint arXiv: /1177/00//11.1,.. 2017.
[Page(s): 17)
Noel Loo, Ramin Hasani, Mathias Lechner, and Daniela Rus. Dataset distillation with convexified implicit gradients. arXiv preprint arXiv:2302.06755, 2023. [Pagets): 17, 24]
Jonathan Lorraine. Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International conference on artificial intelligence and statistics, pp-
1540-1552. PMLR, 2020. [Pagots): 5,45]
Anna Mikusheva. Time series analysis. lecture 9: Bootstrap. Technical report, Mas-
sachusetts Institute of Technology, 2013. https://ocw/ mit edu courses/
lec9/. /. [Pagets): 17]
Susan Murphy, An experimental design for the development of adaptive treatment strategies.
Statistics in medicine, 24(10)) 2005. [Page(s): I]
Whitney K Newey and Daniel McFadden. Large sample estimation and hypothesis testing. Hand- book of econometrics, 4:21 1-2245, 1994. [Page(s): 191
Whitney K Newey and James L Powell. Instrumental variable estimation of nonparametric models. Econometrica, 71(5):1565-177) 2003. [Pagols): 2,
Dung Daniel T Ngo, Logan Stapleton, Vasilis Syrgkanis, and Steven Wu. Incentivizing compliance with algorithmic instruments, In International Conference Machine Learning, pp. 8045-8055. (Pago(s): 2]
PMLR, 2021.
Matteo Papini, Alberto Maria Metelli, Lorenzo Lupo, and Marcello Restelli. Optimistic policy op- timization via multiple importance sampling. In International Conference Machine Learning, pp. 4989-4999. PMLR, 2019. [Pago(s): 17]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035.
Curran Associates, Inc., 2019, [Pagels):
Judea Pearl. Causality. Cambridge university press, 2009. 3
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994, IPage(s): 5, 451
Dimitris N Politis, Joseph P Romano, and Michael Wolf. Subsampling. Springer Science & Business Media, 1999, [Pagets): 17]
Doina Precup. Eligibility traces for off- cef-policy policy evaluation. Computer Science Department Faculty Publication Series, pp. 80, 2000. [Page(s): 4,6]
Tom Rainforth, Adam Foster, Desi R Ivanova, and Freddie Bickford Smith. Modern bayesian ex- perimental design. arXiv preprint arXiv:2302. /4545, 2023. (Page(s): I, 17,44
Lorenz Richter, Ayman Boustati, Nikolas Nüsken, Francisco Ruiz, and Omer Deniz Akyildiz. Var- grad: a low-variance gradient estimator for variational inference. Advances in Neural Information Processing Systems, 33:13481-133 2020. [Page(s): 17]
Emmanuel Rio. Moment inequalities for sums of dependent random variables under projective conditions. Journal of Theoretical Probability, 22(1):146-163 2009. [Page(s): 28)
James Robins, Lingling Li, Eric Tchetgen, Aad van der Vaart, et al. Higher order influence functions and minimax estimation of nonlinear functionals. In Probability and statistics: essays in honor of David A. Freedman, volume 2, pp. 335-422, Institute of Mathematical Statistics, 2008. [Pagols): 25]
13

---

Published as a conference paper at ICLR 2024
Joseph P Romano. On subsampling estimators with unknown rate of convergence. 1995. (Page(s):
Tim Salimans and David A Knowles. On using control variates with stochastic approxima- tion for variational bayes and its connection stochastic linear regression. arXiv preprint [Page(s): 17]
arXiv:1401.1222, 2014.
Andrea Schioppa, Polina Zablotskaia, David Vilar, and Artem Sokolov. Scaling up influence func- tions. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 8179-
8186, 2022. [Page(s): 24]
Jiaxin Shi, Yuhao Zhou, Jessica Hwang, Michalis Titsia,, and Lester Mackey. Gradient estimation with discrete stein operators. Advances in neural information processing systems, 35:25829-
25841, 2022. [Page(s): 17]
Xiaoxia Shi. Econ 715, lecture 10: Bootstrap. Technical report, University of Wisconsin- 2012. https: http://wwwww.......c.. pdf. [Pago(s:: 17]
ssc. wisc. wttp//xaaha//ccc77////tttze bo.tsssss.poooottrpp.ppp.pppppp
Difan Song. Simon Mak, and CF Wu. Ace: Active learning for causal inference with expensive experiments. arXiv preprini arXiv:2306.077 074800 2023. [Pagels): 17]
Masashi Sugiyama, Motoaki Kawanabe, al. Dimensionality reduction for density ratio estima- tion in high-dimensional spaces. Artificial Intelligence Sociery, 2009DMMM-14901,04, 2009.
[Pago(s): 49)
Masashi Sugiyama, Makoto Yamada, Paul Von Buenau, Taiji Suzuki, Takafumi Kanamori, and Mo- toaki Kawanabe, Direct density-ratio estimation with dimensionality reduction via least-squares hetero-distributtional subspace search. Neural Networks, 24(2): 2011. [Pagots): 49]
Vasilis Syrgkanis, Victor Lei, Miruna Oprescu, Maggie Hei, Keith Battocchi, and Greg Lewis. Ma- chine learning estimation of heterogeneous treatment effects with instruments. Advances in Neu- ral Information Processing Systems, 32, 2019. [Page(s): 1, 3, 9,9. 18.49)
Hajime Takahashi. A note on edgeworth expansions for the von mises functionals. Journal of multivariate analysis, 24(1):56-65, 1988. [Page(s): 17]
Yunhao Tang. Biased gradient estimate with drastic variance reduction for meta reinforcement learning. In International Conference on Machine Learning, pp. 21050-21075. PMLR, 2022.
[Page(si: 17]
Philip S Thomas. Safe reinforcement learning. PhD thesis, University of Massachusetts, Amherst, 2015. (Page(s): 6
Michalis Titsias and Jiaxin Shi. Double control variates for gradient estimation in discrete latent variable models. In International Conference on Artificial Intelligence and Statistics, pp. 6134- 6151. PMLR, 2022. [Pagets): 17]
Toon Vanderschueren, Alicia Curth, Wouter Verbeke, and Mihaela van der Schaar. Accounting for informative sampling when learning to forecast treatment outcomes over time. arXiv preprint (Pugels): 17]
arXiv:2306.04255 04255. 2023,
Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 122882)::228-1122) 2a. [Page(s): 42]
Stefan Wager and Susan Athey. Estimation and inference of heterogencous treatment effects using random forests. Journal of the American Statistical Association, 113(623) 2018b. [Pagoa)): 41]
Linbo Wang, Yuexia Zhang, Thomas S Richardson, and James M Robins. Estimation of local treatment effects under the binary instrumental variable model. Biometrika, 108(4):881-894, 2021. [Page(s): 17]
Ronald J Williams. Simple statistical tradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992. [Page(s). 4]
Anpeng Wu, Kun Kuang, Ruoxuan Xiong, and Fei Wu. Instrumental variables in causal inference and machine learning: survey. arXiv preprint urXiv:22/2.05772: 2022. [Pago(s): 3)
Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre M Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel. Variance reduction for policy gradient with action-dependent factorized baselines. arXiv preprint arXiv: /803.0740 2018. [Pagets): 17]
14

---

Published as a conference paper at ICLR 2024
Ruoxuan Xiong, Susan Athey, Mohsen Bayati, and Guido Imbens. Optimal experimental design for staggered rollouts. arXiv preprint
2019. [Page(s): I]
Liyuan Xu, Yutian Chen, Siddarth Srinivasan, Nando de Freitas, Arnaud Doucet, and Arthur Gret- ton. Learning deep features in instrumental variable regression. arXiv preprini arXiv:2010.07155: 2020. [Page(s): 3]
Junkun Yuan, Anpeng Wu, Kun Kuang, Bo Li, Runze Wu, Fei Wu, and Lanfen Lin. Auto iv: Counterfactual prediction via automatic instrumental variable decomposition. ACM Transactions on Knowledge Discovery from Data (TKDD), 16(4):1-20, 2022. [Pagois): 17]
Kelly Zhang, Lucas Janson, and Susan Murphy. Statistical inference with m-estimators adap- tively collected data. Advances in neural information processing systems, 34:7460-7471, 2021. [Puge(s): 10]
15

---

Published as a conference paper at ICLR 2024
Adaptive Instrument Design for Indirect Experiments (Appendix)
CONTENTS
Introduction
2 Background and Problem Setup
3 Approach
3.1 Influence Functions for Control Variates
3.2 Multi-Rejection Sampling for Distribution Correction
3.3 DIA: Designing Instruments Adaptively
4
Theory
5
Experiments
6 Conclusion
10
7 Acknowledgement
10
Extended Discussion on Related Work
17
B Examples of Practical Use-cases
18
C Linear Conditional Instrumental Variables
18
C.1 Specific Instantiations of Lemma 1
20
D Influence functions
24
E Bias and Variances of Gradient Estimators Naive REINFORCE estimator
26
E.
26
E.2
REINFORCE estimator with CV REINFORCE estimator with Influence
29
E.3
30
F
Estimation Error, Bias and Variance Analysis
31
F.I
Preliminaries on U-Statistics
31
F.2
Variance of procedure
F3
Guarantees for Rejection Sampling Procedure
35
F.4
Policy Ordering Consistency Guarantees
F.5
Proof of Theorem 6
40
G Multi- Multi-Rejection Sampling
42
G.I Review: Standard Rejection Sampling
42
G.2
Proposed: Multi-Rejection Sampling
43
Algorithm
H.I Pseudo-code
44
H.2
Influence function usage when the estimates are stochastic
................................
46
H.3
Proxy MSE alternatives
................................
I
Additional Empirical Details
47
1.1
Synthetic Domains
I.2
TripAdvisor domain synti-sytthetic)
49
L.3
Hyper-parameterrs
49
I.4
Details of other plots:
49
16

---

Published as a conference paper at ICLR 2024
A EXTENDED DISCUSSION ON RELATED WORK
Experiment design has a rich literature and no effort is enough to provide a detailed review. We refer readers to the work by Chaloner & Verdinelli (1995); Rainforth et al. (2023) for a survey. Re- searchers have considered adaptive estimation of (conditional) average treatment effect (Hahn et al., 2011; Kato et al., 2020), leveraging Gaussian processes (Song et al., 2023), active estimation of the cul-oooulation benefiting the most from the treatment (Curth et al., 2022), for estimating the treatment effects when samples are collected irregularly (Vanderschueren et al., 2023), and adaptive data collection find the best arm while also maximizing welfare (Kasy & Sautmann, 2021). Che & Namkoong (2023) consider adaptive experiment design using differentiable programming. Our work shares their philosophy in terms of balancing sample complexity with computational complex- ity. Li & Owen (2023) consider using methods from double ML for adaptive direct experiments. In contrast, we consider adaptive indirect experiments that often make use of two-stage and double ML estimators. However, all these works only consider design for direct experiments.
For instrumental variables, researchers have developed methods that can automatically decide how to efficiently combine different instruments enhance the efficiency of the estimator (Kuang al., 2020; Yuan et al., 2022). In contrast, our work considers how to collect more data online. Further, while considered IV estimation under specific assumptions, we refer readers to the work by Angrist et al. (1996); Clarke & Windmeijer (2012); Wang et al. (2021) for discussions on alternate assump- tions. Particularly, we considered conditional LATE be equal to CATE. For more discussion on the relation of CATE and conditional LATE, we refer readers to the work by Heckman & Urzua (2010); Imbens (2010); Athey & Wager (2021).
Some of the tools that developed are also related literature outside of causal estimation and experiment design. Our treatment of the dataset selection policy as a factorized distribution and development of the leave-one-out sample is related to ideas in retion-factorizer baselines in reinforcement learning (Wu et al., 2018; Liu et al., 2017) and leave-one-out control variates (Richter al., 2020; Salimans & Knowles, 2014; Shi et al., 2022; Kool et al., 2019; Titsias & Shi, 2022). In contrast to these, our work is for experiment design, and to be compute efficient in our setup we had to additionally develop black-box influence functions for two-stage estimators.
Our work also complements prior work influence function for conditional IVs (Kasy, 2009; Ichimura & Newey, 2022) as they were not directly applicable to deep neural network-basee esti- mators. Further, our characterization of the leave-one-out estimate of the MSE requires existence of all the higher-order influence functions. Similar conditions have been used by prior works in the context of uncertainty quantification (Alaa & Van Der Schaar, 2020), model selection (Alaa & Van Der Schaar, 2019; Hines et al., 2022; Debruyne et al., 2008), and dataset distillation (Loo et al., 2023).
Tang (2022) quantifies and developes first-order gradient-based control-variates to perform bias- variance trade-off of the naive REINFORCE gradient in the meta-reinforcemmet learning setting. However, in their analysis, the effective 'reward" function admits simple additive decomposition, where in our setting it corresponds to MSE(0(D..) which cannot be analysed using their technique. Further, potential non-linearity of 0 makes the analysis lot more involved in our case. Similarly, to deal with off-policy correction in RI., researchers have also considered using multi-importance- sampling (Papini et al.. 2019; Liotet et al., 2022). However, using multi-importanee sampling (as opposed to multi-rejection sampling) in our setup can still result in exponential variance. Our multi- rejection sampling is designed by leveraging the symmetric structure of our estimator.
Further, our MSE estimator is related to MSE estimation using sub- mub-sampling bootstrap (Politis et al., 1999; Geyer, 2006), where the mean-squared-emt is computed by comparing the estimate from the entire dataset of size with the estimator obtained using the subset of the dataset of size k < and then rescaling this appropriately using the convergence rate of the estimator (Hall, 1990; Cao, 1993). In our setting, we can avoid using the rescaling factor (which requires knowledge of convergence
rates) since we only care about computing the gradient of the MSE. Additionally, we had to address the distribution shift issue for our setting. For more background on statistical bootstrap, we refer readers to some helpful lectures notes (Chen, 2017a; Mikusheva, 2013; Shi, 2012; Hall, 2016). See (Chen, 2017b, 2020) for connections between bootstrap and influence functions, and (Takahashi, 1988) for connections between Von-Mises expansion (used for LOO estimation using influence functions) and Edgeworth expansions (used for bootstrap theory).
17

---

Published as a conference paper at ICLR 2024
Finally, while we leverage tools from RL, our problem setup presents several unique challenges that make the application of standard RL methods as-is ineffective. Off- Off-policy learning is an important requirement for method, and policy-gradien and Q-learning are the two main pillars of RL. As prooraaccessmpling--oe
we discussed in Section 4, conventional have variance exponential in the number of samples (in the worst-case), rendering them practically useless for our setting. On the other hand, it is unclear how to efficiently formulate the optimization problem using Q-learning. From an RL point of view, the 'reward' corresponds to the MSE, and the 'actions' corresponds to instruments. Since this reward depends on all the samples, the effective "state space' for Q-learning style methods would depend on the combinatorial set of the covariates, i.e., let X' be the set of covariates and n be the number of samples, then the state E X This causes additional trouble as n continuously changes/increases in our setting as we collect more data.
policy gradient methods can
B EXAMPLES OF PRACTICAL USE-CASES
Due to space constraints, we presented the motivation concisely in the main paper. To provide more discussion on some real-world use cases, below we have mentioned three use cases across different fields of application:
Education: It is important for designing an education curriculum to estimate the effect of home- work assignments, extra reading material, etc. on a student's 's final performance (Eren & Hender- son, 2008). However, as students cannot be forced to (not) do these, conducting an RCT becomes infeasible. Nonetheless, students can be encouraged via a multitude of different methods to partic- ipate in these exercises. These different forms of encouragement provide various instruments and choosing them strategically can enable sample efficient estimation of the desired treatment effect.
Similarly, for mobile gym applications, or remote patient monitoring settings (Fer- stad et al., 2022), users retain the agency to decide whether they would like to follow the sug- gested at-home exercise or medical intervention, respectively. As we cannot perform random user assignment to control/treatment group, RCTs cannot be performed. However, there is a variety of different messages and reminders (in terms of how to phrase the message, when to notify the patient, etc.) that serve instruments. Being strategic about the choice of the instrument can enable sample efficient estimation of treatment effect.
Healthcare:
Many online digital platforms aim at estimating the impact of premier mem- bership on both the company's 's revenue and also on customer satisfaction. However, is infeasible randomly make users a member or not, thereby making RCTs inapplicable. Nonetheless, var- ious forms of promotional offers, easier sign-up options, etc. serve as instruments to encourage customers become members. Strategically personalizing these instruments for customers can enable sample-efficient treatment effect estimation. In our work, we consider one such case study using the publicly available TripAdvisor domain (Syrgkanis et al., 2019).
Digital marketing:
C LINEAR CONDITIONAL INSTRUMENTAL VARIABLES
In this section, we aim to elucidate how different factors in (a) the data-generating process (e.g.. heteroskedasticity in compliance and outcome noise, structure in the covariates) and (b) the choice of estimators can affect the optimal data collection strategy.
Since this discussion is aimed at more qualitative (instead of quantitative results like those in Section 5) we will consider a (partially) linear CATE IV model,
Y X + fo(X) +
(18)
where Efc|X, A] + 0 but E Z] 0. As E EX constructed based on the solution to the moment vector:
the estimate is E[XZE(
E 8'X A f(X))x
(19)
where scalar, E 10 and B|Z | x = 0 (i.e. we know the propensity of the instrument and we can always exactly center the instrument). Moreover, f(x) is an arbitrary function that converges in probability some function fo-
An example: Z = w(X)VV and E X] = 0. This can simulate a situation where V represents the one-hot-encoding of collection of binary instruments, (X) selects linear combination of these
18

---

Published as a conference paper at ICLR 2024
instruments to observe, yielding the observed instrument Z (e.g. w(X) {ei,..., Cm encodes that we can only select one base instrument to observe). Moreover, each of these base instruments comes from known propensity and we can always exactly center it conditional on X.
The estimate i is the solution to:
xx =0
(20)
We care about the MSE of the estimate Ò:
MSE(0) Ex ( - 86
(21)
Lemma 1. Let V E[XX" and J = [[AAXX and E Ese2 xx"], with c= Y 8
-66
fo(X), Finally, let
U U= レーー
(22)
The mean and the variance of the MSE converge to:
REE[MS(()) - Rucleerr
n Var [ME((() + 2|
(23)
Proof. The proof is structured the following.
-Part A; We first recall the asymptotic properties of GMM estimators.
Part B: We then use this result to estimate the asymptotic property of vn(( - 0), and also of nMSE(().
Part C: Finally, we use singular value decomposition to express the mean and variance for MSE(0) in simplified terms.
Part A: Let S; = {X,, Zz, A, Yi). Recall that for a GMM-estimator, I is the solution to
Σ S,) 0,
(24)
where S.) is the moment for sample S... For large enough represent the difference between the estimates i and the true by use of Taylor expansion (Kahn, 2015).
- n Σ IF S.) + higher order terms,
(25)
where IF(0, is the influence of the sample i, and is given by E (mm))))))mmmmmm_)m (m,, S.). Therefore,
1 Vn Σ IF(O, S.) (1).
vn 0)
(26)
Moreover, (I, and Cov (IF(O, S)) EIF S)]. See (Newey & McFadden, 1994) for a more formal argument.
Part B: Therefore, the parameters estimated by the empirical analogue of the vector of moment equations in 20 are asymptotically linear:
1 - Vn
Vn(O 0o)
X,Z,Y, 0y - fo(x:)) + (1).
(27)
For simplicity, let's take fo(X) We can always redefine Y Y fo()). Moreover, let
v(X) = E[AZ X] Cov(AL Z X) and J = Elu(X)XX']. Let = Yú -Y;00 Then we have:
1
Vn(ū -0g)
(28)
Vn i=
19

---

Published as a conference paper at ICLR 2024
We care about the average prediction error:
E[(0'X X x6x)) -0 ",)'''((XX'(( 80).
(29)
Let V = B[XX]] Then,
E[(6'X 06xx²² = =
(30)
Invoking the asymptotic linearity of vni(0- - 00):
[E[0'--6x)]]]-- = vn Σ Ezzzi2//2 +1p(1).
(31)
Moreover, we have:
Σ D D4 N X1
(32)
Let = x and U = y Thus the mean squared error is distributed as the squared of the norm of multivariate Gaussian vector (O0, U).
Part C: If we let U CAC", be the SVD decomposition, then note that if ~ (0, U') then since
C'C = I, we have:
|Cull = d'C = v'== ||/||2
(33)
Now note that Cv N(0, C'UC) (O, Thus ||Cv|| is distributed the weighted sum of d independent chi-squared distributions, i.e. we can write:
||a|| Σ Xz23.
(34)
where X3 are independent (1) distributed random variables and xy are the singular values of the matrix:
U = -
(35)
Using the mean and variance of the chi-squared distribution, asymptotic mean and variance of the RMSE can be expressed as:
n E
+
Σ
(36)
j=1
n [ar((( +
Σ Var Va)
13 Var(X?) [ 233
(37)
Thus the expected MSE is the trace norm (or nuclear norm) of U and the variance of the MSE is twice the square of the Forbenius norm.
C.I SPECIFIC INSTANTIATIONS OF LEMMA 1
In this subsection, we instantiate Lemma understand the impact of heteroskedastic compli- ance, heteroskedastic outcome errors, and structure of covariates on the optimal data collection policy.
Note that U in Lemma 1 takes the form:
U |XXXX XXAA:///TXTTTEXXXXXXXXXXXXXXXXXX
(38)
Noting that by the instrument assumption IL | X, and denoting with
(x) Eie² X]
(residual variance of the outcome)
(39)
"² (X) E[Z² X]
(variance of the instrument)
(40)
(X) B[A2 Z X
(heteroskedastic compliance))
(41)
E|Z
X
20

---

Published as a conference paper at ICLR 2024
where the heteroskedastic compliance corresponds to the coefficient in the regression A ~ Z con- ditional on X. Then we can simplify:
U - -/Ap////w//KT/TToooo////x///xxx"
(42)
Remark (Homoskedastic Compliance, Outcome Error and Instrument Propensity). If we have lot of homoskedasticity i.e.: (x) = 0², x²( x² and n,²? (X) = tthn U simplifies to:
U = 7 2u // v1/2 = 7 2021
(43)
and we ger:
[[MSE(0)] = d -7 -2 202
(44)
Varl = 2 d
n² u 04
(45)
Thus we are just looking for instruments that maximize Y where 7 == B[AZ]/E[ZZ] is the OLS
coefficient of A ~ Z (the first stage coefficient in 2SLS) and u v /Var(2) is the standard deviation of the instrument.
Remark 2 (Homoskedastic Compliance and Outcome Error). If we have homoskedasticity in com- pliance (i.e. x(X) = =n) and in oulcome (a = о), then:
U=
(46)
Or equivalently, we want to maximize the trace of the inverse Uf:
E(XX111/2E [7? XXXXX
B[XX'1 1/2
(47)
As XX' is positive semi remi-definite the latter is maximized if we simply maximize (yu(X)frrr for each X. Thus assuming that all the instruments in our choice set have homogeneous compliance, then are looking for the instrument policy that maximizes: "yu(X), where ry is the compliance coefficient and u(X) the conditional standard deviation of the instrument. for instance, in our choice set we have only binary instruments and we can fully randomize them, then we should always randomize the instrument equiprobabll and we should choose the binary instrument with the largest 7..
It is harder to understand how the trace norm or the schatten-2 2 norm of these more complex matrices behave. Though maybe some matrix tricks could lead to further simplifications of these.
Remark 3 (Orthonormal Supported X). If X takes values on the orthonormal basis fei..... ei}, }.
then by denoting of = E|e² X = ei). ui E|Z² X es] and %
E[A 2I and by 7 X oq
(u?,,..,, Σ. = (at, and K = diag (u? ..i......... 2g}) and r = diag
)a). let V = R [
W W'W' be the eigen- rige--representationn of then we have:
{(o"(X)=(()xXX' E (X(())(X)XXX WAPKW'.
WAKEW'
(48)
(49)
Leading to:
-- W
(50)
which by orthonormality of the W, simplifies to:
U U-WI-2K-12w
(51)
hence we get that:
of Σ
E2(22 X = e E[2 X = ci)
nE ()(
Σ
(52)
22
E|AZ X e
of
n² Var[MSE(()]
2 Σ
(53)
7 A.
21

---

Published as a conference paper at ICLR 2024
Compliance
Instrument Var. E 2
Estimator
Optimal?
X=1
X
X = -1
X
1/4
0
Yes
1/3
1/4
1/4
No
Bn (Y - 0 X A)X 2 =0
1/4
0
No
1/2
1/4
1/4
Yes
174
0
No
1/3
1(2 En
[I(X] (Y - 0 x 2 = =0
1/4
1/4
Yes
1/4
0
No
1/2
1/4
1/4
Yes
Table 1: In general the optimal instrument-selection policy will depend not only on compliance
per covariates but also the estimation method. We demonstrate this here for simple linear CATE estimation where g = 0g XA, instrument Z is a scalar, A E {0, 1). X E {-1,1), E|Z X] O, and outcome error is homoskedastic. For the first estimator, the optimal instrument- selection policy for = changes depending on the compliance for X 1, where we characterize optimality in terms of the asymptotic mse. In contrast, for the second estimator, randomizing the instrument is best for both compliance values of =
and the problem decomposes into optimizing sepurately for each i, maximize the terms:
74 AZ
= x x=
X
R x X=
(54)
2
assuming that our constraints on the policy for choosing Z are decoupled across the values of X. So similarly, we just want to maximize the compliance coefficient, multiplied by the standard deviation of the instrument, conditional on each X.
Beyond this case, when X doesn't only take values on the orthonormal basis, then the problem of optimizing the choice an instrument distribution so as to minimize the expected MSE doesn't 't seem to decouple across the values of X.
Remark (Scalar X). One can see the intricacies of the problem when there no homoskedastic compliance, even when we have scalar X. In this case, are trying to maximize:
U-1 (XX)
(55)
Suppose for instance that X ~ U({-1,1}) and that our policy can only choose the conditional variance of Z, but the conditional compliance v(X) (e.g. we have a fixed binary instrument and we can only play with its randomization probability). Then we are maximizing:
(n + 2222)
(56)
of u 0žu6
over u², un 1/4] (the variance of Z for each value of X). Without loss of generality, we can take 71 = and σ1 in the above problem, since we can always take out these factors and rename 72/71 + 72 and 02/01 - 02. We then get the simplified problem:
(uf + T22)2
(57)
u + o2u3
where 7, E 00).
Take for instance the case when
(i.e. homoskedastic outcome error) and y 1/3 (i.e.
compliance is 30% less for X = than for X = -11 Then the optimal solution is uř = 1/4, v² 0, i.e. we don't want to randomize the instrument at all when X 1, yielding a value of 1/4 = 0.25 for 1-1 If were for instance to randomize also when X then would get value of 1//3)2(11/// = 2/9 = 0.22.
on the other hand 7 1/2, then if we randomize both points get (3/8)² 0.281, while if we only randomize when X = then we get again 1/4 = 0.25. Thus the relative compliance strength for different values of X, changes the optimal tandomization solution for 7.
(1/2) 9/32 x
22

---

Published as a conference paper at ICLR 2024
Remark 5 (Efficient Instrument). It may very well be the case that the above contorted optimal
solution is an artifact of the estimator that we are using. Under such heteroskedastic compliance, most probably the estimate that are using is not the efficient estimate, and we should be dividing
the instruments by the compliance measure (i.e. construct efficient instruments, e.g. Ż Z 2x(X))
x²(X)
Then maybe once we use an efficient instrument estimator, its variance most probably would always be improved if we full randomize all X points. But at least the above shows that for some fixed estimator (and in particular one that is heavily used in practice), it can very well be the case that we don't 't want to fully randomize the instrument all the time. If we use such an instrument ž then observe that for this instrument, by definition ((X) =²²(X, Then U simplifies to:
u (X) XX (x
E[XX11//
B[Xx1/2
(58)
(X) iee. maximize the product of the OLS coefficient of Thus we just want to maximize x-(X)
A conditional on X' and the conditional standard deviation of the instrument.
Revisiting the simple example in the previous remark, when we an efficient instrument, the matrix U-1 takes the form:
2
2
(59)
For the case when ? = 1/3 and a = 1, if we choose u² -/4, we get 1/4 1/36 (compared the 1/4 we would achieve with the inefficient estimator under the optimal randomization policy). When y = 1/2, with the same u². we would get 1/4 + 1/16 = 0.3125, which is larger than the 0.281 we would get under the optimal policy with the inefficient estimator.
Remark 6. (Non-conditional IV) Even when X x= always, it can be shown that randomizing single binary instrument equiprobably might be sub-optimal. To show this, we will consider the setting where there is heteroskedastiicy in oulcomes with respected to the treatment A, thus with slight abuse of notation lei (Z) = B[e² Z). Under this setting, we can simplify,
U =
(60)
U (()²
(61)
E[yu2]
B[o2(Z)BB
xx(x E|
(62)
(rB1223))
where is the centered instrument. Now assume 7 = 1 (full compliance, i.e., A Z, such that (2 0) of variance in outcome for treatment A = 0, and of is defined similarly.), and 7 E {0, 1} with probability and (1
p).
U 1211 p + p(1 2)0011
(63)
p² p)²
pad + (1 p)o
(64)
p(1 p)
o3 + of
(65)
1-p
When oe = and of = 2, then the minimizer is p R5 0.6, thereby illustrating that drawing the binary instrument equiprobably can be sub-optimal even in this simple setting.
Equivalently the efficient instrument can be viewed as the normalized residualized efficient instrument (x( : F[A Z, X|A X). and (XX is the heterogenenus compliance; normalized by the conditional variance of the conditional moment (X).
23

---

Published as a conference paper at ICLR 2024
D INFLUENCE FUNCTIONS
Influence functions have been widely studied in the machine learning literature from the perspective of robustness and interpretability (Koh Liang, 2017; Bae et al., 2022: Schioppa et al., 2022: Loo et al., 2023), and dates back to the seminal work in robust statistics of (Cook & Weisberg, 1982). Asymptotic influence functions for two stage procedures and remi-parametric estimators have also been well-studied in the econometries and semi- sami-parametric inference literature (see e.g. (Ichimura & Newey, 2022; Breheny, 2020; Kahn, 2015)). Here we derive finite sample influence function of two-stage estimator that arises in our IV setting, from the perspective of a robust statistics definition of an influence function, that approximates the leave-one-out variation of the mean meea--suured-error of estimate.
Influence functions characterize the effect of a training sample S. = {X,,, A,, Yi} on (for brevity, let / = ((D)). i.e., the change in Ó if moments associated with S; were perturbed by small Specifically, let & be solution to the (,, Ø) = 0 and & be solution to Qn = 0, as defined in 3. Similarly, let &- c... be solution the following perturbed moment conditions
M 0, Φ.) 0, and de is the solution to Q(e, Φ) 0, where
0c (0, () + em, o), Qm( (q((s, Φ) =0.
(66)
(67)
The rate of change in MSE due to an infinitesimal perturbation in the moments of S; can be obtained by the (fdrst-order) influence function IMSE which itself can be decomposed using the chain-rule in terms of the (first-order) influence Z on the estimated parameter 0 by perturbing the moment associated with S,,
IISE (S.)
d do
MSE 0 )
c. where, (S.) = de
db
(68)
e=0"
To derive the influence function for our estimate we will use the classical implicit function theo- rem:
Theorem 1 (Implicit Function Theorem (Krantz & Parks, 2002)). Consider a nulti-dimensional
vector-valued function F(x,z) E R", with E Rm and y E R and fix any point (Zo, Yo), such that
F( Ho) =
(69)
Suppose that F differentiable and let F2(x, y) and Fx,x,, v). denote the Jacobians of with respect its first and second arguments correspondingly. Suppose that der (2o. yo)) * 0. Then there exists an open set containing Fn and a unique function w(x), such that (((a)) = yo and such that F(x, 1b(x)) for all U. Moreover, the Jacobian matrix of partial derivatives of vi in U is given by:
2 (1))))))
(a
v2((a) Ox,
- (z,(,)) (a(a,(())
(70)
nxm
F is k-times differentiable, then there exists an open set U and unique function 1i that satisfies the above properties and is also k-times differentiable.
Theorem (Influence Functions for Black-box DML Estimators). Assuming that the inverses exist,
0Mn (0, .) m(S.. 0,0) aM,
TQQu -1 dø (0))()) .))
(S.)
(0, 2)
(71)
00
as
Proof. Let 0, & be the empirical solutions without perturbation. Note that the e-perturhed estimates (()), (b() are defined as the solution to the zero equations:
M(c, 0, Φ) Mf, Φ) + cm( 0,0
(72)
[(c,0)= Qn(() cq(Si,
(73)
24

---

Published as a conference paper at ICLR 2024
Defining y (0: Φ) and F(c, (0, (M,(,, Q(, Suppose that:
(O, (0, x)) = DoM, (0, @) (0.,, (O)
]
(74)
0
is invertible (equiv. has a non-zero determinant). Note that for the latter it suffices that the diagonal block matrices are invertible, since it is an upper block triangular matrix.
Applying the implicit function theorem, we get that there exists an open set U containing = 0 and
unique function (b()) (f(c), o(c)), such that (0) (0, σ) and such that (b(c) solves the zero equations for all c E U. Moreover, for all c E U:
D.0(e) De
|
(e, (0(c), d(e))) (e,e, (((c)))(()))
(75)
Using the form of the inverse of an upper triangular matrix² and applying the latter at we get that D.0(0)
takes the form:
Do0(0)
Do [0.) - [D) D2
[DoQ.(0)]
m(S,, Ø)
]
[D)Qn((0]
((S,, Φ) (76)
0
Since the influence function is (S.) = D.0(0), we get the result by applying the matrix multi- plication.
Higher order influence functions can be calculated in similar manner, using repeated applications of the chain rule and the implicit function theorem. Note that writing an explicit form for general k-th order can often be tedious, and computing can be practically challenging. Discussion about higher-order influences for the single-stage estimators Der Schaar (2019) and Robins et al. (2008). As we formally show in Theorem 5, for our purpose, we recommend using K as it suffices dramatically reduce the variance of the gradient estimator, incurring bias that decays quickly, while also being easy to compute
be found in the works by Alaa & Van
(Alternative) Informal Proof. Here provide alternate way derive the form of the influence function without invoking the implicit function theorem. This derivation only makes use of the chain rule of the derivatives. In the following, we will use Of to denote partial derivative with respect to the immediate argument of the function, whereas of is for the total derivative. That is, let f(, g(x)) xg(x) then
0s (z. (()) = g(x) dr
af (a. = g(x) + x 0g
(z).
(77)
dr
Ōr
From 67 we know that i f. is the solution to the moment conditions Mil (c.0, 0z
M (c, 0. ..)
b))= = n
Σ m(S, 0 f.. .x) + +em(S. B... 6=)==00 =0. 0.
(78)
j=1
Therefore,
d.M (e, c.
b.) = Σ
1 n
dm
(S,,
0 0..00 ..) + mmS., (...
d.) + e dm (S,, 0 d.)
(79)
de
n1 j=1
de
de
dM (Ø (e, : 6.) + m(S;, 0 0. ..) +
dm
(Si, c. 6c)
(80)
de
de
aM, ( 0 3.)
dd
aM,
3.) dô.
dm
+ (0
+ m(s, 0_ (.
Sc) +
(S 0 a. ge).
00
de
do c
de
de
(81)
A
-1
-A -A -1 B-1
For any block matrix:
0
B
0
25

---

Published as a conference paper at ICLR 2024
Further, note that,
d6
09 c.d.
06 c,
dΦ. de
(82)
dc
de
OΦ
Using the fact that (e, O c,
/.)/de = O, rearranging terms in equation 81,
db c.o.
OM, - de 00 (0 22) m(S.. 0,, Φd) +
dm (S 0 0. 2e) + do (0 (0.
OM,
do
Φ.)
de
de
(83)
Now we expand the terms in blue. Similar to earlier, since &e is the solution to the moment condition Q (e, ④) 0.
Q (c.
1 Σ
ass,, + + = 0.
(84)
j=l
Therefore,
dQ
(e.0.)
dg
(S), 6.) + ((,, δ.) +e dq (S (S,, 2c)
(85)
de
de
de
dQn (d.) (( Φ.) + (S 2.)
dg
(86)
aQn dô
dg (Si, &c)
(
qS,, dc) + de
(87)
0s de
Now using the fact that dd((e, / 0, rearranging terms in equation 87,
dø.
dQn -1 (6.) q(S., 2.) + de de OΦ
dg (St, dc)
(88)
Combining equation 83 and equation 88.
dd c. de
aM, -1 00
m(s,, 0 : d.) +c dm
(0 (0.g.
3e)
(S Prg.
(89)
de
OM, (Ø c. ).)
TQQn -1 Oo (o.) g(S,, Se) de (S, d.)
dg
|]
(90)
do
de
At E = 0, notice that 0, 0 and do = Ô. Therefore, using equation 90,
db c.
OM, -1
aM, dó
[QQn -1 Os (0)n(S.
(0 m(S,, 0,
(0,
(91)
de
c=0
00
E BIAS AND VARIANCES OF GRADIENT ESTIMATORS
To convey the key insights, we will consider log (S,) E IR to be scalar for simplicity. Similar results would follow when V log (S;) Rdd.
E.
NAIVE REINFORCE ESTIMATOR
For any random variable Z. we let ||Z||>> (E(Zz))
Theorem 3. E [() = VL(T). Moreover, let:
X, = -MSE(0((S:))
(92)
26

---

Published as a conference paper at ICLR 2024
denote the leave-one-out MSE and let:
A (-)))()))) (SE(
(93)
denote the leave-one-out stability. Suppose that for sufficiently large n,
| S 522, 1|X
(94)
and for Yi = V log (S.), let Vi, IY I C and ||Gllaa 2 <>> 0 0.ror some universal constants c, C,C,C,, Then the variance of the naive REINFORCE estimator is upper and lower bounded as:
3C
- nn|xXi O (1211Ai112z) & Var ((C(T))
2 n X1 + +0 (121411122))
(95)
2
Thus, when n 1 0(1) and n (| = M(a(n)) = w(1), we have
Var (ar(v((m) ((a(n))
(96)
Remark 7. In many cases, would expect that the mean squared ervor decays at the rate of n 1/2 (unless we can invoke a fast parametric rate of 1/n, which holds under strong convexity assumptions); such cases, we have that c<(n) = w11) and Var (VL(T)) can grow with the sample size. Moreover, if the mean squared error does not converge to zero, due persistent approximation error, or local optima in the optimization, then the variance can grow linearly, Lee a(n) = O(n).
Remark 8. The quantity A is leave-one-out stability quantity. Hence, the property that n||A|| ((1) is a leave-one-out--eeeeee leave-one-out--stabllity property of the estimator, which is a well-studied concept (see e.g. Kearns & Ron (1997); Celisse & Guedj (2016); Abou-Moustafa & Szepesvári (2019)). It states that the estimator is 1 m/n-leave-one-oue stable. This will rypically hold for many M-estimators over parametric spaces.
Proof. In the following, we first define some new notation to make the proof more concise. Subse- quently, we show (I) unbiasedness, and then (II) we discuss the variance ((r)
Let D,, be the entire dataset {5;
mt i=1 where S; is the i-th sample.
Z MSE (S,) y V log x (St)
(97)
= MSE((( (S, )-=))
(98)
X; == MSE (((S)) ((S)))
(99)
A; = X;
(100)
Y V log (S.)
(101)
(I) Unbiased
E
[
E, Σ MSE(O((S.)E)))) log (S.))
(102)
(a) IE, (MSE((()))) Pr(D;,
(103)
VE, [ME((((())))))
(104)
VL(#).
(105)
where E, indicates that the dataset D,, sampled using ग, and (a) follows from 5.
(II) Variance
Var (VL(T)) Var Σ Z; = Var
x
Yi
(106)
Notice ( i.i.d random variables, and X is dependent all of (Y;),,, which makes the analysis more involved. We begin with the following alternate expansion for variance,
Var Σ4)= = ΣΣ Cov 2z),
(107)
where, Cov(Zi, Zz) CoV(XY, XY,) Cov( - +A)Y).
(108)
27

---

Published as a conference paper at ICLR 2024
Therefore,
Var Σ 2i 2:)
Σ Cov(X, + Cov(X,,, A.Y, + Cov(A, XYY,) C,,
(109)
Now, observe that as X, 11 Y, y; _1,,1,, y, and - = B[X,Y,] 0. Therefore, Cov(X,,, =
O,
Vi サ
(110)
Cov Cov(X,Y X,Y,) [[
=i=
(111)
For all i,
Cov(X, ANY) = EX EX = B[X,N, Y, B[XAY,, EA
(112)
(113)
JN (IATYHELATY S C
[C,, AY1
(114)
where (a) follows from Cauchy-Schwarz by noting that for any two random variables A and B,
Cov(A, B) & Var and that Var(A) & B]. we let Y Σز= Y, we have:
Var Σ Zi)
Σ E[X < ΣΣ 2EIX -AXX +nAC*[[Ai]
(115)
- + =
(116)
Now, by assumption we have that ||Y||l== S C for some constant C. Further, from Cauchy- Schwarz, [[AB]] I /E[A?]E[B?] for any two random variable and B. Thus we get:
E BA S EI B[X B[
(117)
E / nE((?
(118)
1Yile SC
(119)
= CA X 12
(120)
where (a) follows from observing that B[C, Y.)a BE i MY = E Y? = (Y as
E[ = for * j. The final expression uses that V
= X 12 Similarly,
E E| < / S C || (E|X 1/4
(121)
Now by the Marcinkiewicz-Zyymund inequality Rio (2009) we have that I E, Y
5
G2IlYi for any p 2 and for universal constant CN- Therefore, (E(Y-1) /nCC/|Y/llz and
5
E|AAYY| < CCllANllll/XXille//lXX
(122)
(123)
(124)
where the last line follows ||Xi|L 120, and 124, we conclude that:
Ca, Thus for some constant Ci, combining 116,
Var Σ 2 - Σ
BXX?Y? S C2 Σ VrllA + 12.2.
(125)
We note here that an important aspect of the proof is to first push the summation inside to get Y and then to apply the Sauchy-Schwarr incquality, since Y concentrates around /n and one saves important extra vn factor.
28

---

Published as a conference paper at ICLR 2024
Recall from the AM-GM inequality that for any and b: a 2,a² 2nb² for any n 0. Let
Ci SivulAA and b ||Xi||>> /E[x?] and rj /24 then
2c 122
Var Σ Zi
Σ B[ - Σ
[ + + (126)
α²
Since d² < Y <
C and X; 1T Y. we have E[
E| < C and
E[X 2 E X Further, as
B
+ C and A N
C, we obtain the
lower bound:
B[X,]e 20
2²
(
Var
Zi 2
n 13
(127)
c²
2
n
B[xi| - (112)))
(128)
2
Similarly, for the upper bound:
B[ + 20 Ailia
c²
Var E Z1
A1
(129)
2²
3C S E[xi] +0 F.2))
:. S C
C2
Therefore, we obtain our result
c²
3C2
2 n n f.2 0 (1?11A,11 & Var ([(T)) _ 2 n||x1li + +0
(130)
E.2 REINFORCE ESTIMATOR WITH CV
Theorem 4. E [()) V.(T). Moreover, let:
A =
-
(131)
denote the leave-oneoout stability. Let Y; = V log x(S)) and suppose that and that ||ill L S for some universal constant C. Then the variance of the CV REINFORCE estimator is upper bounded as:
Var
& 1n
(132)
Thus if the estimator satisfies n -lave-one-out stability, i.e. nlIAi O(1), then we have: S 0(1).
Var Var (())
(133)
Remark 9. This holds irrespective of a(n), thus providing more reliable gradient estimator even if the function approximator mis-specified or optimization is susceptible to local optima.
Proof. Let Dn be the entire dataset (S.)) where S; is the i-th sample.
Z; V log o (S;) MME((((SS))) MSE((((S)))
(134)
A; MSE(O((SS)) - MSE MSE(O((())) (((()))
(135)
Y, (Sg
(136)
29

---

Published as a conference paper at ICLR 2024
(I Unbiased
E pcv L(T)]
= E Σ
v log T(S:) (MSE(((())) (SE(0(15)] -F
(137)
Ex
[[(TT]
- EE
Σ
v log (oggs
(138)
(a)
VL(TT - E Σ MSE(((DDM.)) E, V log (S;) Days
(139)
VL(T),
(140)
where (a) follows as S, 11 Dayi and Ex, ( log (S;)) 0.
(II) Variance
Let Z, = Zi [[ First, observe that
27
( Σ 24
Var
Σ 7 = -Var
- - 74
= E
(141)
11
From Jensen's inequality, as E. 2i)²
S + Σ, (2:)²
Var
Σ4
v Σ
E|
1 Σ
(i))
(142)
n
i
Therefore,
Var (()L(()) Var
Σ Uz S
Σ Var Var(Zi)
n n E[A S n CPEAAA
(143)
E.3 REINFORCE ESTIMATOR WITH INFLUENCE
Theorem 5. E ( V[()) OOnnnnnn Moreover, let:
A = MSE( MSS((((())))
(144)
denote the leave-one-oul stability. Let MSE(O
admit convergent Taylor series expan- sion. Let Y; = V log π (S,) and suppose that and that ||Y|ll S C for some universal constant C. Then the variance of the Influence function based REINFORCE estimator is upper bounded as:
Var ***((x)) = 0 (0 + =2)1-k))
(145)
Thus if the estimator satisfies -leave-one-out stability, iee. nl/Ai||r> O(1), and K 2 1, then we have:
Var (FL < O(1).
(146)
Proof. Let (Y.) be i.i.d random variables, and let A; be variable dependent on all of (Y;)
Z; = V log 77 A
(147)
K
(-1/n)*
A, =
MSE = A; + +On
(148)
k!
K=1
A MSE ( ((S)))=))) MSE((((S,))
(149)
Y, V log (Sa)
(150)
30

---

in Published as a conference paper at ICLR 2024
Notice (-))-1 are i..d random variables, and Å, is dependent all of {Y The bias follows from standard results on K-th order remainder term in a convergent Taylor series expansion. Finally, can be observed that Var E Zs) follows the exact same analysis as done for (()):
Var 4 ((T)) S Sn S < + O
En' + n n
(151)
F ESTIMATION ERROR, BIAS AND VARIANCE ANALYSIS
F.1 PRELIMINARIES ON U-STATISTICS
We first present a result on the variance of U-statistics with a growing order that primarily follows from recent prior work. For references (2018b) and some concise course notes [A, B, C. D, Ej. With slight abuse of notation, in the following let Zg represents set of S random variables (and is unrelated to notation for instrumental variables). Let n be the number of random variables available and k be the size of the selected random variables.
Fan et al. (2018); Hoeffding (1948); Wager & Athey
Theorem (Variance of U-Statistics). Consider any k-order U-statistic
1
h(ss)
where h is symmetric function in its arguments. Let:
Var(B[M(Z) Z1de))
(152)
Then, we have that:
-1
n k) k: Ne.
Var(U)
Σ
(153)
k
Moreover, one can show that:
2.2
k22
22
1/2
S Var(U)
171
n² nk
(154)
n
and that
1
(155)
These results, for instance, follow from the classical Hoeffding's canonical decomposition of a U- statistic and an inequality due to Wager Athey (2018b), to upper bound the non-leading term, for every k. n, ......, 7k not just asymptotically and for fixed k ........ Tjk, and letting Hoeffding's 's classical analysis. The proof is included in Appendix F.5.
Typically, due computational considerations, one considers incomplete version of a U-statistic, where instead of calculating all possible subsets of size k, we draw B random subsets {Si..... S ) each of size k. uniformly at random among all subsets of size k. Then we define the incomplete U-statistic approximation as:
B Σ hZss))
(156)
B b=1
We can also derive the following finite sample variance characterization for an incomplete U- statistic:
Lemma 2. The variance of the incomplete U-statistic Ú is:
Var(i) = (1 (1-3) Var(U) + B 7
(157)
31

---

Published as a conference paper at ICLR 2024
Proof.
Note that Ü is unbiased estimate of U, conditional on the samples, i.e.:
B[Ú Zi:1] U.
(158)
Moreover, the variance of an incomplete U-statistic can be decomposed by the law of total variance, as:
Var(U) Var(EE( Z1:n)) + E[Var(U Z1m) = Var(U) + E[[ar Zim)].
(159)
Note that, conditional Z1 the incomplete statistic Ü is the mean of i.i.d. samples of h(Zss).
where S is a random subset of the original n samples of size k. Thus:
Var(U ZI..
Var Var(h(Z2)) (Zs) Zim)
(160)
B
Combining 159 and 160,
1 B(Var(h(Zs) Zim)).-
Var(t)= = Var(U) +
(161)
Moreover, note that the un conditional variance of the first & samples, is equal to the unconditional variance random subset of the samples, since we can equivalently think drawing k i.i.d. samples, by first drawing samples and then choosing random subset of them.
Var(h(Zi:+)) = Var Var(h(Zs) = Var(E[h(Zs) ZIm,)) + (h())(((Zss) Zim)
(162)
Moreover, note that by the definition of the random sample S and the U-statistic:
E (Zs) Z1:1] = U Var(E(N(Zs) Ziml)) Var(U).
(163)
Thus we get:
Var(U)= = Var(U) + Var(h((71x)) Var(U)= 1
Var(U) +
B th-
(164)
BB
F.2 VARIANCE OF IS PROCEDURE
Observe that for the full n sample size, the importance sampling based estimate of MSE is
[II V=1
n Pr(Dniz) MSE(O(D,.))
[II m (ZII),) (Z,x..))
MSE R
E
E
MSE(O(D,.)
D. (
Pr(Dn:
D
(165)
where (a) follows from expanding Pr Pr(Dnim T and Pr(D,; m.) using 6. Let MSF, be the estimate of MSE for a subset dataset of size k obtained using importance sampling and a complete enu-
meration over all subsets of n of size k. Similarly, let MSF, denote it's computationally friendly approximation that draws subsets of size k uniformly random.
Moreover, for simplicity, we will assume here, that given a sub-sample of size i we can exactly calculate the MSE of the estimate that produced from that sub-sample. Since our goal to showcase the poor behavior of the IS approach, suffices to showcase such a behavior in this ideal scenario.
Theorem 7. If [M)) akk) then
Var(MSE a1²)
12
n
k.
Pinxx
(166)
k
k
122
h22
< a(x)2
Pmax
+
no Piuaxx
(167)
(Mr(M 15 5 aBk)
122
22
1
Pmax
n2 Punax
pmnax
(168)
B
32

---

Published as a conference paper at ICLR 2024
Moreover, for any deterministic data generating process without covariates, and for any determin- istic policy x. the variance can be exactly characterized as:
Var(MSER a(k)²
1
-1
n2 - kb k c c) (Pmax - 1).
(169)
k
C=1
Var(MSSA (1-B)
T3
1 Var (ar(MSEE + a(k)) (P - 1).
(170)
B
Even though the lower bound formula for the complete U-statistic hard to parse in terms of a rate, that for many reasonable values of n and k. its dependence in Pmax is exponential (see Figure 7). Moreover, is obvious that for any finite B (which would be the typical application), the dependence in Piaxx is exponential in k, due to the extra variance stemming from the random sampling of subsets.
Proof. Let n be the total number of samples. Let o(n) be the desired number of samples. To consider analysis with all possible combination C(n, k). we will construct a U-estimator. Let the be the kernel for the importance weighted base estimator, and D& (5:)
h((S:)=)) = PI:k MSF(((D))))
(171)
Pisk = II P(S.).
(172)
1=1
The U-statistic corresponding to this kernel is
U kl(n k)!
< ((S
(173)
n!
For this kernel, we can derive that:
[[((() Z
E (E [1:e]]
(174)
E (SS(( St:e] Piie
(175)
Ex (MS)(((De)) S1.0 Pi:e-
(176)
Thus have that:
Te Var (B(h(22)11:ee)
(177)
E E., [MSE(O(D:)) S1:c] Pi:c E, [MSE(((D())]
(178)
F Er [MSF((((D:)) S1:c] P1:c
(MME((((()))))))
(179)
S EE, EE [MSE( S1.e] P1:e] E, (MSE(((D)))
(180)
S E,
Ex MSS(((D))) S1.e]] P
- E, (M))((()))))
(181)
F [MSF(O(D2)))
Piaax - By (MEE((())))
(182)
Upper bound From this we can derive the upper bound:
7e S Ex [MSE(((D&)) PIaxx (k)))pnaa
(183)
Which, by invoking Theorem 6 yields the upper bound:
n k
Var(U) a1:)
Pinax.
(184)
1:
Moreover, from the looser upper bounds in Theorem 6, we also get that:
2
1.2
Var(U) akk)
Punax +
n² Pimax
(185)
33

---

Published as a conference paper at ICLR 2024
20
Figure 7: Behavior of complete U-statistic variance n 1000, 100 as a function of Pmax-
Then, by invoking Lemma 2, have that the incomplete version of our estimate with B random sub-samples of size k has:
Var(ū)=
Var(U) + TThh
(186)
1 1 Var(U) + + (k) Pt
(187)
122
h2 Piaax
S ax (k)2
Pmax +
n2
B3 TPmax
(188)
where the first inequality comes by upper bounding Equation 182 and using our assumption in the Theorem that Er [M a(k)², and the second inequality comes from substituting in Equation 185.
Lower bound In general hard to characterize the lower bound. However, in the following, will show that for a certain class of problems, the lower bound on the variance from using the importance sampling procedure can grow exponentially. Specifically, for this theoretical analysis, consider the case where there are covariates, all aspects of the data generating process is deterministic, and the policy π is also deterministic. Figure (Right) provides an empirical evi- dence of exponential growth of variance for more general setting with both stochastic policy and stochastic data generating process.
Notice that (182) follows with equality when steps (180) and (181) follow with equality. This holds when the entire data generating process is deterministic and the policy π is also deterministic. Further, since there are no covariates and that deterministic policy, then Pt Pmax almost surely when S; is drawn from x. Therefore,
Te E, [MSE(B(DA)) (DE))) PiNxx E, [MSE(0(D:)]
(189)
E, (SE(((D))) (p (Pmaxx
(190)
akk))2(fuxx 1), where the last equality holds because π is deterministic, and by our assumption the Theorem, E, [MSE( = akk)) Moreover, from Theorem 6, the variance of the U-statistic is:
(191)
Var(U) = (1))2
Σ
n k) x) (Pimax - 1).
(192)
k
Similarly, using Lemma 2, the variance of the incomplete U-statistic is: Var(() 1
Var(U) + TM
(193)
B
Var(U) + (k)) B (Piaxx -1),
(194)
B
where in the second equality we have used Equation 191.
34

---

Published as a conference paper at ICLR 2024
F.3 GUARANTEES FOR REJECTION SAMPLING PROCEDURE
We will analyze the bias and variance of the estimate of the mean squared error of the rejection sampling procedure. Almost identical analysis also applies to the analysis of the bias and variance of policy gradient estimates based on the rejection sampling procedure, but we omit it for concise- ness.
Let n be the total number of available samples. Let MSE be the estimate of MSE for subset dataset of size k, obtained using rejection sampling. This estimates first accepts a random subset of size N' and if N' < k returns 0, otherwise if No 2 k, returns the estimate that goes over all subsets of size of the N' accepted samples:
N'
MSE
R
MSE(0(15,,))..)
C
k
(195)
M
MSF(O(D))) = M
A;; - (;;,, Σ 1=1
(196)
where MSE(0(D) is the estimate of the aquare error produced by the samples in De. (same as 14) and where (X,, A. = are held-out samples of covariates and treatments (outcomes for these are not available), which is not used in the estimation of 0, i.e. is separate from D,, We will assume throughout that M >>
RS
We will also consider an alternative estimate MSEg that is the computationally friendly approxi- mation that draws B subsets of size & uniformly at random from the N' accepted samples, instead of performing complete enumeration
subsets of size done for MSE
Theorem 8 (Consistency of Rejection Sampling). Consider the rejection sampling estimate MSF Rs as defined in Equation ( (195) and its incomplete U-statistic variant MSF. For any dataset Dn, of iid samples of si'ze 'e n. drawn from policy n, define:
a(n) (MSE(O(D,)))lla
(197)
Assume that ks S n1/2 and large enough, such that n/ log(n) 2 8pmax. Then:
Var (MSE)*) S o (ak))2 lipmax
+ M + +t(mm))
(198)
BIAS SIAS(MEE;) < ((k))e-m n n/8Pamxx + VM
+ va(n))
(199)
and similarly for the incomplete variant:
MSE S o a(()) (o(k)=kpmaxx kpmmax + a(k)²
1
1
Var
B + + a((n)
(200)
no
M
BIAS
MSE,
S (ukk)e-//ppal n/8pmax
VM + va(n)
(201)
Moreover, the probability faiture, i.e. Pr(N' < k), is bounded as: e (n//(Mpmas))
Proof. Let be the total number of samples and N' be the number of of samples accepted by the rejection sampler, which in expectation equals to n' == TE[N" = n/ a/Pmaxx- Like before, let l be the desired number of samples. Let D3 }.
We first consider the difference between MSE? from 195 and its ideal analogue (note that this ideal version is biased as it returns 0 when N' < k).
(N''
U MSE 11-1))
c
(202)
k
(S)() = Ex.A (;(() - f(X, F(X.,.)))))
(203)
We now break the proof into three parts:
35

---

Published as a conference paper at ICLR 2024
Part I: Express bias and variance of MSE in terms of bias and variance of U.
Part II: Compute Variance of U (for both complete and incomplete U-statistic).
Part III: Compute bias of U (for both complete and incomplete U-statistic).
(Part 1) Bias and variance of MSE in terms of that U: We will first express the error of
MSE in terms of the the convergence rate of MSE(((D,))) as 0 (D,) is used as a proxy for 0g by MSE l Observe that,
E IIMSEE - U)
(204)
[E.. (MSE(((())) - E., (MSE(((Da))) ]
(205)
(M)) (MS(((())) |
EE
(206)
(MSE(((())) - MSE(((())
< E
En
(Jensen's 's inequality)
( MSE(((()))
E
(207)
(a)
E
(MSE(O(D))) MSE(((D&)) - )
(208)
((DD))(())) MSE(O(D))) | 2B (MIEE((())) - MSE()
21E
(209)
where (a) follows from defining an intermediate quantity MSE which unlike MSE(O(Da)) 195 computes the true expectation instead of empirical average.
MSE(O(D))) = Ex.A (F(X,, - ((x.))))))
(210)
and (b) follows from (a + 6)2 < 2(a + b²). Now we bound the two terms in the RHS of 209.
To bound the first term in the RHS of 209, note that since predictions are uniformly bounded and the M samples are independent of the samples Dn. we have:
MSE(O(D.)) MSE(O(DA)) M
(211)
for some constant C, since MSE(O(Da)) is the mean of MSE(O(D))), conditional on D, and MSE ()(D)) is the sum of M iid variables, conditional on D,,-
To bound the second term in the RHS of 209, have that:
MSE(((D))) (MSB)) (O(((((D))))
(212)
EX.A [f(X,A:00)) (U..A002))---C.AAA000.--)-.1
(
(xX, -(x,X
(213)
< E Ex.A (J(X, A;00) - ((X, (;(,)))
(Jensen's 's inequality)
E (MS(((())) < /E (MS) a(())
(214)
where (a) follows as (a - b)2 - (c 6)2 < (a -c Thus, combining 209,211, 211, and 214:
2C
E (MSE U3 <
M 2a(n).
(215)
36

---

Published as a conference paper at ICLR 2024
Therefore, using 215, bias and variance of MSE can be expressed using the bias and variance of the idealized estimate U as the following,
Var(MSE: Var(MS + U U)
(216)
I 2Var(U) 2 U)
Var(A + B) s 2(Var(A) + Var (B))
S 2Var(U)+ + +M U99
(217)
4C 4a(n)).
< 2Var(U) M
(218)
Bias (
I 10 - B[MSE(((PL)]] &
(219)
LIMSET RS + E'U B[MSE(((D+)]]
(220)
[U E[MSE(((D&)]] + B[MSS U)
(221)
S (U) + V |2C
M + 2a(n).
(222)
Thus it suffices to analyze the bias and variance of the idealized estimate U. (Part ID) Analysis of variance of U: Note that the idealized estimate U returns 0 if N' < k and otherwise returns U-statistic (or an incomplete version of it):
N h:
UN' Σ ((
C
(223)
So if we let U be our estimate of the MSE on samples, we have:
U U 1NN's 2 kj.
(224)
Variance of complete U-statistic First we note that:
Var(U) = Var(EEU NT) + E[Var(U [N')
(225)
The latter term, i.c. Var(U | N') the variance of U-statistic of order l with N' samples drawn iid from distribution æ. Thus based on Theorem 6, we have that for N' 2 k:
k2
Var(U 1 IN) <
N
m +
(Nrg2 Th
(226)
k2
N mlk +
(Nr)²² Th
C: S {m)
S 2 k Var (A((11)))
(k/N" < 1)
N7
k (M)) = N akk)2.
< N7
(227)
Moreover, for N' < k. we have by the definition of that Var(U N') = O. Thus we get that:
L(N'2K)
Var(U [N]] = (
s 2kka())
(228)
N'
max LN KJ
Note that N' is a binomially distributed random variable, Bin(n, 1/Pmax). Thus by a Chernoff bound, and reminding that ni' =E[N' n/Pmaxx we have that:
Pr(N' s (1 0-nn')) & 65/1/
(229)
Therefore to upperbound E max(NV [3
we split it into the following two cases
1
when N' > (1 5)n'
(230)
max(N' k}
otherwise
37

---

Published as a conference paper at ICLR 2024
where the first case holds because irrespective of the value of N', the value of 1/ max k) I 6)n'. Thus we get that:
1/N". Further, when N' > (1- 6)n', then 1/N' - 11/(1
Pr(N' (1 - 8)n')
Pr(N' s (1 6)n'))
E[Var(U NN)] - (k)(
(231)
(1- 6)))
k
2k((k)²
1
s'n'12
(232)
5)nl k
2x(2)
k
e -88P112
(233)
5)ml
2a(k)²
kpmax
+ -6"n =6"2n/(20mma)
(234)
8)m
Choosing
V 2praa log(n) we get:
E [U N2) S 2xx())) ( kipmax
(1-8)n + 1 1 S 4a(k))
kpmmax
(235)
(1-8)m
For n large enough such that n/ log((n) 2 8pmaxx we get d= s 1/2 and:
E[Var(U |N') S (k)())2 kpmax
(236)
n
We now consider the first part in the variance decomposition in Equation (225). Note that for N' > k
BIU | N' = B[N(Z = E, (ME((((D:))
(237)
While for N' < ks we have E(U N = O. Thus we have:
Var(BR[U N')) VAY(EE, k))
(238)
E,, [MSEE(0 2 k))
(239)
S E,, (MSE((()))))))
2 k))
(240)
S 2( (ar(1 2}}
(241)
= a(k) Pr(N' 2 k) (1 Pr(N' 2 k))
(242)
S a(k)² Pr(N' < k).
(243)
If we let ō, be such that k =(1 11-81mme 8)m, then we have by a Chernoff bound
Pr(N' < <k)se S
821112 -8 E (/((mo))) =e e (1-k/n)² 2t/kk///////2// (2pmmx)
Assuming that 1 S n/2, we have:
Pr(N' < e en/
(244)
Since, we assume that n/ Iog(n) 8pmaxx have:
1
Pr(N < <k) n
(245)
Thus overall we have derived that:
Var(U) < (k) kPmax
(246)
n1
Variance of incomplete U-statistic With an identical analysis, if we instead use incomplete U- statistic with B random sub-samples (Lemma 2), then we can apply the exact same analysis, albeit, when N' 2 k:
k
Var(U |N) < 2
ak)2
+
Var, (h(S)))))
(247)
N
B
< 2 k
al (k)²
+ 13 (k))
(248)
N
38

---

Published as a conference paper at ICLR 2024
Following then identical analysis, can derive: (Skrmax kPmmxx
Var(U) S a(k))²
B)
(249)
(Part IIII Analysis of bias of U:: Finally, we also quantify the bias of the rejection sampling
estimate. Note that when No 2 k. we have:
E N = E[((S1+)) = E, (MSE(((D)))
(250)
and the estimate is un-biased. However, when N' < k. then we output O, hence we incur a bias of:
EEU N E (M))(((D)))] = E, (MSE(((D))) & a(k).
(251)
Thus overall we have a bias of:
[BU] - E, (OSE()
& EU (MSE(((()) Pr(N' <
(252)
S a(k)e=-/(Spunn (8ppma))
(253)
The bias of the incomplete U-statistic variant is identical, since both variants are un-biased when N' k.
Combining the aforementioned bounds the idealized estimate U with our error bounds between and MSE we get the result.
F.4 POLICY ORDERING CONSISTENCY GUARANTEES Let:
(k) Ex (Dx)))
Or (k: V E. (MSE(((D)))))
(254)
Suppose that we assume that the mean-squared-emoe irrespective of sampling distribution, satisfies that:
(n) + VR
(n) (l),
(255)
for some random variable Vn and some rate rn (e.g. Fa = Vn). Then we can consider the normal- ized estimate:
FA MSE
(256)
Suppose we choose M Ra] and B E and we choose such that r//r,, and k/n + 0. Then, from Theorem 8, we have that the normalized estimate of the mean-squared-error from 256 has:
n Var(r&MSE, o (ra0(1)+* + +rRa(m) +r8a(m)= -0 + +r///ra +0
(257)
BIAS MSE; K5
< O (rza(k)e-n18pmmm +rkaa()) 0 (e-///8pmm + rx/ rrl/Vra) vra)
+ 0
(258)
Thus we can conclude that the normalized mean squared error of the estimate will satisfy:
(MSE, -x)))) +
(259)
Thus get that:
Th MSE, = (k)) + (MSF, Lx(k)) =V= +z)
(260)
35
From this conclude that optimizing MSE over policies approximately optimizes V,, up to an asymptotically neglibible error. Thus for a large enough sample n, we should expect that we are choosing approximately optimal policy æ.
39

---

Published as a conference paper at ICLR 2024
Corollary 1 (Approximate Policy Ordering), For any dataset Dn, of iid samples of size drawn from policy n, define:
(k) - E, (MSE(((D)))
(x = V Ex (S)((((x)))
(261)
Suppose that for some appropriately defined growth rate Tw, we have that:
(n) V En
Tn O(1)
(262)
for some rate In that is policy independent and for some approximation error En + 0. Let
MSER (④) denote the rejection sampling estimate of the mean squared error of a. Suppose that choose such that r -> 0 and k/n 0 and k and M, B are large enough. Then for any fixed policy n.
MSE, - -z) B[(rA (T) = r (R) V=
(263)
< 26 + 2r MSE Cx (k))
(264)
(a) 0 c + n
+ en/ (80max)) (n) - 0,
(265)
Tn
where (a) follows from using the bias and variance terms from Theorem 8 to expand the mean- squared-error E[(MSE, - -x,
Let Ti 32 be two candidate policies. if we choose π2 over #n based on V. (i.e., Vn, < Vaa), ), By our assumptions the convergence of (nff((1) (n), we have:
Tn (n,, (n) - LTT (n)) 1 Vi VA + 26n
(266)
x V., Vnn +
Cn + max =E(T)TTZ)
VV - Vzl
(267)
< 6m +
max =E(T)TT2)
V - Vil
(268)
By Markov's inequality and union bound we have w.p. 1:
V= - V=l BIIV= - -val < V - Vu121 S vV(nkk)
2
(269)
for x E {(11 T2). Thus overall we get w.p. 1 8:
1 Tn (n(C - (1)) 50 en + Vi(mn))
(270)
Thus the policy that best according to the estimated criterion V. is also approximately best ac- cording the normalized expected mhean-qquarederron with samples, i.e. (n).
F.5 PROOF OF THEBRRMM
For the first part of the Lemma, i.e. proving Equation (153), we first observe that:
Var(U))
12
Σ
Σ
Cov (h(Z), ....... M ...,,)))) (271)
1:
15
Moreover, note that (i,,..., in (ir,.. ... then
Cov with 7/u 0. Furthermore, the number of subsets (fI...., ix) and (ir,.... j& that have intersection equal to is (2) (5) (n-k) Thus we derive Equation (153):
h, 7:,.)) Te
n - k.
Var(U)
t: c ne-
(272)
40

---

Published as a conference paper at ICLR 2024
The proof of the second part follows from along the lines of Hoeffding's canonical decomposition and bares resemblance to the asymptotic normality proofs in Fan et al. (2018); Wager & Athey (2018b). Consider the following projection functions:
hz(21) = [2 Zz..... Zz]],
(11(1) = h1(21) - E [M]]
(273)
(2(21, 22) = (2 22, Zz...., Zb)],
h2(21, 22) = he(21, 22) - E [h]
(274)
(275)
11x(11 , =x) = [B[h(21, F2, ;. =x]], ha(21, ,.,...,...))
=x) = (11 22. .2..... 2k) 13 [M]
(276)
where E [h] E ['(,,,,.... Zx)]. Then we define the canonical terms of Hoeffding's U-statistic
decomposition as:
91 (21) = hi(21),
(277)
(2( he(21, 22) - -92(22)
(278)
g3(21, 22, 22) ha(z1, 22, 23) Σ g1()))
Σ
g2(2),2))
(279)
1sKjss3
(280)
gh (2,,,,2, .......2... 2k)
ha ;
Σ
((())
Σ
g2(2);
(281)
ISiejsk
Σ
0k-1(2z)
Rig
(282)
156 Sin-...ii_11$
The key property is that all the canonical terms in the latter expression are uncorrelated and mean zero.
Subsequently the kernel of the U-statistic can be re-written as a function of the canonical terms:
M( 2x) = M(21, 2k) [M] Σ ((()))) +
Σ
g2(2), 23) +... + gh (2., 2k)-
Isicisk
By the uncorrelatedness of the canonical terms have:
Var [M(Z1, ......... Z+)] (1) [oi]]
(0)
Lo
(283)
10
We can now re- re-write the U statistic also as function of canonical terms:
U --E
E--
n2
Σ
i(ii,..., Zine)
(284)
k
15 <12 Siann
n
-1
Σ
n
91 (Zx) +
(n-2)
Σ 92 2,) +...
(285)
k
h - 2
ISieisn
k
Σ
9u (Z Zin)
(286)
15h <i......iii5
Now we define the Hájek projection to be the leading term in the latter decomposition:
U1
gi().).
The variance of the Hajek projection is:
222
2.2
of = Var [U1]
Var (hg (21)
m
m
41

---

Published as a conference paper at ICLR 2024
Moreover, since the canonical terms are un-correlated and mean zero, we also have:
Var(U) = Var(Ui) + Var(U- E - U1 = Var(U,) + E [U Elu - !1
(287)
From an inequality due to Wager & Athey (201 8a):
E -U- [0 -- U1)
n- 2)
2
n1
Elog|
n - ./) +
n2
B Blgkl
k: 2 2
2
h k)
(288)
-2 *(n (n >)
2 (m)
1: k (x-r)
(r) Elaa.
(289)
h:l(n r)! (k)
Elgh
(290)
n!(kk r)! (r)
kik - 1)
Σ
Elga'
(291)
nin 1)
22
Var [h(Z1,.... Zx)1
(292)
n²
ha
n² n
(293)
From the above we get that:
k m = Var(Ui) S Var(U) S Var(Ui)
+ 122
1.2
1.2
n² Tk
-/1
n²
(294)
Moreover, from Equation (283), we have that:
(4) FlO (2)))
hh'
(1) Var(hi (21)) km
7m Var. xx)) 2
(295)
which completes the proof of the Lemma.
G MULTI-REJECTION SAMPLING
G.1 REVIEW: STANDARD REJECTION SAMPLING
Recall that to simulate draws from a distribution using samples from another sequence of distribution {/ the standard rejection sampling procedure accepts a sample S if & < ((..)/(((S..CC) where C' = max.,; p(s) (s)) and & ~ U. While it is well-known in the literature, for completeness, we show that the samples drawn using the above rejection sampling procedure will simulate draws from p(x),
Pr(X = x)
1
Σ Pr(Accept x; (x)
(296)
p(x)
Pr
U <
9: (z(z)
(297)
K
Cqi(x))
p(x)
(x(
(298)
(x)
p(x)
(299)
p(z)
(300)
p(x).
(301)
An instantiation of standard rejection sampling for setup is provided in 13.
42

---

Published as a conference paper at ICLR 2024
G.2 PROPOSED: MULTI- REJECIIO SAMPLING
Here, we consider discussing the proposed multiple-importance sampling procedure more generally. Consider the case when we have samples from multiple proposal distributions {q } we can either treat each of them independently to sample from as discussed above. Alternatively, as we show below, we can treat them as a mixture jointly, such that even if a sample X ~ qis we p(X)
form the acceptance ratio as o 3, (x)) where C = max, p Σ (z(x)) The following
provides proof that the proposed procedure draws samples that simulates sampling from the desired distribution p(z):
1
Pr(X- = =)
Pr(Accept x; (x)
(302)
k
p(x)
Pr
U
di(x)
(303)
k 1=1
C 2 (x)
p(x)
C شラ= (x) ((())
(304)
p(x)
k
k ((x)
(305)
Σラ (x)
p(x)
(306)
x p(z).
(307)
An instantiation of multi-rejection sampling for our setup is provided 15.
Remark 10. Validity of rejection sampling requires the support assumption. that is for X' == {x
p(x)= > 0} it hods that (x) > 0, Vi E {I....,k] k), Vx E X. Multiple-rejection sampling replaces the support condition from all qi 's to at least one qi That is, we only require that 1 & (())
k), 0, Vx E X. Alternatively, we only require that Ve E X, (3i E (l....,k), s.I. g;(x) > 0}.
For instance, if q (the first exploration policy) is uniform, then subsequent qi 's can even be deter- ministic and the data from can still be used for multiple rejection sampling. This would not have been possible if we had used single-rejection sampling.
Remark 11. Multiple-rejectin sampling can often also reduce the value of the normalizing constant significantly now
p(x)
Fmax
(308)
レー (x)
which can reduce the failure rate of rejection sampling significantly.
can be shown that the expected number of samples accepted using multiple-rejection sampling will always be more than equal the number of samples accepted under individual rejection sampling, irrespective of how different are the proposal distributions } to the target p. To see
this, recall that for individual rejection sampling, the expected number of samples accepted from N samples drawn from a proposal is N/ Pmaax as
((X) Pmax qx))
Pr(Accepp X) = Pr U
(309)
p(x)
.) X = x ((x) dr
Pr U <
(310)
Pmax g(z)
p(x)
((x) dx
(311)
Pmax g (x)
(312)
Piax
43

---

Published as a conference paper at ICLR 2024
Let there be proposal distributions, with N samples drawn from each distributions. Therefore, the expected number of samples accepted would be
Σ
N
N
ming
q:
(313)
Pinxx
P
p(a) (=(m)
p(x))
i=1
==1
maxę
1=1
Contrast this with the expected number of samples accepted under multiple-rejection sampling. where all the Nk samples treated equally,
Nk
Nk
Nimin 1 Ei ((()) Σ p(x)
qi(xr)
Miin
(314)
Pinxx
max;
Di (1)))
p(z)
p(x)
Now,
[i(x))
(((x))
vxr
ming
(315)
i=1 p(x:)
p(x:))
qi (((x))
(((1))
min
min
(316)
p(x)
p(x))
N
N
N
Vi {1,..., k}.
(317)
Pmax
Pinax
Prmax
Example 1. consider the case where N samples are drawn from each of the two proposal distribu- tions 41 and over {0, 1}. such that 91 (r 1) 92(x 0) = 0.75 and (z = 0) (2
1) = 0.25. Let target distribution be p(x = 0) = p(æ 1) 0.5. In this case, can observed that individual rejection sampling will reject 50% of the samples! In contrast, multiple-rejection sampling will accept all the samples as average proposal distribution (qi + 222 p.
Example 2. Consider the other extreme case where one of the proposal distribution is exactly the same the target distribution and the other is completely opposite. We will see that multiple- rejection sampling stays robust against such settings as well.
Let N samples be drawn from each of the two proposal distributions @i and g2 over (0, 1), such that qı (2 = 1) (2(x = 0) 0 and gi (2 = 0) (2(x = 1) (here we use 'ze" instead of -=' to ensure that individual rejection sampling satisfies support assumption (note: multiple rejection sampling will be valid in the case equality as well)). Let the target distribution be Q1-
In this case, both individual rejection sampling and multiple-rejection sampling accept 50% of all the samples drawn (i.e., 100% of the samples drawn from 91). This be worked out by observing that (a) Since p(x 1) = O, no samples will be selected from the samples drawn from q2. (b) The average proposal distribution is q = [0.5, 0.5], therefore max, p(x)/q(>> 2. Since qi (5r 0)
only O's are sampled from 41- Probability of accepting zero under multiple rejection sampling is
(p(x 0)/q(= ())/(maxx) (1/0.5)/2
H ALGORITHM
H.1 PSEUDO-CODE
Algorithm 1: DIA: Designing Instruments Adaptively
Input Number of allocations K, Size of each allocation n, Subsampling factor a
= uniform
D Get (T,
Sample n new data using
for i [l.... K do
π =
Kn)
D GetData
Return 0 = Est imstteeD(D)
44

---

Published as a conference paper at ICLR 2024
Algorithm 2: Optimize
Input Dataset D, Sub-sampling factor o, Max-budget
Initialize Th Initialize θ
b Set of parameters
0o = -Fstimate(D)
D. Compute estimate on the entire data
while ui not converged do
(Z)) * Pr(ZZI; + (T,
Equation 16
#Parallel For loops for b E [1,... B] do
9
D₁ = Multi Rejei-Reject--- -ee---eeeet--eeleeeeeee--------e Sampler n a)
b> Equation 15, with k = |D]
@ Est imatee(( Init [bb]
Optional: Init from previous solution
MSE = (+16) 0o)²
11
I Ge:GGeIIIffeme (MSE, (66),
Equation 12
V [ = E SED l (s)[(s)
Equation 17
14
( V
Any optimizer: SGD, Adam, etc.
Return Tip
We provide pseudo code for the proposed DIA algorithm in and 2. In the following we provide short description of the functions used there-in.
GetData: Uses the given policy sample
data samples
Estimated Uses 3 to solve for the required nuisances and the parameters of interest.
Multi-Rejecct-SSe -Sappe-- Takes as input dataset D of size n and returns a sub-sampled dataset of size & n² using the proposed multi-rejection sampling 15. Since the data is col- lected by the algorithm itself, DIA has access to and also all the prior policies (that are require for the denominator of p) and can directly estimate p. practice, the max mutli-importance ratio Pmax may not be known. Therefore, use the empirical supremum (Caffo et al., 2002), where empirical max of multi-importance ratios are used in the place pmax.
Get In In fuencee:: Uses 12 to return influence of each of the samples s D2 on the MSE. Here we discuss how to compute it efficiently using Hessian vector products (Pearlmutter, 1994). Recall, from 11 and 12,
d ( (S.) MSE( (S.) MSE
(318)
d0
aM,
aM,
TQQ -1 ds (0) T
(S,) 00 (0, )) m( 0,
(0,
(319)
do
Note that d can be computed directly as is just the gradient of the MSE. Below, we focus on de I (S.). To begin, Let 0 Rd and ø e dd Let H aQ Rdgxd and q(S, Φ) RRd,, such that we want to compute H-'e. Notice that this is solution to the equation Hp = c, therefore we can solve for arg minper* ||H r/|2 using any method (we make use of conjugate gradients). Importantly, note that we no longer need to explicitly compute the inverse. Further, to avoid even explicitly computing or storing H, we use the 'stop-gradient' operator sg in auto-diff libraries and express
i Hp 06 p dó (Q
aQn.
E 12d2
(320)
which reduces merely taking derivative of the scalar (g()) R. Thus using hessian- vector product and conjugate gradients we can compute u, even for arbitrary neural networks with dy parameters. Similarly, Hessian-vece vector products. Other tricks can be used to scale up this computation to millions (Lor- raine al., 2020) and billions of parameess (Grosse al., 2023).
compute all the terms in I I by repeated use of
45

---

When using influence functions for deep-learning based estimators, prior works raise the caution that influence function might provide an accurate estimate of the leave-one-out loss (Basu et al., 2020; Bae et al., 2022). One of the reasons is that the optimization process susceptible to converge to different (local) optimas based on the stochasticity in the training process. Therefore, the difference between an estimate of O(Dx) and (Dnns)) is not only due to the sample S; but also on the other stochastic factors (e.g., what was the parameter initialization when computing ((Dx) vs (DDv))) Published as a conference paper at ICLR 2024
Finally, we also observe that the higher order influence (S.) can be partially estimated using the first order Ig (())( (St) (S:) terms. Recall from 68
d0
Mis MSE (0, (0 (o.t.d..) (g
where, (S.)
(321)
d0
de
rm=
Therefore,
I () (S.)
MSE
d
d
MSF O (.t..bb..) ) I (())
(322)
dc
d8
lc=0
(S))
d²
MSE 0 @frciooe I002 (S.)
(323)
d20
==
+ d MSE 0 @urirr ) de
d (S))
(324)
dG
Ignore
d²
(S))
MSE (S.). (S).
(325)
d2D
Hessian-vector product can now again be used to copmute this approximation of MSE (5,) using the already computed (1()) (S.).
Update: Uses any optimizer to update the parameters of the policy.
H.2 INFLUENCE FUNCTION USAGE WHEN THE ESTIMATES ARE STOCHASTIC
However, computing the influence of sample S; using influence functions does not account for stochasticty in the training process. In the following, we discuss why this might be less of a concern for our use-case.
Let & be a noise variable that governs all the stochastic factors (e.g., parameter initialization). Let 0(Dn,E) <) be deterministic function given dataset D,, and Therefore, similar to (4), [MSE(((D..
L(T))
E
(326)
D
Then similar to (5), (7), and (9)
Olog π (x) dπ
VL(T)) = E
MSE(0(D,, Dn,, E)
(327)
D
Olog π (Z)
(MSE(O(D,,.)) M 8)))
E D
(328)
Ón
log T (Z,
E D
IMISE(S;.))
(329)
where, IMSE (S:, {) is similar to (9) and (10), but 0 is also a function of &. Therefore, from (328) it can be observed that, for our setting, we indeed want compute the difference from the leave-one- out estimate, where there is no difference due to the stochasticity from g.
In practice, as we compute sample estimate using a single sample of D,, and &
i Ölog क (Z, Iπ
TP ((T)
IMSE (S,,
(330)
46

---

Published as a conference paper at ICLR 2024
the resulting procedure is essentially the same if running the DIA algorithm considering ((D,)) to be deterministic. Our experimental setup uses DIA from Algorithm as-is for all the domains considered. For instance, TripAdvisor setting uses deep learning based estimators whose outputs are stochastic (e.g., due to parameter initialization), and the synthtetic IV domain uses closed form solutions where there is stochasticity in the learned estimator, given the data.
Beyond the initialization difference, Bae et al. (2022) also point out three other sources of issue with practical influence function computation. (a) Linearization: or using first order influences (9). For our purpose, formally characterize in Theorem 5 the bias due to such approximation. Further, in (325), we discussed how second-order influence can also be estimated partially and be used to obtain a better estimate of the leave-one-out difference. (b) Non-convergence of the parameters. As experiment design is most useful when sample complexity is much more expensive than compute complexity, this issue can be mitigated with longer training time. (c) Regularization when computing the inverse hessian vector product. For our purpose, we used conjugate gradients with hessian vector products compute the inverse hessian vector product (see discussion around (320)). In our experimental setup we did not use any additional regularization for this computation.
More importantly, contributions of our proposed DIA framework is complementary to the solutions the above mentioned challenges. Therefore, any advancements to resolve these challenges can also potentially be incorporated in DIA.
H.3 PROXY MSE ALTERNATIVES
Recall from 4 that under the knowledge of the oracle l, the MSE can be expressed as,
M
4;; MSE(O(D()) = M Σ 1(
(331)
However, do not have access either O. or (unbiased estimates of) the outcomes of f(X,, A,;0), 0o), we cannot directly estimate (331). One way would be to decompose the MSE is bias and variance, and only consider the variance component,
M Σ 2=1
1 Var(O(DD)) M
(332)
Just optimizing for the variance is analogous to the objective considered by most prior work (Chaloner & Verdinelli, 1995; Rainforth et al., 2023) and can also be casily used in our frame- work. However, instead of discarding the bias term from the MSE's decomposition, we consider the proxy MSE where 0g is substituted with ((D.) (Lines and 11 Algorithm 2),
M
1 Σ ((DD)) -x;
MSE(O(D:)) M
(333)
Intuitively, for a consistent estimator, (DD.)) can be considered a reasonable approximation of 8g for estimation of the MSE of O( (D)),, where k is much smaller than n (for e.g., k o(n)). This approach is similar to MSE estimation using sub-sampling bootstrap (Romano, 1995) and we provide formal justification for this in Theorem 8.
As we noticed above, there multiple different choices of target quantity that can be used, and this work focused on studying the one in (333). However, an important advantage of DIA is that the target is easily eustomizable, and one use any desired target quantity fz,
M
MSE,(((D)))
Σ ( A.) -1044-(XX,,,... A;; 4x(
(334)
M
1=1
ADDITIONAL EMPIRICAL DETAILS
To demonstrate the flexibility of the proposed approach, we use DIA across various settings, with different kinds of estimators,
47

---

Published as a conference paper at ICLR 2024
IV (synthetic): For this domain, use 2SLS based linear regression for both the nuisance and ATE parameters, where the solutions can be obtained in a closed-form. The parameters sp of the mnstrument-sampling policy Te correspond to logits for each instrument. The results for this setting are reported using 100 trials.
CTV (synthetic): For this domain, we use moment conditions from (Hartford al., 2017) and use logistic regression with linear parameters for both the nuisance and CATE parameters, and thus require gradient descent search for the optimal parameters (no closed-form solution). Further, to account for covariates, the parameters of the instrument-sampinng policy "e correspond to the parameters non-linear function modeled using a neural network. The results for this setting are reported using 30 trials.
TripAdvisor (semi-synthetie): For this domain, we use neural network based non-linear parame- terization of both 6 and ø. for the CATE and the nuisance functions, respectively. The parameters oo of the setrruenn--sapllinn policy Thp also correspond to the parameters of a non-linear function modeled using neural network. The results for this setting are reported using 30 trials.
The policy parameters yp in all the settings are searched using gradient expression in 17. Below, discuss details for each of these settings.
1.1 SYNTHETIC DOMAINS
For both the IV and the CIV setting, random 5% (or I, whichever is more) of the instruments had strong positive encouragement for treatment positive encouragement for treatment A = 1. The strength (7) of other instruments was in between. Below, | denotes the number of instruments.
and 5% (or 1, whichever is more) had strong
The following provides the data-generating process for the IV setting:
0o E IR?
7E 10,11
E())
(335)
Z ( z(-)
E {0, 1)
(336)
U (0,
E R
(337)
clip(Z y min max = 1)
E [0, 1]
(338)
A ~ Bernoulli(p)
E {0, 1}
(339)
(b) AN 01) +(1 11-- A),
E R
(340)
A) Y 14,1-A] 0. + +
E R
(341)
where (a) samples from a multinomial and Z is a one-hot vector that indicates the chosen instrument, and (b) induces heteroskedastic noise in the outcomes based on the chosen treatment.
For the IV setting, we make use of 2SLS which makes use of linear functions in both the first
and the second stages of regression. The parameters for those settings can be obtained in closed form. Additionally, the influence function can also be computed in closed-form (Kahn, 2015). The instrument sampling policy a an (unconditional) distribution on A(Z).
The following provides the data- data-generating process for the CIV setting:
0n E R,
XER
E [0, 1|11
Vr <(-1x) E (
(342)
z ( x(1x)
(0, 1]
(343)
U~ N((,ouu)
E R
(344)
C (
X1v+ (1-))(1)
E [0, 1||
(345)
P = clip(Z TC C
min 0, max 1)
[0,1]
(346)
A Bernoulli(p)
E (0,1)
(347)
5 (g) ol( + -1 A),(0,)
R
(348)
Y X, A0
+U +U+
CR
(349)
48

---

Published as a conference paper at ICLR 2024
where (a) samples from multinomial and Z is one-hot vector that indicates the chosen instrument, (b) induces heteroskedastic compliance by flipping the compliance factor of the instruments based on the covariates (by construct, X, {0,1}) 1)), (c) induces heteroskedastic noise in the outcomes based on the chosen treatment, and (d) induces heteroskedastic outcomes based on the covariates (by construct, X2 E IR).
For the CIV setting, d X, A. Similarly, we & is linearly parametrized to estimate the nuisance function dP(A|X, Z; 6) using logistic regression. Parameters for both and dP are obtained using gradient descent and the moment conditions in 3. The instrument sampling policy (-(r(z) is modeled using two-layered neural network with 8 hidden units.
and we parameterize such that g(X, g A) as linear function of
1.2 TRIPADVISOR DOMAIN (SEMI-SY SYNTHETIC)
Adaptivity and learning the distribution of instruments are most relevant when there are lot of in- struments. Our paper is developed for the setting where online sampling is feasible. Unfortunately, simulators for real-world scenarios that we are aware of and could access publicly (e.g., TripAdvi- sor's (Syrgkanis et al., 2019)) only consider a single/binary instrument. These simulator domains modeled represent the setting where expert knowledge was used find optimal instruments (e.g.. better/easier sign-up strategy to make the membership process easier). However, in reality, there could be multiple ways encourage membership (emails, notifications, sign-up bonuses, etc.) that can all serve as instruments. Adaptivity is more relevant in such a setting to discover an opti- mal strategy for instrument selection, while minimizing the need for expert knowledge. Therefore, given the above considerations, we created a semi-synthetic TripAdvisor with varying numbers of potential instruments simulate such settings.
The original data-generating process for Adviso domain is available on Github. The co-variates X E Rd correspond to how many times the user visited web pages of different categories (hotels, restaurants, etc.), how many times they visited the webpage through different modes (direct-scarch, ad-click, etc.), and other demographic features (geo-location, laptop operating system, etc.). The original setting only had a binary instrument. To make resemble realistic settings that are more broadly applicable (e.g., where there to a different way to encourage user to uptake the treatment), we incorporated several weak in- struments. The compliance strength of the instrument varies non-linearly with the covariates. Our semi- semi-synthetic version is available in the supplementary material.
multitude of different instruments, each corresponding
For the TripAdvisor setting, we parameterize 0 such that (X, A; 0) as a non-linear function of X, Similarly, we é is non-linearly parametrized estimate the nuisance function (P Ø; In both cases, the non-linear function is a two-layered neural network with 8 hidden nodes and sigmoid activation units. Parameters for both g and dP are obtained using gradient descent and the moment conditions in 3. The instrument sampling policy Tpp-<<0 (c) is modeled using a two-layered neural network with 8 hidden units.
1.3 HYPER-PARAMETERS.
The choice of sub-sampling size l is used as hyper- pageer-rramtter in our work. We parametrize k as na For our empirical results, we searched over the hyper-parameter settings of a e [0.5, 0.8] and report the best pest-performing setting.
Auto-tuning suggestion for a: As the expected number of samples that get accepted via rejection sampling from a set of n samples is n/ Pmaxx it would be ideal for a to be such that n. > n/ Pmax- Empirical supremum can be used as proxy for Prax-
Further, doing rejection sampling in higher dimensions can be challenging as Pmax can be very large. standard technique for density ratio estimation (i.e., p that governs acceptance-rejectio, ratio in 13) in higher dimensions is through performing density ratio estimation on a lower dimensional sub- space (Sugiyama et al., 2009, 201 I). We believe that incorporating similar ideas into our framework can provide further improvements.
1.4 DETAILS OF OTHER PLOTS:
Figure 1: that there no confounding between what group (treatment/control) the user recommended to
This figure provides a comparison with conventional experiment design (that assumes
49

---

Published as a conference paper at ICLR 2024
10
Variance
103
RS
10a
15
10a
3
Samples x10
Figure 8: Log-scale version of Figure 4 to better visualize the difference in variances at smaller values of n.
be part of (i.e., Z), and the group that the user actually became part of (i.e., A)), and the proposed method DIA on the following data-generating process:
0n E I (~M(-))
T(-) E A(Z)
(350)
E {0, 1}
(351)
~ N((,
E
(352)
p clip(Z + U. min 0, max 1)
[0, 1]
(353)
A ~ Bernoulli(p)
E {0, 1]
(354)
& AN 01) + (1-A)[(0,00)
R
(355)
Y [A,1- A U +
R
(356)
The confounder strength corresponds ou- Observe that when d. 0, then the binary treatment's value is the same as that of the binary instrument's value, i.c., = Z.
For the illustrative plots regarding bias and variance trade-off's of different gradient estimators and sampling strategies, we make use of the following data aata--enerating process where the treatment E E is real-valued, the outcomes Y are quadratic in and |2| 2,
Figure 3:
0o E R
E 10,0,11121
E A(2)
(357)
Z ~ T(-) U~ ~ o(),
{0, 1
(358)
E R
(359)
A~ 1o-Z'+U++NNN.0
E R
(360)
Y + +N(,0,
E R
(361)
This figure illustrates the bias and variance of different gradient estimators when the function ap- proximator mis-specified, i.e., Y is modeled as a linear function treatment but is actually quadratic function of treatment. We use the standard 2SLS estimator for this setting.
This domain also uses a 2SLS estimator and binary instrument with the data generating process in (357)-3361). (Left) Illustration of how the policy orderings preserved when using different values of a in = a nn collection policy is (1) 0.5. (Right) Variance of evaluating MSE under different sampling strategies. The data collection policy ((1) = 0.5 and the target policy œ (1) = 0.6. Sub-sample size
Figure 4:
0.2, (1) 0.5, and T2(1) = 0.8, where the data
k o(n) 0.75 To better visualize the difference in the variance for small sample sizes, we have also included a log-scale version of the plot in Figure
50


Reviews:
[{"review_id": "lM9sc107rb", "reviewer": "Reviewer_ST2k", "summary": "This paper discusses how to design an adaptive data collection process over the instruments that can improve the sample-efficiency of the estimation of the counterfactual prediction. The previous works mitigate the bias in estimation of the predictor $f$, but they are often subject to high variance problem. This paper mitigates the high variance problem of the gradient estimator by using influence functions and multi-rejection importance sampling and provides theoretical analysis of the bias and variance of the proposed gradient estimator. Specifically, although there exists a slight estimation error, this paper proposes $∇^{IF}L(π)$ estimator based on influence functions to solve the time-consuming problem caused by re-training and the high variance problem. Meanwhile, this paper proposes a multi-rejection important sampling approach, which has lower variance compared to the traditional importance sampling approach. In addition, this paper proposes an algorithm that is able to design instruments adaptively. Moreover, experiments are conducted on three regimes to demonstrate the effectiveness of the proposed method.", "questions": "Please refer to the weaknesses part.\n\n***\n\nAfter rebuttal: Thank you very much to the authors for their answers to our reviews and for improving the paper during the rebuttal period. The modifications bring valuable content. I read also carefully the other reviews and the corresponding answers. My (positive) recommendation remains unchanged.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1: The motivation is clear. How to design indirect experiments when direct assign interventions is impractical is a important problem.\n\nS2: The techniques adopted in this paper are sound, and are supported by solid theoretical analysis. \n\nS3: The proposed algorithm is novel and demonstrates good performance.\n\nS4: The experimental results on the three datasets are convincing.", "weaknesses": "W1: The paper uses uniform data collection method as the baseline, however, I think evaluating some more RL algorithms and comparing their performance will make the paper more convincing.\n\nW2:  In practice, the max mutli-importance ratio may not be known, so this paper use the empirical supremum instead. May $\\bar{ρ}(S_{i})$ also be unknown?\n\nW3: Is there some clear pattern for DIA-X with different X in Figure 1, 5 and 6? For example, the U-trend is not obvious in Figure 1.\n\nW4: Is Figure 3 showing the result with K=1 in $∇^{IF}L(π)$? Providing more results with varying K may helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TC4VC6CbFx", "reviewer": "Reviewer_SUta", "summary": "Authors present a current and well motivated problem, execute the ideas well, communicate results clearly and as such make a relevant contribution the literature.\n\nThe problem statement is delivered at different levels of intuition and formality which helps exposition (i.e. “consider how to automatically learn data-efficient adaptive instrument-selection decision policies, in order to quickly estimate conditional average treatment effects” and “aim to develop an adaptive data collection policy π(·|x) ∈ ∆(Z) over the instruments Z for all x ∈ X that can improve sample-efficiency of the estimate of the counterfactual prediction f. Importantly, we aim to develop an algorithmic framework that can work with general (non)-linear two-stage estimators.”)\n\nTheir “general framework for adaptive indirect experiments” is well placed with a reasonable long-term perspective and careful analysis of limitations. They also maturely accommodate natural limitations by presenting a framework that is “designed to minimize the need for expert knowledge and can readily scale with computational capabilities”.\n\nI am unable to comment on the correctness of the theorems, though it seems the authors heavily rely on previously shown results and plug and play those, which, given the empirical results, suggests they are successful.\n\nEmpirical examples substantiated the theoretical claims well, though the final discussion has significant potential for development. It is possibly a bit underdeveloped with a weak conclusion of the impact of reallocation. \n\nThe conclusion of a ‘Unshaped’ trade off between number of instruments and number of reallocations might oversimplify deeper issues, though for the given work is perfectly adequate.\n\nOverall, the paper makes a relevant contribution to the literature, tackling an important problem with skilful navigation of theoretical tools (influence functions and multi-rejection importance sampling) resulting in convincing results and arguments for using DIA.", "questions": "- [ ] Do you have more empirical or theoretical evidence to enrich the discussion on the ‘U-shaped’ trade off between number of instruments and number of reallocations? It seem like you might be running out of space, but if camera-ready allows another page, please enrich.\n- [ ] Figure 2: I am not sure what the dotted red lines indicate. I assume they are related to special conditions and assumptions on the SCM, but these are not connected to the text as far as I can see. Did I miss it?\n- [ ] Typo: Page 5 bottom: “multi-rejection important sampling” should be importance I assume.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- [ ] The background is curated at the right level of depth and supports exposition very well. They navigate the page limit well with a carefully formulated and rich appendix.\n- [ ] The conceptual development throughout the paper is very consistent and easy to follow.\n- [ ] Identifiability conditions are present effectively for the given task.\n- [ ] Figure 3 is incredibly effective to demonstrate the improvements, the last sentence could be boldened/underlined/emphasised more. (“Observe the scale on the y-axes.”)\n- [ ] The exposition of a linear example in the example is very much appreciated.", "weaknesses": "- [ ] I was able to understand “Indirect experiments” on an intuitive level from the problem statement and the given examples, but a less informed reader might struggle and benefit from a more thorough/formal definition, though I am aware authors can’t cater to all levels and the current introduction of the term is just fine for the usual causa ICLR reader.\n- [ ] The conclusion is possibly a bit underdeveloped with a weak conclusion of the impact of reallocation, e.g. Figure 5.\n- [ ] The conclusion of a ‘Unshaped’ trade off between number of instruments and number of reallocations might oversimplify deeper issues, though for the given work is perfectly adequate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kJChAuS4mz", "reviewer": "Reviewer_7XxM", "summary": "The paper investigates enhancing sample efficiency for indirect experiments by adaptively designing a data collection policy over instrumental variables. The authors propose a practical computational procedure that utilizes influence functions to search for an optimal data collection policy, together with the idea of rejection sampling. By many experiments in various domains, the authors showcase the significant improvement of the sample efficiency in indirect experiments.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThe problem considered in this paper, from my perspective, is important and interesting from both a theoretical and practical perspective.\n2.\tThe ideas of generalizing the influence functions and adopting rejection sampling are quite inspiring. Although the core concepts are standard, the generalization is still novel, in my opinion.\n3.\tThe paper is well written and relatively easy to follow, considering it is a quite theoretical one.", "weaknesses": "1.\tAdaptivity can bring us a lot of benefits like the improvement of sample efficiency. However, the technical challenge is that adaptivity usually harms the independence among the data. The adaptively collected data is usually challenging to analysis, even for the basic M-estimator (see, e.g., [A]). The authors do not seem to cover any points along this line. It will be beneficial to present whether the adaptivity in this paper affects the independence structure and how the authors handle such difficulties.\n2.\tFor the multi-rejection sampling, if $\\pi’$ and $\\pi_i$ are very different, the algorithm might reject many samples before getting a useful one, which can be very inefficient and impractical. Things become even worse when the dimensions of the problem get larger, for example, as the authors mentioned, when the natural language serves as instruments Additionally, it would be good to know how to choose the value of \"k\" in practice.\n3.\tIn the introduction, when summarizing the contributions, I didn't notice a clear mention of the technical challenges and novel aspects of the work. I found several such points in the main text. It would be beneficial, in my opinion, to include them in the introduction, especially since many of the ideas are quite traditional.\n4.\tOne minor point is that the writing can be further improved.\tWhen referring to an equation, it is better to put the equation number in parentheses. The phrase to define $D_{n\\i}$ ($D_n$ except the one in the $log \\pi (Z_i | X_i)$ term) is a little confusing.\n\n\nReference:\n[A] Zhang, K., Janson, L., & Murphy, S. (2021). Statistical inference with m-estimators on adaptively collected data. Advances in neural information processing systems, 34, 7460-7471.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y24Z8IMSnB", "reviewer": "Reviewer_QTvC", "summary": "The paper introduces the computational procedure DIA to increase the sample efficiency for indirect experiments for CATE estimation.  Specifically, the procedure leverages influence functions for iteratively optimizing the data collection policy through adaptive instrument selection.  Optimality is defined through a minimal mean-squared error of the estimator.  The paper emphasizes the applicability of the theoretical procedure through experiments conducted on two synthetic datasets and an extended version of the semi-synthetic TripAdvisor dataset.", "questions": "The paper would benefit from additional details on the following questions:\n\n1) Why is the MSE a good metric of choice? What is the benefit above other objectives (e.g., minimizing regret)?\n2) What would be the general form of the k-th order influence function?\n3) What is meant by the perturbation of the distribution function induced by Dn? In which sense are the samples perturbed?\n4) Why can the estimator theta(Dn) be considered symmetric? A short mathematical statement would benefit the flow of reading.\n5) What is the formulation of the importance ratio on the entire data? (page 6 might be difficult to follow for non-expert readers).\n6) Similarly, a short introduction/theory of the acceptance-rejection method would be beneficial. I am not convinced that the average reader is familiar with the concept.\n7) The authors mention the flexibility of their approach multiple times. Nevertheless, it is unclear what precisely is meant by flexibility/ which properties make the approach flexible.\n9) How does the performance of DIA-X for different X relate to the data generating mechanism? Can the optimal X be deducted from the data for the presented experiments?\n10) Figure 3: The funnel (standard dev.?) is only plotted for the IV-bias. Why is it not visible for the other cases or the variance plot?\n11) TripAdvisor data: Why was it necessary to synthetically enhance the data? Could you also provide a comparison of the results of the method on the original real-world dataset and the enhanced semi-synthetic dataset? It would also be interesting for the reader if the authors could state the optimal instruments for the real-world dataset.\n\nThe paper has multiple imprecise parts:\n\n1) Background: The theoretical background/ problem setting of the paper is taken from reference 23. In contrast to the original work, the paper lacks motivation for and explanation of the specific problem setting.\n2) Control Variates: The choice of the control variate (section 3.1) should be justified mathematically (possibly in the appendix).\n3) Figure 4: According to the text, one should observe an exponentially increasing variance for IS in the number of samples. However, the figure does not support this statement.\n4) Experiments: The synthetic data generation is not properly described. Furthermore, no details on the networks employed for estimation are stated.\n5) It would be nice to formalize \\pi in Sec 2 upon first experience. \n6) References: Multiple references are incomplete.\n\nThings to improve the paper that did not impact the score:\n\n1) Structure: The structure of the paper can be optimized to facilitate reading. A constant reminder of what will follow later (e.g., Section 4) might confuse the reader more than it aids the flow of the paper. Furthermore, key contributions (e.g. Theorem 2) are referred to the appendix. It would aid the understanding of the theory to have the main results presented as such in the main part of the paper.\n2) Consistency in wording, e.g., importance weighting vs. importance sampling\n3) Multiple times it is unclear if a certain aspect is only assumed or proven. Clarification emphasizes the contribution of the paper.\n\nMinor comments:\n\n1) There are some minor typos and grammar errors in the text.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) To the best of my knowledge, the presented problem statement is novel and of high interest for CATE estimation in scenarios in which direct interventions are impractical, costly or unethical.\n2) The authors provide theory for the proposed method DIA.", "weaknesses": "1) The paper suffers from impreciseness and multiple open questions (see below).\n2) The results are not reproducible: The experimental setting (e.g., the employed datasets) are not described, neither is code provided. Besides the reproducibility aspects, this also hinders understanding and interpretation of the presented figures and results.\n3) The paper does not employ the required format of citations in the text, i.e. reference number instead of author name + year. \n4) The motivation could be much improved by elaborating more exactly where the method is relevant and providing a real-world case study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)