A Simple Unified Framework for High Dimensional Bandit Problems
A Simple Unified Framework for High Dimensional Bandit Problems
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Wenjie Li;Adarsh Barik;J. Honorio
中科院分区：
文献类型：
--
作者：
Wenjie Li;Adarsh Barik;J. Honorio
具有低维结构的随机高维强盗问题在网络广告、药物研发等领域有着广泛的应用。在这项工作中，我们针对这类问题提出了一个简单的统一算法，并给出了算法遗憾上界的一般分析框架。我们证明了在一些温和的单一假设下，我们的算法可以应用于不同的高维Banddit问题。我们的框架利用低维结构来指导问题中的参数估计，因此我们的算法在Lasso Banddit中获得了类似的后悔界作为理智检验，并且在一个新的问题：多智能体Lasso Banddit中获得了对数依赖于低阶矩阵Banddit、群稀疏矩阵Bdidit和新问题中的维度的新的界。
Stochastic high dimensional bandit problems with low dimensional structures are useful in different applications such as online advertising and drug discovery. In this work, we propose a simple unified algorithm for such problems and present a general analysis framework for the regret upper bound of our algorithm. We show that under some mild unified assumptions, our algorithm can be applied to different high-dimensional bandit problems. Our framework utilizes the low dimensional structure to guide the parameter estimation in the problem, therefore our algorithm achieves the comparable regret bounds in the LASSO bandit as a sanity check, as well as novel bounds that depend logarithmically on dimensions in the low-rank matrix bandit, the group sparse matrix bandit, and in a new problem: the multi-agent LASSO bandit.