文章名称
【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。
在给定时，延迟的转化反馈可以被表示为函数
。因为存在用户转化但未被观测到（数据没有收集到）的情况，所以
是对
的有偏估计。理想情况下，我们希望对真实的delayed reward（公式2）进行无偏估计，但通常观测都是有偏的（公式3）。其中，
分别代表，biased delayed reward和true delayed reward。
由于，我们观测的数据一定比真实转化数据少，所以如下图所示的公式一定满足。
作者通过估计来实现无偏估计，此处的
就是上面说的反事实重要性权重。
修改后的优化目标为，。论文的附录给出了无偏的理论证明，感兴趣的同学可以参考原文。
作者强调权重可能大于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]。
可以被理解，用户真实转化的情况（
）没有在
的时间间隔内被观测到的概率的对数。
作者利用如下图所示的公式求得模型参数，其中
。
如前所述，模型的reward是点击和转化的线性组合，经过加权后，可以直接把点击随机变量和观测转化变量
（不是实际转化变量
）带入线性组合公式。得到如下图所示的，调权后的reward。
Model Training and Online Recommendation
有了调整后的reward ，作者利用[3]中的方法进行batched policy update，
- 记录上下文向量和调整后的reward，
。其中
是上下文向量的维度，
表示动作
在整个episode结束的时候，共被采用了多少次。
- 利用上下文向量和调整后的reward计算协方差矩阵，
。
- 在岭回归的场景下，可以得到策略参数的闭式解。
。
- 最后，利用泛化的UCB方法，得到策略
，具体计算公式如下图所示。
image
随后，利用如下图所示的公式，依据新的policy进行在线推荐。
代码实现
reward调整过程的伪代码如下图所示。
心得体会
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.
