Asymptotically Best Causal Effect Identification with Multi-Armed Bandits
Authors: Alan Malek
Silvia Chiappa
Venue: NeurIPS 2021 Poster (2021)
Keywords: causal identification formulas
frontdoor criterion
adjustment criterion
causal inference
multi armed bandits
best-arm-identification
confidence sequences
double machine learning
causal effect estimator
nuisance parameter

Abstract: This paper considers the problem of selecting a formula for identifying a causal quantity of interest among a set of available formulas. We assume an online setting in which the investigator may alter the data collection mechanism in a data-dependent way with the aim of identifying the formula with lowest asymptotic variance in as few samples as possible. We formalize this setting by using the best-arm-identification bandit framework where the standard goal of learning the arm with the lowest loss is replaced with the goal of learning the arm that will produce the best estimate. We introduce new tools for constructing finite-sample confidence bounds on estimates of the asymptotic variance that account for the estimation of potentially complex nuisance functions, and adapt the best-arm-identification algorithms of LUCB and Successive Elimination to use these bounds. We validate our method by providing upper bounds on the sample complexity and an empirical study on artificially generated data.

Asymptotically Best Causal Effect Identification with Multi-Armed Bandits
Alan Malek
Silvia Chiappa DeepMind London cs reilvia@deepmind.comm com
Deep London alaamaalexOdeeepnndd. com
Abstract
This paper considers the problem of selecting formula for identifying a causal quantity of interest among set of available formulas. We assume an sequential setting in which the investigator may alter the data collection mechanism in a data-dependent way with the aim of identifying the formula with lowest asymptotic variance in as few samples as possible. We formalize this setting by using the best- cum-identification bandit framework where the standard goal of learning the arm with the lowest loss is replaced with the goal of learning the arm that will produce the best estimate. We introduce new tools for constructing finite-sample confidence bounds on estimates of the asymptotic variance that account for the estimation of potentially complex nuisance functions, and adapt the best-arm- -ar---idtiiffiatiion algorithms of LUCB and Successive Elimination to use these bounds. We validate our method by providing upper bounds on the sample complexity and empirical study on artificially generated data.
Introduction
Many scientific disciplines, including biology, healthcare, and social and behavioral sciences, are concerned with estimating the causal effect of some exposure observational study. When the structure of the causal relationships between relevant variables is known and satisfies certain conditions, the investigator the do-calculus to express a causal quantity 7 as a functional of the distribution of the observations 23 24, after which estimate of can be obtained with appropriate estimato For many structures, 7 can be identified using several formulas involving different variables. In most real- weal-world applications, the costs of measuring different variables can vary considerably. For instance, different medical tests can be more or less expensive or difficult to perform. Ideally, the investigator should conduct the observational study using the formula that optimally balances statistical performance with observational cost.
outcome of interest through an
use identification formulas derived from
Recently introduced graphical criteria allow the comparison of identification formulas derived from the popular adjustment criterion w.r.t. the asymptotic variance of linear and nonparametric estimators [7] (29 31) However, information about the causal graph structure alone does not allow comparison certain adjustment formulas nor arbitrary identification formulas. In addition, such criteria only focus statistical performance and disregard observational cost. A selection method that is applicable to arbitrary identification formulas and accounts for both statistical performance and observational cost must make use of data.
naive approach to choose a formula would be to collect a dataset in which each observation includes all variables needed by all formulas, and then compare the cost-adjusted statistical performances of
For simplicity of exposition, we assume that an identification formula is associated with only one estimator, but the method proposed in this paper can also be used in the more general case of several estimators.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the formulas. We instead propose sequential strategy in which the investigator decides, observation- by-observation, which subset of variables to observe with the goal of identifying the best formula with the fewest observations. We cast this strategy into the cost-arm-identifien by considering each formula as one arm and by replacing the typical goal of learning the arm with the best mean with the goal of learning the formula with the best long-run cost-adjusted statistical performance. This enables us to introduce methods for implementing the strategy by leveraging algorithms from the bandit literature.
bandit framework [20],
To enable us to meaningfully compare long-run behavior of different estimators, we focus on vn- consistent estimators, i.ehwith enror (p(1/ nt), and use the asymptotic variance, which is the leading constant in the error rate [22]. as the performance evaluation metric. We adapt algorithms to this goal by introducing finite-sample confidence intervals on the asymptotic variance. In particular, we show how to obtain such intervals for asymptotically linear estimators with known influence functions, which form large class of /i--consistent estimators that can be constructed for any causal effect [15]. Estimators of causal quantities typically contain high-dimensional nuisance functions 1), and modern practice is to estimate such functions using large model classes that do not have classical Donsker-like smoothness (e.g. neural networks), which often leads to a slow convergence rate of O(n 1/44 and therefore loosing asymptotic linearity. Recent work in double machine learning has established Neyman orthogonality as a sufficient condition for asymptotic linearity even when is estimated at rate On -1/4) [2). This result allows us to include estimators with complex nuisance functions in our setting. A critical aspect of our setting is that the asymptotic variance needs to be estimated at the same rate as т; otherwise the samples needed to estimate the asymptotic variance could be larger than the samples needed to directly estimate with an arbitrary estimator. Our main theorems show that, even without Neyman orthogonality, ((n-1/2) estimation of the asymptotic variance is possible whenever (nn11/2 estimation of is possible.
bandit
The rest of the paper is organized as follows. Section 2 introduces our technical assumptions on cest-arm-identiffcation problem
the estimators and formalizes selection of the best formula in aaddti-ammedd bandits. Section Battiinnnssooo shows how to construct finite-sample confidence sequences (i.e. confidence intervals that hold uniformly over sequences of random variables) the asymptotic variance, which are then used in Section to adapt the LUCB and Successive Elimination bandit algorithms to our setting. Sample complexity upper bounds are also derived. Finally. Section presents an empirical evaluation of our methods on artificially generated data, showing significant sample complexity reduction with respect a naïve uniform sampling method.
2 Causal Effect Identification with Multi-Armed Bandits
Let X, Y, and V be random variables with X denoting exposure, Y an outcome of interest, and V a set of observable covariates. Let and Pdo(z) indicate the observational and interventional distributions, respectively, which differ in passively observing X versus intervening on X by fixing its value to x.
Zi
X
Z
Y
We consider the causal contrast T == Eg )aHao(a)) where (do(x)) := Epaces Y = ar] and A2 is a scalar, in the overidentified setting in which (do(2) can be expressed as a functional of the observational distribution with K identification formulas, each using a different subset of covariates 2& C V. For example, in the causal DAG above (see Appendix A), /do(aa) can be identified with the adjustment criterion using Z1, i.e. as Mdo(z) = =Epluz (Zz) with Ma (Zz) = [YIX- = x. Zi), or with the frontdoor criterion using Zz, i.e. as M)o(w)) Ex, p(Z2 = 22 X x) E. p(X x 2z)
22).
We assume that each identification formula is associated with only one estimator î of mapping a dataset { of samples from p(W+= == (X, Y. Z,)), each having cost ck. to estimate of 7.
The goal of this paper is to propose a method for identify the estimator Ωष- with the best cost-adjusted statistical performance, using sequential strategy in which the investigator chooses an estimator î.. collects an observation of WR, k. and uses it to update its belief about the estimators. The investigator continues this process until the optimal estimator can be identified with high confidence. The aims is
to concentrate observations on the most promising estimators and to identify the best estimator in as few observations possible.

---

Assumptions on Estimators T. We focus on estimators that are /n-connistent, i... with error (,(1/ /n), and compare their statistical performance by using the asymptotic variance, which the leading constant in the emor rate [22]] To make this comparison, our proposed algorithms in Section 4 require finite-samlle confidence intervals on the asymptotic variance. While any fimite-sample confidence interval can be employed, we show how to construct such intervals for a very common and stuui-studied class of / /n-consistent estimators, namely asymptotically linear estimators with known inftuence fimctions in the presence of nuisance functions.
Nuisance functions are quantities that are required for the estimation of r, but of no interest otherwise. For example, the augmented inverse probability weighted (AIPW) estimator using covariates Z S V, defined as +(D) = EED EE A
(Y - (z( + uz (2)) where lg is the indicator function, (2) == p(X = x|| 2), and ED| denotes empirical expectation w.r.t. dataset D of samples from P(W == (X,Y, 2)). has nuisance function 1j = cx,
[
(2)
Definition 1. Let Yi=) be a dataset of samples from p(W). An estimator f of with muisance
function 7) is asymptotically linear [I7 30] if there exists function 6, called influence function (IF), satisfying Fplo(W.,, (,,,,, 7)] = 0 and Eplo² n. < oc, and such that vn(+(D) 7) = Jn -i== ...T) T) + op(). By the central limit theorem, is / and asymptotically normal with asymptotic variance o² Enlss [,,,,,T]]
If the influence function can be decomposed as @WW. m. T) = ((W, - 5, then vb is called the uncentered inftuence function (UIF). In this case, Eplo m)) and 0² varpl n)]]
The important property of asymptotically linear estimators is that they have a well-understood asymptotic variance, and the UIF case provides additional structure.
When we need to estimate 7/, asymptotic linearity of might not hold depending on the function class used to model the estimator fj and on the rate at which r converges to vj: a rate slower than ((m=1/2) could cause the same rate for the error of and, therefore, a loss of asymptotically linearity. For example, if f is modelled with a high-dimensional or nonparametric function class, one generally expects rate On114). Recent work in double machine learning 2 has shown that Neyman orthogonality a sufficient condition for asymptotic linearity of even when ij converges rate On (n-11))) Jung et al. [T3] [6] show that asymptotically linear estimators with Neyman orthogonality exist for all identification formulas. Hence, all identification formulas can be included in our framework even with nuisance functions estimators that converge at rate On11/)
Multi- Arme Bandit Formalism. We formalize the problem of identifying the estimator with the bandits
best cost-adjusted asymptotic variance as a cess--rm--ddetiffccati (BAI) in (MAB) problem. MAB is powerful framework for modeling sequential decision problems under uncertainty as a repeated game between an investigator and the environment (see Appendix BB.
For k E [K] := f1...., K}. let f be an asymptotically linear estimator of T with asymptotic variance of and cost cy. The goal of the investigator is to identify the estimator Tke such that k- == arg m This scaling arises because guaranteeing Ifx r| (c)) with high probability
requires = ( samples, which has cost of Occ ffff/// fe2)).
For some 5 O, and >> 0, the
goal is to find an (e, 6)PA) index k. i.e one that satisfies
( 2 min + <
In words, & has probability at least 8 of being at most e-suboptimal.
At each round n = 1, l... ... the investigator chooses an index hos E [K], obtains an observation wh pWW),, updates its belief about the cost-adjusted asymptotic variance cga and decides whether to continue sampling or return an (e, 6)C index.
The standard BAI goal is to identify the arm with the smallest average loss in as few samples as possible. Our setting can be treated variant by replacing this goal with the goal of learning the estimator with the lowest adjt-adjusted asymptotic variance. This enables us to leverage algorithms from the BAI literature.
Most BAT algorithms fall into the following three categories: (1) action elimination algorithms, such as Successive Elimination (SE) 44, which keep set of arms that could be optimal and alternates
3

