文章名称

【AAAI-2019】【Renmin University of China/Tencent】Counterfactual Reward Modification for Streaming Recommendation with Delayed Feedback

核心要点

文章旨在解决流式推荐场景中延迟反馈的问题。流失场景要求快速收集训练样本，频繁重新训练推荐模型，这些都与延迟反馈存在冲突。现有方法要么忽略未观测到的反馈，要么利用启发式的方法调整反馈信息，引入了偏差并影响了模型的精度。作者流失推荐看作是序列决策问题，利用batch bandit方法结合反事实重要性采样，每一回合在调整过reward的训练样本上进行训练，并用于对下一个回合的决策进行预测。

上一节讲解了流式推荐系统中，用户转化反馈延迟的问题背景以及作者对问题的抽象建模思路，概括了方法的要点和步骤，本节继续介绍各个步骤的细节。

方法细节

问题引入

如上一节所述，CBDF的算法流程主要是，

• 利用反事实重要性采样，得到权重，调整观测数据的reward；

• 更新在线推荐模型，并进行在线推荐；

• 收集新的数据用于下一轮更新迭代。

那么，存在两个问题，

• 如何得到权重，所谓的反事实重要性采样又是什么？

• 如何进行模型更新，以及推荐并收集数据？

具体做法

Counterfactual Reward Modification

延迟反馈的无偏估计

如前所述，CBDF的reward是点击和转化的线性组合，即，其中。

所谓的反事实重要性权重，是利用如下公式实现Important Sampling。

image

在给定时，延迟的转化反馈可以被表示为函数。因为存在用户转化但未被观测到（数据没有收集到）的情况，所以是对的有偏估计。理想情况下，我们希望对真实的delayed reward（公式2）进行无偏估计，但通常观测都是有偏的（公式3）。其中，分别代表，biased delayed reward和true delayed reward。

image image

由于，我们观测的数据一定比真实转化数据少，所以如下图所示的公式一定满足。

image

作者通过估计来实现无偏估计，此处的就是上面说的反事实重要性权重。

修改后的优化目标为，。论文的附录给出了无偏的理论证明，感兴趣的同学可以参考原文。

作者强调权重可能大于1，意味着观测到的转化数据应该受到重视。

延迟反馈的重要性计算

上述权重（公式4）由于包含了的笛卡尔积，直接求期望计算量巨大。作者受到[4]的启发，提出了一种反事实学习的方法来直接预测（predict）权重。

作者引入counterfactual deadline 的概念（上一节代码中有提到），本质就是一个介于episode开始和结束之间的时间戳，即。

利用counterfactual deadline，把上一个epsiode（或之前的所有episode收集到）的数据集分别为observed set和hold-out set。在hold-out set观测到转化的样本是所谓的delayed转化样本。

在observed set中的被当做训练样本得到训练集。其中，是一个episode经历的所有step（也就是收集了多少轮推荐结果），分别表示在观测集合的时候，是否有观测到转化以及counterfactual deadline与用户点击的时间间隔。由于在里所有的样本，因此如果，那么。值得注意的是，这个数据集是关于特定动作的。

利用这些样本可以用来训练一个生存模型模型（Survival Model），得到如下图所示的reward权重，其中是模型的参数。该生存模型主要是预测用户的转化反馈是否能够被观测到，即。其中，是生存模型的hazard function[1,2]。可以被理解，用户真实转化的情况（）没有在的时间间隔内被观测到的概率的对数。

image

作者利用如下图所示的公式求得模型参数，其中。

image

如前所述，模型的reward是点击和转化的线性组合，经过加权后，可以直接把点击随机变量和观测转化变量（不是实际转化变量）带入线性组合公式。得到如下图所示的，调权后的reward。

image

Model Training and Online Recommendation

有了调整后的reward ，作者利用[3]中的方法进行batched policy update，

• 记录上下文向量和调整后的reward，。其中是上下文向量的维度，表示动作在整个episode结束的时候，共被采用了多少次。

• 利用上下文向量和调整后的reward计算协方差矩阵，。

• 在岭回归的场景下，可以得到策略参数的闭式解。。

• 最后，利用泛化的UCB方法，得到策略，具体计算公式如下图所示。

image

随后，利用如下图所示的公式，依据新的policy进行在线推荐。

image

代码实现

reward调整过程的伪代码如下图所示。

image

心得体会

Counterfactual Important Sampling

个人感觉，方法并没有特别多的利用反事实的框架，而是利用了时间戳前移构造了观测数据集。当然，也可以理解为，作者是在回答一个反事实问题：“如果收集数据的时间戳提前到counterfactual deadline，转化情况会怎么变化“？但使用了之前很多episode收集的数据，完全可以利用真实的转化来构造数据集。除非，要求时间上足够接近。

文章引用

[1] J. D. Kalbfleisch and R. L. Prentice. 2002. The Statistical Analysis of Failure Time Data (2nd Edition). John Wiley & Sons.

[2] Qingyun Wu, Hongning Wang, Liangjie Hong, and Yue Shi. 2017. Returning is Believing: Optimizing Long-term User Engagement in Recommender Systems. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 1927–1936.

[3] Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose H. Blanchet, Peter W. Glynn, and Yinyu Ye. 2020. Sequential Batch Learning in Finite-Action Linear Contextual Bandits. CoRR abs/2004.06321 (2020).

[4] ShotaYasui,GotaMorishita,KomeiFujita,andMasashiShibata.2020.AFeedback Shift Correction in Predicting Conversion Rates under Delayed Feedback. In Proceedings of the Web Conference 2020. 2740–2746.