Improved Path-length Regret Bounds for Bandits
  We study adaptive regret bounds in terms of the variation of the losses (the
so-called path-length bounds) for both multi-armed bandit and more generally
linear bandit. We first show that the seemingly suboptimal path-length bound of
(Wei and Luo, 2018) is in fact not improvable for adaptive adversary. Despite
this negative result, we then develop two new algorithms, one that strictly
improves over (Wei and Luo, 2018) with a smaller path-length measure, and the
other which improves over (Wei and Luo, 2018) for oblivious adversary when the
path-length is large. Our algorithms are based on the well-studied optimistic
mirror descent framework, but importantly with several novel techniques,
including new optimistic predictions, a slight bias towards recently selected
arms, and the use of a hybrid regularizer similar to that of (Bubeck et al.,
2018).
  Furthermore, we extend our results to linear bandit by showing a reduction to
obtaining dynamic regret for a full-information problem, followed by a further
reduction to convex body chasing. We propose a simple greedy chasing algorithm
for squared 2-norm, leading to new dynamic regret results and as a consequence
the first path-length regret for general linear bandit as well.
