  We address policy learning with logged data in contextual bandits. Current
offline-policy learning algorithms are mostly based on inverse propensity score
(IPS) weighting requiring the logging policy to have \emph{full support} i.e. a
non-zero probability for any context/action of the evaluation policy. However,
many real-world systems do not guarantee such logging policies, especially when
the action space is large and many actions have poor or missing rewards. With
such \emph{support deficiency}, the offline learning fails to find optimal
policies. We propose a novel approach that uses a hybrid of offline learning
with online exploration. The online exploration is used to explore unsupported
actions in the logged data whilst offline learning is used to exploit supported
actions from the logged data avoiding unnecessary explorations. Our approach
determines an optimal policy with theoretical guarantees using the minimal
number of online explorations. We demonstrate our algorithms' effectiveness
empirically on a diverse collection of datasets.
