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.


Reviews:
[{"review_id": "qTuUziTuX59", "reviewer": "Reviewer_ysqL", "summary": "This paper uses the best-arm identification framework to select an appropriate estimator for identifying a causal relationship between two variables. Such an estimator takes the observed data as input to quantify the causal effect between the variables of interest. In the setup proposed in this paper, each arm corresponds to an estimator, and the goal of the learner is to select the best estimator (the one with lowest variance), while also considering the cost associated with the estimator (available apriori).\n\nThe primary contribution of this paper is a confidence bound for the variance of such estimators under assumptions such as Lipschitz continuity on the “uncentered influence function”. This bound is then used in two standard best-arm identification algorithms (a UCB based strategy and an elimination algorithm) to select the “best” arm. The paper derives upper bounds on the sample complexity of both the algorithms. Experiments show that the algorithms perform favorably as compared to a random strategy.", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "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": "Originality – Posing the problem of selecting the best estimator for causal effect identification as a best-arm identification problem appears to be new. The confidence bound and the best-arm identification algorithms (and their analysis) are fairly standard.\n\nQuality – I have the following issues:\n1.\tThe paper lacks a clear motivation and does not provide a satisfactory answer as to why it is a good idea to formulate this problem as a best-arm identification problem. Are there any limitations of this formulation?\n2.\tIt is hard for me to assess why the technical contributions in this paper are significant enough. I would be happy to revise my score if the authors can provide simple explanations for this.\n3.\tAlgorithm 1 does not take cost into account. Moreover, shouldn’t the condition inside the first if predicate be: \\hat{\\sigma}^2_{l_t} + \\beta_{l_t} \\leq \\hat{\\sigma}^2_{u_t} - \\beta_{u_t} + \\epsilon?\n4.\tL372 is confusing. I don’t understand why regret minimization will be better objective in this case if the goal is to find the best estimator?\n\nClarity – \n1.\tIt was hard for me to follow the paper. It would be better to clarity in the beginning itself as to what is being done adaptively. L60 gives the impression that the goal is to adaptively select observations to reduce the variance of an estimator. However, the actual goal appears to be slightly different. Once an estimator (an arm) is chosen, collecting the samples for this estimator is not done adaptively. The goal instead is to decide whether it is reasonable to collect more data for an estimator before ruling it out, not to decide what data has to be sampled for a particular estimator. Am I missing something?\n2.\tIn L76, lambda was used without any explanation.\n3.\tMore details in the paragraph that starts at L108 will be helpful. In particular, taking a concrete example of \\eta and \\psi here will make things easier to follow.\n\nSignificance – Please see the 2nd point under quality.\n\nStrengths – The bandit formulation of the problem seems to be new.\n\nWeaknesses – The paper is difficulty to follow (see more details above)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss a limitation in L364-365, however, even before that they should highlight the limitations of posing this problem as a best-arm identification problem.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "kSrFUu5NKn2", "reviewer": "Reviewer_bePw", "summary": "The author considers the problem of selecting the best (in terms of variance) estimator among K estimators in an online manner. The estimators class is limited to the ones that satisfy the asymptotic linearity and its asymptotic variance can be computed from the uncentered influence function. The author considered this problem setting as a best-arm identification problem and applied the SE and LUCB algorithms. The variance computation is based on the sample splitting approach. The authors conducted theoretical analyses of its performance as well as numerical experiments on synthetic data.", "questions": "", "limitations": "", "rating": 4, "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": "I do not see the novelty of this problem setting. It seems to me that this is just an application of BAI with the arm’s mean as the value of the variance. The computation of the confidence bound for the variance does not look novel. The proof of Theorem 1 looks straightforward to me. (please point out the difficulties of the proof) If the sample splitting idea is based on Chernozhukov et al 2018, the authors should cite it in the main paper and proofs. Even if it is a different problem setting, it would be strange not to cite the causal bandit papers (e.g., [1], [2]). The differences from those studies should be compared and carefully discussed. In some places, (even in the title) there are typos \"casual\". No sample complexity lower bounds are given. The title having \"Best\" causal effect identification, it is a bit misleading to put the word \"Best\" in the title, since the authors are not showing the lower bound and a method that matches the lower bound. LUCB and SE are not the state of the art algorithms for the fixed confidence BAI (see e.g., [3], [4]). \n\n\", we could consider the problem of trying to obtain the best estimate of the causal effect given a limited budget. This problem is more analogous to the cumulative regret minimizing bandit problem\"\n\nI don't think this problem resembles the expected cumulative regret minimization problem. Might be similar to the problem of fixed budget BAI. \n\n\n\n\n[1] Lattimore et al, Causal Bandits: Learning Good Interventions via\nCausal Inference, NeurIPS 2016\n\n[2] Kallus, Instrument-Armed Bandits, ALT 2018\n\n[3] Non-Asymptotic Pure Exploration by Solving Games, Neurips 2019.\n\n[4] Garivier and Kaufmann, Optimal Best Arm Identification with Fixed Confidence, COLT 2016.\n\n\n---------- After Rebuttal --------\n\nAfter reading your rebuttals and other reviewers' comments, my score remains the same. \nTechnical contributions can be made much clearer and I think the work needs a clear comparison with the existing pure exploration literature.\nThe argument on cumulative regret still does not make sense to me. You need to prove the equivalence to claim the similarity I think.\nFurthermore, again the typo \"casual\" is in your rebuttal. Please make sure to proofread.\n\n \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't think there is a problem.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "QLnRrl6JKe", "reviewer": "Reviewer_t43v", "summary": "This paper studies the problem of identifying the formula with the best asymptotic variance among a set of formulas used to estimate a causal effect, and frames it as a best-arm identification (BAI) problem. The paper develops finite-sample confidence sequences with nuisance functions for the proposed sample-splitting estimator of the asymptotic variance. With these confidence sequences, the paper can modify the existing algorithms LUCB and successive elimination for the studied BAI problem and prove sample complexity bounds in terms of the estimation rate of the nuisance function.", "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": "The paper is well organized and relatively clearly written. The main technical result is developing finite-sample confidence sequences with nuisance functions for the proposed sample-splitting estimator of the asymptotic variance. With this, it is not hard to modify the existing LUCB and successive elimination algorithms for the studied BAI problem and to use the standard techniques in BAI literature to show the corresponding sample complexities.\n\nTheorem 2 shows the sample complexity of CS-LUCB in terms of finding an $\\epsilon$-optimal formula for any $\\epsilon \\geq 0$. In my opinion, it is important to show the lower bound, and it is possible to find such result in the existing BAI literature. Theorem 3 only proves the sample complexity of CS-SE for $\\epsilon=0$, and how about the sample complexity for general $\\epsilon \\geq 0$? I guess it is not hard to extend the current result. In Corollary 2, is it true that we have the first bound only if $\\nu_\\eta \\leq -1/2$ instead of $-1/4$?\n\nI suggest doing a more comprehensive literature review; for example, [1] (and some references therein) needs to be cited and compared in detail.\n\nHere are some minor comments. On line 249, there is a redundant \"s\" in the word \"miss-classified\". In the expression of $\\nu$ on lines 280 and 282, $\\nu_\\eta$ should replace $\\nu_\\theta$.\n\n[1] Masahiro Kato, Takuya Ishihara, Junya Honda, and Yusuke Narita, Adaptive Experimental Design for Efficient Treatment Effect Estimation, https://arxiv.org/abs/2002.05308, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper briefly mentions the limitations in the Discussion section and it seems there is no potential negative societal impact. Please address my comments.", "review_text": "", "extra_scores": {"ethical_concerns": "It seems that there is no ethical concern.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "~8 hours"}, "extra_text": {}}, {"review_id": "1d3isHTEfZ", "reviewer": "Reviewer_sw9W", "summary": "This paper proposed two bandit methods (CS-LUCB and CS-SE) that learn the best causal identification formula in terms of the cost-adjusted asymptotic variance. In the two bandit algorithms, they replaced the usual empirical reward terms with the empirical variance estimations. They showed their methods find the best formula under some conditions and also provided sample complexities. ", "questions": "", "limitations": "", "rating": 3, "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": "Originality:\nUsing bandit framework to learn the best causal identification terms is new to me. The way they mixed the variance estimation terms in standard algorithms such as LUCB and SE was trivial.\n\nQuality: \nIn my opinion, this paper was written very poorly. \nFirst, the notations and terms were defined very unclearly. For example, in line 76, what are \\lambda_x, what do you mean by causal contrast? in the paragraph starting in line 97, what is the function \\phi? why asymptotic linear? etc.\nSecond, several (in)equalities are incorrect. E.g. in line 81, the decomposition is not correct, there should be a do operator over X=x in the condition of \\mu_x(Z_1). Line 82 has similar issue as well, the decomposition does not hold. If interventional quantities, i.e. do operators need to exist in the decompositions, it will contradict with the authors' claim that they express the causal contrast using only observational quantities. This example doesn't make sense to me.  In the inequality below line 132, the event in the probability bracket is not even a random event.\nThird, theorems hold under too many conditions. It's hard to interpret their sample complexity results theoretically.\nAlso, there is no practical motivation for the problem. \nTypos: 'casual' -> 'causal' in the title.\n\nClarity:\nThe paper was poorly written.\n\nSignificance:\nLearning the causal expression adaptively is a worth-pursuing problem, but this paper is not good enough.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers came to consensus that the techniques materials of this paper is standard and the contribution is somewhat limited, though the introducing the idea of using BAI for causal effect identification is novel. Some reviewers also point out the writing issues and they must be thoroughly addressed to make the paper acceptable for publication.
Decision: Accept (Poster)