  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.
