  We initiate the study of learning in contextual bandits with the help of loss
predictors. The main question we address is whether one can improve over the
minimax regret $\mathcal{O}(\sqrt{T})$ for learning over $T$ rounds, when the
total error of the predictor $\mathcal{E} \leq T$ is relatively small. We
provide a complete answer to this question, including upper and lower bounds
for various settings: adversarial versus stochastic environments, known versus
unknown $\mathcal{E}$, and single versus multiple predictors. We show several
surprising results, such as 1) the optimal regret is
$\mathcal{O}(\min\{\sqrt{T}, \sqrt{\mathcal{E}}T^\frac{1}{4}\})$ when
$\mathcal{E}$ is known, a sharp contrast to the standard and better bound
$\mathcal{O}(\sqrt{\mathcal{E}})$ for non-contextual problems (such as
multi-armed bandits); 2) the same bound cannot be achieved if $\mathcal{E}$ is
unknown, but as a remedy, $\mathcal{O}(\sqrt{\mathcal{E}}T^\frac{1}{3})$ is
achievable; 3) with $M$ predictors, a linear dependence on $M$ is necessary,
even if logarithmic dependence is possible for non-contextual problems.
  We also develop several novel algorithmic techniques to achieve matching
upper bounds, including 1) a key action remapping technique for optimal regret
with known $\mathcal{E}$, 2) implementing Catoni's robust mean estimator
efficiently via an ERM oracle leading to an efficient algorithm in the
stochastic setting with optimal regret, 3) constructing an underestimator for
$\mathcal{E}$ via estimating the histogram with bins of exponentially
increasing size for the stochastic setting with unknown $\mathcal{E}$, and 4) a
self-referential scheme for learning with multiple predictors, all of which
might be of independent interest.
