Adaptive Instrument Design for Indirect Experiments

We thank the reviewer for their appreciation of the novelty of the proposed results, and also for their valuable time to provide constructive feedback regarding all aspects of the draft. Your feedback has helped us significantly improve the accessibility of the paper for a wider audience.

W2. The results are not reproducible: The experimental setting (e.g., the employed datasets) are not described, neither is code provided. Besides the reproducibility aspects, this also hinders understanding and interpretation of the presented figures and results.

Thank you for sharing the concern about reproducibility. We have uploaded the code under the supplementary material section. It contains the data-generating processes and the proposed algorithm. We will publicly release the code and expand Appendix I to include more experimental details.

W3. The paper does not employ the required format of citations in the text, i.e. reference number instead of author name + year.

We will update the reference style in the draft.

W4. The motivation could be much improved by elaborating more exactly where the method is relevant and providing a real-world case study.

Due to space constraints, we had presented the motivation concisely, but thank you for highlighting that further discussion on some real-world use cases would be helpful. Below we have mentioned three use cases across different fields of application:

Education: It is important for designing an education curriculum to estimate the effect of homework assignments, extra reading material, etc. on a student’s final performance [1]. However, as students cannot be forced to (not) do these, conducting an RCT becomes infeasible. Nonetheless, students can be encouraged via a multitude of different methods to participate in these exercises. These different forms of encouragement provide various instruments and choosing them strategically can enable sample efficient estimation of the desired treatment effect.

Healthcare: Similarly, for mobile gym applications, or remote patient monitoring settings [2], users retain the agency to decide whether they would like to follow the suggested at-home exercise or medical intervention, respectively. As we cannot perform random user assignment to a control/treatment group, RCTs cannot be performed. However, there is a variety of different messages and reminders (in terms of how to phrase the message, when to notify the patient, etc.) that serve as instruments. Being strategic about the choice of the instrument can enable sample efficient estimation of treatment effect.

Digital marketing: Many online digital platforms aim at estimating the impact of premier membership on both the company’s revenue and also on customer satisfaction. However, it is infeasible to randomly make users a member or not, thereby making RCTs inapplicable. Nonetheless, various forms of promotional offers, easier sign-up options, etc. serve as instruments to encourage customers to become members. Strategically personalizing these instruments for customers can enable sample-efficient treatment effect estimation. In our work (Figure 1), we consider one such case study using the publicly available TripAdvisor domain [3].

[1] Eren, Ozkan, and Daniel J. Henderson. "The impact of homework on student achievement." The Econometrics Journal 11, no. 2 (2008)

[2] Ferstad, J., Prahalad, P., Maahs, D. M., Fox, E., Johari, R., & Scheinker, D. (2022). 1009-P: “The Association between Patient Characteristics and the Efficacy of Remote Patient Monitoring and Messaging.” Diabetes, 71

[3] Syrgkanis, Vasilis, Victor Lei, Miruna Oprescu, Maggie Hei, Keith Battocchi, and Greg Lewis. "Machine learning estimation of heterogeneous treatment effects with instruments." Advances in Neural Information Processing Systems

Q1. Why is the MSE a good metric of choice? What is the benefit above other objectives (e.g., minimizing regret)?

That’s a great question! Our chosen metric is closely related to simple regret (that compares the final performance of the estimator to the ground truth). The proposed method DIA (Section 3.3) adapts the key ideas and aims to be optimal after each round of re-allocation, which is related to the cumulative regret as it aims to learn an estimator that is optimal not just at the end, but also after each re-allocation.

Q2. What would be the general form of the k-th order influence function?

Thank you for highlighting that some readers might benefit from the general form of higher-order influence functions. Writing an explicit form for a general $k$-th order can often be tedious, and computing it can be practically challenging. Discussion about higher-order influences for the single-stage estimators can be found in the works by Alaa et al. [1] and Robins et al. [2]. As we formally show in Property 3, for our purpose, we recommend using $k=1$ as it suffices to dramatically reduce the variance of the gradient estimator, incurring bias that decays quickly, while also being easy to compute.

