the case of general finite ${{\mathcal{F}}}$, the online algorithm given by [@rakhlin2014online] actually requires $\Omega(|{{\mathcal{F}}}|)$ computational cost at each round. As a result, in parallel with the excellent work of [@foster2020beyond], a more thorough “online-to-offline reduction” from contextual bandits to offline regression is highly desirable.

### Empirical Evaluation and Summary

Recently, [@bietti2018contextual] and [@foster2018practical] conduct some extensive empirical evaluations on different approaches to contextual bandits. The experimental results show that offline-regression-oracle-based algorithms like `RegCB` typically outperforms other algorithms (including classification-oracle-based algorithms like `ILOVETOCONBANDITS`) across multiple datasets, statistically and computationally. Given the empirical success of `RegCB`, a huge gap between the theory and practice of contextual bandits is that, however, a provable optimal offline-regression-oracle-based algorithm is still unknown. This is the major motivation of our study, and we hope that our work can contribute to closing this gap.

Research Question {#sec:rq}
-----------------

In this paper, we study the following open question which is repeatedly mentioned in the contextual bandit literature (@agarwal2012contextual [@foster2018practical; @foster2020beyond]): *Is there an offline-regression-oracle-based algorithm that achieves the optimal regret for contextual bandits?*

Similar to [@dudik2011doubly; @agarwal2012contextual; @agarwal2014taming], we mainly focus on the case of general finite ${{\mathcal{F}}}$, as this is the starting point for further studies of 