An Asymptotically Optimal Primal-Dual Incremental Algorithm for
  Contextual Linear Bandits
  In the contextual linear bandit setting, algorithms built on the optimism
principle fail to exploit the structure of the problem and have been shown to
be asymptotically suboptimal. In this paper, we follow recent approaches of
deriving asymptotically optimal algorithms from problem-dependent regret lower
bounds and we introduce a novel algorithm improving over the state-of-the-art
along multiple dimensions. We build on a reformulation of the lower bound,
where context distribution and exploration policy are decoupled, and we obtain
an algorithm robust to unbalanced context distributions. Then, using an
incremental primal-dual approach to solve the Lagrangian relaxation of the
lower bound, we obtain a scalable and computationally efficient algorithm.
Finally, we remove forced exploration and build on confidence intervals of the
optimization problem to encourage a minimum level of exploration that is better
adapted to the problem structure. We demonstrate the asymptotic optimality of
our algorithm, while providing both problem-dependent and worst-case
finite-time regret guarantees. Our bounds scale with the logarithm of the
number of arms, thus avoiding the linear dependence common in all related prior
works. Notably, we establish minimax optimality for any learning horizon in the
special case of non-contextual linear bandits. Finally, we verify that our
algorithm obtains better empirical performance than state-of-the-art baselines.
