We consider the general (stochastic) contextual bandit problem under the realizability assumption, i.e., the expected reward, as a function of contexts and actions, belongs to a general function class $\mathcal{F}$. We design a fast and simple algorithm that achieves the statistically optimal regret with only ${O}(\log T)$ calls to an offline least-squares regression oracle across all $T$ rounds (the number of oracle calls can be further reduced to $O(\log\log T)$ if $T$ is known in advance). Our algorithm provides the first universal and optimal reduction from contextual bandits to offline regression, solving an important open problem for the realizable setting of contextual bandits. Our algorithm is also the first provably optimal contextual bandit algorithm with a logarithmic number of oracle calls.

该论文考虑了具有普适性假设的（随机性）上下文赌博问题，设计了一种快速、简单的算法，在所有$T$回合中通过对离线回归神谕的$logT$次调用实现了统计优化遗憾。我们的结果提供了第一个从上下文赌徒到离线回归的通用和最优化简化，解决了上下文赌徒文献中的一个重要开放问题。我们的结果表明，离线回归中的任何进展都将立即在上下文赌客中进行统计和计算翻译。

绕开怪物：一种更快、更简单的实现环境下上下文二项式算法