usually extremely large). The primary focus of prior literature is on the case of general finite $\Pi$, as this is the starting point for further studies of infinite (parametric or nonparametric) $\Pi$. For this case, the EXP4-family algorithms (@auer2002nonstochastic [@mcmahan2009tighter; @beygelzimer2011contextual]) achieve the optimal $O(\sqrt{KT\log|\Pi|})$ regret but requires $\Omega(|\Pi|)$ running time at each round, which makes the algorithms intractable for large $\Pi$. In order to circumvent the $\Omega(|\Pi|)$ running time barrier, researchers (e.g., @langford2008epoch [@dudik2011efficient; @agarwal2014taming]) restrict their attention to *oracle-based* algorithms that access the policy space only through an *offline optimization oracle* — specifically, an offline cost-sensitive classification oracle that solves $$\label{eq:csc}
\arg\max_{\pi\in\Pi}\sum_{s=1}^t \tilde{r}_{s}(\pi(x_s))$$ for any given sequence of context and reward vectors $(x_1,\tilde{r}_1),\cdots,(x_t,\tilde{r}_t)\in{{\mathcal{X}}}\times\mathbb{R}_{+}^{{{\mathcal{A}}}}$. An *oracle-efficient* algorithm refers to an algorithm whose number of oracle calls is polynomial in $T$ over $T$ rounds.

The first provably optimal oracle-efficient algorithm is the `Randomized UCB` algorithm of [@dudik2011efficient], which achieves the optimal regret with $\widetilde{O}(T^6)$ calls to the cost-sensitive classification oracle. A breakthrough is achieved by the `ILOVETOCONBANDITS` algorithm in the celebrated work of [@agarwal2014taming], where the number of oracle calls is significantly reduced to $\widetilde{O}(\sqrt{KT/\log|\Pi|})$. The above results are fascinating in theory because they enable a “online-to-offline reduction” from contextual 