---

between sampling all the arms in this set and using confidence intervals to prune the set; (2) optimistic algorihhms, including Upper Confidence Bound (UCB) and LUCB [T7, which first construct the most optimistic problem instance that is consistent with the confidence intervals (e.g. by assuming the smallest mean values) and then act greedily as the instance was true; (3) Bacc-and-Stop-sty algorithms [9]] which compute an asymptotic lower bound on the sample complexity and try to keep the empirical sampling proportion close to the sampling proportion achieving the lower bound.
Track-and-Stop-S0 algorithms require the sampling distribution of all the arms to be from parametric family and therefore are not appropriate for our setting. Instead, action elimination and optimistic algorithms can be implemented whenever one has unite-sample confidence sets. We focus on LUCB and SE, as both algorithms can be implemented using arbitrary confidence sets (i.e. that are not a known function of n²).
In the next section, we develop the necessary tools for estimating two-sided confidence bounds of that hold for all estimators and all rounds simultaneously.
3 Finite-Sample Confidence Sequences for the Asymptotic Variance
We now turn towards constructing a finite-sample confidence sequence on the asymptotic variance d² of a particular estimator of r that depends on assumptions on the distribution of W, smoothness properties of the influence function o, and the rate of convergence of fj.
3.1 Confidence Sequences
confidence sequence. defined for a stochastic process, essentially provides a confidence interval that holds uniformly over time.
Definition 2. For a stochastic process (Em)a2 En E R, and coverage level a > 0, confidence sequence of level a sequence of real numbers == {un]a2 referred to as boundary sequence at level a, satisfying P(vn 2 1: &n S un)) > - a.
Instead of using a confidence sequence, one could control En by defining a confidence interval for every n and taking union bound. However, to maintain a total probability of error of a, the confidence interval for &n must have error probabilities that sum to at most a, which typically results in confidence interval width that is logarithmic factor larger [3]
3.2 Sample-Splitting Estimator of o²
Let f be estimator of with IF o, asymptotic variance o². and nuisance function with estimator f). We propose and analyze the following sample-splitting estimator 62 of o² on dataset DD We first divide D into the three folds D", Dr and D We then D to obtain estimate rj(")) of n, compute f(D", (D")) as an arbitrary solution in (r' Ep (ø(W, i(D"), r')] = 0}, and evaluate
8 (D = Epr Io² (D") ((D", ((D")))
(1)
In the case in which f has UIF vb, the estimation procedure be simplified by dividing D into two folds, and Dr, and computing
0² (D) varp- (W, ((D)) Ep= [o² (W, (W,n(""), (D"""""))
where var indicates empirical variance w.r.t. D In both cases, data splitting alleviates the bias in 6² by forcing it to be independent of the bias in r (and of the bias of in the IF case). The UIF case more sample efficient because we do not need to directly compute 4.
3.3 Confidence Sequences for (D) o²
We want to study the behavior of an estimator i evaluated on growing datasets, as one would find in a bandit problem. We consider datasets D2 S D: ..., where D, obtained by augmenting D, with new samples. We also assume that the data folds grow in the same manner. For example, in the UIF case, we have D, D D with D S D., and D S Dr. We wish obtain confidence sequence on the estimation error of the asymptotic variance, [D, a²I, terms the estimation error of the nuisance function [D)) 7/l and other problem parameters.

---

The main result of this section is that the estimation error of the sample-spliting estimators defined in Eqs. 1 and 2 only scales with (l)) - ) this scaling allows for (D,) - o²1 =
O(n even when I(r( nl On 1/4). We present the UIF case first. Theorem 1. Consider
L-Lipschitz UIF v. upper bound 7 on [T], and les > O. Let (Da]n21 be a sequence of datasets with Dn = Då U Dr D= C D2, and D C Dr Assume that w( v())2) and un are boundary sequences of level ar for [Eag [o,, n)] B(yb(W, n)l,,
ED [u, n) (lb, n) and ((A(D)) - 7I1, respectively. Then, the estimator 8² defined in Eq. satisfies
Vn 1: (D.) -o²1 = 222 (x + un (1:2) + (1) 2Fu 2 1 11-13 -3a.
P
A confidence sequence for ( ml and tail control of ((W,,) are sufficient for con- trol of (D.) - o²|. Note that we only re- quire control of (W, at the true 1J. Also note that (u rather than u... appears in the bound, m/13) scaling. Computing this bound is an essential subroutine, outlined on the right.
CSUpdate (UIF version)
Input Boundary sequences u == (u,,u², 2²),, i L, 7, Dd, D", 3 8² f varD- (WW
Using n. = |Da] and n2 = (D0
which justifies our claim of O(Il
B - 2L² )² + un + (4,, + 2
Return o², ,
Proof Outline. Let im == (D(D). 82 == (D().). and En := Edg. Using the identity
var, (W, mmm)] = Em, (.,, nn - E., (bW,, I. we can expand 0² 0², as
a 0² = =R., [W, <W,, m)) + 2T (wb( (n)) (W,
(W, (),)) (W, [WW, (.)) + (W,
+ (Enlv (W, [W]]]]] -)]] 1E (W.))) + [E,.v Ble ())))
Since v T--Lipschitz, the first term can be bounded by I.2 1 - nl1² The second and third terms can be simplified with 2 Am - n/12 term. The forth term controlled by uia (.)2) and the final term can bounded
the first order terms cancel out, and the result is another
m)9 < (B(&(W, W.W )) 2 - (IW,
E. [W,, n1
< 1)) + 2 Dl mi| s (u. + (
similar result can be obtained without an UIF as long as one has an additional confidence sequence | For precise statement and all proofs. In this case, the CSUpdate subroutine needs to be modified to use a third data fold D;, the appropriate o², and the confidence sequence from Theorem 2
on f +("), ((D))) See Appendix
Theorem 2. Consider an T-Liipscitz IF ds an upper bound i on |T]. and let a O. Let (Dn) n>1 be a sequence of datasets with D, = DR DT, D.D,, D==1 S DD Dr R- C DT and De n-1 C Do Assume that there exists boundary sequences of level as in Theorem with e replacing vb throughout, and that u is a boundary sequences of level a for [+(D%, (DD)) T/. Then, the estimator 8² defined in Eq. ( satisfies
PP Vn 2 1: (D,) - = 2L + )² + u (d.2) + (2 + 2F1(
2 2-
Combined with a result that [+(,, (Di:)) - -| = (lI((D)) - m (see e.g.
2 5),, we have that
[&²(D..) o2 = (II())))))))))))))))))) - ).
We emphasize that the O (())))))) - n|13) scaling is surprising, as naive argument would produce a
dependence on (lI))(D)) nl) instead; using the shorthand ft. ((D)) and f, =((D, )m,),
0² (DD) - x² = =E,, im, f.]] - ((o n. 7)]
= =E,, (oW,, Pmy f.)) <WW,,, 7))² + (WW, (,, Fw) - (WW TT)
+ E,, (W"(W, , n, T)] - Elo"
5

---

and the second term is ( - -ll) under a simple bound (e.g. Cauchy-Schwarc
3.4 Sub-Gaussian Random Variables
Confidence sequences for empirical expectations around their means well established in the literature, see e.g. [00]. As an illustration, this section derives a confidence sequence under the common assumption that the variables are sub-Gaussian.
Definition 3. A random variable W is À sub-Gaussian if there exists constant X such that [c"[ [<[[W-][]]] S e²4 for all E IR. random variable W is sub-exponential with scale c if there exist constants U, such that E [4(W-BIWD] S. e Vt E 10.)/c).
useful property is that the square of uub-Gaussian random variable is sub-exponential. The specific parameters can be found by comparing moments; for example, [8 Appendix BJ shows the following result.
Lemma 1. IfW is À nau--Gassiin, then W is 4v2x² sub-exponential with scale 4X.
Intuitively, sub-Gru So--Gasssian random variables have tails no heavier than a Gaussian with variance A, and sub-exponential random variables have tails heavier than x² distribution. Sub-Gaussianity is common assumption in the bandit literature satisfied in many applications; for example, B-bounded random variable is B sub- Gaussian.
Confidence sequences for sub-Gaussian and and sub-exponential random variables can be found in the literature, see e.g. [10]. Then, we may use the fact that Epg (W,, n)] ([v((,))) is sub-Gaussian and DE [xb (W n - (W r7 is sub-exponential to derive the following bound for our variance estimation error. See Appendix for more details.
Corollary 1. Let E (0, 1) and assume the same setting as Theorem 7 and additionally that ( À sub-Gaussian Then, X' AV8X2, any m and n' (91X (log(X'n/ (Nn//m) (og(l/o)) (m/X) X),, we can show that
X
Xnn
2 + log - S
IP
An 2 n' (0²((D)) -2) 21!) 6F)
6F)
log
2
3.5
Confidence Sequences for [ 1/
Our main theorem presents a confidence sequence on the asymptotic variance terms of the nuisance function estimation error, [}r)(D:) 7/l. There are many estimators that have confidence sequences established in the literature, such as least squares estimators 3 Additionally, for estimators with confidence interval but no confidence sequence, we can always take a union bound over
To be precise, suppose that we have function R(n, a) such that, for any n and a < 0, [(]()())) 1l1 > R(n, a)) I a. Then uy = R(n, 6a/ (Tn) 2) is boundary sequence of level a, verified by the calculation TP (An > 1: [l)(D.) 7l 2 2 S E% (I)((P)) nill Z R(n, (a/(T))²) s >
1
60 a.
Hence, without loss of generality, our algorithms and results can be stated in terms boundary sequence u". Typically, if R(n, a) Onn" log(1/a)). the above union bound construction only adds log terms to the final bound, which is generally sufficient for most applications.
CS-LUCB and CS-SE Algorithms
This section introduces adaptations of the LUCB and SE bandit algorithms that the confidence sequences derived in Section 3 we refer to them as CS-LUCB and CS-SE. For simplicity of exposition, we present the UIF case (the IF case requires keeping a third data fold and modifying CSUpdate as described in Section 3.3)
CS-LUCB and CS-SE are summarized in Algorithms D and 2 These algorithms take input, for & E [K]. the UIF the the estimator în the nuisance function 7]s, the cost c₁ the boundary sequences uy (u). ut u and constants required by Theorem and a batch size B.

---

At every round, CS-LUCB samples obser- vations for the estimator with the lowest cost-adjusted asymptotic variance and for the estimator with the lowest lower confi- dence bound among the remaining estima- tors. Intuitively, samples from these esti- mators are the most informative. The algo- rithm stops when the confidence sequence of the best estimator is separated from the rest, up to the error tolerance.
Algorithm 1 CS-LUCB
Input e > 0, B 7 0, 0,
(w),, îi, Mg, C : E [K]] for k=
do
Obtain B new samples D Add half of 'D to D2 and half to Dj K Bx CSUpdate(uk: tes 2/k, L, 7, Db D2.)
end for
= 1, 2,..... do 4 arg minke[ uy arg minxx,,,c*60 - Bx)
CS-SE keeps set S of plausibly best es- timators. every round, it obtains sam- ples for every estimator in S, updates their confidence sequences, and removes all es- timators with lower bounds higher than the upper bound the best from S, as these estimators are no longer plausibly optimal. The algorithm terminates when only one es- timator remains all remaining estimators are within e of each other.
if ct. (oī, + B.,)) Cue (0 BBa)) then
Return k =1e end for
k E ur, do Obtain B new samples D
Add half of D to Dj and half Dj
0 B CSUpdate(uu, njk 19k, L, F, D2, D()
end
end
We define the gap of estimator k to be A := 4.0 mi The random variable 3g (n) is the confidence width re- turned by CSUpdate for estimator after updates, which might be random. We as- sume that 3p (n) is independent of B, (n) for all j * k. In the remainder of the section, we prove that both algorithmss re- turn (c, PPC indices if the confidence quence width approaches zero and provide upper bounds the sample complexities when an upper bound on the confidence width is available.
Algorithm CS-SE
Input 6 > 0, B 1, 7 1, 0,
(wk, fik, Uk, C k E K]]
S - [K]. and D + 0, DE t 1 Ak [K]
while |S| > 1 do
for k E S do
Obtain B new samples D
Add half of D to D2 and half to D
0 B CSUpdate(uu, me, th, L, F, Di, Di)
end
1 t arg c
Theorem 3. Assume that the con- ditions of Theorem [ hold, that
R+ E (0) + +3) cu -x)}
S S R
u Unn -kk. - 0 for all k E [K]. and that all boundary sequences are of level a = =8/(3). Then both CS-LUCB
(e:1) (4.2)
if B < for all k E S then
S arg minkesc4
end
and CS-SE with Wi (ug. "k .uk return an (c, ()PC index.
(v.1)
(1)2))
end
Return ==
If we have deterministic upper bound By(n, 8) such that, for all ò > 0, (P333x (n) S BB 8)) > 1 - 8, then both algorithms terminate in at most Σne(K] min {n= (n,n,,ō/K < 4 V 1 samples.
If. additionally, there exists constants Vay 1) and (()22) such that uh,,, I O( log (nK/8))
for all 0 E {n, (1) 1),()))))) 2)} and all le [K], then the sample complexity
K Σ
(108
K
1/V
(A
8(AA
V L/
1=1
with probability at least 1 where v min 1) (( In particular, if &(W, n) is sub-Gaussian, we recover the sample complexity results (up to log factors) of 14 17 under the mild condition of vn 2 1/4.
Discussion.
To aid comparison with the BAI literature, we have provided sample complexity bounds for the special case which uf,, = O(n log(n/5)). The most common assumption in the bandit literature is that the data is sub-Gaussian meaning that may take ve 1. In this case, sample
7

---

complexity results are within log-factor of the optimal and within a log-factor of the lower bound when 0. Algorithms achieving the optimal rate include Ui [1] and Exponential Gap Elimination [88. Unfortunately, these algorithms require the widths of the confidence regions for the arm mean estimates to decrease at the same rate, which not an assumption we can make in our setting (as the rates in our setting depend on properties of the estimator and its influence function).
5 Experiments
We studied the empirical sample complexities of the CS- LUCB and CS-SE algorithms for the task of selecting an identification formula for the causal DAG the right, where the plate notation indicates that the path X & Vn Zm + Y is repeated M times. Specifically, we considered the problem of selecting between the 2 identification formulas obtained from the adjustment criterion using either Vm or Zm. for all m E [M.) and the identification formula obtained from the frontdoor criterion using Zo: i.e. between 2d +1 1 different formulas. We compared our two algorithms against a simple uniform sampling baseline that samples every estimator the same number of times. The code implementing the experiments is available at github. cow hwtp//deemmmmaaeeeeeeeee halpddddbeiimmmne _ma
Vm
7mm
X
Zo
Y
If we ignore cost, graphical criteria suggest that the adjustment formula with the lowest lower asymptotic variance is obtained by choosing Zm for all m [M] (see Appendix A.2) Therefore, we set the cost of including Zm or Vm equal to and 1, respectveely (X and Y have no cost).
We assumed binary exposure X and considered causal contrast := Σx >x//do(a) with À -1, A1 = 1, corresponding to the average treatment effect. We used the AIPW estimator for the adjustment formulas and Neyman orthogonal estimator derived from Fulcher et al. [6 Theorem 1] for the frontdoor formula (see Appendix A..3 for details); both have uncentered influence functions, thus the estimator from Eq. was used.
5.1 Linear Model
In our first experiment, we considered observational data generated from the following linear model.
For m E [M], Vm (0, I2), Zm Am Vm + Cz,m for matrix A. E 3x and 62,m ~ ~N( .1Ts).
X Bernoulli (1/( + EM B,, for vector B,, E RR,, and Zu is sampled from a categorical distribution conditioned on X. Specifically, for support points S {sa E R E [10]} and vectors Q1 and gu in the 9-simplex, we set p( = s,|X i) q (j), where q: (i))) is the jth element of q. Finally, Y Em= ZT +.y for vector C. 2R22 and E, (0,....
MM
Specific observational distributions were obtained by sampling Um ~ Uniform (.1.9) and then each element of Am. B,n, and C... from (00 UZ/ /4), (O, U and (N (2 - )n) respectively. The purpose of this sampling scheme was to produce distributions where the correlation between Vn and X and the correlation between Zm and Y are not both large. This choice widens the gaps to the best estimator and results in a more interesting bandit problem. By had elements independently sampled from (O,,) 1/4).
To generate the distribution of Zo. we sampled each support point of from (N, 12), G1 and Go from (0, 11)), and set qı softmax(A4G.) and go softmax(.4Go) We then computed D 10 (g) (i) - (i)) (()) BJ s; and resampled S, go. and qı until was larger than 1, which avoided the hardest instances and allowed us to run more simulations. As harder instances increase the sample complexity of the uniform algorithm the most, this resampling step does not inflate the advantages of CS-LUCB or CS-SE.
For the AIPW estimator, we used ridge regression and logistic regression to fit (z) E,, x. 2] and e..(2) == p () respectively. We used known confidence sequences for ridge regression (see Abbasi- Yadkori Abbasi-Yadkori al. [1 Theorem 2] or Lemma 7 in Appendix D), and confidence intervals for logistic regression were approximated by a standard central limit theorem (CLT) confidence interval, [2 + 2a,,/2 v
std 6² + 21 21-a./2
std(63) Vn
with 5 0.1 and an 68 rn? following the
construction described in Section 3.5
8

---

40
1.25
frontdoor
Samples
1,00
V/2223
Variance
20
V/
0.50
VIVE3
0.25
0.00
0.2
0.4
0.6
0.8
1.0
CS-LUCB
CS-SE
uniform
Samples x 100 (a)
Figure 1: (a): Example of confidence sequences corresponding the four best estimators for CS-SE, up to the 8.1 * 100 samples required to find the optimal estimator. (b): Box plot comparing sample complexities of CS-LUCB, CS-SE, and uniform sampling.
For the frontdoor estimator, we used ridge regression for urr (Zo) and the MLE (i.e. empirical counts since the random variables categorical) for p(X x) and ez (Zo).
Results. For M 3 (which produces adjustment formulas and frontdoor formula), we generated 10 observational distributions and, for each distribution, ran the algorithms 5 times from scratch on independent data. typical run of CS-SE shown Fig. aa): confidence sequences of the four best formulas are plotted, and one can identify visually when sub-optimal estimators are removed from S. The algorithm terminates as soon as the two lowest confidence sequences no longer intersect. In Fig. [b), we provide box plot for the distribution of sample complexities for the three algorithms. The orange line, box, and whiskers indicates the median, the IQR (the 25th percentile percentile), and the outlier-fitered range (points with values 1.5 xIQR greater than the 75th percentile are removed), respectively. We see that some instances can be difficult for all algorithms (if, for example, many of the gaps are small), but CS-LUCB and CS-SE display substantial reduction in sample complexity w.r.t. the uniform sampling algorithm, on average needing 34% and 51 % the number of samples to terminate.
the 75th
5.2 Nonlinear Model
key result from Theorems and 2 the second-order dependence on the rate of f estima- tion, which allows the use of high-dimensional. nonparametric estimators for n7. To showcase this, we considered a more complex nonlinear generation process. Given nonlinear functions fms Im, Am for
[M] and go, generated observations as in Section 5.1 except with X
Bernoulli (1/(1 (1+e-E - (V.)) 7m = fm(()) + 62,m, and Y ΣM Im (7m) + Cy- We sampled the nonlinear functions to be element-wise from a Gaussian process prior with the RBF kernel on 10d equidistant points in (- where d is the dimension of the domain. We fit all the nonlinear functions with gradient-booster regression trees with the same kernel. The confidence sequences for the nuisance functions were approximated using the same CLT-based construction used for logistic regression.
Results. Similar to the linear case, we generated 10 random observational distributions with 9 formulas and, for each distribution, ran each algorithm times from scratch on independent data. We found similar reduction in sample complexity as in the linear case (see Fig. [(a)). We also explored how the sample complexity changes with the number of formulas. We sampled an observational distribution for all M E {3, 5, 6] (corresponding to 9, 17, 33, and 65 formulas); for each distribution, we ran the algorithms from scratch times on independent data and plotted average sample complexities as function of the number of formulas in Fig. b). Our theory from Section 4 predicts that the sample complexity is determined not by the number of estimators but by the reciprocals of the squared gaps, which increases sub-lincarly with the number of estimators as

---

x10
x10
CS-SE
Samples
CS-LUCB
Samples
uniform
0.0
CS-LUCB
CS-SE
uniform
Number of Formulas
(a)
(b)
Figure 2: (a) Box plot of sample complexities with 9 formulas. (b) Sample complexities function of the number of formulas.
many of them have large gaps. In contrast, the sample complexity of the uniform algorithm should increase linearly. This prediction is confirmed by our experiments.
Discussion
Much of the literature on causal inference from observational data has focused either on identify- ing causal effects using structural knowledge of the causal graph underlying the data generation mechanism or on the design or selection of sample efficient estimators. The problem of selecting an identification formula using the efficiency of corresponding estimator is only starting to receive attention.
Despite the recent progress of graphical criteria, comparing arbitrary formulas with statistical and practical considerations, such as cost or inability to observe certain covariates, remains an open problem. This work attempts to provide a functional answer to this problem: instead of trying to derive solution from graph properties, we have provided a practical method that uses observational data to select formula. When the graphical criteria do not apply, such when the graph is partially unknown, latent variables exist, or when costs need to be considered, our methods can help the investigator reach conclusion in a sample efficient way.
Our methods have the limitations only guaranteeing an asymptotically optimal formula and relying on the availability of influence functions to quantify the asymptotic variance. To the best of our knowledge, more data-driven approaches estimating the variance of estimators, such as resampling methods, do not have any finite-sane finite-sample guarantees and are not appropriate for bandit algorithm. Still, selecting between more general classes of estimators an interesting direction.
References
[1] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances Neural Information Processing Systems, pages 2312-2320, 2011.
[2] Victor Chernozhukov, Denis Chetverikov, Mert Demirer, Esther Duflo, Christian Hansen, Whitney Newey, and James Robins. Double/debiased machine learning for treatment and structural parameters. The Econometrics Journal, 21(1):C1-C63 2018.
[3] Victor de la Peña, Guodong Pang, et al. Exponential inequalities for self normaazzdl processes with applications. Electronic Communications in Probability, 14:372-388 2009.
[4] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 10)9 2006.
10

---

[5] Dylan J. Foster and Vasilis Syrgkanis. Orthogonal statistical learning. arXiv preprint arXiv:1901.00030 2019.
[6] Isabel R. Fulcher, Ilya Shpitser, Stella Marealle, and Eric J. Tchetgen. Robust inference on population indirect causal effects: the generalized front door criterion. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 82(1):199-214, 2020.
[7] Leonard Henckel, Emilija Perković, and Marloes H. Maathuis. Graphical criteria for efficient total effect estimation via adjustment in causal linear models. arXiv preprint 2019.
[8] Jean Honorio and Tommi Jaakkola. Tight bounds for the expected risk of linear classifiers and pac-bayes finite-sample guarantees. In Artificial Intelligence and Statistics, pages 384-392. PMLR, 2014.
[9] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform chernoff bounds nonnegative supermartingales. Probability Surveys, 17:257-317, 2020.
[10] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametrie, nonasymptotic confidence sequences. The Annals of Statistics, 1952)1055--1000 2021.
[1]] Hidehiko Ichimura and Whitney K. Newey. The influence function of semiparametric estimators. arXiv preprint arXiv: wet.:500800000 508,01378, 2015.
[12] Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In Annual Conference on Information Sciences and Systems, pages 1-6, 2014.
[13] Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparame- ter optimization. In Artificial Intelligence and Statisttics, pages 240-248 2016.
[14] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil' ucb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439, 2014.
[15] Yonghan Jung, Jin Tian, and Elias Bareinboim. Estimating identifiable causal effects through double machine learning. In AAAI Conference on Artificial Intelligence, pages 121 121222 2021.
[16] Yonghan Jung, Jin Tian, and Elias Bareinboim. Estimating identifiable causal effects markov equivalence class through double machine learning. In International Conference on Machine Learning, pages 5168-511 2021.
[17] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. PAC subset selection in stochastic multi-armed bandits. In International Conference Machine Learning, pages 227-234, 2012.
[18] Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-1246, 2013.
[19] Emilie Kaufmann and Shivaram Kalyanakrishnan. Information complexity in bandit subset selection. In Conference on Learning Theory, pages 228-251, 2013.
[20] Tor Lattimore and Csaba Szepesvári. Bandit Algorithums. Cambridge University Press, 2020.
[21] Shie Mannor and John N. Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5:623-648, 2004.
[22] Whitney K. Newey. The asymptotic variance of semiparametric estimators. Économetrica, 62 (6):1349-1382, 1994.
[23] Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2000.

---

[24]
Judea Pearl, Madelyn Glymour, and Nicholas P. Jewell. Causal Inference in Statistics: A Primer. John Wiley & Sons, 2016.
[25] Emilija Perković, Markus Kalisch, and H. Marloes Maathuis. Interpreting and using CPDAGs with background knowledge. In Conference Uncertainty in Artificial Intelligence, 2017.
[26] Emilija Perković, Johannes Textor, Markus Kalisch, and Marloes H. Maathuis. Complete graphical characterization and construction of adjustment sets in markov equivalence classes of ancestral graphs. Journal of Machine Learning Research, 18(220):1662 2018.
[27] Andrea Rotnitzky and Ezequiel Smucler. Efficient adjustment sets for population average causal treatment effect estimation in graphical models. Journal of Machine Learning Research, 21 (188):1-86, 2020.
[28] Ilya Shpitser, Tyler VanderWeele, and James M. Robins. On the validity of covariate adjustment for estimating causal effects. In Conference on Uncertainty in Artificial Intelligence, 2010.
[29] Ezequiel Smucler, F Sapienza, and Andrea Rotnitzky. Efficient adjustment sets in causal graphical models with hidden variables. Biometrika, 2021.
[30] Aad W. Van der Vaart. Asymptotic Statistics. Cambridge University Press, 2000.
[31] Janine Witte, Leonard Henckel, Marloes H. Maathuis, and Vanessa Didelez. On efficient adjustment causal graphs. Journal of Machine Learning Research, 21(246): 2020.
12


Reviews:
[{"review_id": "nls2Ktw69Qo", "reviewer": "Reviewer_QgMM", "summary": "This paper aims to select the best causal formula among a set of available formulas based on the asymptotic variance criterion. An online setting with best-arm-identification framework is considered. The paper poses the sequential decision problem on how to choose which observations in a sample efficient way. Framing the problem in multi-armed bandits framework avoids the requirement of structural knowledge of the graph and allows comparing arbitrary formulas. Novel confidence sequences with nuisance functions for a sample-splitting estimator are introduced. Two well-known bandit algorithms, lower-upper confidence bounds (LUCB) and successive elimination (SE), are adapted with these confidence sequences and sample complexity results are established. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper attempts to provide a step towards identifying best available formula for the causal effect identification without deriving a solution from graphical criteria. Causal effect identification is posed as a sequential decision problem where the investigator chooses which observations to make and updates the beliefs regarding the available formulas. \n\nStrengths: \n-\tThe difference from the previous works is stated clearly. Some of the limitations of the recent works, e.g., practical constraints for selection methods based on graphical criteria, are addressed via estimating the asymptotic variance directly. \n-\tThe idea of framing this problem as a best-arm-identification bandits problem is simple yet effective. It may serve as a first step for solving more general problems as briefly touched in the discussion section.\n-\tThe main technical result is a novel confidence sequence for the sample-splitting estimator. It shows that having an uncentered influence function leads to a better convergence rate in terms of nuisance estimation. Since most causal estimators require a nuisance estimate, this can be a nice feature.\n-\tAdaptation of LUCB and SE bandit algorithms are sound.\n\nWeaknesses:\n-\tIn simulations section, the proposed algorithms are shown to require significantly smaller number of samples than uniform sampling at finding the optimal arm (best formula). However, only 9 formulas are considered. It would have been insightful to comment on the effect of the number of formulas, e.g., does scaling behavior bear similarities to the sample complexity results presented in the section 4.\n-\tThe general problem of trying to obtain the best estimate of the causal effect is briefly mentioned in the limitations section. The reviewer understands that this paper is a first step in that direction. Nevertheless, it would have been interesting to talk a bit more about the general problem. For instance, a discussion on the applicability of the methods employed in this paper to infinite-armed bandits setting would shed light on the importance of this work for the future research.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the work are addressed in discussion section. Negative societal impacts are not given, yet the reviewer does not foresee any such impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "QNKG3ZChB6Z", "reviewer": "Reviewer_5RfN", "summary": "This work considers the problem of selecting identification formulas to estimate a causal effect. The problem is formed as a best-arm-identification bandits problem, i.e. in each round, the investigator can select a formula and observe some data, and the target is to find out the best formula with as few samples as possible. The return of each arm is weighted asymptotic variance of the estimator. The authors provide finite-sample confidence sequences for asymptotic variances, which is then used in the bandits algorithm. Theoretical guarantees and numerical experiments for a toy problem are provided. This paper is the first work in using observational data to select formulas.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- Novelty: This paper is the first work that frames the problem of formula identification as a best-arm-identification problem. In addition, the authors develop novel finite-sample confidence sequences with nuisance functions for a sample-splitting estimator of the asymptotic variance. They proved that having an uncentered influence function allows for confidence sequences that are insensitive to errors of the nuisance function estimates.\n\n- Clarity: Overall the paper is well-writed and structured while there are some minor issues. This work covers two area, i.e. causal inference and bandits, which makes the exhibition of background knowledge important. It is reasonable to move some background knowledge to the appendix, but it should be mentioned in the main text. In addition, little background knowledge on bandits theory is provided. It would be great if the authors can give an overview on algorithms for best-arm-identification, especially LUCB and SE. \n\n- Significance: It is interesting that the authors connect the problem of formula identification with bandits and this is not the popular casual bandits/RL. However, this work seems to be lack of technical and algorithmic contribution. The only technical contribution is Theorem 1, which seems to be quite straightforward. The algorithms are also just LUCB and SE with few changes.\n\nI am curious about why the problem is formed as best-arm-identification instead of regret minimization. With the confidence sequence, the UCB-type algorithms for regret minimization can be adapted just as LUCB and SE. Is there any difficulty in doing so?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation is stated in the Main Review, i.e. this work lacks technical and algorithmic contributions. There are also some minor issues.\n\n- Are there typos in Appendix D? For example in (2), $\\lambda^\\top S_t$ is a scalar while $\\psi(\\lambda)V_t\\in\\mathbb{R}^{d\\times b}$. In addition, what is $\\psi(\\lambda,V)$? Also in Lemma 5, what does $sub-\\psi(\\lambda,V)=\\sigma^2\\lambda^\\top V\\lambda/2$ mean?\n\n- The experiments only compare the algorithms with uniform sampling. It would be great if they can be compared with graph-structured-based algorithms.\n\n- In the Discussion, the authors state that when the graph is partially unknown or latent variables exist, their methods still work. Is there any example when the above situation happens, the influence functions are still available?\n\n- As mentioned in the paper, this method relies on asymptotic linearity and influence functions need to be known.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "CVK4M7nFuoe", "reviewer": "Reviewer_NBmz", "summary": "This paper proposed a novel BAI framework. In the proposed framework, the goal is to identify an estimator with the lowest asymptotic variance.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Concerns:\n### Asymptotic optimality\nThis study insists that \"Asymptotically Best Casual Effect Identification,\" but there is not proof the asymptotic optimality.  \nThe \"Asymptotically Best\" may refer to asymptotically efficient estimator for the causal effect.  \nHowever it does not mean the asymptotic optimality of the best arm identification (BAI) algorithm.\nFor more details, see Gariver and Kaufmann 2016.  \n[Optimal Best Arm Identification with Fixed Confidence](http://proceedings.mlr.press/v49/garivier16a.pdf  )\n\n### Inefficient sampling\nIn the main algorithm, the authors do not use half of samples to use double/debiased machine learning (DML).  \nHowever, I think that this is a bit inefficient.  \nCan we use the method of Howard et al. 2019?\nThat is, by using past observations, we can conduct DML for dependent samples.  \nThis is also used by van der Laan 2008 and Kato, Yasui, and McAlinn 2020.  \n[The Construction and Analysis of Adaptive Group Sequential Designs](https://biostats.bepress.com/ucbbiostat/paper232/)  \n[The Adaptive Doubly Robust Estimator for Policy Evaluation in Adaptive Experiments and a Paradox Concerning Logging Policy](http://128.84.4.18/pdf/2010.03792)\n\n### Application\nI don't really understand how this paper can be applied.  \nI understand that the authors' study are motivated by the study of causal inference, but I could not understand the contribution to the field of bandit and design of experiments until the authors connect it a bit more with the literature on bandit and design of experiments.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not fully understand where the proposed method can be used.   \nI will consider social impact in discussion with the authors.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper used best-arm identifications to select the best estimator for identifying a causal effect. While the techniques are not new, the reviewers and the AC believe the result in this paper is an important first step. 
The AC also recommends that the authors add discussions on recent theoretical results (e.g., finite-sample regret analysis) of causal bandits.
Decision: Accept (Poster)