文章名称

【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]方法高方差的风险。

方法细节

问题引入

准确的离线评估新模型（策略）的潜在收益提升十分重要，离线的估计方法被称为counterfactual或者off-policy估计方法。Capped importance sampling或normalised importance sampling等传统的反事实估计方法，由于没有很好的平衡偏差与方差，导致性能欠佳。为了克服这个问题，作者建模估计量的偏差，而不是对偏差进行限制，并提出了新的估计方法NCIS。

具体做法

在介绍具体方法之前，首先形式化的定义，推荐系统场景下，所谓的在线AB实验以及离线AB实验，

• 作者关注的推荐模型是排序模型，返回Top-商品
• 推荐模型（也被成为推荐策略，由模型产出）分别表示线上和目标推荐模型。
• 推荐时的上下文特征和物品特征统一表示为随机变量，对应的top-列表表示为随机变量。
• 对应推荐列表会得到具体的反馈（被表示为reward），这个反馈可以是点击或者是购买等。
• 离线评估的目标是估计两种策略平均收益的差值，被作者定义为average treatment effect，具体公式如下图所示。
  average treatment effect

• 其中，某个策略的期望收益公式如下图所示。

  
  expected reward of policy

针对上述average treatment effect的估计，在线AB和离线AB试验的差异如下，

• 在线AB试验时，受试对象被随机分为两组，可以利用如下公式估计。
  

  average treatment effect estimation with online AB

• 在有限数据集上，利用经验估计得到对在线AB试验的估计值。

  empirical average treatment effect estimation with online AB

• 离线AB试验时，我们只有线上策略的历史数据集。其中表示收集到的线上观测数据数量。可以直接利用经验估计的方法估计线上策略的期望收益。

• 相反，由于没有目标策略的数据，无法进行经验估计。一种主流做法是，利用importance sampling 或者说叫做inverse propensity score[3]来纠正经验估计的偏差。具体的公式如下图所示。

  empirical average treatment effect estimation with offline AB

在推荐场景下，由于动作空间巨大（从多至亿甚至十亿的候选物品中选取top-个物品作为推荐列表，排列结果有），IS/IPS方法受到高方差的影响，尽管它是无偏的。为了解决这个问题，许多采用传统的方差消除方法（控制变量法）的IS/IPS的变种方法被提出，但由于利用的是无偏或一致估计量，所以仍然会受到高方差的影响。 另一类方法是capped importance sampling[1]，通过平衡偏差和方差来提升性能。

减少方差的方法

本节介绍了作者研究的问题背景，即进行离线AB实验，通过模拟在线AB来快速迭代原型。并且，介绍了问题的形式化表示以及现有方法存在的问题。下一节继续介绍问题的细节和原因，以及作者提出的解决方案。

心得体会

High Variance

推荐场景下，动作空间巨大导致普通的方差纠正方法失效。之前也介绍过一些文章，提到利用独立性假设，消除组合的影响，简化推荐列表，缩小动作空间，详见因果推断推荐系统工具箱 - RIPS（一）。但这种方法已经被证实假设过于强了，并且交互影响的地位非常重要。

文章引用

[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.