Thompson sampling (e.g., @agrawal2013thompson [@russo2018tutorial]). While these approaches have received practical success in several scenarios (@li2010contextual), their theoretical guarantee and computational tractability critically rely on their strong assumptions on ${{\mathcal{F}}}$, which restrict their usage in other scenarios (@bietti2018contextual).

To our knowledge, [@agarwal2012contextual] is the first paper studying contextual bandits with a general finite ${{\mathcal{F}}}$, under the minimal realizability assumption. They propose a eliminaton-based algorithm, namely `Regressor Elimination`, that achieves the optimal $\widetilde{O}(\sqrt{KT\log|{{\mathcal{F}}}|})$ regret. However, their algorithm is computational inefficient, as it enumerates over the whole function class and requires $\Omega(|{{\mathcal{F}}}|)$ computational cost at each round (note that the size of ${{\mathcal{F}}}$ is typically extremely large). The computational issues of [@agarwal2012contextual] are resolved by [@foster2018practical], who propose an oracle-efficient contextual bandit algorithm `RegCB`, which always accesses the function class through a weighted least-squares regression oracle that solves $$\label{eq:wlsr}
\arg\min_{f\in{{\mathcal{F}}}}\sum_{s=1}^t w_s(f(x_s,a_s)-y_s)^2$$ for any given input sequence $(w_1,x_1,a_1,y_1),\cdots,(w_t,x_t,a_t,y_t)\in\mathbb{R}_{+}\times{{\mathcal{X}}}\times{{\mathcal{A}}}\times[0,1]$. As [@foster2018practical] mention, the above oracle can often be solved efficiently and is very common in machine learning practice, far more reasonable than the cost-sensitive classification oracle (\[eq:csc\]). However, unlike `Regressor Elimination`, the `RegCB` algorithm is not minimax optimal — its worst-case regret could be as large as $\widetilde{\Omega}(T)$. Whether the optimal $\widetilde{O}(\sqrt{KT\log|{{\mathcal{F}}}|})$ regret is 