Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms
Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithms
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Qin Ding;Yi-Wei Liu;Cho-Jui Hsieh;J. Sharpnack
中科院分区：
文献类型：
--
作者：
Qin Ding;Yi-Wei Liu;Cho-Jui Hsieh;J. Sharpnack
随机上下文强盗问题对探索和利用之间的权衡进行建模，具有许多实际应用，包括推荐系统、在线广告和临床试验。与许多其他机器学习算法一样，上下文强盗算法通常具有一个或多个超参数。例如，在大多数最优随机上下文强盗算法中，存在一个未知的探索参数，该参数控制探索和利用之间的权衡。正确选择超参数对于上下文老虎机算法的良好性能至关重要。然而，在上下文强盗环境中使用离线调优方法来选择超参数是不可行的，因为没有预先收集的数据集并且必须实时做出决策。为了解决这个问题，我们首先提出了一种用于自动调整探索参数的两层 bandit 结构，并将其进一步推广到 Syndicated Bandits 框架，该框架可以在上下文 bandit 环境中动态学习多个超参数。我们得出了我们提出的 Syndicated Bandits 框架的遗憾界限，并表明它可以避免遗憾与要调整的超参数数量呈指数关系。此外，它在某些情况下实现了最佳后悔界限。 Syndicated Bandits 框架足够通用，可以处理许多流行的上下文 bandit 算法中的调整任务，例如 LinUCB、LinTS、UCB-GLM 等。在合成数据集和真实数据集上的实验验证了我们提出的框架的有效性。
The stochastic contextual bandit problem, which models the trade-off between exploration and exploitation, has many real applications, including recommender systems, online advertising and clinical trials. As many other machine learning algorithms, contextual bandit algorithms often have one or more hyper-parameters. As an example, in most optimal stochastic contextual bandit algorithms, there is an unknown exploration parameter which controls the trade-off between exploration and exploitation. A proper choice of the hyper-parameters is essential for contextual bandit algorithms to perform well. However, it is infeasible to use offline tuning methods to select hyper-parameters in contextual bandit environment since there is no pre-collected dataset and the decisions have to be made in real time. To tackle this problem, we first propose a two-layer bandit structure for auto tuning the exploration parameter and further generalize it to the Syndicated Bandits framework which can learn multiple hyper-parameters dynamically in contextual bandit environment. We derive the regret bounds of our proposed Syndicated Bandits framework and show it can avoid its regret dependent exponentially in the number of hyper-parameters to be tuned. Moreover, it achieves optimal regret bounds under certain scenarios. Syndicated Bandits framework is general enough to handle the tuning tasks in many popular contextual bandit algorithms, such as LinUCB, LinTS, UCB-GLM, etc. Experiments on both synthetic and real datasets validate the effectiveness of our proposed framework.