algorithm of [@foster2018practical] is, however, theoretically sub-optimal — it could incur $\widetilde{\Omega}(T)$ regret in the worst case. Whether the optimal regret of contextual bandits can be attained via an offline-regression-oracle-based algorithm is listed as an open problem in [@foster2018practical]. In fact, this problem has been open to the bandit community since 2012 — it dates back to [@agarwal2012contextual], where the authors propose a computationally *inefficient* contextual bandit algorithm that achieves the optimal $O(\sqrt{KT\log|{{\mathcal{F}}}|})$ regret for a general *finite* function class ${{\mathcal{F}}}$, but leave designing computationally tractable algorithms as an open problem.

More recently, [@foster2020beyond] propose an algorithm that achieves the optimal regret for contextual bandits using an *online regression oracle* (which is not an offline optimization oracle and has to work with an adaptive adversary). Their finding that contextual bandits can be completely reduced to online regression is novel and important, and their result is also very general: it requires only the minimal realizability assumption, works with possibly nonparametric function classes, and holds true even when the contexts are chosen adversarially. However, the online regression oracle that they appeal to is still much stronger than an offline regression oracle, and to our knowledge computationally efficient algorithms for online regression are 