[1] Alaa, Ahmed, and Mihaela Van Der Schaar. "Discriminative jackknife: Quantifying uncertainty in deep learning via higher-order influence functions." International Conference on Machine Learning. PMLR, 2020.

[2] Robins, James, et al. "Higher order influence functions and minimax estimation of nonlinear functionals." Probability and statistics: essays in honor of David A. Freedman. Vol. 2. Institute of Mathematical Statistics, 2008. 335-422.

Q3. What is meant by the perturbation of the distribution function induced by Dn? In which sense are the samples perturbed?

We will update the draft to emphasize that perturbing the distribution function (in the direction of a sample S) induced by Dn corresponds to up-weighting the moment conditions corresponding to the data sample S. A formal discussion of perturbed moment conditions, along with exact equations, are also available in Appendix C.

Q4. Why can the estimator theta(Dn) be considered symmetric? A short mathematical statement would benefit the flow of reading.

Thank you for helping us improve the flow of the paper. We assume an estimator $\theta(Dn)$ to be symmetric in its arguments as popular estimators do not treat data samples differently based on their index number in the dataset. For example, let $D_2=(S_1, S_2)$ and $D_2’=(S_2, S_1)$, then $\theta(D_2) = \theta(D_2’)$.

While it is possible to define contrived estimators that are not symmetric, (e.g., estimators that only use the first sample, and discard all other samples), we focus on popular estimators that are symmetric.

Q5. What is the formulation of the importance ratio on the entire data? (page 6 might be difficult to follow for non-expert readers).

We appreciate the reviewer’s feedback regarding accessibility. We will updated the draft to include the importance ratio formulation of the entire data.

$\nabla \mathcal L(\pi)= \underset{D_n \sim \beta} {\mathbb E}\left[\left(\prod_{i=1}^n \frac{\pi(Z_i|X_i)}{\beta(Z_i|X_i)}\right)\text{MSE}(\theta(D_n)) \sum\limits_{i=1}^n \frac{\partial \log \pi(Z_i|X_i)}{\partial \pi} \right]$

Q6. Similarly, a short introduction/theory of the acceptance-rejection method would be beneficial. I am not convinced that the average reader is familiar with the concept.

We are happy to add this. Due to space limitations, we will put it in Appendix F.

Q7. The authors mention the flexibility of their approach multiple times. Nevertheless, it is unclear what precisely is meant by flexibility/ which properties make the approach flexible.

Thank you for raising this issue. By flexible, we mean that DIA can be used with a variety of estimators (it is suitable for approaches that assume a linear structure and non-linear), and settings (unconditional IV where instruments do not depend on the context, or conditional IV, where they do). We describe this at the start of Section 5, but we will clarify this earlier, when we first discuss the flexibility of our proposed approach.

Q8. How does the performance of DIA-X for different X relate to the data generating mechanism? Can the optimal X be deducted from the data for the presented experiments?

Thank you for asking this question! We will add more details about the domain to clarify that X is not a variable that is being optimized, and hence there is no optimal X. Instead, X is a part of the domain specification. For instance, DIA-10 corresponds to the performance of using DIA when the domain has 10 instruments. Of course, given these 10 instruments, DIA needs to learn a sampling distribution over these instruments, conditioned on the context.

Q9. Figure 3: The funnel (standard dev.?) is only plotted for the IV-bias. Why is it not visible for the other cases or the variance plot?

Your careful observation is much appreciated. We will update Figure 3 to include the variance/std-err in the variance estimates itself as well.

Q10. TripAdvisor data: Why was it necessary to synthetically enhance the data? Could you also provide a comparison of the results of the method on the original real-world dataset and the enhanced semi-synthetic dataset? It would also be interesting for the reader if the authors could state the optimal instruments for the real-world dataset.

