论文 | Doubly Robust Policy Evaluation and Learning

论文地址：http://www.icml-2011.org/papers/554_icmlpaper.pdf

《Doubly Robust Policy Evaluation and Learning》总结 作者为Miroslav Dud´ık、John Langford和Lihong Li，来自Yahoo! Research。

研究背景

在部分观测奖励的环境中进行决策，如互联网广告和医疗保健等领域，被称为上下文老虎机问题（contextual bandits）。该问题的核心任务是根据历史数据评估新策略的价值，但过去的数据通常不能准确代表新策略采取的行动比例，以往的方法存在偏差大或方差大的问题。

主要内容

• 问题定义与方法：

  • 现有方法：直接法（DM）估计奖励函数来评估策略价值，但可能存在偏差；逆倾向得分法（IPS）通过重要性加权来纠正历史数据中行动比例的偏差，但方差较大。
  • 双重稳健估计器（DR）：结合了奖励的估计和行动概率的估计，形式为$\hat{V}_{DR}^{\pi} = \frac{1}{|S|}\sum_{(x,h,a,r_{a})\in S}\Biggl [\frac{(r_{a} - \hat{\varrho}_{a}(x))I(\pi(x) = a)}{\hat{p}(a|x,h)} + \hat{\varrho}_{\pi(x)}(x)\Biggr]$。

• 偏差分析：

  • 定义了$\Delta(a, x) = \hat{\varrho}_{a}(x) - \varrho_{a}(x)$和$\delta(a,x,h) = 1 - p(a|x,h)/\hat{p}(a|x,h)$。
  • 得出定理1：双重稳健估计器的偏差为$|E_{S}[\hat{V}_{DR}^{\pi}] - V^{\pi}| = \frac{1}{|S|}\Big |E_{S}\Big [\sum_{(x,h)\in S}\Delta \delta \Big ]\Big |$，若过去策略和估计静止，则简化为$|E[\hat{V}_{DR}^{\pi}] - V^{\pi}| = |E_{x}[\Delta \delta ]|$。
  • 与DM和IPS对比，DR能更好地利用信息进行估计。

• 方差分析：

  • 得出定理2：双重稳健估计器的方差为$Var[\hat{V}_{DR}^{\pi}] = \frac{1}{|S|}\left(E_{x,\vec{r},a}[\varepsilon^{2}] + Var_{x}[\varrho_{\pi(x)} + \Delta \delta] + E_{x}[\frac{1 - p}{p} \cdot \Delta^{2}(1 - \delta)^{2}]\right)$。
  • 方差可分解为三个部分，与IPS估计器的方差进行对比，DR或IPS的方差取决于多种因素，而DM的方差通常较低，但偏差较大。

• 实验：

  • 多类分类与老虎机反馈：

    • 数据集设置：将分类任务转化为上下文老虎机问题，采用来自UCI仓库的基准问题进行实验。
    • 策略评估：DR技术能更准确地估计策略价值，IPS和DR无偏，DM偏差较大，且DR方差更低。
    • 策略优化：DR在所有数据集上都比IPS更具优势，能显著改进分类器，且对不同算法都有普遍适用性。
      • 估计平均用户访问量：在实际问题中对比IPS和DR，随着数据量增加，估计误差减小，DR的均方根误差（rmse）始终优于IPS，其准确性提升源于较低的方差。

结论

双重稳健政策估计是一种有效的技术，通常能改进广泛使用的逆倾向得分法，实验结果证实了其能给出更可靠和准确的估计，未来有望在改进上下文老虎机算法中得到广泛应用。