Efficient Online Estimation of Causal Effects by Deciding What to Observe

Abstract:
Researchers often face data fusion problems, where multiple data sources are available, each capturing a distinct subset of variables. While problem formulations typically take the data as given, in practice, data acquisition can be an ongoing process. In this paper, we aim to estimate any functional of a probabilistic model (e.g., a causal effect) as efficiently as possible, by deciding, at each time, which data source to query. We propose online moment selection (OMS), a framework in which structural assumptions are encoded as moment conditions. The optimal action at each step depends, in part, on the very moments that identify the functional of interest. Our algorithms balance exploration with choosing the best action as suggested by current estimates of the moments. We propose two selection strategies: (1) explore-then-commit (OMS-ETC) and (2) explore-then-greedy (OMS-ETG), proving that both achieve zero asymptotic regret as assessed by MSE. We instantiate our setup for average treatment effect estimation, where structural assumptions are given by a causal graph and data sources may include subsets of mediators, confounders, and instrumental variables.

heading: 1 Introduction
text: Statistical and causal modeling typically proceed from the assumption that we already know which variables are (and are not) observed. However, this perspective fails to address the difficult data collection decisions that precede such modeling efforts. Doctors must select a set of tests to run. Survey designers must select a slate of questions to ask. Companies must select which datasets to purchase. Whether or not we model these decisions, they pervade the practice of data science, influencing both what questions we can ask and how accurately we can answer them.
One might ask, why not collect everything? The answers are two-fold: First, data acquisition can be expensive. In a medical setting, blood tests can cost anywhere from tens to thousands of dollars. Running every test for every patient is infeasible. Likewise, space on surveys is limited, and asking every conceivable question of every respondent is infeasible. Second, in many settings, we lack complete control over the set of variables observed. Instead, we might have access to multiple data sources, each capturing a different subset of variables. Such data fusion problems pervade economic modeling and public health, and present interesting challenges: (i) efficiently estimating (or even identifying) a population parameter of interest often requires intelligently combining data from multiple sources; (ii) data collection is often iterative, with tentative conclusions at each stage informing choices about what data to collect next.
In this paper, we formalize the sequential problem of deciding, at each time, which data source to query (i.e., what to observe) in order to efficiently estimate a target parameter. We propose online moment selection (OMS), a framework that applies the generalized method of moments (GMM) [17] both to estimate the parameter and to decide which data sources to query. This framework can be
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
applied to estimate any statistical parameter that can be identified by a set of moment conditions. For example, OMS can address (i) any (regular) maximum likelihood estimation problem [13, Page 109]; and (ii) estimating average treatment effects (ATEs) using instrumental variables (IVs), backdoor adjustment sets, mediators, and/or other identification strategies.
Our strategy requires only that the agent has sufficient structural knowledge to formulate the set of moment conditions and that each moment can be estimated using the variables returned by at least one of the data sources. Interestingly, the optimal decisions which lead to estimates with the lowest mean squared error (MSE) depend on the (unknown) model parameters. This motivates our adaptive strategy: as we collect more data, we better estimate the underlying parameters, improving our strategy for allocating our remaining budget among the available data sources.
We first address the setting where the cost per instance is equal across data sources (Section 4). First, we show that any fixed policy that differs from the oracle suffers constant asymptotic regret, as assessed by MSE. We then overcome this limitation by proposing two adaptive strategies—explorethen-commit (OMS-ETC) and explore-then-greedy (OMS-ETG)—both of which choose data sources based on the estimated asymptotic variance of the target parameter.
Under OMS-ETC, we use some fraction of the sample budget to explore randomly, using the collected data to estimate the model parameters. We then exploit the current estimated model, collecting the remaining samples according to the fraction expected to minimize our estimator’s asymptotic variance. In OMS-ETG, we continue to update our parameter estimates after every step as we collect new data. We prove that both policies achieve zero asymptotic regret. To overcome the non-i.i.d. nature of the sample moments, we draw upon martingale theory. To derive zero asymptotic regret, we show uniform concentration of sample moments and a finite-sample concentration inequality for the GMM estimator with dependent data. Next, we adapt OMS-ETC and OMS-ETG to handle heterogeneous costs over the data sources (Section 5) and prove that they still have zero asymptotic regret.
Finally, we validate our findings experimentally 1 (Section 6). Motivated by ATE estimation in causal models encoded as directed acyclic graphs, we generate synthetic data from a variety of causal graphs and show that the regret of our proposed methods converges to zero. Furthermore, we see that despite being asymptotically equivalent, OMS-ETG outperforms OMS-ETC in finite samples. Finally, we demonstrate the effectiveness of our methods on two semi-synthetic datasets: the Infant Health Development Program (IHDP) dataset [19] and a Vietnam era draft lottery dataset [2].

