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

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,\delta)$-correct algorithm and propose \textsc{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 \textsc{FOCUS} is $(\epsilon,\delta)$-correct and that its expected stopping time matches the lower bound in its $\Theta(\log(1/\delta))$ 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 this https URL

Machine Learning (stat.ML); Machine Learning (cs.LG)

arXiv:2609.32165 [stat.ML]

(or arXiv:2609.32165v1 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2609.32165 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.