give an affirmative answer to the open question in §\[sec:rq\], by providing the first optimal black-box reduction from contextual bandits to offline regression, with only the minimal realizability assumption. As we mention before, a direct consequence of this result is that (stochastic) contextual bandits become no harder than offline regression: any advances in solving offline regression problems immediately translate to contextual bandits, statistically and computationally.

Moreover (and quite surprisingly), we go far beyond the conventional “polynomial/sublinear oracle calls” criteria of computational efficiency: we propose an algorithm achieving the optimal regret using only $O(\log T)$ calls to the regression oracle, and the number of oracle calls can be further reduced to $O(\log\log T)$ if $T$ is known. As we mention before, this can be understood as a “triply exponential” speedup over existing algorithms. Overall, our algorithm is fast, simple, memory-efficient, and has the potential to be implemented on a large scale. We compare our algorithm’s properties with existing (general-purpose) contextual bandit algorithms[^2] in Table \[tab\].

  -------------------------- ------------------------ --------------------------------------------------------------
  Algorithm                  Statistical optimality   Computational complexity
  `Regressor Elimination`    **optimal**              $\Omega(|{{\mathcal{F}}}|)$
  (@agarwal2012contextual)                            [intractable]{}
  `ILOVETOCONBANDITS`        **optimal**              $\widetilde{O}(\sqrt{KT/\log|{{\mathcal{F}}}|})$ calls to an
  (@agarwal2014taming)                                offline [classification]{} oracle
  `RegCB`                    [suboptimal]{}           $O(\sqrt{T})$ calls to an
  (@foster2018practical)                              **offline regression** oracle
  `SquareCB`                 **optimal**              