only known for specific function classes. Whether the optimal regret of contextual bandits can be attained via a reduction to an offline regression oracle is listed as an open problem again in [@foster2020beyond].

In this paper, we give an affirmative answer to the above open problem repeatedly mentioned in the literature (@agarwal2012contextual [@foster2018practical; @foster2020beyond]). Specifically, we provide the first optimal black-box reduction from contextual bandits to offline regression, with only the minimal realizability assumption. The significance of this result is that it reduces contextual bandits, a prominent online decision-making problem, to offline regression, a very basic and common offline optimization task that serves as the building block of modern machine learning. A direct consequence of this result is that any advances in solving offline regression problems immediately translate to contextual bandits, statistically and computationally. Note that such online-to-offline reduction is highly nontrivial (and impossible without specialized structures) for online learning problems in general (@hazan2016computational).

Our reduction is accomplished by a surprisingly fast and simple algorithm that achieves the optimal ${O}(\sqrt{KT\log(|{{\mathcal{F}}}|T)})$ regret for general finite function class ${{\mathcal{F}}}$ with only $O(\log T)$ calls to an offline least-squares regression oracle over $T$ rounds. The number of oracle calls can be further reduced 