$O(T)$ calls to an
  (@foster2020beyond)                                 [online]{} regression oracle
  `FALCON`                   **optimal**              $\bm{O(\log T)}$ or $\bm{O(\log{} \log T)}$ calls to an
  (this paper)                                        **offline regression** oracle
  -------------------------- ------------------------ --------------------------------------------------------------

  : Algorithms’ performance with general finite ${{\mathcal{F}}}$. Advantages are marked in bold.[]{data-label="tab"}

Our approach is closely related to (and reveals connections between) three lines of research in contextual bandits over twenty years: (1) a celebrated theory of optimal contextual bandit learning in the agnostic setting using a (seemingly unavoidable) classification oracle, represented by [@dudik2011efficient] (the “monster paper”) and [@agarwal2014taming] (“taming the monster”); (2) a simple probabilistic selection strategy mapping the predicted rewards of actions to the probabilities of actions, pioneered by [@abe1999associative] (see also @abe2003reinforcement) and followed up by [@foster2020beyond]; and (3) some technical preliminaries developed in an early work of [@agarwal2012contextual]. In particular, we rethink the philosophy behind [@dudik2011efficient] and [@agarwal2014taming], reform it with our own understanding of the value of realizability, and come up with a new idea of “bypassing” the classification oracle under realizability — our algorithm is essentially a direct consequence of this new idea, see the derivation of our algorithm in §\[sec:born\]. Interestingly, our derived algorithm turns out to use a different but similar probabilistic selection strategy like 