is important for understanding the key technical hurdles. Below we discuss three challenges. **Computational hurdle.** [@agarwal2012contextual] propose a provably optimal but computational algorithm for contextual bandits with a general finite ${{\mathcal{F}}}$. At each round $t$, their algorithm maintains a subset ${{\mathcal{F}}}_t\subset{{\mathcal{F}}}$ based on successive elimination and solves a complicated optimization problem over ${{\mathcal{F}}}_t$. Here, the key difficulty of using an offline regression oracle like (\[eq:lsr\]) is that one cannot reformulate the complicated optimization problem over ${{\mathcal{F}}}_t$ in the form of (\[eq:lsr\]), as its objective function is far more complicated than a sum of squares. This is essentially why using an offline regression oracle (\[eq:lsr\]) is more challenging than using an offline cost-sensitive classification oracle (\[eq:csc\]): reformulating an optimization problem as (\[eq:lsr\]) is much harder than reformulating an optimization problem as (\[eq:csc\]).

**Statistical hurdle associated with constructing confidence bounds.** [@foster2018practical] propose a computationally efficient confidence-bounds-based algorithm using an offline regression oracle. However, their algorithm only has statistical guarantees under some strong distributional assumptions. An important reason is that confidence-bounds-based algorithms typically rely on accurate confidence intervals constructed for *each context*. While this is possible for a simple ${{\mathcal{F}}}$ like a linear class, it is impossible for a general ${{\mathcal{F}}}$. Here, the 