显示带有标签的帖子 价格差异. 显示所有帖子
显示带有标签的帖子 价格差异. 显示所有帖子

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)$通常无法计算,因为评估它所必需的奖励向量的元素不可用。特别是对于价格差异,我无法确定未选择的较大价格是否会产生购买,因此有助于显示特定价格的价值。

2010年10月9日,星期六

相依奖励启示:第二部分

在我的 以前的帖子 我谈到了价格差异,以及价格差异是如何激发依赖的奖励启示的,这是一种很好的说法,即揭示哪些奖励取决于奖励价值。我必须承认,我对如何利用这些附加信息有些困惑。

我将在这里重复设置:
  1. 世界从$ D $中选择$(x,\ omega,r)$并显示$(x,\ omega)$。
  2. 玩家通过$ p(a | x,\ omega)$在A $中选择$ a \。
  3. 世界通过$ q(\ mathcal {A} | x,\ omega,r,a)$选择$ \ mathcal {A} \ in \ mathcal {P}(A)$,其中$ a \ in \ mathcal {A} $是必需的。
  4. 世界揭示$ \ {r(a)| \ mathcal {A} \} $中的\ in。
通常的``看看你做了什么''的情况是$ q(\ mathcal {A} | x,\ omega,r,a)= 1 _ {\ mathcal {A} = \ {a \}} $差异是\ [
q(\ mathcal {A} | x,\ omega,r,a)=
\ begin {cases}
\{ a^\prime | a^\prime \leq a \} & \mbox{if } r (a) > 0; \\
\ {a ^ \ prime | a ^ \ prime \ geq a \}和\ mbox {if} r(a)= 0。
\ end {cases}
\]因为需要$ a \ in \ mathcal {A} $,所以我总是可以扔掉其他信息,并将任何$ q $转换为$ q = 1 _ {\ mathcal {A} = \ {a \}} $,然后使用 偏移树。这似乎很浪费,但是目前我没有别的选择可以解决价格差异问题。

滤镜偏移样式更新(失败)


考虑一个 滤波偏移树 样式解决方案。修复$(x,\ omega,r)$,并考虑使用输入$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $输入的固定内部节点。 $ \ lambda $的预期重要性权重为\ [
\ begin {aligned}
w _ {\ lambda | r}&= E_ {a \ sim p} \ biggl [E _ {\ mathcal {A} \ sim q | r,a} \ biggl [\ alpha _ {\ lambda,\ neg \ phi} 1_ { \ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} 1_ {r(\ lambda)\ geq \ frac {1} {2}} \ left(r(\ lambda) -\ frac {1} {2} \ right)\\
&\ quad \ quad \ quad + \ alpha _ {\ neg \ lambda,\ phi} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} 1_ {r(\ phi)\ leq \ frac {1} {2}} \ left(\ frac {1} {2}-r(\ phi)\ right)\\
&\quad\quad\quad + \alpha_{\lambda, \phi} 1_{\lambda \in \mathcal{A}} 1_{\phi \in \mathcal{A}} 1_{r (\lambda) > r (\phi)} \left( r (\lambda) - r (\phi) \right) \biggr] \biggr] \biggl/ \\
&E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} + 1 _ {\ lambda \ in \ mathcal {A}} + 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]。
\ end {aligned}
\]与滤波器偏移量更新的类比建议了选择
\ begin {aligned}
\ alpha _ {\ lambda,\ neg \ phi}&=(1-\ gamma)\ frac {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1_ { \ phi \ in \ mathcal {A}} + 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]]} {E_ {a \ sim p } \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in A} 1 _ {\ phi \ not \ in \ mathcal {A}} \ right] \ right]},\\
\ alpha _ {\ neg \ lambda,\ phi}&=(1-\ gamma)\ frac {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1_ { \ phi \ in \ mathcal {A}} + 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]} {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ not \ in A} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]},\\
\ alpha _ {\ lambda,\ phi}&= \ gamma \ frac {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1_ { \ phi \ in \ mathcal {A}} + 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]} {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in A} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]},
\ end {aligned}
\] for some $\gamma \in [0, 1]$. Unfortunately in general these quantities cannot be computed since $r$ is only partially revealed per instance. For the price differentiation $q$, for instance, only when $a$ is the largest possible price and $r (a) > 0$, or when $a$ is the smallest possible price and $r (a) = 0$, can these quantities be computed.

