  Contextual bandits serve as a fundamental model for many sequential decision
making tasks. The most popular theoretically justified approaches are based on
the optimism principle. While these algorithms can be practical, they are known
to be suboptimal asymptotically. On the other hand, existing asymptotically
optimal algorithms for this problem do not exploit the linear structure in an
optimal way and suffer from lower-order terms that dominate the regret in all
practically interesting regimes. We start to bridge the gap by designing an
algorithm that is asymptotically optimal and has good finite-time empirical
performance. At the same time, we make connections to the recent literature on
when exploration-free methods are effective. Indeed, if the distribution of
contexts is well behaved, then our algorithm acts mostly greedily and enjoys
sub-logarithmic regret. Furthermore, our approach is adaptive in the sense that
it automatically detects the nice case. Numerical results demonstrate
significant regret reductions by our method relative to several baselines.
