2010年10月11日,星期一

相依奖励启示和离线评估

在我的 以前的帖子 我通过探索性学习问题继续了我大部分失败的斗争,其中探索性学习揭示的奖励集取决于奖励矢量的值(又称``依赖奖励启示'')。激励性的例子是价格差异。到目前为止,我在训练期间无法利用历史数据中的其他信息。在这里,我还将表明,对于价格差异问题,我也不能使用其他信息进行脱机策略评估(也许不足为奇,因为学习和评估是相互关联的)。这样说来就更令人惊讶了,因为它说的类似于``即使对于一个特定的历史实例,人们知道拟议的新政策将如何执行,但人们却不能无偏见地使用这些信息。''

当绘制示例IID时,可以使用离线策略估计器来评估静态策略。假设分布$ D = D_x \ times D_ {r | x} $,其中$ x $是与实例关联的特征向量,而$ r:A \ to [0,1] $是与每个动作关联的奖励。我有一个建议的策略$ \ pi:X \ to A $,我想估计$ D $,$ E _ {(x,r)\ sim D} \ left [r \ left(\ pi( x)\ right)\ right] $。

进一步假设历史策略在给定实例$ p(a | x)$的情况下对操作使用已知的条件分布。历史策略定义了由定义的历史数据的分布$ S $
  1. 从$ D $中提取$(x,r)$。
  2. 从$ p(a | x)$中提取$ a $。
  3. 输出实例$ \ left(x,a,r(a),p(a | x)\ right)$。
它是 容易展示 那\ [
\ begin {aligned}
E _ {(x,a,r(a),p)\ sim S} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x )| x)} \ right]&= E _ {(x,r)\ sim D} \ left [E_ {a \ sim p | x} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x)| x)} \ right] \ right] \\
&= E _ {(x,r)\ sim D} \ left [r(\ pi(x))\ frac {1} {p(\ pi(x)| x)} E_ {a \ sim p | x} \ left [1 _ {\ pi(x)= a} \ right] \ right] \\
&= E _ {(x,r)\ sim D} \ left [r \ left(\ pi(x)\ right)\ right],
\ end {aligned}
\]在给定历史数据集$ H $的情况下使用经验策略估计量进行证明,\ [\ frac {1} {| H |} \ sum _ {(x,a,r(a),p)\ in H} r (\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x)| x)}。\]这也是针对上下文强盗的argmax回归方法的基础(即,学习$ r(a)/ p(a | x)$的回归值,以及针对上下文强盗的重要性加权方法(即,将每个历史示例视为具有权重$ r(a)的多类分类问题/ p(a | x)$),尽管这两种方法的后悔界限比偏移树更糟。

到目前为止,一切都是标准的。现在,我将添加一个细微的皱纹,并假设历史策略可能在每个实例中产生一个以上的显示奖励,但仍与奖励值无关。在这种情况下,历史策略会使用已知的操作集$ \ mathcal {A} \ in \ mathcal {P}(A)$中的条件分布,并赋予实例$ p(\ mathcal {A} | x)$,并且历史策略定义了由定义的历史数据的分布\\ mathcal {S} $
  1. 从$ D $中提取$(x,r)$。
  2. 从$ p(\ mathcal {A} | x)$中绘制$ \ mathcal {A} $。
  3. 输出实例$ \ left(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p(\ mathcal {A} | x)\ right)$。
定义$ p(\ mathcal {A} | x)= E _ {\ mathcal {A} \ sim p} \ left [1_ {a \ in \ mathcal {A}} \ right] $,我可以证明\ [
\ begin {aligned}
E _ {(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p)\ sim \ mathcal {S}} \ left [r(\ pi(x)) \ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p(\ pi(x)\ in \ mathcal {A} | x)} \ right]&= E _ {(x,r) \ sim D} \ left [E _ {\ mathcal {A} \ sim p} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p (\ pi(x)\ in \ mathcal {A} | x)} \ right] \ right] \\
&= E _ {((x,r)\ sim D} \ left [\ frac {r(\ pi(x))} {p(\ pi(x)\ in \ mathcal {A} | x)} E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ pi(x)\ in A} \ right] \ right] \\
&= E _ {((x,r)\ sim D} \ left [r(\ pi(x))\ right],
\ end {aligned}
\]到目前为止,这都是非常文明的。这表明经验政策评估者\ [\ frac {1} {| H |} \ sum _ {(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p) \ in H} r(\ pi(x))\ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p(\ pi(x)\ in \ math {A} | x)} ; \]一种argmax回归方法,其中每个历史示例都为估计$ r(a)/ p(a \ in \ mathcal {A} | x)$)贡献了多个回归训练示例;以及一种成本敏感的多类方法,其中奖励向量的非零元素的成本为$ -r(a)/ p(a \ in \ mathcal {A} | x)$。最后两种方法是否有比后一种方法更糟糕的遗憾 滤波偏移树?我应该弄清楚(大概是)。

但是现在,我将假设一些适用于价格差异的附加结构:行动就是价格;行动就是价格;行动就是价格。奖励是零(如果没有购买发生)或价格的已知函数(如果发生购买);以特定价格购买意味着将以任何较小的价格购买;而未按特定价格购买则意味着不会以更大的价格进行购买。更普遍地讲,有一项历史政策选择单个动作$ p(a | x)$,然后世界选择依赖地揭示某些特征$ q(\ mathcal {A} | x,a,r)$。这定义了由定义的历史数据的分布$ \ mathcal {S} ^ \ prime $
  1. 从$ D $中提取$(x,r)$。
  2. 从$ p(a | x)$中提取$ a $。
  3. 从$ q(\ mathcal {A} | x,a,r)$中绘制$ \ mathcal {A} $。
  4. 输出实例$ \ left(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p(a | x),q(\ mathcal {A} | x,a ,r)\ right)$。
现在定义$ p(a \ in \ mathcal {A} | x,r)= E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q} \ left [1_ {a \ in \ mathcal {A}} \ right] \ right]。$然后\ [
\ begin {aligned}
&E _ {(x,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p,q)\ sim \ mathcal {S} ^ \ prime} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p(\ pi(x)\ in \ mathcal {A} | x,r)} \ right] \\
&= E _ {((x,r)\ sim D} \ left [E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)\ in \ mathcal {A}}} {p(\ pi(x)\ in \ mathcal {A} | x,r)} \ right] \ right] \ right] \\
&= E _ {((x,r)\ sim D} \ left [\ frac {r(\ pi(x))} {p(\ pi(x)\ in \ mathcal {A} | x,r)} E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q} \ left [1 _ {\ pi(x)\ in \ mathcal {A}} \ right] \ right] \ right] \\
&= E _ {((x,r)\ sim D} \ left [r(\ pi(x))\ right]。
\ end {aligned}
\]很棒,除了问题再次在于$ p(\ mathcal {A} | x,r)$通常无法计算,因为评估它所必需的奖励向量的元素不可用。特别是对于价格差异,我无法确定未选择的较大价格是否会产生购买,因此有助于显示特定价格的价值。

没意见:

发表评论