a completely *implicit* way (which means that all the requirements are automatically satisfied without explicit computation), our algorithm comes with significantly reduced computational cost compared with previous work (thanks to the realizability assumption), and we thus title our paper as “bypassing the monster”.

Finally, we extend all the above results to the case of general infinite function class ${{\mathcal{F}}}$. For this case, we state our results in a more general way: for any function class ${{\mathcal{F}}}$, given an arbitrary offline regression oracle with an arbitrary offline *estimation error* (or *excess risk*) guarantee, we propose a fast and simple contextual bandit algorithm whose regret can be bounded by a function of the offline estimation error, through only $O(\log T)$ calls (or $O(\log\log T)$ calls if $T$ is known) to the offline regression oracle. We show that our algorithm is statistically optimal as long as the offline regression oracle is statistically optimal. Notably, the above results provide a universal and optimal “converter” from results of offline/batch learning with general function classes to results of contextual bandits with general function classes. This leads to improved algorithms with tighter regret bounds for many existing contextual bandit problems, as well as practical algorithms for many 