An efficient high-probability algorithm for Linear Bandits
  For the linear bandit problem, we extend the analysis of algorithm CombEXP
from [R. Combes, M. S. Talebi Mazraeh Shahi, A. Proutiere, and M. Lelarge.
Combinatorial bandits revisited. In C. Cortes, N. D. Lawrence, D. D. Lee, M.
Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing
Systems 28, pages 2116--2124. Curran Associates, Inc., 2015. URL
http://papers.nips.cc/paper/5831-combinatorial-bandits-revisited.pdf] to the
high-probability case against adaptive adversaries, allowing actions to come
from an arbitrary polytope. We prove a high-probability regret of
\(O(T^{2/3})\) for time horizon \(T\). While this bound is weaker than the
optimal \(O(\sqrt{T})\) bound achieved by GeometricHedge in [P. L. Bartlett, V.
Dani, T. Hayes, S. Kakade, A. Rakhlin, and A. Tewari. High-probability regret
bounds for bandit online linear optimization. In 21th Annual Conference on
Learning Theory (COLT 2008), July 2008.
http://eprints.qut.edu.au/45706/1/30-Bartlett.pdf], CombEXP is computationally
efficient, requiring only an efficient linear optimization oracle over the
convex hull of the actions.
