  The combinatorial pure exploration of causal bandits is the following online
learning task: given a causal graph with unknown causal inference
distributions, in each round we choose a subset of variables to intervene or do
no intervention, and observe the random outcomes of all random variables, with
the goal that using as few rounds as possible, we can output an intervention
that gives the best (or almost best) expected outcome on the reward variable
$Y$ with probability at least $1-\delta$, where $\delta$ is a given confidence
level. We provide the first gap-dependent and fully adaptive pure exploration
algorithms on two types of causal models -- the binary generalized linear model
(BGLM) and general graphs. For BGLM, our algorithm is the first to be designed
specifically for this setting and achieves polynomial sample complexity, while
all existing algorithms for general graphs have either sample complexity
exponential to the graph size or some unreasonable assumptions. For general
graphs, our algorithm provides a significant improvement on sample complexity,
and it nearly matches the lower bound we prove. Our algorithms achieve such
improvement by a novel integration of prior causal bandit algorithms and prior
adaptive pure exploration algorithms, the former of which utilize the rich
observational feedback in causal bandits but are not adaptive to reward gaps,
while the latter of which have the issue in reverse.
