关注我们，提升效率
title：Show Me the Whole World: Towards Entire Item Space Exploration for Interactive Personalized Recommendations
link：https://arxiv.org/pdf/2110.09905.pdf
from：WSDM 2022
1. 导读
EE是推荐系统中不变的话题，我们需要通过探索用户的兴趣来避免进入闭环，增加推荐系统的多样性和个性化，因此需要在探索和利用之间做权衡。
本文提出了两种简单高效的分层 Contextual bandit （CB）算法，使得经典的CB方法，如linUCB和汤普森采样可以用于整个商品空间，而不是小型商品集合。首先，通过自底向上的聚类来构建一颗分层树；然后，通过分层CB（HCB）算法来探索用户的兴趣。
总体思路：通过聚类将不同商品聚类，然后根据相似度构建树，最后通过经典的MAB算法进行树的遍历和参数跟新。通过聚类将大型商品空间缩小，从而使得整个算法可以在整个商品空间中应用。
2. 基础与问题
2.1 推荐系统中的UCB
推荐系统可以被看做是一个智能体，包含M个用户和N个商品。每一轮迭代t=1,2,...,T，给定用户u智能体根据策略π推荐一个商品
，然后从用户那得到反馈，比如，如果用户对其进行点击，则
，否则为0。最优策略表示为
，目标就是学习到一个策略使得累积遗憾最小，公式如下，由于现实中没有最优策略，因此将公式改写为最大化累积奖励
。
bandit算法的核心是在利用（完全基于从用户交互历史中学习的用户资料进行推荐）和探索（找出用户可能更喜欢的新项目）之间找到最佳权衡，从而使用户多样化新的兴趣有一定的机会暴露，同时系统不会在用户不感兴趣的项目上浪费太多资源。以用户为中心的算法LinUCB为例，每个商品看作是一个手臂，在第t轮，当接收到用户请求，智能体通过下式选择一个手臂
，
LinUCB的策略π是特征向量
和可学习参数θ之间的线性函数，
，其中η是高斯随机变量，表示噪声。上界Ca衡量奖励估计的不确定性。参数θ和上界C的计算公式如下，其中Dt是直到t时，交互臂的特征矩阵，α是超参数，r_t是直到t时的用户响应向量。
2.2 挑战
如LinUCB选择商品的公式所示，LinUCB 需要枚举和计算每个臂的分数，然后选择最好的一个。在现代推荐系统中，商品的数量通常非常大（数百万甚至数十亿），这使得无法计算所有商品的分数。因此，现有的典型设置是在时间