heading: 2 Related Work
text: Many works attempt to identify and estimate causal effects from multiple datasets. [4, 21] study the problem of combining multiple heterogeneous datasets and propose methods for dealing with various biases. Other works study causal identification when observational and interventional distributions involving different sets of variables are available [28, 40]. [12] introduce estimators of the ATE that efficiently combine two datasets, one where confounders are observed (enabling the backdoor adjustment) and another where mediators are observed (enabling the frontdoor adjustment). [29] derive an estimator for the ATE in linear causal models with multiple confounders, where the confounders are observed in different datasets.
Another related line of work addresses finding optimal adjustment sets for covariate adjustment [18, 33, 45, 36]. While these works take for granted the collection of available datasets, we focus on the problem of deciding which data to collect. Our work shares motivation with active learning, where the learner strategically chooses which (unlabeled) samples to label in order to learn most efficiently [35, 26]. [8] design algorithms for actively collecting samples in a manner that minimizes the learner’s variance. In settings where there is a cost associated with collecting each feature, active feature acquisition methods incrementally query feature values to improve a predictive model [22, 34, 20]. [47] propose an active learning criterion to find the most informative questions to ask each respondent in a survey. In the context of causal inference, [37] study active structure learning of causal DAGs by finding cost-optimal interventions, [11] demonstrate that for ATE estimation, actively deconfounding data can improve sample complexity. [44] propose strategies for acquiring missing confounders to efficiently estimate the ATE.
1The code and data are available at https://www.github.com/acmi-lab/ online-moment-selection.
Others have studied moment selection and IV selection from batch data. [1] introduce consistent moment selection procedures for the GMM setting with some incorrect moments. [6] propose an information-based lasso method for excluding invalid or redundant moment conditions. [41] propose a variable selection framework that uses lasso regression to decide which covariates to include. [14] propose four statistical criteria—including estimation efficiency and non-redundancy—for selecting among a set of candidate IVs. [9] develop an IV selection criteria based on asymptotic MSE and develop it for the GMM and generalized empirical likelihood estimators. [7] develop conservative confidence intervals for structural parameters when the off-diagonal entries of the covariance matrix of the empirical moments are unknown (e.g., when the moments are obtained from different datasets). By contrast, we are interested in selecting the data sources for the moments in an online setting.
Previous works address learning from adaptively collected data. [25] propose methods for adaptive experimental design, where at each step, the experimenter must decide the treatment probability using past data in order to efficiently estimate the ATE. [23, 24] propose a doubly-robust estimator for off-policy evaluation with dependent samples. [46] provide regret bounds for learning an optimal policy using adaptively collected data, where the probability of selecting an action is a function of past data. [48, 49] study statistical inference for OLS and M-estimation with non-i.i.d. bandit data. While these settings are different from ours, some of the theoretical tools (e.g., martingale asymptotics and uniform martingale concentration bounds) are similar.

heading: 3 Preliminaries
text: In the GMM framework [17, 30], we estimate model parameters by leveraging moment conditions that are satisfied at the true parameters θ∗. A moment condition is a vector g(Xt, θ) such that E[g(Xt, θ ∗)] = 0. We estimate θ∗ by minimizing the objective Q̂T :
θ̂T = arg min θ∈Θ Q̂T (θ), where Q̂T (θ) =
[ 1
T T∑ t=1 gt(θ)
]> Ŵ [ 1
T T∑ t=1 gt(θ)
] ,
Θ is the parameter space, gt(θ) := g(Xt, θ), and Ŵ is some (possibly data dependent) positive definite matrix. In this work, we use the two-step GMM estimator, where the one-step estimator θ̂(os)T is computed with Ŵ := I (identity) and the two-step estimator with Ŵ := [ Ω̂T (θ̂ (os) T ) ]−1 , where
Ω̂T (θ) = [ 1 T ∑T t=1 gt(θ)gt(θ) > ] .
Let V be the set of variables of interest and ψ a collection of subsets of V, each corresponding to the specific variables observable via one of the available data sources. Our methods are applicable whenever the target parameter can be identified by a set of moment conditions such that each moment relies on variables simultaneously observable in at least one data source. The selection vector, denoted by st ∈ {0, 1}|ψ|, is the binary vector indicating the data source selected at time t. Assumption 1. The agent queries one data source at each step: ∑|ψ| i=1 st,i = 1, i.e., st is one-hot.
We can handle the querying of multiple sources by adding the union of their variables to ψ. In our setup, the moment conditions can be written as gt(θ) = m(st)⊗ g̃t(θ) ∈ RM , where ⊗ is the Hadamard product, m : {0, 1}|ψ| → {0, 1}M is a fixed known function such that m(st) determines which moments get selected, and g̃t(θ) are i.i.d. across t. For concreteness, we instantiate our setup with a simple example: Example 1 (Instrumental Variable (IV) graph). Consider a linear IV causal model (Figure 2a) with instrument Z, treatment X , outcome Y , and the following data-generating process:
X := αZ + η, Y := βX + , 6⊥⊥ η, ⊥⊥ Z, η ⊥⊥ Z. The target parameter is the ATE β. For ψ = {{Z,X}, {Z, Y }}, the moment conditions are
gt(θ) = [ st,1 st,2 ] ︸ ︷︷ ︸ =m(st) ⊗ [ Zt(Xt − αZt) Zt(Yt − αβZt) ] ︸ ︷︷ ︸ =g̃t(θ) = [ st,1Zt(Xt − αZt) (1− st,1)Zt(Yt − αβZt) ] ,
where θ = [β, α]> and {Zt, Xt, Yt} are i.i.d.
For some known function ftar : Θ→ R, let β∗ := ftar(θ∗) be the target parameter (e.g., the ATE). In practice, we estimate the target parameter by plugging-in the GMM estimate: β̂ = ftar(θ̂). Let Ht represent the history or the data collected until time t with H0 = {} and spaceHt. A data collection policy π consists of a sequence of functions πt : Ht−1 → {0, 1}|ψ| with st = πt(Ht−1). Thus st can be dependent on data collected until time (t− 1) and so the sample moments gt(θ) are not i.i.d. Definition 1 (Selection ratio). The selection ratio, denoted by κ(π)t , encodes the fraction of samples collected from each data source until time t: κ(π)t = 1 t ∑t i=1 st ∈ ∆|ψ|−1 (standard simplex).
We use θ̂(π)t and θ̂ (os) t to denote the two-step and one-step GMM estimators, respectively, that use the data Ht. To reduce clutter, we use ∆ψ := ∆|ψ|−1, ctr (∆ψ) = [ 1 |ψ| , 1 |ψ| , . . . , 1 |ψ| ] (center of the
simplex), and might drop the superscript π from κt, θ̂t, and β̂t. ‖.‖ denotes the spectral and l2 norms for matrices and vectors, respectively, and N (θ) := {θ′ : ‖θ′ − θ‖ ≤ } ( -ball around θ).

