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 (ε,δ)-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 (ε,δ)-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
Related
- Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means
- Strongly Adaptive Online Learning with Time-Varying Movement Costs
- Adaptive Beam Hopping and Power Control for Dual-Layer Over-the-Air Online Federated Learning in LEO Satellite Networks
- Sequential Confidence Sets for Coverage-Constrained Conformal Model Selection
- Adaptive confidence intervals with missing data
BibTeX
@misc{xu2026focus,
title = {{FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions}},
author = {Haijie Xu and Chen Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32165},
eprint = {2609.32165},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32165},
}
RIS
TY - UNPB
TI - FOCUS: Fixed-Confidence Online Causal Learning Using Sequential Adaptive Interventions
AU - Haijie Xu
AU - Chen Zhang
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32165
UR - https://arxiv.org/abs/2609.32165
AB - 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 \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 (ε,δ)-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
ER -