Lipschitz Bandit Optimization with Improved Efficiency
This work addresses efficiency issues in Lipschitz bandit optimization, offering a more practical solution for researchers and practitioners in online learning and optimization.
The paper tackles the Lipschitz bandit optimization problem by proposing a novel algorithm, Tree UCB-Hoeffding, which improves practical efficiency by reducing computational cost to O(T log T) and achieving near-optimal regret up to a logarithmic factor.
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.