heading: 4 Adaptive Data Collection
text: The central challenge in this work is to make strategic decisions about which data to observe so that we most efficiently estimate the target functional. In this section, we present three policies: (i) fixed: query the data sources according to a pre-specified ratio; (ii) OMS-ETC: query uniformly for a specified exploration period, estimate the optimal ratio based on the inferred parameters and thereafter aim for that ratio; and (iii) OMS-ETG: same as OMS-ETC but continue to update parameter (and thus oracle ratio) estimates after the exploration period. For now, we analyze these policies for the case when the cost to query is identical across data sources. By T ∈ N, we denote the (known) horizon, which can be thought of as the agent’s data acquisition budget. We defer all proofs to Appendix A.
We now present sufficient conditions for consistency and asymptotic normality of the GMM estimator under adaptively collected data. We later use these results to derive the regret of our policies. Assumption 2. (a) (Identification) ∀θ 6= θ∗,P ( lim infT→∞ Q̄(θ) > 0 ) = 1, where Q̄(θ) =
g∗T (θ)Ŵg ∗ T (θ) > and g∗T (θ) = [ 1 T ∑T t=1m(st)⊗E [g̃t(θ)] ] ; (b) Θ ⊂ RD is compact; (c) ∀θ, g̃i(θ) is twice continuously differentiable (c.d.); (d) ∀θ,E[g̃i(θ)] is continuous; and (e) ftar is c.d. at θ∗.
By Assumption 2(a), the GMM objective is uniquely minimized at θ∗. Informally, this means that each moment is (asymptotically) collected enough times to allow identification. If M = D (justidentified case), this holds when (i) an asymptotically non-negligible fraction of every moment is collected: ∀j ∈ [M ], P ( lim infT→∞ 1 T ∑T t=1mj(st) 6= 0 ) = 1; and (ii) ∀θ 6= θ∗, E [g̃t(θ)] 6= 0.
Property 1 (ULLN). Let ai(θ) := a(Xi; θ) ∈ R be a continuous function with Xi sampled i.i.d. We say that ai(θ) satisfies the ULLN property if (i) ∀θ, E [ ai(θ) 2 ] < ∞; (ii) ai(θ) is dominated by a function A(Xi): ∀θ, |ai(θ)| ≤ A(Xi); and (iii) E[A(Xi)] <∞. Proposition 1 (Consistency). Suppose that (i) Assumption 2 holds, (ii) ∀j ∈ [M ], g̃t,j(θ) satisfies Property 1, and (iii) ∀(i, j) ∈ [M ]2, [ g̃t(θ)g̃t(θ) >] i,j satisfies Property 1; Then, θ̂(π)T p−−−−→ T→∞ θ∗.
Proposition 2 (Asymptotic normality). Suppose that (i) θ̂(π)T p−→ θ∗; (ii) ∀(i, j) ∈ [M ] × [D], [ ∂g̃t ∂θ (θ) ] i,j satisfies Property 1; (iii) ∃δ > 0 such thatE [ ‖g̃i(θ∗)‖2+δ ] < ∞, and (iv) (Selection ratio convergence) κ(π)T p→ k for some constant k ∈ ∆ψ . Then θ̂T is asymptotically normal: √ T (θ̂
(π) T − θ ∗) d→ N (0,Σ(θ∗, k)) ,
where Σ(θ∗, k) is a constant matrix that depends only on θ∗ and k (see Appendix A.2 for the complete expression). By Assumption 2(e) and the Delta method, β̂T is asymptotically normal:
√ T (β̂T − β∗) d→ N (0, V (θ∗, k)) , whereV (θ∗, k) = ∇θftar(θ∗)>[Σ(θ∗, k)]∇θftar(θ∗).
Proposition 2 shows that for a policy under which the selection ratio κT converges in probability to a constant, the GMM estimator θ̂T can be asymptotically normal. The specific order in which the data sources are queried does not affect asymptotic normality as long the selection ratio κ(π)T converges.
Input: T ∈ N, e ∈ (0, 1) 1 n = bTec; 2 Collect n samples s.t. κn = ctr (∆ψ); 3 θ̂n = GMM(Hn); 4 k̂ = arg minκ∈∆ψ V (θ̂n, κ); 5 Collect remaining samples such that
κT = proj(k̂, ∆̃); 6 θ̂T = GMM(HT );
Output: ftar(θ̂T )
(a) The Explore-then-Commit policy.
Input: T ∈ N, s ∈ (0, 1) 1 k̂ = ctr (∆ψ); 2 J = 1s ; 3 for j ∈ [1, 2, . . . , J ] do 4 t = bTsjc; 5 Collect bTsc samples s.t. κt = k̂; 6 θ̂t = GMM(Ht, Ŵ = Ŵvalid); 7 k̂t = arg minκ∈∆ψ V (θ̂t, κ); 8 k̂ = proj(k̂t, ∆̃j+1(κt)); 9 end
10 θ̂T = GMM(HT , Ŵ = Ŵefficient); Output: ftar(θ̂T )
(b) The Explore-then-Greedy policy.
Figure 1: Algorithms for OMS-ETC and OMS-ETG.
A fixed (or non-adaptive) policy, denoted by πk, has κT = k for some constant k ∈ ∆ψ. Here, the collection decisions do not depend on the data and each data source is queried a fixed fraction of the time. By Proposition 2, θ̂(πk)T is asymptotically normal. The oracle policy, denoted by π
∗, is the fixed policy with the lowest asymptotic variance. Thus for π∗, we have κ(π
∗) T = κ
∗, where κ∗ = arg minκ V (θ
∗, κ). We call κ∗ the oracle selection ratio. For the oracle policy, we have√ T (β̂
(π∗) T − β) d→ N (0, V (θ∗, κ∗)). The following assumption ensures that κ∗ is unique and consequently the data collection decisions are meaningful. Assumption 3. κ∗ uniquely minimizes V (θ∗, κ): ∀κ ∈ ∆ψ s.t.κ 6= κ∗, V (θ∗, κ) > V (θ∗, κ∗). Definition 2 (Asymptotic regret). The asymptotic regret captures how close the scaled asymptotic error of a given policy is to the oracle policy. We define the asymptotic regret of a policy π as
R∞(π) = AMSE (√ T ( β̂ (π) T − β ∗ )) − V (θ∗, κ∗), (1)
where AMSE is the asymptotic MSE (i.e., the MSE of the limiting distribution).
For any fixed policy πk such that κ (πk) T = k for some constant k 6= κ∗, we have R∞(πk) = [V (θ∗, k)− V (θ∗, κ∗)] > 0 (by Assumption 3). This shows that a fixed policy suffers constant regret. This motivates the design of adaptive policies, where the regret asymptotically converges to zero.

