  The exploration/exploitation (E&E) dilemma lies at the core of interactive
systems such as online advertising, for which contextual bandit algorithms have
been proposed. Bayesian approaches provide guided exploration with principled
uncertainty estimation, but the applicability is often limited due to
over-simplified assumptions. Non-Bayesian bootstrap methods, on the other hand,
can apply to complex problems by using deep reward models, but lacks clear
guidance to the exploration behavior. It still remains largely unsolved to
develop a practical method for complex deep contextual bandits.
  In this paper, we introduce Guided Bootstrap (GuideBoot for short), combining
the best of both worlds. GuideBoot provides explicit guidance to the
exploration behavior by training multiple models over both real samples and
noisy samples with fake labels, where the noise is added according to the
predictive uncertainty. The proposed method is efficient as it can make
decisions on-the-fly by utilizing only one randomly chosen model, but is also
effective as we show that it can be viewed as a non-Bayesian approximation of
Thompson sampling. Moreover, we extend it to an online version that can learn
solely from streaming data, which is favored in real applications. Extensive
experiments on both synthetic task and large-scale advertising environments
show that GuideBoot achieves significant improvements against previous
state-of-the-art methods.
