Towards Practical Lipschitz Bandits
Tianyu Weicheng Dawei Cynthia
Abstract
Stochastic Lipschitz bandit algorithms balance exploration and exploitation, and have been used for a variety of important task domains. In this paper, we present a framework for Lipschitz bandit methods that adaptively learns partitions of context- and arm-space. Due to this flexibility, the algorithm is able to efficiently optimize rewards and minimize regret, by focusing on the portions of the space that are most relevant. In our analysis, we link tree-based methods to Gaussian processes. In light of our analysis, we design a novel hierarchical Bayesian model for Lipschitz bandit problems. Our experiments show that our algorithms can achieve state-of-the-art performance in challenging real-world tasks such as neural network hyperparameter tuning.
中文速览
随机Lipschitz赌博机（stochastic Lipschitz bandit）算法在医疗试验、超参数调优等真实场景中有广泛应用，但现有方法要么对整个臂空间做均匀细化划分，要么对划分方式有严格限制，灵活性不足、实用性有限。本文提出了一个名为TreeUCB的框架，通过让决策树在算法运行过程中自适应地学习臂空间（及上下文空间）的划分，使算法能聚焦于奖励最高的区域，从而更高效地平衡探索与利用。在理论层面，作者建立了树方法与高斯过程（Gaussian process）之间的新联系，并借此设计了一种分层贝叶斯模型来构造更精细的置信上界索引，解决了传统分区方法中"同一格子内所有臂一视同仁"以及"相邻格子信息互不共享"两大痛点。实验表明，TreeUCB在神经网络超参数调优等挑战性任务上达到了最优水平，超越了现有专用基准工具，这为将Lipschitz赌博机方法推广到复杂实际问题提供了坚实的理论与实践基础。
原文 arXiv:1901.09277;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1901.09277v7