§\[sec:conclusion\]. All the proofs of our results are deferred to the appendix.

Throughout the paper, we use $O(\cdot)$ to hide constant factors, and $\widetilde{O}(\cdot)$ to hide logarithmic factors. Given ${{\mathcal{D}}}$, Let ${{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}$ denote the marginal distribution over ${{\mathcal{X}}}$. We use $\sigma(Y)$ to denote the $\sigma$-algebra generated by a random variable $Y$, and use ${\mathcal{B}}(E)$ to denote the power set of a discrete set $E$. We use ${\mathbb{N}}$ to denote the set of all positive integers, and $\mathbb{R}_{+}$ to denote the set of all non-negative real numbers. Without loss of generality, we assume that $|{{\mathcal{F}}}|\ge4$.

The Algorithm {#sec:alg}
=============

We present our algorithm, “FAst Least-squares-regression-oracle CONtextual bandits” (`FALCON`), in Algorithm \[alg:cbor\]. Note that this algorithm is specialized for the case of general finite ${{\mathcal{F}}}$. In §\[sec:extension\], we will propose a more general algorithm that works for general infinite ${{\mathcal{F}}}$, which is derived from the same idea but has some slight differences due to technical reasons.

[**input** epoch schedule $0=\tau_0<\tau_1<\tau_2<\cdots$, confidence parameter $\delta$.]{}

. . Define $$p_t(a)=\begin{cases}
        \frac{1}{K+\gamma_m\left(\widehat{f}_m(x_t,\widehat{a}_t)-\widehat{f}_m(x_t,a)\right)},&\text{for all }a\ne \widehat{a}_t,\\
        1-\sum_{a\ne\widehat{a}_t}p_t(a),&\text{for }a=\widehat{a}_t.
        \end{cases}$$

Our algorithm runs in an epoch schedule to reduce oracle calls, i.e., it only calls the oracle on certain pre-specified rounds $\tau_1,\tau_2,\tau_3,\dots$. For $m\in{\mathbb{N}}$, we refer to the 