Stochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making
Stochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making
复制标题
用于多维在线决策的随机低秩张量老虎机
DOI：
10.1080/01621459.2024.2311364
复制
发表时间：
2020
影响因子：
3.7
通讯作者：
W. Sun
中科院分区：
文献类型：
--
作者：
Jie Zhou;Botao Hao;Zheng Wen;Jingfei Zhang;W. Sun
多维度在线决策在在线推荐、数字营销等许多实际应用中发挥着至关重要的作用。在这些问题中，每次的决策都是来自不同类型实体的选择的组合。为了解决这个问题，我们引入了随机低秩张量老虎机，这是一类其平均奖励可以表示为低秩张量的老虎机。我们考虑两种设置，没有上下文的张量老虎机和有上下文的张量老虎机。在第一种设置中，该平台的目标是找到具有最高预期奖励的最佳决策，即真实奖励张量的最大条目。在第二种设置中，张量的某些模式是上下文，其余模式是决策，目标是在给定上下文信息的情况下找到最佳决策。我们针对没有上下文的张量强盗提出了两种学习算法张量消除和张量历元贪婪，并为它们推导了有限时间遗憾界限。与现有的竞争方法相比，张量消除具有最佳的总体遗憾界限，并且张量历元贪婪对奖励张量的维度具有更强烈的依赖性。此外，我们还开发了一种实用的贝叶斯算法，称为张量集成采样，用于具有上下文的张量强盗。在线广告数据中的广泛模拟和真实分析支持了我们的理论发现，并表明我们的算法优于忽略张量低秩结构的各种最先进的方法。
Multi-dimensional online decision making plays a crucial role in many real applications such as online recommendation and digital marketing. In these problems, a decision at each time is a combination of choices from different types of entities. To solve it, we introduce stochastic low-rank tensor bandits, a class of bandits whose mean rewards can be represented as a low-rank tensor. We consider two settings, tensor bandits without context and tensor bandits with context. In the first setting, the platform aims to find the optimal decision with the highest expected reward, a.k.a, the largest entry of true reward tensor. In the second setting, some modes of the tensor are contexts and the rest modes are decisions, and the goal is to find the optimal decision given the contextual information. We propose two learning algorithms tensor elimination and tensor epoch-greedy for tensor bandits without context, and derive finite-time regret bounds for them. Comparing with existing competitive methods, tensor elimination has the best overall regret bound and tensor epoch-greedy has a sharper dependency on dimensions of the reward tensor. Furthermore, we develop a practically effective Bayesian algorithm called tensor ensemble sampling for tensor bandits with context. Extensive simulations and real analysis in online advertising data back up our theoretical findings and show that our algorithms outperform various state-of-the-art approaches that ignore the tensor low-rank structure.
DOI：
10.1146/annurev-statistics-042720-020816
发表时间：
2021-03
期刊：
--
影响因子：
--
作者：
Xuan Bi;Xiwei Tang;Yubai Yuan;Yanqing Zhang;A. Qu
通讯作者：
Xuan Bi;Xiwei Tang;Yubai Yuan;Yanqing Zhang;A. Qu