Additive Causal Bandits with Unknown Graph

• URL: http://arxiv.org/abs/2306.07858v1
• Date: Tue, 13 Jun 2023 15:43:04 GMT
• Title: Additive Causal Bandits with Unknown Graph
• Authors: Alan Malek and Virginia Aglietti and Silvia Chiappa
• Abstract summary: We explore algorithms to select actions in the causal bandit setting where the learner can choose to intervene on a set of random variables related by a causal graph. The learner's goal is to quickly find the intervention, among all interventions on observable variables, that maximizes the expectation of an outcome variable.
• Score: 10.575089475850465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We explore algorithms to select actions in the causal bandit setting where the learner can choose to intervene on a set of random variables related by a causal graph, and the learner sequentially chooses interventions and observes a sample from the interventional distribution. The learner's goal is to quickly find the intervention, among all interventions on observable variables, that maximizes the expectation of an outcome variable. We depart from previous literature by assuming no knowledge of the causal graph except that latent confounders between the outcome and its ancestors are not present. We first show that the unknown graph problem can be exponentially hard in the parents of the outcome. To remedy this, we adopt an additional additive assumption on the outcome which allows us to solve the problem by casting it as an additive combinatorial linear bandit problem with full-bandit feedback. We propose a novel action-elimination algorithm for this setting, show how to apply this algorithm to the causal bandit problem, provide sample complexity bounds, and empirically validate our findings on a suite of randomly generated causal models, effectively showing that one does not need to explicitly learn the parents of the outcome to identify the best intervention.

Related papers

• Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits [7.064432289838905]
  Current works often assume the causal graph is known, which may not always be available a priori. We focus on the causal bandit problem in scenarios where the underlying causal graph is unknown and may include latent confounders. We formally characterize the set of necessary and sufficient latent confounders one needs to detect or learn to ensure that all possibly optimal arms are identified correctly.
  arXiv  Detail & Related papers  (2024-11-06T16:59:11Z)
• Sample Efficient Bayesian Learning of Causal Graphs from Interventions [6.823521786512908]
  This study considers a Bayesian approach for learning causal graphs with limited interventional samples. We show theoretically that our proposed algorithm will return the true causal graph with high probability. We present a case study showing how this algorithm could be modified to answer more general causal questions without learning the whole graph.
  arXiv  Detail & Related papers  (2024-10-26T05:47:56Z)
• Adaptive Online Experimental Design for Causal Discovery [9.447864414136905]
  Causal discovery aims to uncover cause-and-effect relationships encoded in causal graphs. We focus on data interventional efficiency and formalize causal discovery from the perspective of online learning. We propose a track-and-stop causal discovery algorithm that adaptively selects interventions from the graph separating system.
  arXiv  Detail & Related papers  (2024-05-19T13:26:33Z)
• Bayesian causal discovery from unknown general interventions [55.2480439325792]
  We consider the problem of learning causal Directed Acyclic Graphs (DAGs) using combinations of observational and interventional experimental data. We develop a Markov Chain Monte Carlo scheme to approximate the posterior distribution over DAGs, intervention targets and induced parent sets.
  arXiv  Detail & Related papers  (2023-12-01T11:30:51Z)
• Nonparametric Identifiability of Causal Representations from Unknown Interventions [63.1354734978244]
  We study causal representation learning, the task of inferring latent causal variables and their causal relations from mixtures of the variables. Our goal is to identify both the ground truth latents and their causal graph up to a set of ambiguities which we show to be irresolvable from interventional data.
  arXiv  Detail & Related papers  (2023-06-01T10:51:58Z)
• Subset verification and search algorithms for causal DAGs [13.108039226223793]
  We study the problem of identifying the smallest set of interventions required to learn the causal relationships between a subset of edges (target edges) We prove several interesting structural properties of interventional causal graphs that we believe have applications beyond the subset verification/search problems studied here.
  arXiv  Detail & Related papers  (2023-01-09T06:25:44Z)
• Active Bayesian Causal Inference [72.70593653185078]
  We propose Active Bayesian Causal Inference (ABCI), a fully-Bayesian active learning framework for integrated causal discovery and reasoning. ABCI jointly infers a posterior over causal models and queries of interest. We show that our approach is more data-efficient than several baselines that only focus on learning the full causal graph.
  arXiv  Detail & Related papers  (2022-06-04T22:38:57Z)
• Deconfounded Score Method: Scoring DAGs with Dense Unobserved Confounding [101.35070661471124]
  We show that unobserved confounding leaves a characteristic footprint in the observed data distribution that allows for disentangling spurious and causal effects. We propose an adjusted score-based causal discovery algorithm that may be implemented with general-purpose solvers and scales to high-dimensional problems.
  arXiv  Detail & Related papers  (2021-03-28T11:07:59Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  We provide guarantees on identifiability and learnability under mild assumptions. We develop efficient algorithms based on coupled tensor decomposition with linear constraints to obtain scalable and guaranteed solutions.
  arXiv  Detail & Related papers  (2021-01-17T07:48:45Z)
• Causal Bandits without prior knowledge using separating sets [3.1000291317725]
  The Causal Bandit is a variant of the classic Bandit problem where an agent must identify the best action in a sequential decision-making process. Methods proposed for this problem thus far in the literature rely on exact prior knowledge of the full causal graph. We formulate new causal bandit algorithms that no longer necessarily rely on prior causal knowledge.
  arXiv  Detail & Related papers  (2020-09-16T20:08:03Z)
• Amnesic Probing: Behavioral Explanation with Amnesic Counterfactuals [53.484562601127195]
  We point out the inability to infer behavioral conclusions from probing results. We offer an alternative method that focuses on how the information is being used, rather than on what information is encoded.
  arXiv  Detail & Related papers  (2020-06-01T15:00:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.