That’s an important point and we will include a discussion about this in the updated draft. As evident from Figures 1,5, and 7, adaptivity and learning the distribution of instruments are most relevant when there are a lot of instruments. Our paper is developed for the setting where online sampling is feasible. Unfortunately, simulators for real-world scenarios that we are aware of and could access publicly (e.g., TripAdvisor’s) only consider a single/binary instrument. These simulator domains are modeled to represent the setting where expert knowledge was used to find optimal instruments (e.g., better/easier sign-up strategy to make the membership process easier). However, in reality, there could be multiple ways to encourage membership (emails, notifications, sign-up bonuses, etc.) that can all serve as instruments. Adaptivity is more relevant in such a setting to discover an optimal strategy for instrument selection, while minimizing the need for expert knowledge. Therefore, given the above considerations, we created semi-synthetic domains with varying numbers of potential instruments to simulate such settings.

Background: The theoretical background/ problem setting of the paper is taken from reference 23. In contrast to the original work, the paper lacks motivation for and explanation of the specific problem setting.

We agree with the reviewer that having more motivation for the specific instrumental variable setting and method can potentially help some readers. Unfortunately, we were constrained by the page limit. Since the IV setting itself is already well established in prior literature, we chose to focus on the motivation regarding why strategic sampling of instruments is useful---that is the subject of our paper. We will revise the background to further emphasize and motivate our setting.

Control Variates: The choice of the control variate (section 3.1) should be justified mathematically (possibly in the appendix).

Thank you for raising this wasn’t clear– we did actually provide a formal justification of this (see Property 2 in Section 4 which states the proposed control variate-based gradient estimator is both unbiased and has lower variance: a formal proof is provided in the appendix under Theorem 4). We will update the paper to mention to the readers earlier, in Section 3.1 itself when we introduce the control variate.

Figure 4: According to the text, one should observe an exponentially increasing variance for IS in the number of samples. However, the figure does not support this statement.

We should have and will highlight that the naive importance sampling-based estimator can have variance exponential in the number of samples, in the worst case, though it may not always have exponential dependence in all domains. In practice, we observe that the variance is too large to do any meaningful gradient estimation. For instance, in Figure 4, the variance of the IS estimator is around 100000, whereas the variance of the proposed method is <10.

Experiments: The synthetic data generation is not properly described. Furthermore, no details on the networks employed for estimation are stated.

We agree more details would improve the paper – we have uploaded the code under supplementary material. The code contains details about data generation and the models used. We will also expand Appendix I to include more experimental details.

It would be nice to formalize \pi in Sec 2 upon first experience.

We will update section 2 to emphasize that $\pi(\cdot|x) \in \Delta(Z)$ denotes a distribution over the instruments, conditional on the covariates.

References: Multiple references are incomplete.

We found one reference that lacked relevant details (the reference to Phil Thomas’s Safe RL was missing the school and that it was a Ph.D. thesis). If there are others with missing information, please let us know.

Things to improve the paper that did not impact the score

We thank the reviewer again for their careful review, and we will incorporate as many suggestions as possible to improve the readability of the draft further.

We thank the reviewer again for taking out their valuable time and engaging in a constructive discussion. We were glad to hear that our previous response was able to address some of the concerns. Below we provide comments for the remaining ones:

1. Flow of paper:

The introduction of notation is not comprehensive (e.g., ,). Rewriting the beginning of Section 2 to include all notation used in this Section would significantly help the flow of the paper.

Thank you for helping us improve the readability of the draft further. We have updated Section 2 to ensure that all the relevant notation is introduced before the problem statement is discussed.

It is still difficult to follow the argument in the text (e.g. continuous references to later sections). Main results are still referred to the Appendix.

We appreciate the reviewer’s encouragement to make the paper even clearer. As the reviewer can imagine, the page limits mean that many of our results and details had to be deferred to the appendix, and we do appreciate that the comments from other reviewers’ suggest that the current organization does appeal to some of the target audience. Of course, we would be grateful if the reviewer could point out particular results in the appendix that they think would be beneficial to appear in the main text.

The restriction to symmetric estimators should be mentioned early in the paper, not only one page 5.