heading: 4.1 Online Moment Selection via Explore-then-Commit (OMS-ETC)
text: OMS-ETC is inspired by the ETC strategy for multi-armed bandits (MABs) [27, Chapter 6]. Under OMS-ETC, we first explore by collecting a fixed number of samples for each choice. Then, we use these samples to estimate the oracle selection ratio κ∗. Finally, we commit to this ratio for the remaining time steps. We denote the OMS-ETC policy by πETC (Figure 1a).
The policy πETC is characterized by an exploration fraction e ∈ (0, 1). We first collect Te samples by querying each data source equally so that κTe = ctr (∆ψ). We then estimate θ̂Te and obtain the plugin estimate of κ∗ as k̂ = arg minκ∈∆ψ V (θ̂Te, κ). The feasible region for κT is defined as the set of values that κT can take after we have devoted Te samples to exploration and is given by ∆̃ = {eκTe + (1− e)κ : κ ∈ ∆ψ} (proof in Appendix C). We collect the remaining T (1−e) samples such that κT is as close to k̂ as possible: κT = proj(k̂, ∆̃), where proj ( k, ∆̃ ) = arg mink′∈∆̃ ‖k − k′‖.
Remark. The feasible region shrinks as e increases because, as e increases, the T (1− e) samples that remain after exploration decrease thereby shrinking the possible values that κT can take.
Theorem 1 (Regret of OMS-ETC). Suppose that (i) Conditions (i)-(iii) of Proposition 2 hold and (ii) Assumption 3 holds. Case (a): For a fixed e ∈ (0, 1), if κ∗ ∈ ∆̃, then the regret converges to zero:
R∞(πETC) = 0. If κ∗ /∈ ∆̃, then πETC suffers constant regret: R∞(πETC) = r for some constant r > 0. Case (b): If e depends on T such that e = o(1) and Te→∞ as T →∞ (e.g. e = 1√
T ), then
∀θ∗ ∈ Θ, we have R∞(πETC) = 0.
The theorem provides sufficient conditions for when the regret converges to zero. Case (a) of the theorem shows that if we explore for a fixed fraction of the horizon T , the regret will only converge to zero if κ∗ is inside the feasible region. Thus the regret will not converge to zero over the entire parameter space Θ as there would be certain parameter values for which κ∗ would be outside the feasible region. Case (b) shows that we can achieve zero asymptotic regret for every θ∗ ∈ Θ by setting e such that it becomes asymptotically negligible (e ∈ o(1)). The main idea in the proof (see Appendix A.3) is to show that κT
p→ κ∗ and apply Proposition 2. In Case (b), the feasible region ∆̃ asymptotically covers the entire simplex (∆̃ T→∞−−−−→ ∆ψ) and this is sufficient to show that κT p→ κ∗.

