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 $很少执行的操作,导致估计量对一些具有重要重要性的示例高度敏感。即使我们使用$ \ 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。

2020年7月17日,星期五

凹凸凹面游戏

如果您现在需要解决凸优化问题,那么您的情况就很好。任何形式为$$的问题
\ begin {alignat} {2}
&\!\ inf_z&\ qquad&f(z)\\
& \ text {根据}& & h(z) = 0 \\
&&&g(z)\ preceq 0
\ end {alignat}
$$,其中$ f $和$ g $是凸的,而$ h $是仿射的,可以用几个优秀的免费提供的软件包来攻击:我目前最喜欢的是 cvxpy,使用起来很愉快。如果您有很多变量而不是很多约束,则可以解决一个双重问题。最终看起来像$$
\ begin {alignat} {2}
&\!\ sup_ {x}和\ qquad&L(x)\\
& \ text {根据}& & \tilde{h}_x(x) = 0 \\
&&&\\ tilde {g} _x(x)\ preceq 0
\ end {alignat}
$$,其中$ L $是凹面的,假设您很幸运,并且可以分析地消除所有原始变量$ z $,从而仅保留对偶变量$ x $。但是,如果您不能消除所有原始变量,而只能消除其中的大多数,那该怎么办?您可能会遇到类似$$的问题
\ begin {alignat} {2}
&\!\ sup_ {x} \ inf_y&\ qquad&L(x,y)\\
& \ text {根据}& & \tilde{h}_x(x) = 0 \\
&&&\\ tilde {g} _x(x)\ preceq 0 \\
&&&\\ tilde {h} _y(y)= 0 \\
&&&\\ tilde {g} _y(y)\ preceq 0
\ end {alignat}
$$,其中$ \ tilde {g} _x $和$ \ tilde {g} _y $是凸的,而$ \ tilde {h} _x $和$ \ tilde {h} _y $是仿射的,$ L(x,\ cdot)$在给定$ x $的情况下在$ y $中是凸的,而$ L(\ cdot,y)$在给定$ y $的情况下在$ x $中是凹的。如果已分析上消除了许多原始变量,似乎该问题应该比原始问题更容易解决。不幸, 我最喜欢的凸优化工具包都不会接受这种形式的问题。 尽管 内点方法解决此类问题的可行性。笨蛋

我尝试的一件事是使用标准工具包求解内部极小值,通过灵敏度图计算带有外部参数的解的梯度,然后对外部极值使用一阶方法。这对我不起作用:它适用于玩具问题,但在实际问题上,外部上层的收敛非常缓慢,这表明身体不适。

我需要的是内点方法通过二阶信息处理疾病的能力。我可以通过顺序二次极大极小编程来实现此目标:首先,在当前点周围用二次方局部逼近目标$ L(\ lambda,\ mu,y)$并将约束线性化。 $$
\ begin {alignat} {2}
&\!\ sup _ {\ delta x} \ inf _ {\ delta y}&\ qquad&\ frac {1} {2} \ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)^ \ top \ left(\ begin {array} {cc} P_ {xx}和P_ {yx} ^ \ top \\ P_ {yx}&P_ {yy} \ end {array} \ right )\ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)+ \ left(\ begin {array} {c} q_x \\ q_y \ end {array} \ right)^ \ top \ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)\\
&\ text {根据}&&\ left(\ begin {array} {cc} A_x&0 \\ 0&A_y \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)= \ left(\ begin {array} {c} b_x \\ b_y \ end {array} \ right)\\
&&&\ left(\ begin {array} {cc} G_x&0 \\ 0&G_y \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \ end {array} \ right)\ preceq \ left(\ begin {array} {c} h_x \\ h_y \ end {array} \ right)\\
\ end {alignat}
$$ 沃尔夫双重 将此问题转换为标准的QP:$$
\ begin {alignat} {2}
&\!\ sup _ {\ delta x,\ delta y,\ lambda,\ mu}&\ qquad&\ frac {1} {2} \ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)^ \ top \ left(\ begin {array} {cccc} P_ {xx}&0&0&0 \\ 0&-P_ {yy} &0&0 \\ 0&0&0&0 \\ 0&0&0&0 \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \ \ \ lambda \\ \ mu \ end {array} \ right)+ \ left(\ begin {array} {c} q_x \\ 0 \\ -b_y \\ -h_y \ end {array} \ right)^ \ top \ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)\\
&\ text {取决于}&&\ left(\ begin {array} {cc} A_x&0&0&0 \\ P_ {yx}&P_ {yy}&A_y ^ \ top&G_y ^ \ top \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)= \ left(\ begin {array} {c} b_x \\ -q_y \ end {array} \ right)\\
&&&\ left(\ begin {array} {cc} G_x&0&0&0 \\ 0&0&0&-I \ end {array} \ right)\ left(\ begin {array} {c} \ delta x \\ \ delta y \\ \ lambda \\ \ mu \ end {array} \ right)\ preceq \ left(\ begin {array} {c} h_x \\ 0 \ end {array} \ right)\ \
\ end {alignat}
$$如果为$(\ delta x,\ delta y)$解决此问题,您将获得牛顿步骤以解决原始问题。这里的步验收标准很棘手:如果迭代可行,则您希望利用鞍点条件(请参见方程式(11) Essid等。等)。如果迭代不可行,则需要更复杂的方法,但是幸运的是,我的约束实际上是线性的,因此,进行初始的精确内部求解可使我在保持可行的同时进行迭代。 (注意:如果您在每个步骤上都解决了更一般的凸问题,则无需线性化$ x $约束。)

YMMV!