Taking a hint: How to leverage loss predictors in contextual bandits?

  • 2020-10-15 17:31:50
  • Chen-Yu Wei, Haipeng Luo, Alekh Agarwal
  • 0


We initiate the study of learning in contextual bandits with the help of losspredictors. The main question we address is whether one can improve over theminimax regret $\mathcal{O}(\sqrt{T})$ for learning over $T$ rounds, when thetotal error of the predictor $\mathcal{E} \leq T$ is relatively small. Weprovide a complete answer to this question, including upper and lower boundsfor various settings: adversarial versus stochastic environments, known versusunknown $\mathcal{E}$, and single versus multiple predictors. We show severalsurprising 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 asmulti-armed bandits); 2) the same bound cannot be achieved if $\mathcal{E}$ isunknown, but as a remedy, $\mathcal{O}(\sqrt{\mathcal{E}}T^\frac{1}{3})$ isachievable; 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 matchingupper bounds, including 1) a key action remapping technique for optimal regretwith known $\mathcal{E}$, 2) implementing Catoni's robust mean estimatorefficiently via an ERM oracle leading to an efficient algorithm in thestochastic setting with optimal regret, 3) constructing an underestimator for$\mathcal{E}$ via estimating the histogram with bins of exponentiallyincreasing size for the stochastic setting with unknown $\mathcal{E}$, and 4) aself-referential scheme for learning with multiple predictors, all of whichmight be of independent interest.


Quick Read (beta)

loading the full paper ...