Thank you for bringing this up. We have also mentioned this now in Section 2, right where we first introduce the estimators, before stating the problem statement. And then in Section 3.2 again as a reminder to the readers, when the symmetric condition is used.

2. Influence functions:

Introducing eq.9 is highly confusing at this point in the text. The reader would expect a general form of influence functions, not only the form for k=1. If presenting a general form (or even forms for other small is not possible, then the order of equations 8 to 12 should be revised. It should be clear from the beginning, that only k=1 is needed.

We like the reviewer’s suggestion! We have updated the draft to revise the ordering of this section, such that it is clear that only $k=1$ is needed. Thank you for helping us improve the clarity of this section.

How would a practitioner know if all k-th order influence functions exist? Why is k=1 sufficient? Property 3 does not directly state this, since was defined over all k-th order functions.

Thanks for letting us know we had not yet clearly explained this. The existence of higher-order influence requires smoothness of the estimate to perturbations in sample weights in the loss. For example, let $l_i(\theta)$ be the loss from the $i^{th}$ sample, such that the total loss is $L(\theta) = \frac{1}{n} \sum_i l_i(\theta)$. Here, the weight associated with the loss of each sample is $1/n$. Here smoothness would refer to how would the minimizer of $L(\theta)$ change if for one of the samples, the weight is changed from $1/n$ to $(1/n +\epsilon)$, as $\epsilon \rightarrow 0$.

Note that such an assumption on the smoothness of estimators is not new and is used across a wide range of applications of influence functions. For example: for model selection [1], dataset distillation [2], uncertainty quantification [3], studying model generalization [4], studying interpretability of models [5], and many other applications [6]. We have highlighted these works in the extended related work section in Appendix A.

Fortunately, under this (common) assumption, Property 3 ensures that $k=1$ suffices for our setting to reduce variance, incur small bias, and remain computationally feasible. It is worth pointing out that the above-mentioned works [1,2,3,4,5,6] also only consider $k=1$ for their respective applications.

Additionally, performance improvement achieved by DIA suggests that this assumption also seems robust to different kinds of estimators (linear with closed form (Fig 5), logistic regression (Fig 6), and neural-network-based non-linear estimators (Fig 1)) used for our experiments.

[1] Alaa, Ahmed, and Mihaela Van Der Schaar. "Validating causal inference models via influence functions." In International Conference on Machine Learning, pp. 191-201. PMLR, 2019.

[2] Loo, Noel, Ramin Hasani, Mathias Lechner, and Daniela Rus. "Dataset Distillation with Convexified Implicit Gradients." arXiv preprint arXiv:2302.06755 (2023).

[3] Alaa, Ahmed, and Mihaela Van Der Schaar. "Discriminative jackknife: Quantifying uncertainty in deep learning via higher-order influence functions." In International Conference on Machine Learning, pp. 165-174. PMLR, 2020

[4] Grosse, Roger, Juhan Bae, Cem Anil, Nelson Elhage, Alex Tamkin, Amirhossein Tajdini, Benoit Steiner et al. "Studying large language model generalization with influence functions." arXiv preprint arXiv:2308.03296 (2023).

[5] Guo, Han, Nazneen Fatema Rajani, Peter Hase, Mohit Bansal, and Caiming Xiong. "Fastif: Scalable influence functions for efficient model interpretation and debugging." arXiv preprint arXiv:2012.15781 (2020).

[6] Koh, Pang Wei, and Percy Liang. "Understanding black-box predictions via influence functions." In International conference on machine learning, pp. 1885-1894. PMLR, 2017.

3. Figure 4

We agree that the variance of IS is multiple times higher that the variance of RS. Nevertheless, it does not increase exponentially in the sample size (one could argue that this might happen only after ~4500 samples) Therefore, the figure still does not support the statement in the text.

Thank you for helping us improve this illustrative example. We have updated it to bring out this worst-case behavior better. We have also removed the log scale on the y-axis that was present earlier. Appendix I.4 contains more details about the plot, as well as the log-scale version of this plot (Fig 8) to highlight the difference in variances even at smaller values of n.

We thank the reviewer for appreciating the importance of the problem and the novelty of the contributions. We were glad to see that we were able to convey the key ideas adequately and we agree with the reviewer on the next big steps in this direction. We answer the questions below, in order.

1. Adaptivity can bring us a lot of benefits like the improvement of sample efficiency. However, the technical challenge is that adaptivity usually harms the independence among the data. The adaptively collected data is usually challenging to analysis, even for the basic M-estimator (see, e.g., [A]). The authors do not seem to cover any points along this line. It will be beneficial to present whether the adaptivity in this paper affects the independence structure and how the authors handle such difficulties.

That is a great point! While in this work we focused on adaptive data collection and empirical finite sample performance, we will update the conclusion to cite [A] and highlight that adaptive data collection can harm the independence assumption and can make inference more nuanced. Similar to [A], recent work by Gupta et al. [B] also presents initial steps to show consistency and asymptotic normality for simpler GMM estimators under adaptive data collection. While generalizing these results is important, it is orthogonal to our current contribution, and addressing this would result in interesting future work.

[B] Gupta, Shantanu, Zachary Lipton, and David Childers. "Efficient online estimation of causal effects by deciding what to observe." Advances in Neural Information Processing Systems 34 (2021)

2. For the multi-rejection sampling, if and are very different, the algorithm might reject many samples before getting a useful one, which can be very inefficient and impractical. Things become even worse when the dimensions of the problem get larger, for example, as the authors mentioned, when the natural language serves as instruments Additionally, it would be good to know how to choose the value of "k" in practice.

Your observation is accurate. A standard technique for density ratio estimation (that governs acceptance-rejection ratio in our setup) in higher dimensions is through performing density ratio estimation on a lower dimensional subspace [1, 2]. We believe that incorporating similar ideas into our framework can provide further improvements.

Regarding setting the value of k: We parametrize $k$ as $n^\alpha$. As the expected number of samples that get accepted via rejection sampling from a set of $n$ samples is $n/\rho_\text{max}$, it would be ideal for $\alpha$ to be such that $n^\alpha > n/\rho_\text{max}$. Empirical supremum can be used as a proxy for $\rho_\text{max}$.

[1] Yamada, Makoto, and Masashi Sugiyama. "Direct density-ratio estimation with dimensionality reduction via hetero-distributional subspace analysis." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 25, no. 1, pp. 549-554. 2011.

[2] Sugiyama, Masashi, and Motoaki Kawanabe. "Dimensionality reduction for density ratio estimation in high-dimensional spaces." 人工知能学会第二種研究会資料 2009, no. DMSM-A901 (2009).

3. In the introduction, when summarizing the contributions, I didn't notice a clear mention of the technical challenges and novel aspects of the work. I found several such points in the main text. It would be beneficial, in my opinion, to include them in the introduction, especially since many of the ideas are quite traditional.

Thank you for the good suggestion– we will update the introduction accordingly.

4. One minor point is that the writing can be further improved. When referring to an equation, it is better to put the equation number in parentheses. The phrase to define ... is a little confusing.

We thank the reviewer again for their careful review, and we will incorporate these suggestions to improve the readability of the draft further.

We thank the reviewer for their support and valuable time to provide constructive feedback! We answer the questions, in order, below.

[ ]I was able to understand “Indirect experiments” on an intuitive level from the problem statement and the given examples, but a less informed reader might struggle and benefit from a more thorough/formal definition, though I am aware authors can’t cater to all levels and the current introduction of the term is just fine for the usual causa ICLR reader.

We agree with the reviewer. We had to indeed navigate the issues of addressing this to different audiences, within the prescribed page limit, while also discussing all the contributions. We wanted to provide some informal intuition and thus had to defer the formal problem statement to Eqn 4 in Section 2.

"...impact of reallocation.." "The conclusion of a ‘Unshaped’ trade off between number of instruments and number of reallocations might oversimplify deeper issues, though for the given work is perfectly adequate." , "more empirical or theoretical evidence to enrich the discussion on the ‘U-shaped’ trade off between number of instruments and number of reallocations? It seem like you might be running out of space, but if camera-ready allows another page, please enrich."

Thank you for your suggestions to improve the conclusions further! While in this work we took the first step towards addressing several bias-variance challenges underlying a general framework for adaptively designing the instrument sampling policy, our results do provide interesting next challenges to work on and improve the method further. We plan to continue this investigation in future work.

(Unfortunately, it looks like the camera-ready version this year does not allow an additional page.)

[ ]Figure 2: I am not sure what the dotted red lines indicate. I assume they are related to special conditions and assumptions on the SCM, but these are not connected to the text as far as I can see. Did I miss it?

That’s correct, the dotted lines visually depict the standard IV condition (Assumption 1) for the SCM. We will update the text to mention this.

[ ]Typo: Page 5 bottom: “Multi-rejection important sampling” should be importance I assume.

Thank you for catching this typo. We will fix it.

We were glad to hear that the reviewer found the motivation clear, and the theoretical and empirical analyses useful. We thank the reviewer for appreciating the novelty of the algorithm and taking their valuable time to provide constructive feedback.

W1: The paper uses a uniform data collection method as the baseline, however, I think evaluating some more RL algorithms and comparing their performance will make the paper more convincing.

We agree that some justification regarding other RL methods would be useful. We will update the draft to mention that while we leverage tools from RL, our problem setup presents several unique challenges that make the application of standard RL methods as-is ineffective.

Off-policy learning is an important requirement for our method, and policy-gradient and Q-learning are the two main pillars of RL. As we discussed in Section 4, conventional importance-sampling-based policy gradient methods can have variance exponential in the number of samples, rendering them practically useless for our setting. On the other hand, it is unclear how to efficiently formulate the optimization problem using Q-learning. From an RL point of view, the “reward” corresponds to the MSE, and the “actions” corresponds to instruments. Since this reward depends on all the samples, the effective “state space” for Q-learning style methods would depend on the combinatorial set of the covariates, i.e., let $\mathcal X$ be the set of covariates and $n$ be the number of samples, then the state $s \in \mathcal X^n$. This causes additional trouble as $n$ continuously changes/increases in our setting as we collect more data.

W2: In practice, the max multi-importance ratio may not be known, so this paper uses the empirical supremum instead. May the importance ratio also be unknown?

Thanks for asking this question! We should have and will clarify in the draft that the multi-importance ratio $\bar \rho(S)$ is always known in our setting. Since the proposed method does the data collection itself, we have access to both the current and the prior data-collection policies that are needed to compute the multi-importance ratio.

W3: Is there some clear pattern for DIA-X with different X in Figures 1, 5, and 6? For example, the U-trend is not obvious in Figure 1.

That’s a great observation. Indeed, the severity of the U-trend will vary from problem to problem. In general, our goal in mentioning the U-trend was to highlight the over-arching tension that as the number of potential instruments increases, there is a greater opportunity to be more effective. However, an increase in the number of instruments also increases the challenge with the optimization routine. Therefore, this results in the aforementioned U-trend.

W4: Is Figure 3 showing the result with K=1? Providing more results with varying K may helpful.

While we agree that having $k>1$ would be interesting, writing an explicit form for a general $k$-th order influence function can often be tedious, and computing it can be practically challenging. For instance, see the higher-order influences for the single-stage estimators in the works by Alaa et al. [1] and Robins et al. [2]. Fortunately, as we formally show in Property 3, for our purpose, using $k=1$ suffices to dramatically reduce the variance of the gradient estimator, incur a bias that decays quickly, while also being easy to compute.

[1] Alaa, Ahmed, and Mihaela Van Der Schaar. "Discriminative jackknife: Quantifying uncertainty in deep learning via higher-order influence functions." International Conference on Machine Learning. PMLR, 2020.

[2] Robins, James, et al. "Higher order influence functions and minimax estimation of nonlinear functionals." Probability and statistics: essays in honor of David A. Freedman. Vol. 2. Institute of Mathematical Statistics, 2008. 335-422.