Lipschitz Bandit Optimization with Improved Efficiency

04/25/2019
by   Xu Zhu, et al.
12

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 O(T T) for the first T iterations. In addition, our algorithm achieves the regret lower bound up to a logarithmic factor.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset