to $O(\log\log T)$ if $T$ is known. Notably, this can be understood as a “triply exponential” speedup over previous work: (1) compared with the previously known regret-optimal algorithm [@agarwal2012contextual] for this setting, which requires enumerating over ${{\mathcal{F}}}$ at each round, our algorithm accesses the function class only through an offline regression oracle, thus typically avoids an exponential cost at each round; (2) compared with the sub-optimal algorithm of [@foster2018practical] which requires $\widetilde{O}(\sqrt{T})$ calls for non-convex ${{\mathcal{F}}}$, and the classification-oracle-based algorithm of [@agarwal2014taming] which requires $\widetilde{O}(\sqrt{KT/\log|{{\mathcal{F}}}|})$ calls to a computationally expensive classification oracle, our algorithm requires only $O(\log T)$ calls to a simple regression oracle, which implies an exponential speedup over all existing provably optimal oracle-efficient algorithms, even when we ignore the difference between regression and classification oracles; (3) when the number of rounds $T$ is known in advance, our algorithm can further reduce the number of oracle calls to $O(\log\log T)$, which is an exponential speedup by itself. Our algorithm is thus highly computational efficient.

The statistical analysis of our algorithm is also quite interesting. Unlike existing analysis of other realizability-based algorithms in the literature, we do not directly analyze the decision outcomes of our algorithm — instead, we find 