我的怀疑是进行此偏移滤镜样式更新的唯一方法是,始终显示$ q $所依赖的一组奖励。所以类似\ [
q(\ mathcal {A} | x,\ omega,r,a)=
\ begin {cases}
\{ \tilde a \} \cup \{ a^\prime | a^\prime \geq a \} & \mbox{if } r (\tilde a) > 0; \\
\ {a,\ tilde a \}& \mbox{if } r (\tilde a) = 0; \\
\ {\ tilde一个\} \ cup \ {a ^ \ prime | a ^ \ prime \ leq a \}和\ mbox {if} r(\ tilde a) < 0, \end{cases} \] would work since $q$ only depends upon $r (\tilde a)$ which is always revealed, so the above expectations can always be computed. With such a cooperative $q$, 其余的偏移滤镜树曲柄 可以转向,加权因子为\ [
\ begin {aligned}
\ alpha _ {\ lambda,\ neg \ phi}&= \ frac {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1_ { \ phi \ in \ mathcal {A}} \ right] \ right]} {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in A} 1 _ {\ phi \ not \ in \ mathcal {A}} \ right] \ right]},\\
\ alpha _ {\ neg \ lambda,\ phi}&= \ frac {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1_ { \ phi \ in \ mathcal {A}} \ right] \ right]} {E_ {a \ sim p} \ left [E _ {\ mathcal {A} \ sim q | r,a} \ left [1 _ {\ lambda \ not \ in A} 1 _ {\ phi \ in \ mathcal {A}} \ right] \ right]},\\
\ alpha _ {\ lambda,\ phi}&= 1,
\ end {aligned}
\]很好,但仍然让我想知道如何利用价格差异问题中可用的其他信息。

2010年10月7日,星期四

价格差异和相关奖励启示

为某人提供商品或服务的价格选择始终是一个重要的选择,在某些情况下可以 改善社会福利。特别是在Internet上,当您提供的服务的有效边际成本通常有效地为零时,如果您可以说服bean计数器提高产量,则有很大的空间可以有选择地降低价格。

想象一下,我有一个与每个用户相关联的丰富特征向量$ x $,并且我必须在一组价格$ A $之间进行选择,以便为用户提供单位数量的单一商品。想象一下价格是粘性的(用户无法获得新的身份来获取新的价格)并且是不可转让的(用户无法给他人提供的价格)。当我向用户提供价格时,我看到他们对该价格的响应,但没有看到我本可以提供给他们的其他价格。如果他们选择购买,我会得到一种奖励,它是所提供价格的已知函数(例如,价格减去成本),否则则为零。 (我要等多久才能决定他们永远不会购买?这是一个好问题。)这种设置看起来像是通过探索获得的经典学习方法,可以通过使用 偏移树 与在线探索策略一起热烈开始。问题解决了!

除了$ \ ldots $,感觉这里还有更多信息。具体来说,如果我向用户提供特定价格$ a $并且他们购买了商品,我可以假设他们会以任何价格$ a ^ \ prime \ leq a $购买商品,并且由于奖励是给定购买价格的已知函数这意味着额外的奖励正在显露。类似地,如果我为用户提供特定价格$ a $而他们没有购买,我可以假设他们不会以任何价格$ a ^ \ prime \ geq a $购买,因此再次显示了其他奖励。对于非奢侈品,这些假设似乎是合理的。

没问题吧?的 滤波偏移树 可以处理每个历史实例何时显示多个奖励,因此我应该使用它。但是,不幸的是,在过滤器偏移树情况下显示其奖励的一组动作是独立于奖励选择的。在这里,揭示其奖励的一组动作取决于奖励,这是产生偏见的秘诀。这种情况类似于向朋友询问最近的一次拉斯维加斯之旅:如果他们赢了钱,他们会谈论数小时,而如果他们输了钱,您得到的一切就是``还可以''。

可以这样形式化设置:
  1. 世界从$ D $中选择$(x,\ omega,r)$并显示$(x,\ omega)$。
  2. 玩家通过$ p(a | x,\ omega)$在A $中选择$ a \。
  3. 世界通过$ q(\ mathcal {A} | x,\ omega,r,a)$选择$ \ mathcal {A} \ in \ mathcal {P}(A)$。
    1. 在\ mathcal {A} $中要求$ a \似乎很合理。换句话说,我总是至少观察到我选择的动作。也许这不是严格要求的,但似乎符合实际情况。
  4. 世界揭示$ \ {r(a)| \ mathcal {A} \} $中的\ in。
通常的``看看你做了什么''的情况是$ q(\ mathcal {A} | x,\ omega,r,a)= 1 _ {\ mathcal {A} = \ {a \}} $如上\
q(\ mathcal {A} | x,\ omega,r,a)=
\ begin {cases}
\{ a^\prime | a^\prime \leq a \} & \mbox{if } r (a) > 0; \\
\ {a ^ \ prime | a ^ \ prime \ geq a \}和\ mbox {if} r(a)= 0。
\ end {cases}
\]现在我想知道在什么情况下可以使用这些额外信息。显然,我总是可以丢弃多余的信息,而仅检查$ r(a)$,这将是普通的偏移量树。我可以做得更好吗?