heading: 4.2 Online Moment Selection via Explore-then-Greedy (OMS-ETG)
text: We extend OMS-ETC by periodically updating our estimate of κ∗ as we collect additional samples instead of committing to a value after exploration. The data is collected in batches. OMS-ETG (Figure 1b) is characterized by a batch fraction s ∈ (0, 1). The algorithm runs for J = 1s rounds and we collect b = Ts samples in each round. In the first round, we explore and thus κb = ctr (∆ψ). After every round j ∈ [J − 1], we estimate θ̂bj and the oracle selection ratio: k̂bj = arg minκ∈∆ψ V (θ̂bj , κ). The feasible region for round j + 1 (the set of values of κb(j+1) can take) is
∆̃j+1(κbj) = { jκbj+κ j+1 : κ ∈ ∆ψ } (proof in Appendix C). In round (j + 1), we (greedily) collect
samples such that κb(j+1) is as close to k̂j+1 as possible: κb(j+1) = proj ( k̂j , ∆̃j+1(κbj) ) .
Theorem 2 states sufficient conditions for when OMS-ETG has zero regret. We first state a finitesample tail bound for the two-step GMM estimator under adaptively collected (non-i.i.d.) data in Lemma 1 (which might be of independent interest) and use it to prove the theorem. Property 2 (Concentration). Let ãi(θ) := ã(Xi; θ) ∈ R with Xi sampled i.i.d., ã∗(θ) = E [ã(Xi; θ)], A(Xi, θ) = ∂ã(Xi;θ) ∂θ , ui(η) = supθ,θ′∈Θ,‖θ−θ′‖≤η |ãi(θ)− ãi(θ
′)|, and u∗(η) = E [ui(η)]. Let L1, η0, and A0 be some positive constants. We say that ãi(θ) satisfies the Concentration property if (i) ã∗(θ) is L1-Lipschitz, (ii) ∀θ ∈ Θ, [ãi(θ)− ã∗(θ)] is sub-Exponential, (iii) E [‖A(Xi, θ)‖] < A0 < ∞, and (iv) one of the following two conditions hold: (a) ∀η ∈ (0, η0), [ui(η)− u∗(η)] is sub-Exponential, or (b) supθ∈Θ ‖A(Xi, θ)‖ is sub-Exponential. Remark. Property 2 is used to derive a uniform law (see Lemma 4) that is used to prove Lemma 1. Property 2(iv) might be hard to check but (iv)(a) is satisfied for bounded function classes, i.e., when ‖ãi‖∞ < A <∞ (see Proposition 9) and (iv)(b) for linear function classes with sub-Exponential data (see Proposition 10). For the linear IV model in Example 1, Property 2(iv) would hold if Z2i is sub-Exponential (e.g., when Zi is sub-Gaussian). Lemma 1 (GMM concentration inequality). Let λ∗, C0, η1, η2, and δ0 be some positive constants. Suppose that (i) Assumption 2 holds; (ii) ∀j, g̃i,j(θ) satisfies Property 2; (iii) The spectral norm of the GMM weight matrix Ŵ is upper bounded with high probability: ∀δ ∈ (0, C0) , P ( ‖Ŵ‖ ≤ λ∗ ) ≥ 1 − 1
δD exp
{ −O ( Tδ2 )} (see Remark 1); (iv) (Local strict con-
vexity) ∀θ ∈ Nη1(θ∗), P (∥∥∥∂2Q̄∂θ2 (θ)−1∥∥∥ ≤ h) = 1 (Q̄(θ) is defined in Assumption 2a); (v) (Strict minimization) ∀θ ∈ Nη2(θ∗), there is a unique minimizer κ(θ) = arg minκ V (θ, κ) s.t. V (θ, κ)−V (θ, κ(θ)) ≤ cδ2 =⇒ ‖κ−κ(θ)‖ ≤ δ; and (vi) supκ |V (θ, κ)−V (θ′, κ)| ≤ L‖θ−θ′‖. Then, for k̂t = arg minκ∈∆ψ V (θ̂ (π) T , κ), any policy π, and ∀δ ∈ (0, δ0),
P (∥∥∥θ̂(π)T − θ∗∥∥∥ > δ) < 1δ2D exp{−O (Tδ4)} and P(∥∥∥k̂T − κ∗∥∥∥ > δ) < 1δ4D exp{−O (Tδ8)} .
Better rates for k̂T are applicable under additional restrictions on θ∗ (see Lemma 6).
To derive the tail bound for θ̂T , we first prove that the minimized empirical GMM objective is close to Q̄(θ∗) with high probability (w.h.p.) (using Conditions (i)-(iii)). Then we show that θ̂T is close to
θ∗ w.h.p. (using Condition (iv)). Next, we use the inequality for θ̂T to derive the tail bound for k̂. For this, we show that V (θ∗, k̂) is close to V (θ∗, κ∗) (using Condition (vi)) and then show that k̂ is close to κ∗ w.h.p. (using Condition (v)).
Theorem 2 (Regret of OMS-ETG). Suppose that Conditions (i)-(iv) of Proposition 2 hold. Let ∆̃(s) = {sκb + (1− s)κ : κ ∈ ∆ψ}. Case (a): For a fixed s ∈ (0, 1), if the oracle selection ratio κ∗ ∈ ∆̃(s), then the regret converges to zero: R∞(πETG) = 0. If κ∗ /∈ ∆̃(s), then R∞(πETG) > 0 (non-zero regret). Case (b): Now also suppose that the conditions for Lemma 1 hold. If s = CT η−1 for some constant C and any η ∈ [0, 1), then ∀θ∗ ∈ Θ, R∞(πETG) = 0.
Similar to OMS-ETC, Case (a) of the theorem shows that if the batch size is a constant fixed fraction, some values of κ∗ will be outside the feasible region and thus we do not get zero regret over the entire parameter space. Case (b) shows that to get zero asymptotic regret for every θ∗ ∈ Θ, s must depend on T and be asymptotically negligible. But unlike OMS-ETC, the estimate of κ∗ is updated after every round. The batch fraction s can be as small as CT−1 allowing the agent to collect a constant number of samples in each batch.
We prove the theorem by showing that κT p→ κ∗ and applying Proposition 2. To do so for Case (b), we show that the estimated oracle ratio after every round is close to κ∗, i.e., ∀ > 0, P ( ∀j ∈ [J − 1], k̂bj ∈ N (κ∗) ) −−−−→ T→∞ 1 (by using Lemma 1). Since we move as close as possible to k̂bj after every round, this ensures that ∀ > 0, P (κT ∈ N (κ∗))→ 1 (and thus κT p→ κ∗).
Both OMS-ETC and OMS-ETG are asymptotically equivalent as they can achieve zero regret for every θ∗ ∈ Θ. But our experiments show that OMS-ETG outperforms OMS-ETC (in terms of regret) for small sample sizes. This may be because with OMS-ETG, the estimate of κ∗ keeps improving as more samples are collected instead of being fixed after exploration. This suggests that better estimates of κ∗ may lead to higher-order reductions in MSE.
Remark 1 (Weight matrix Ŵ ). For OMS-ETG, the GMM weight matrix Ŵ needs to satisfy Condition (iii) of Lemma 1 till round (J − 1). We denote this matrix by Ŵvalid in Figure 1b. For the final step of OMS-ETG, we use the standard efficient two-step GMM weight matrix (denoted by Ŵefficient in Figure 1b) and thus the final estimate of θ∗ is still asymptotically efficient. Condition (iii) of
Lemma 1 would hold for the efficient two-step GMM weight matrix (i.e., for Ŵ := [ Ω̂T (θ̂ (os) T ) ]−1 ) if ∀(j, k), [g̃i,j(θ)g̃i,k(θ)] satisfies Property 2 (see Lemma 5 for proof). This would hold if the moments g̃i,j(θ) are uniformly bounded. Condition (iii) can also be satisfied with a regularized weight matrix:
Ŵ := [ Ω̂T (θ̂ (os) T ) + λW I ]−1 for some λW > 0 as this ensures that ‖Ŵ‖ ≤ λ−1W .
Additional exploration. MAB algorithms usually require additional exploration to perform well (e.g., -greedy and upper confidence bound strategies [27, Chapter 7]). However, we empirically noticed that additional exploration hurts performance in our setup. This might be because unlike typical bandit setups where pulling one arm does not improve the estimates of another arm, querying any data source can improve the estimates of the model parameter θ∗ in our setup.

