FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions

Haijie Xu; Chen Zhang

stat.MLSep 26, 2026

FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions

Authors: Haijie Xu, Chen Zhang

Organizations: Department of Industrial Engineering Tsinghua University Beijing, China

Abstract

We study fully online fixed-confidence causal discovery without any historical observational data. Starting from zero samples, the learner sequentially selects interventions to recover both the causal DAG and its edge weights under a linear-Gaussian structural equation model. We establish an instance-dependent lower bound for any $(ε,δ)$ -correct algorithm and propose FOCUS, which adaptively allocates interventions through an online max--min game. A key contribution is a computable concentration inequality for the accumulated KL divergence involving causal parameters shared across interventions. We prove that FOCUS is $(ε,δ)$ -correct and that its expected stopping time matches the lower bound in its $Θ(\log(1/δ))$ dependence up to an instance-dependent constant. Experiments demonstrate improved structure and edge-weight recovery and confirm the predicted stopping-time trend. Our codes are available on https://anonymous.4open.science/r/FOCUS_code-76E5

Figures & tables

Panel of Figure 1 — Figure 1: Performance for $p=6$ and $\rho=0.3$ . Panels (a)–(c) show SHD, maximum edge-weight estimation error, and the stopping time of FOCUS versus $\log(1/\delta)$ , respectively. Shaded bands and error bars denote 95% confidence intervals.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

\bm{b}^{\star}\in\argmin_{\bm{b}\in\mathbb{R}^{|S|}}Q_{j,t}(\bm{b};S)\quad\text{s.t.}\quad\beta_{\min}\leq\nu_{k}b_{k}\leq A_{\max},\ \ k\in S

Appendix

Algorithm 2 Finite implementation of the joint-MLE oracle

Panel of Figure 2 — Figure 2: Performance for $p=5$ and $\rho=0.3$ . Panels (a)–(c) show SHD, maximum edge-weight estimation error, and the stopping time of FOCUS versus $\log(1/\delta)$ , respectively. Shaded bands and error bars denote 95% confidence intervals.

Panel of Figure 3 — Figure 3: Performance for $p=7$ and $\rho=0.3$ . Panels (a)–(c) show SHD, maximum edge-weight estimation error, and the stopping time of FOCUS versus $\log(1/\delta)$ , respectively. Shaded bands and error bars denote 95% confidence intervals.

Panel of Figure 4 — Figure 4: Performance for $p=6$ and $\rho=0.4$ . Panels (a)–(c) show SHD, maximum edge-weight estimation error, and the stopping time of FOCUS versus $\log(1/\delta)$ , respectively. Shaded bands and error bars denote 95% confidence intervals.

Panel of Figure 5 — Figure 5: Performance for $p=6$ and $\rho=0.5$ . Panels (a)–(c) show SHD, maximum edge-weight estimation error, and the stopping time of FOCUS versus $\log(1/\delta)$ , respectively. Shaded bands and error bars denote 95% confidence intervals.

Causal Discovery

Causal discovery infers cause-and-effect structures from observational and interventional data, distinguishing causal relationships from correlation.

See all 221 papers

Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound
May 26, 2026Eichi UeharaBayesian Networks Causal Discovery
aflo, Inc., Tokyo, Japan
FoundCause: Causal Discovery with Latent Confounders from Observational Data
Jun 16, 2026Patrick Blöbaum, Krishnakumar Balasubramanian, Shiva Prasad KasiviswanathanStructural Causal Models Amortized Inference
Amazon Web Services · Department of Statistics, University of California, Davis
I-FLOP: Fast Learning of Order and Parents from Interventional Data
Aug 28, 2026Liuting Chen, Alex MarkhamCausal Discovery Causal Structure Learning
Department of Mathematical Sciences University of Copenhagen Denmark

May 26, 2026J/K move · Enter open · S save

Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound

Eichi Uehara

aflo, Inc., Tokyo, Japan

Bayesian Networks Causal Discovery Causal Structure Learning Causal Identifiability

Open paper AskPDF arXiv

Causal-discovery algorithms return a directed graph, yet provide no principled means of distinguishing edge directions identified by the data from those assigned without an identifying assumption. Under the standard Markov and faithfulness conditions, the observational distribution identifies only a Markov equivalence class; orientations within that class are not determined by the joint distribution and cannot be recovered from additional samples alone, but require either a functional restriction or an intervention. We introduce a protocol for observational causal discovery on continuous data that attaches to each candidate edge a discrete impossibility certificate: a RESOLVED code records the identifiability theorem under which the direction was committed, while an IMPOSSIBLE code records the failure mode together with the specific question a domain expert must answer to resolve it. The bivariate cascade is extended with five gated identifiability tiers LSNM, IGCI, Stein, MDL, and PEIT that abstain when their precondition test rejects. Two oracle primitives, the meta-hub query and the node-children query, jointly establish an upper bound of

1+K

expert interactions sufficient to recover any DAG, where

K

denotes the number of non-leaf vertices. Under an ideal-oracle assumption, the bound is met exactly on the asia, sachs, child, and alarm benchmarks.

Abstract

Causal Discovery

Explore similar work

Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the 1+K1+K1+K Lower Bound

FoundCause: Causal Discovery with Latent Confounders from Observational Data

I-FLOP: Fast Learning of Order and Parents from Interventional Data

Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound