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

arXiv:2609.32165v1 Announce Type: cross 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 (epsilon,elta)-correct algorithm and propose extsc{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 extsc{FOCUS} is (epsilon,elta)-correct and that its expected stopping time matches the lower bound in its Theta(log(1/elta)) 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

Source: arXiv cs.LG | 2026-09-29