heading: 5 Incorporating a Cost Structure
text: In many real-world settings, the agent has a budget constraint and must pay a different cost to query each data source. We adapt OMS-ETC and OMS-ETG to this setting where a cost structure is associated with the data sources in ψ. We prove that these policies still have zero asymptotic regret for every θ∗ ∈ Θ. Let (ψi)i∈[|ψ|] be an indexed family. We denote the (known) budget by B ∈ N and by c ∈ R|ψ|>0, a cost vector such that ci is the cost of querying data source ψi. Due to the cost structure, the horizon T is a random variable dependent on π with T = ⌊ B κ>T c ⌋ . The setting in Section 4 is a special case of this formulation when ∀i, ci = 1 and B = T . We defer proofs to Appendix B.
For a fixed policy πk, we have κ (πk) T = k, for some constant k ∈ ∆ψ. By Proposition 2, as B →∞, we have √ B ( β̂
(πk) T − β∗
) d−→ N ( 0, V (θ∗, k) ( k>c )) . Here we scale by √ B instead of
√ T to make comparisons across policies meaningful. The oracle selection ratio is now defined as κ∗ = arg minκ∈∆ψ [ V (θ∗, κ) ( κ>c )] and the asymptotic regret of policy π now is
R∞(π) = AMSE (√ B ( β̂ (π) T − β ∗ )) − V (θ∗, κ∗) ( (κ∗)>c ) .
OMS-ETC-CS (OMS-ETC with cost structure) is an adaptation of OMS-ETC for this setting. We use Be budget to explore and estimate κ∗ by k̂ = arg minκ∈∆ψ [ V (θ̂Te , κ) ( κ>c )] , where Te = ⌊ eB κ>Tec ⌋ and κTe = ctr (∆ψ). Exploration strategies that utilize the cost structure can also be used (e.g., evenly dividing the budget across data sources while exploring). With the remaining budget, we collect samples such that κT = proj ( k̂, ∆̃ ) , where ∆̃ is the feasibility region (expression given in
Appendix C). The following proposition shows that OMS-ETC-CS can achieve zero regret. Proposition 3 (Regret of OMS-ETC-CS). Suppose that the conditions of Theorem 1 hold. If e = o(1) such that Be→∞ as B →∞, then ∀θ∗ ∈ Θ, R∞(πETC-CS) = 0.
We propose two ways of adapting OMS-ETG to this setting: (i) OMS-ETG-FS (OMS-ETG with fixed samples) where we collect a fixed number of samples in every round and (ii) OMS-ETG-FB (OMS-ETG with fixed budget) where we spend a fixed fraction of the budget in every round.
Let cmax = maxi∈[|ψ|] ci and cmin = mini∈[|ψ|] ci. In OMS-ETC-FS (Figure 6a), we collect b = ⌊ Bs cmax ⌋ samples in every round except the last one (the last batch can be smaller as we may not have enough budget left for a full batch). The number of rounds J is random since, in every round, depending on what we collect, we use up a different amount of the budget. Like OMS-ETG, after each round, we estimate κ∗ and greedily collect samples to get as close to it as possible.
In OMS-ETG-FB (Figure 6b), we spend Bs budget in each round. Thus the number of rounds J is fixed with J = 1s but the number of samples collected per round is now random. Like OMS-ETG, after each round, we estimate κ∗ and collect samples to get as close to the estimate as possible. The next two Propositions show that both OMS-ETG-FS and OMS-ETC-FB have zero asymptotic regret. Proposition 4 (Regret of OMS-ETG-FS). Suppose that the conditions of Theorem 2b hold. If s = Bη−1 for any η ∈ [0, 1), then ∀θ∗ ∈ Θ, R∞ (πETG-FS) = 0. Proposition 5 (Regret of OMS-ETG-FB). Suppose that the conditions of Theorem 2b hold. If s = Bη−1 for any η ∈ [0, 1), then ∀θ∗ ∈ Θ, R∞ (πETG-FB) = 0.

