Bilinear Bandits with Low-rank Structure
Bilinear Bandits with Low-rank Structure
复制标题
DOI：
--
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Kwang-Sung Jun;R. Willett;S. Wright;R. Nowak
中科院分区：
文献类型：
--
作者：
Kwang-Sung Jun;R. Willett;S. Wright;R. Nowak
我们引入了具有低秩结构的双线性强盗问题，其中动作是来自两种不同实体类型的一对手臂，奖励是手臂已知特征向量的双线性函数。这个问题是由许多应用程序引起的，在这些应用程序中，学习者必须将两种不同的实体类型推荐为一个动作，例如在线约会服务中的男性/女性配对。问题中的未知数是一个$d_1$ × $d_2$矩阵$\mathbf{\Theta}^*$，等级$r \ll \min\{d_1,d_2\}$控制奖励生成。确定具有低阶结构的$\mathbf{\Theta}^*$对寻找正确的勘探开发权衡提出了重大挑战。在这项工作中，我们提出了一种新的两阶段算法，称为“探索-子空间-细化”（ESTR）。第一阶段是显式的子空间探索，而第二阶段是一种称为“近低维OFUL”（LowOFUL）的线性强盗算法，该算法通过正则化技术利用并进一步细化估计的子空间。我们证明了ESTR的遗憾为$\tilde{O}((d_1+d_2)^{3/2} \sqrt{r T})$（其中$\tilde{O}$隐藏了对数因子），它改进了朴素线性强盗约简的遗憾$\tilde{O}(d_1d_2\sqrt{T})$。我们推测ESTR的遗憾界在多对数因素下是不可改进的。
We introduce the bilinear bandit problem with low-rank structure where an action is a pair of arms from two different entity types, and the reward is a bilinear function of the known feature vectors of the arms. The problem is motivated by numerous applications in which the learner must recommend two different entity types as one action, such as a male / female pair in an online dating service. The unknown in the problem is a $d_1$ by $d_2$ matrix $\mathbf{\Theta}^*$ with rank $r \ll \min\{d_1,d_2\}$ governing the reward generation. Determination of $\mathbf{\Theta}^*$ with low-rank structure poses a significant challenge in finding the right exploration-exploitation tradeoff. In this work, we propose a new two-stage algorithm called "Explore-Subspace-Then-Refine" (ESTR). The first stage is an explicit subspace exploration, while the second stage is a linear bandit algorithm called "almost-low-dimensional OFUL" (LowOFUL) that exploits and further refines the estimated subspace via a regularization technique. We show that the regret of ESTR is $\tilde{O}((d_1+d_2)^{3/2} \sqrt{r T})$ (where $\tilde{O}$ hides logarithmic factors), which improves upon the regret of $\tilde{O}(d_1d_2\sqrt{T})$ of a naive linear bandit reduction. We conjecture that the regret bound of ESTR is unimprovable up to polylogarithmic factors.