文章名称
【WSDM-2020】【Criteo Research】Offline A/B testing for Recommender Systems
核心要点
文章旨在构造实际可用的推荐模型离线评估器，实现没有线上AB实验的情况下，评估目标模型相对线上模型的潜在提升，快速迭代原型，筛选策略。作者提出了两个capped importance sampling[1]的两个变种，解决capped importance sampling假设过于不切实际的问题，并避免Basic Importance Sampling[3,4]与Doubly Robust[2]方法高方差的风险。
上一节介绍了作者研究的问题背景，即进行离线AB实验，通过模拟在线AB来快速迭代原型。并且，介绍了问题的形式化表示以及现有方法存在的问题。本节继续介绍问题的细节和原因，以及作者提出的解决方案。
方法细节
问题引入
如前所述，推荐系统场景下，模型的动作空间巨大（推荐列表组合数巨大）。因此，IPS方法会因为分母的概率过小造成极大的方差。现有方法主要利用Control Variates来缩减方差，不过收益有限，因此作者分析了这些方法的本质和问题，基于capped importance sampling，提出了NCIS。
具体做法
Control Variates
控制变量缩减方差的核心思路是，
寻找另一个具有已知期望的随机变量，并且该变量与要估计的变量具有相关性，通过控制这个变量来减少待估计的方差。
DR
DR方法是利用我们已有的知识对特征到收益的映射关系进行建模，相当于把外部知识融入收益的模型结构中[2]。具体地，我们假设在给定和
的情况下，可以利用模型
得到对应的收益
，其计算公式如下所示。
DR是无偏的，其之所以可以缩减方差是因为和真实的收益
具有相关性（因为我们是回归，模型学习的就是相关性），可以作为control variates，因此可以从理论上保证减小方差，具体可以参见引文。
然而，该方法具有一些缺陷，
- 当动作空间很大的时候很难准确的估计
。
- 当
的估计也很难准确。特别是在推荐场景，当真实的期望收益大约为
左右，这种情况很难把
NIS
基于，可以利用经验方法
当做全局比例控制变量。由此可以得到normalized importance sampling (NIS)[6,7]，其具体公式如下图所示。
其中，归一化常数等于重要性权重的总和，并且期望等于（数据集中的样本数量）。NIS对预期收益的估计是有偏的，但方差比IS要低（因为引入了一个control variable）。不过，该方法仍然是预期收益的期望
的一致估计量，随着
增大而渐进一致。然而，最终降低方差的效果是有限的，让然和普通的IS差别不大。
Capped importance sampling
作者表示，如果不引入偏差，就需要大量的外部知识来消除方差的影响（也就是说还是需要限制模型的复杂度等）。因此，作者讨论了引入一定偏差的capped importance sampling，其中有两种capping的方法，max capping和zero capping，其具体公式如下图所示。
其中，分别表示两种策略下的capped weight，zero capping的思路是，只有weight小于某个阈值c的样本才被用来计算，而max capping则用统一的阈值
代替了超过该阈值的weight。两者本质上差别不大，作者只讨论了max capping，直觉上，这两种方法都只是考虑了目标收益
的一部分（子集），其具体公式如下图所示。
可以看出，capping是有偏的，偏差项记作。如果只顾及子集
，偏差项的影响会比较大，只有当新策略
所频繁选择的动作的得分都比较低时，才会消除这个偏差，显然这是不可能的，因为我们要的就是新策略来提升就策略的性能，两者还是有比较大差异的。尽管各种方法[2,5]被引入来解决这个问题，但是仍然只能保证最坏的情况下，结果是合理的。
本节介绍了DR，NIS，capping IS方法的问题，下节介绍capping IS的阈值选取以及度作者的启发。并介绍作者提出的NCIS方法。
心得体会
capping
个人理解，capping，其实就是忽略那些证据不充分的。悖论的是，我们有需要探索这部分空间中，新策略的性能。因此，需要利用其他额外的信息，来帮助模型在不同的空间有不同的capping，这也是作者的思路。
文章引用
[1] Léon Bottou and Jonas Peters. 2013. Counterfactual reasoning and learning systems: the example of computational advertising. Proceedings of Journal of Machine Learning Research (JMLR).
[2] Miroslav Dudik, John Langford, and Lihong Li. 2011. Doubly robust policy evaluation and learning. Proceedings of the 28th International Conference on Machine Learning (ICML).
[3] JM Hammersley and DC Handscomb. 1964. Monte Carlo Methods. Chapter.
[4] Daniel G Horvitz and Donovan J Thompson. 1952. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association.
[5] Andreas Maurer and Massimiliano Pontil. 2009. Empirical Bernstein bounds and sample variance penalization. Proceedings of the 22nd Annual Conference on Learning Theory (COLT).
[6] MJD Powell and J Swann. 1966. Weighted uniform sampling: a Monte Carlo technique for reducing variance. Journal of Applied Mathematics.
[7] AdithSwaminathanandThorstenJoachims.2015.TheSelf-NormalizedEstimator for Counterfactual Learning. Proceeding of Neural Information Processing Systems (NIPS).
