  In causal bandit problems, the action set consists of interventions on
variables of a causal graph. Several researchers have recently studied such
bandit problems and pointed out their practical applications. However, all
existing works rely on a restrictive and impractical assumption that the
learner is given full knowledge of the causal graph structure upfront. In this
paper, we develop novel causal bandit algorithms without knowing the causal
graph. Our algorithms work well for causal trees, causal forests and a general
class of causal graphs. The regret guarantees of our algorithms greatly improve
upon those of standard multi-armed bandit (MAB) algorithms under mild
conditions. Lastly, we prove our mild conditions are necessary: without them
one cannot do better than standard MAB algorithms.