heading: 6 Experiments

heading: 6.1 Synthetic data
text: We validate our methods on synthetic data generated from known causal graphs (see Appendix D for parameter values and moment conditions used). In our experiments (including the ones in Section 6.2), for OMS-ETG, we use the regularized GMM weight matrix with λW := 0.01 (see Remark 1). The regret is only minimally affected with an unregularized matrix (λW := 0) despite theoretical guarantees only holding for the regularized case (the maximum change in regret was 1.98%) and thus our conclusions do not change. We first simulate data from a linear IV graph (Figure 2a) and compare the performance of different polices (Figure 3a). We use ψ = {{Z,X}, {Z, Y }} and assume that both sources cost the same. We set parameter values such that κ∗ ≈ [0.36, 0.64]>. We compare policies based on relative regret (RR) with respect to the oracle policy:
Relative regret = RR(π) = MSE(π) −MSE(oracle)
MSE(oracle) × 100%.
The MSE values are computed across 12, 000 runs. The label etc_{x} in the plot refers to OMSETC with exploration fraction e = x (e.g., etc_0.1 means e = 10%). Similarly, etg_{x} refers to OMS-ETG with s = x. We see that as the horizon increases, the RR of all policies converges to zero. This supports the claim that both OMS-ETC and OMS-ETG have zero asymptotic regret. However, when the horizon is small (T = 300), both etc_0.1 and etc_0.2 perform poorly due to insufficient exploration. In contrast, OMS-ETG has close to zero RR even for small horizons which shows that repeatedly improving the parameter estimates can lead to faster convergence of regret.
Next, we simulate data from a linear graph with two IVs (Figure 2b). Here ψ = {{X,Y, Z1}, {X,Y, Z2}} and both choices cost the same. We set the parameters such that κ∗ = [0, 1]> (κ∗ is on the corner of the simplex). We compare the RR across various horizons (Figure 3b). We see the OMS-ETC performs worse than OMS-ETG for small horizons. One difference from the previous case (Figure 3a) is that etc_0.4 performs poorly even for large horizons. This is because after using 40% of the samples for exploration, the feasibility region is not large enough to get close to the corner of the simplex. This demonstrates another benefit of OMS-ETG over OMS-ETC: OMS-ETG can achieve close to zero regret in finite samples when the oracle ratio κ∗ is either on the boundary or in the interior of the simplex.
Finally, we simulate data from a linear confounder-mediator graph (Figure 2c). Here, both the backdoor (using {X,Y,W}) and frontdoor (using {X,Y,M}) adjustments are applicable [31, Section 3.3]. We use ψ = {{X,Y,W}, {X,Y,M}} with cost structure c = [1.8, 1]> (confounders W cost more than the mediators M ). We set the parameters such that κ∗ ≈ [0.15, 0.85]>. We see similar conclusions as the previous cases. OMS-ETC with low exploration performs poorly but converges for large horizons. Both OMS-ETG variants—OMS-ETG-FS and OMS-ETG-FB—have close to zero RR for all horizons. We see no significant difference between the regret of OMS-ETG-FS and OMS-ETG-FB. The policy fixed_equal is a fixed policy that collects an equal fraction of both subsets. Its RR does not converge and is substantially higher than the oracle (≈ 20%). This demonstrates that adaptive policies can lead to significant gains in MSE over fixed policies and that our methods remain applicable even with an associated cost structure on the data sources.

