Lipschitz Bandit Optimization with Improved Efficiency
  We consider the Lipschitz bandit optimization problem with an emphasis on
practical efficiency. Although there is rich literature on regret analysis of
this type of problem, e.g., [Kleinberg et al. 2008, Bubeck et al. 2011,
Slivkins 2014], their proposed algorithms suffer from serious practical
problems including extreme time complexity and dependence on oracle
implementations. With this motivation, we propose a novel algorithm with an
Upper Confidence Bound (UCB) exploration, namely Tree UCB-Hoeffding, using
adaptive partitions. Our partitioning scheme is easy to implement and does not
require any oracle settings. With a tree-based search strategy, the total
computational cost can be improved to $\mathcal{O}(T\log T)$ for the first $T$
iterations. In addition, our algorithm achieves the regret lower bound up to a
logarithmic factor.
