2020年12月5日,星期六

分布稳健的上下文强盗学习

这篇博客文章是关于通过分布稳健性来改善非政策性背景下的土匪学习的。我将提供一些理论背景并概述 vowpal wabbit的实现。这些材料中的一些在 NeurIPS博览会演讲视频,并且其他材料在 接受的论文.

动机

在上下文匪徒的非政策学习中,我们的目标是从历史数据中生成最佳策略,而我们无法控制生成数据的历史日志记录策略。 (注意,由于推理,训练和模型更新之间的延迟,以闭环配置运行的生产系统实际上仍在进行非策略学习。)非策略学习类似于监督学习,简化为策略价值估计器的优化;但是,政策价值估算的准确性取决于所评估的政策与生成数据的政策之间的不匹配,因此对于不同的政策可能会大不相同(与监督学习不同,在假设类别中,估算器分辨率的差异较小在实践中发音)。要了解这种影响,请考虑IPS政策价值估算器$$ \ hat {V}(\ pi; \ mu)= \ frac {1} {N} \ sum_ {n \ in N} \ frac {\ pi(a_n | x_n)} {\ mu(a_n | x_n)} r_n , $$ 其中$ \ mu $是历史策略,$ \ pi $是要估计的策略,我们的历史数据由元组$ \ {(x_n,a_n,r_n)\} $组成。如果$ \ pi $频繁执行$ \ mu $很少执行的操作,导致估算器执行以下操作,则重要性权重$ \ frac {\ pi(a_n | x_n)} {\ mu(a_n | x_n)} $可能会很大。对一些具有重要重要性的示例高度敏感。即使我们使用$ \ pi = \ mu $初始化学习,随着优化的进行,由于学习算法遇到具有高奖励的稀有事件,因此$ \ pi $会导致动作分布越来越不同于$ \ mu $。为了克服这种过拟合技术,我们将引入正则化。

分布稳健优化

分布稳健的优化是用于规范化机器学习目标的通用方法。基本思想是将观察到的数据视为一种可能的数据分布(“经验分布”),然后在所有分布中优化最坏情况的结果“sufficiently close” to the 经验分布. In the case of IPS we can find the smallest policy value estimate over a set of distributions that are close in KL divergence to the 经验分布, $$ \begin{alignat}{2} &\!\ min_ {P \ in \ Delta}& \qquad &\ mathbb {E} _P \ left [w r \ right],\\ &\text{subject to} & &\ mathbb {E} _P \ left [w \ right] = 1,\\ & & &\ mathbb {E} _N \ left [\ log \ left(P \ right)\ right] \ geq \ phi。 \end{alignat} $$,其中$ w \ doteq \ frac {\ pi(a | x)} {\ mu(a | x)} $。事实证明,您可以廉价地(在对偶中)执行此操作,并且可以根据所需的渐近置信度来计算$ \ phi $的值。这些结果来自于该领域的经典著作 经验似然.

上面的问题找到了下界。找到一个上限是类似的,从而得出论文的置信区间:

经验似然置信区间是更紧密的高斯区间。 未显示:经验似然CI的覆盖范围比二项式(Clopper-Pearson)更好。


当我们进行分布式鲁棒优化时,实际上是在优化策略值的下限。上图中的绿色曲线是一个Clopper-Pearson区间,该区间确实有保证的覆盖范围,但是它是如此之宽,以至于优化下限在数据量很大之前不会有多大作用。蓝色的“经验似然”曲线产生的间隔更紧密,这意味着下限优化将仅使用适度的数据来引发有趣的策略排序。

实际上,即使经验平均值(经验IPS值)是固定的,下界也为:

  • 当策略通过重要性权重远大于1的少数事件和重要性权重接近于零的许多事件来产生价值时,则较小;和
  • 当政策通过重要性权重接近1的许多事件产生价值时,该值会更大。
这正是我们想要的正则化类型。直观地讲,对一些观察到的示例敏感的任何估计量(也称为 高杠杆)将受到更大的惩罚,因为“cheap”,以KL散度衡量,以减少出现这些问题的可能性。

在Vowpal Wabbit中实施

要激活功能,请添加 --cb_dro 标记为您在VW中的上下文强盗命令行。请注意,这只会影响训练,因此,如果您只是预测,则不会看到任何区别。希望使用默认的超参数,您会发现学习策略的质量有所提高,例如 这个要点.

大众内部在每个示例上都从上面解决了下限优化问题。有一些修改:

  1. 如上所述,这在计算上会太昂贵,但是从KL散度切换到Cressie-Read功率散度可以让我们得出一种快速计算的闭式解。
  2. 如上所述,下限要求始终记住所有政策决策。取而代之的是,我们为Cressie-Read的时间和空间$ O(1)$中的幂散度积累了足够的统计量。
  3. 为了跟踪非平稳性,我们使用足够统计量的指数加权移动平均值。超参数 --cb_dro_tau 指定衰减时间常数。
与往常一样,YMMV。