heading: 6.2 Semi-synthetic data
text: IHDP. Hill [19] constructed a dataset based on the Infant Health and Development Program (IHDP). The data [10] is from a randomized experiment studying the effect of home visits by a trained provider on future cognitive test scores of children. Following Hill [19], we create an observational dataset by removing a non-random subset of the data. The treatment X is binary. The dataset contains pre-treatment covariates which are measurements on the mother and the child. For simplicity, we only use two covariates: birth weight (continuous) (W1) and whether the mother smoked (binary) (W2). For each sample of the generated semi-synthetic data, (X,W1,W2) are sampled uniformly at random from the real data. The outcome Y (continuous) is simulated: Y := α1W1 + α2W2 + βX + y,
where y ∼ N (0, σ2y), α1, α2, β ∈ R, and σ2y ∈ R+ (see Figure 4a). Here α1, α2, β, and σy are model parameters with β being the ATE (target parameter).
For this experiment, we use ψ = {{X,Y,W1}, {X,Y,W2}, {X,Y,W1,W2}} with cost structure c = [1, 3, 3.5]>. Thus, at each step, the agent can collect either one of the covariates or both of them, and each choice has a distinct cost. Setting model parameters such that κ∗ ≈ [0.59, 0, 0.41]>, we compare performance across policies for various total budgets (Figure 4b). The policy collect_all is a fixed policy that collects {X,Y,W1,W2} at every step. This policy has higher RR (≈ 50% higher MSE than the oracle) for all budgets demonstrating that collecting all covariates for every sample can be sub-optimal. The policy etc_0.2 does poorly with a small budget whereas etc_0.4 has close to zero RR. Both OMS-ETG-FB and OMS-ETG-FS have close to zero RR for all horizons.
The Vietnam draft and future earnings. Angrist [2] computed the effect of veteran status on future earnings from the Vietnam draft lottery data [3] using an IV (Figure 2a). The IV Z (binary) indicates whether an individual was eligible for the draft based on a random lottery. The treatment X (binary) indicates whether they actually served. The outcome Y (continuous) represents their future earnings. The IV removes bias caused by certain types of men being more likely to serve. In this dataset, {Z,X} and {Z, Y } were collected using different data sources (thus {Z,X, Y } are not observed simultaneously) , which suits our framework. We construct a semi-synthetic dataset that closely matches the real data so that we know the ground-truth causal effect (needed to compute the MSE). For each instance, we sample Z uniformly at random from the empirical distribution. X is sampled from the Bernoulli distribution P̂(X|Z) with conditional probabilities given by the empirical distribution (values taken from [2, Table 2]). We generate the outcome as Y := βX+γ+ , where ∼ N (0, σ2 ) and 6⊥⊥ X . The parameters β, γ, and σ2 are set such that the distribution of (Z, Y ) is close to the real data (see Appendix D.5 for details). We compare the RR of our policies on this dataset (Figure 4c). Most adaptive policies converge to near zero RR as the horizon gets large. OMS-ETC does poorly with low exploration while OMS-ETG policies have significantly lower RR for smaller horizons. By contrast, fixed_equal (the fixed policy that queries both data sources equally) suffers constant regret and has ≈ 25% higher regret than the oracle even for large horizons. This demonstrates that adaptive policies can lead to substantial MSE gains in a real-world setting.

heading: 7 Conclusion
text: This paper takes some initial strides towards endogenizing decisions about which variables to solicit into the modeling process. Addressing the problem of deciding, sequentially, which data sources to query in order to efficiently estimate a parameter, we developed the online moment selection (OMS) framework and two instantiations: OMS-ETC and OMS-ETG. We prove that over the entire parameter space, adaptive data collection with either method can provide substantial MSE gains. While our work focuses on ATE estimation, our framework is more broadly applicable to any parameter identified by moment conditions. In future work, we hope to apply our framework to more general prediction problems, addressing practical considerations including high-dimensional data and complex model classes (e.g., neural networks). Moreover, in real-world settings, common assumptions like ignorability rarely hold. We hope to extend our framework to overcome issues such as model misspecification, or to overcome biases present in some, but not all data sources.

Review summaries:
Given multiple data sources, each related to a subset of variables, authors study the problem of deciding which data source to sample from at each time step. Then, by using the samples, the goal is to estimate the model parameters as good as possible. The proposed framework is based on the generalized method of moments. Their contributions are as follows:  1. In Section 4, it is assumed that each instance has the same cost across all data sources. Then, authors first show that any fixed policy that differs from the optimal one will attain a constant asymptotic regret. To overcome this issue, two adaptive methods are proposed OMS-ETC and OMS-ETG. Here, OMS-ETC resembles the classical explore-then-commit algorithm in the context of bandits, where there is an exploration step to estimate the model parameters and then the model commits to a data source that minimizes the asymptotic variance of the target parameter. In contrast, OMS-ETG keeps updating the model parameters as more data is gathered. Under certain conditions, authors show that both adaptive methods will attain a zero asymptotic regret.  2. In Section 5, both adaptive methods are modified as to attain zero regret in the case where instances have different costs across data sources.  3. Experiments are provided in Section 6, where authors depict the behavior of the regret for different causal DAGs. Semi-synthetic dataset are also provided to showcase the usability of their method.

The asymptotic property of GMM estimator is proposed by some previous papers. In this paper, from the theoretical aspect, the authors generalize that to the setting with multiple domains and apply the results in the online estimation of causal effects. They evaluate the regret under three online policies to select which dataset to observe. 

The paper proposes online moment selection (OMS), a framework in which structural assumptions are encoded as moment conditions. This algorithm allows users to actively acquire data (variables) given the very moments that identify the functional of interest. The paper shows that there is substantial empirical gains in doing so.

This paper proposes online moment selection, an approach for choosing which data sources to draw from in an online setting. The goal is estimation of causal effects, the structural causal model is encoded as moment conditions, and the data sources drawn from are chosen to minimize the variance of the estimate. Explore then commit and explore then greedy approaches are suggested and analyzed. A limitation is that the structural equations need to be parametric and have a clear noise term. Improvement is shown over simple fixed policy baselines.