聚合没收偏移树

在一个 以前的帖子 我谈到了带有部分反馈的成本敏感型最佳m（CSBM）。想法是选择一组动作，其中该组的奖励是各个元素奖励的总和。我之前考虑过的部分反馈的性质是，只揭示了所选动作组的奖励，但是揭示了该组动作中的每个奖励。另一个可能的情况是，仅揭示所选动作组的总奖励。这比较困难，因为它既是部分反馈又是汇总反馈。但是，在我目前的工作中，存在一个问题，即要优化一组页面元素，但是用户只能通过一种方式与页面进行积极的交互，即，各个页面组件是决策的单元，而不是决策单元。用户反馈的单位。如果所讨论集合的基数很小，则可以将整个集合视为动作并直接利用偏移树。对于我在这里处理的第一个问题，有$ {9 \ choose 2} = 36 $个组合，因此这是完全可行的。占据页面的更多部分可能会将其扩大2或3个数量级，但是我有很多数据，因此也许仍然可以使用。

不过，还是有痒的感觉，我希望使用$ \ ldots $ 偏移树 方法，但对于未设置的单个动作，请使用 约束CSBM约束CSMC减少。第一步是使用汇总反馈来解决约束的CSMC，即从给定的历史数据中选择最佳操作，该历史数据由操作集和相关的总奖励构成。受约束的CSMC设置如下。有一个分布$ D = D_x \ times D _ {\ omega | x} \ times D_ {r | \ omega，x} $其中$ r：A \ to [0，1] \ cup \ {-\ infty \} $以单位间隔上增加$-\ infty $的值，并通过$ \ omega \ in \ mathcal将特定实例的$ r $的分量作为$-\ infty $的值作为问题实例的一部分进行显示。 {P}（A）$（即$ \ omega $是$ A $的子集）。特定确定性策略$ h的遗憾：X \ times \ mathcal {P}（A）\ to A $是\ [v（h）= E _ {（x，\ omega）\ sim D_x \ times D _ {\ omega | x}} \ left [\ max_ {k \ in A} \\; E_ {r \ sim D_ {r | \ omega，x}} \ left [r（k）\ right]-E_ {r \ sim D_ {r | \ omega，x}} \ left [r（h（x， \ omega））\ right] \ right]。 \]我假设历史策略在给定实例$ p（\ mathcal {A} | x，\ omega）$的情况下，在操作的力量集合上使用了已知的条件分布。我将使用缩写$ \ mathcal {A} $来指代$ \ mathcal {P}（A）$的实现。而不是包含$ \ mathcal {A} $每个元素的奖励的历史数据，而是只有$ \ sum_ {a \ in \ mathcal {A}} r（a）$。

算法：汇总没收偏移树火车

数据： 受约束的CSMC具有汇总反馈培训数据集$ S $。
输入： 重要性加权的二进制分类程序$ \ mbox {Learn} $。
输入： 带有内部节点$ \ Lambda（T）$的标签上的二叉树$ T $。
结果： 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda（T）\} $。

1. 从叶子到根的每个$ n \ in \ Lambda（T）$：
1. $ S_n = \ emptyset $。
2. 对于每个示例$ \ left（x，\ omega，\ mathcal {A}，\ sum_ {a \ in \ mathcal {A}}} r（a），p（\ cdot | x，\ omega）\ right）\ in带$ \ mathcal {A}的S $ \ cap \ omega = \ emptyset $：
1. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类（分别预测输入$（x，\ omega）$的左和右子树）。
2. 如果$ \ lambda \ in \ omega $，预测$ \ phi $以便为父节点构建训练输入（``$ \ lambda $ forfeits''）;
3. 否则，如果$ \ phi \ in \ omega $，预测$ \ lambda $以便为父节点构建训练输入（``$ \ phi $ forfeits''）;
4. 否则（（$ \ lambda \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $））或（$ \ lambda \ not \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $）：
1. 让\ [\ alpha = {| A \ setminus \ omega | -2 \ choose | \ mathcal {A} | -1} ^ {-1} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset}（1 _ {\ lambda \ in \ mathcal { A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}）\ right]} { E _ {\ mathcal {A} ^ \ prime \ sim p} [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]}。 \]
2. 如果$ \ sum_ {a \ in \ mathcal {A}} r（a）<\ frac {| \ mathcal {A} |} {2} $，$ S_n \ leftarrow S_n \ cup \ left \ {\ left（x，1 _ {\ phi \ in \ mathcal {A}}，\ alpha \ left（ \ frac {| \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r（a）\ right）\ right）\ right \} $;
3. else $ S_n \ leftarrow S_n \ cup \ left \ {\ left（x，1 _ {\ lambda \ in \ mathcal {A}}，\ alpha \ left（\ sum_ {a \ in \ mathcal {A}}} r（a ）-\ frac {| \ mathcal {A} |} {2} \ right）\ right）\ right \} $。
3. 令$ \ Psi_n = \ mbox {Learn}（S_n）$。
2. 返回$ \ {\ Psi_n | n \ in \ Lambda（T）\} $。

评论： 这假设一个历史策略，其中$ | \ mathcal {A} | $几乎可以肯定是一个常数，并且所有可行集都具有正概率。

算法：汇总没收偏移树测试

输入： 带有内部节点$ \ Lambda（T）$的标签上的二叉树$ T $。
输入： 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda（T）\} $。
输入： 实例实现$ {x，\ omega）$。
结果： 预测标签$ k $。

1. 令$ n $为根节点。
2. 重复直到$ n $是叶节点：
1. 如果$ n $左子树中所有叶子的标签都在$ \ omega $中，则遍历右孩子；
2. 否则，如果$ n $的右子树中所有叶子的标签都在$ \ omega $中，则遍历到左孩子；
3. 否则，如果$ \ Psi_n（x）= 1 $，则遍历左孩子；
4. 否则（当$ \ Psi_n（x）= 0 $并且每个子树中至少有一个标签不在$ \ omega $中时），遍历右孩子。
3. 返回叶子标签$ k $。

激励更新

基本思想是将总奖励用作偏移树中的信号，但仅当一个节点的输入（而非全部）都在一组动作中时才进行归因。利用过滤树样式后悔约束证明策略的关键是确保内部节点上的预期重要性权重差等于对该节点的两个输入而言的策略后悔。由于总奖励是各个奖励的线性组合，因此可以通过评估与相同动作同时出现的动作值之间的差异来比较动作值。选择该更新，使得当采用期望时，仅在输入到特定节点的动作上不同的集合组合以有助于期望的重要性权重差。

对于固定的$（x，\ omega，r）$和一个内部节点，其左输入$ \ lambda \ not \ in \ omega $和右输入$ \ phi \ not \ in \ omega $， $ \ lambda $的预期重要性权重为\ [
\ begin {aligned}
w _ {\ lambda | r}＆= \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal { A}} 1 _ {\ phi \ not \ in \ mathcal {A}} \ alpha _ {\ lambda，\ neg \ phi} \ left（\ sum_ {a \ in \ mathcal {A}} r（a）-\ frac {| \ mathcal {A} |} {2} \ right）_ + \ right]} {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset } 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \在\ mathcal {A}}中1 _ {\ phi \在\ mathcal {A}}中\ right]} \\
＆\ quad + \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ alpha _ {\ neg \ lambda，\ phi} \ left（\ frac {| \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal { A}} r（a）\ right）_ + \ right]} {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A }} 1 _ {\ phi \ in \ mathcal {A}} \ right]}，
\ end {aligned}
\]其中$（x）_ + = \ max（x，0）$和$ \ alpha _ {\ lambda，\ neg \ phi} $和$ \ alpha _ {\ neg \ lambda，\ phi} $确定比例因子。这表明\ [
\ alpha _ {\ neg \ lambda，\ phi} = \ alpha _ {\ lambda，\ neg \ phi} \ propto \ begin {cases} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right]} {E _ {\ mathcal {A} ^ \ prime \ sim p} [ 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]}& \mbox{if } E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A} \cap \omega = \emptyset} 1_{\mathcal{A}^\prime = \mathcal{A}} ] >0; \\ 0＆\ mbox {否则}，\ end {cases}
\]产生\ [
\ begin {aligned}
w _ {\ lambda | r}＆\ proto \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ lambda，\ neg \ phi}} \ left（\ sum_ {a \ in \ mathcal {A}} r（a ）-\ frac {| \ mathcal {A} |} {2} \ right）_ + + \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ neg \ lambda，\ phi}}} left（\ frac { | \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r（a）\ right）_ +，\\
w _ {\ phi | r}＆\ propto \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ neg \ lambda，\ phi}} \ left（\ sum_ {a \ in \ mathcal {A}} r（a ）-\ frac {| \ mathcal {A} |} {2} \ right）_ + + \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ lambda，\ neg \ phi}}} left（\ frac { | \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r（a）\ right）_ +，\\
\ end {aligned}
\] \\
\ begin {aligned}
\ Upsilon _ {\ lambda，\ neg \ phi}&= \{ \mathcal{A} | \mathcal{A} \cap \omega = \emptyset, \lambda \in \mathcal{A}, \phi \not \in \mathcal{A}, E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A}^\prime = \mathcal{A}} ] > 0 \}, \\
\ Upsilon _ {\ neg \ lambda，\ phi}&= \{ \mathcal{A} | \mathcal{A} \cap \omega = \emptyset, \lambda \not \in \mathcal{A}, \phi \in \mathcal{A}, E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A}^\prime = \mathcal{A}} ] > 0 \}.
\ end {aligned}
\]现在，如果并且仅在历史策略下可能用$ \ lambda $而不是$ \ phi $的集合在历史策略下是可能的，并且只有我将用$ \ Upsilon _ {\ lambda，\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda，\ phi} $表示，那么预期的重要权重差为\ [
w _ {\ lambda | r}-w _ {\ phi | r} \ propto | \ Upsilon | \ left（r（\ lambda）-r（\ phi）\ right），
\] and therefore the proper choice when $|\Upsilon_{\lambda,\neg \phi}| = |\Upsilon_{\neg \lambda, \phi}| \doteq |\Upsilon| > 0$ is \[
\ alpha _ {\ phi，\ neg \ lambda} = \ alpha _ {\ lambda，\ neg \ phi} = \ begin {cases} | \ Upsilon | ^ {-1} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right]} {E _ {\ mathcal {A} ^ \ prime \ sim p} [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]}& \mbox{if } E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A} \cap \omega = \emptyset} 1_{\mathcal{A}^\prime = \mathcal{A}} ] >0; \\ 0和\ mbox {否则}。 \ end {cases}
\]在最简单的情况下，在历史政策下所有完全可行的集合都具有正概率，并且由历史政策构造的所有集合都具有相同的$ | \ mathcal {A} | $，然后$ | \ Upsilon | = {| A \ setminus \ omega | -2 \ choose | \ mathcal {A} | -1} $。

在某些情况下，可以遵循不遵循$ \ Upsilon _ {\ lambda，\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda，\ phi} $的历史策略 通过拒绝修改 历史数据的一部分变成有效的历史策略，该策略确实遵循$ \ Upsilon _ {\ lambda，\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda，\ phi} $。

后悔分析

总计没收偏移树的后悔分析与没收偏移树的后悔分析几乎相同。

令$ \ Psi =（T，\ {\ Psi_n | n \ in \ Lambda（T）\}）$表示特定的合计没收偏移树（即，选择二叉树和一组特定的节点分类器），并令$ h ^ \ Psi $表示因没收补偿树而产生的策略。后悔分析利用三元组（x ^ \ prime，y，w）$上的诱导重要性加权二元分布$ D ^ \ prime（\ Psi）$，定义如下：

1. 从$ D $绘制$（x，\ omega，r）$。
2. 在二叉树的内部节点$ \ Lambda（T）$上绘制均匀的$ n $。
3. 设$ x ^ \ prime =（x，n）$。
4. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类（分别预测输入$ x $的左和右子树）。
5. 如果$ \ lambda \ in \ omega $，则创建重要性加权的二进制示例$（x ^ \ prime，0，0）$;
6. 否则，如果$ \ phi \ in \ omega $，则创建重要性加权的二进制示例$（x ^ \ prime，1，0）$;
7. 其他（当$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $时）：
1. 从$ p（\ mathcal {A} | x，\ omega）$中绘制$ \ mathcal {A} $。
2. 如果$ \ mathcal {A} \ cap \ omega \ neq \ emptyset $，则拒绝样本；
3. 否则（（$ \ lambda \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $））或（$ \ lambda \ not \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $）：
1. 让\ [\ alpha = | \ Upsilon | ^ {-1} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset}（1_ { \ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A} }} \ right]} {E _ {\ mathcal {A} ^ \ prime \ sim p} [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]}，\]，其中$ | \ Upsilon | $为 以上定义.
2. 如果$ \ sum_ {a \ in \ mathcal {A}} r（a）<\ frac {| \ mathcal {A} |} {2} $，创建重要性加权的二进制示例\ [\ left（x ^ \ prime，1 _ {\ phi \ in \ mathcal {A}}，\ alpha \ left（ \ frac {| \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r（a）\ right）\ right）; \]
3. 否则（当$ \ sum_ {a \ in \ mathcal {A}} r（a）\ geq \ frac {| \ mathcal {A} |} {2} $）时，创建重要性加权的二进制示例\ [\ left（ x ^ \ prime，1 _ {\ lambda \ in \ mathcal {A}}，\ alpha \ left（\ sum_ {a \ in \ mathcal {A}} r（a）-\ frac {| \ mathcal {A} | } {2} \ right）\ right）; \]
4. 否则拒绝样品。

诱导分布$ D ^ \ prime（\ Psi）$取决于特定的合计没收偏移树，但对于任何固定的合计没收偏移树都得到了很好的定义。现在，我想将$ h ^ \ Psi $的政策遗憾与$ \ Psi $的重要性加权二进制遗憾联系起来，\ [\ begin {aligned} q（\ Psi）&= E_{(x^\prime, y, w) \sim D^\prime (\Psi)} \left[ w 1_{y \neq \Psi (x^\prime)} \right] \\ &= \frac{1}{|\Lambda (T)|} \sum_{n \in \Lambda (T)} E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ q_n (\Psi | x, \omega) \right], \ end {aligned} \] where \[ q_n (\Psi | x, \omega) = \begin{cases} 0 & \mbox{if } \Gamma (n_\lambda) \setminus \omega = \emptyset \mbox{ or } \Gamma (n_\phi) \setminus \omega = \emptyset; \\ 0 & \mbox{if } \Psi_n (x) = 1_{w_\lambda >w_ \ phi}; \\ \左| w_ \ lambda-w_ \ phi \ right | ＆\ mbox {otherwise}，\ end {cases} \]是内部节点$ n $上的重要性加权后悔，$ \ Gamma（n）$指的是根于$ n $的子树中的一组标签（叶）， $ n_ \ lambda $表示$ n $的左子代，$ n_ \ phi $表示$ n $的右子代，$ w_ \ lambda $是在$（x， \ omega）$和$ w_ \ phi $是以$（x，\ omega）$为条件的正确孩子的预期重要性权重。

定理：遗憾的结界

对于所有CSMC发行版$ D $;所有历史政策$ p $，这样对于所有对动作$ \ lambda $和$ \ phi $，$ \ Upsilon _ {\ lambda，\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda，\ phi} \ neq \ emptyset $，只要$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $，并且使得$ E _ {\ mathcal {A} \ sim p} [1_ {a \ in \ mathcal { A}} | x，\ omega]>每当$ a \ not \ in \ omega $时为0 $;以及所有合计没收的偏移树$ \ Psi $，\ [v（h ^ \ Psi）\ leq（| A |-1）q（\ Psi），\]其中$ q（\ Psi）$是重要性加权关于引起的子问题的二元遗憾。

证明： 看到 附录.

尽管这很整洁，但仍然存在缺陷：在以前的情况下，确定对特定动作进行惩罚的约束似乎很自然，但是在这里，更合理的情况是对特定动作组合进行惩罚。它开始看起来像是随机最短路径（SSP），而没有求助于部分（汇总？）反馈和未完全连接的图。在OR中，它们减少了SSP的许多问题，因此，既然我对偏移树有了更好的命令，也许是时候重新访问SSP了。

附录

这就是后悔的证明。

考虑一个固定的$（x，\ omega）$。讨论内部节点$ n $，\ [v（h ^ \ Psi | x，\ omega，n）= \ max_ {k \ in \ Gamma（n）} E_ { r \ sim D_ {r | \ omega，x}} \ left [r（k）\ right]-E_ {r \ sim D_ {r | \ omega，x}} \ left [r（h ^ \ Psi_n（x ，\ omega））\ right]。 \]其中$ h_n ^ \ Psi $是内部节点$ n $的预测。当$ n $是树的根时，$ v（h ^ \ Psi | x，\ omega，n）$是后悔的，以$（x，\ omega）$为条件的抵消树策略。

证明策略是通过感应绑定$ v（h ^ \ Psi | x，\ omega，n）\ leq \ sum_ {m \ in \ Lambda（n）} q_m（\ Psi | x，\ omega）$。对于只有一片叶子（没有内部节点）的树，基本情况很容易满足，因为它的值为$ 0 \ leq 0 $。为了显示在特定内部节点$ n $上的递归，让$ \ lambda $和$ \ phi $为左子树（$ n_ \ lambda $）和右子树（$ n_ \ phi $）的预测。

情况1：$ \ Gamma（n_ \ lambda）\ setminus \ omega = \ emptyset $。在这种情况下，\ omega $中的$ \ lambda \和为假，因此选择了$ \ phi $。右子树中必须有一个最大化器，因为左子树中的所有值都是$-\ infty $。此外，对于$ m = n $和$ m \ in \ Lambda（n_ \ lambda）$，$ q_m（\ Psi | x，\ omega）= 0 $。因此\ [\ begin {aligned} v（h ^ \ Psi | x，\ omega，n）＆=
\ max_ {k \ in \ Gamma（n）} E_ {r \ sim D_ {r | \ omega，x}} \ left [r（k）\ right]-E_ {r \ sim D_ {r | \ omega， x}} \ left [r（\ phi）\ right] \\＆= \ max_ {k \ in \ Gamma（n_ \ phi）} E_ {r \ sim D_ {r | \ omega，x}} \ left [ r（k）\ right]-E_ {r \ sim D_ {r | \ omega，x}} \ left [r（\ phi）\ right] \\＆= v（h ^ \ Psi | x，\ omega， n_ \ phi）\\＆\ leq \ sum_ {m \ in \ Lambda（n_ \ phi）} q_m（\ Psi | x，\ omega）\\＆= \ sum_ {m \ in \ Lambda（n）} q_m （\ Psi | x，\ omega）。 \ end {aligned} \]
情况2：$ \ Gamma（n_ \ lambda）\ setminus \ omega \ neq \ emptyset $和$ \ Gamma（n_ \ phi）\ setminus \ omega = \ emptyset $。在这种情况下，\ omega $中的$ \ phi \和\\ omega $中的$ \ lambda \，而不是\ omega $中的$ \ phi $，因此选择了$ \ phi $充公和$ \ lambda $。左子树中必须有一个最大化器，因为右子树中的所有值都是$-\ infty $。此外，对于$ m = n $和$ m \ in \ Lambda（n_ \ phi）$，$ q_m（\ Psi | x，\ omega）= 0 $。因此\ [\ begin {aligned} v（h ^ \ Psi | x，\ omega，n）＆=
\ max_ {k \ in \ Gamma（n）} E_ {r \ sim D_ {r | \ omega，x}} \ left [r（k）\ right]-E_ {r \ sim D_ {r | \ omega， x}} \ left [r（\ lambda）\ right] \\＆= \ max_ {k \ in \ Gamma（n_ \ lambda）} E_ {r \ sim D_ {r | \ omega，x}} \ left [ r（k）\ right]-E_ {r \ sim D_ {r | \ omega，x}} \ left [r（\ lambda）\ right] \\＆= v（h ^ \ Psi | x，\ omega， n_ \ lambda）\\＆\ leq \ sum_ {m \ in \ Lambda（n_ \ lambda）} q_m（\ Psi | x，\ omega）\\＆= \ sum_ {m \ in \ Lambda（n）} q_m （\ Psi | x，\ omega）。 \ end {aligned} \]
情况3：$ \ Gamma（n_ \ lambda）\ setminus \ omega \ neq \ emptyset $和$ \ Gamma（n_ \ phi）\ setminus \ omega \ neq \ emptyset $。这是``正常''偏移树情况，其中$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $都没有，所以没收没收。如 如上所示，以$（x，\ omega，r）$和$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $为条件的期望重要性权重满足\ [| w_ \ lambda-w_ \ phi | = \ left | E_ {r \ sim D_ {r | \ omega，x}} \ left [w _ {\ lambda | r}-w _ {\ phi | r} \ right] \ right | = \ left | E_ {r \ sim D_ {r | \ omega，x}} [r（\ lambda）-r（\ phi）] \ right |，\]，即内部节点的重要性加权后悔等于策略对于输入到该节点的两个动作感到遗憾。

不失一般性地假设分类器选择$ \ phi $。如果最大化器来自右边的子树，则\ [\ begin {aligned} v（h ^ \ Psi | x，\ omega，n）＆= \ max_ {k \ in \ Gamma（n_ \ phi）} E_ {r \ sim D_ {r | \ omega，x}} \ left [r（k）\ right]-E_ {r \ sim D_ {r | \ omega，x}} \ left [r（\ phi）\ right] \ \＆= v（h ^ \ Psi | x，\ omega，n_ \ phi）\\＆\ leq \ sum_ {m \ in \ Lambda（n_ \ phi）} q_m（\ Psi | x，\ omega）\\ ＆\ leq \ sum_ {m \ in \ Lambda（n）} q_m（\ Psi | x，\ omega）。 \ end {aligned} \]如果最大化器来自左子树，则\ [\ begin {aligned} v（h ^ \ Psi | x，\ omega，n）＆= \ max_ {k \ in \ Gamma（n_ \ lambda）} E_ {r \ sim D_ {r | \ omega，x}} \ left [r（k）\ right]-E_ {r \ sim D_ {r | \ omega，x}} \ left [r（ \ phi）\ right] \\＆= E_ {r \ sim D_ {r | \ omega，x}} \ left [r（\ lambda）-r（\ phi）\ right] + v（h ^ \ Psi | x，\ omega，n_ \ lambda）\\＆= q_n（\ Psi | x，\ omega）+ v（h ^ \ Psi | x，\ omega，n_ \ lambda）\\＆\ leq q_n（\ Psi | x，\ omega）+ \ sum_ {m \ in \ Lambda（n_ \ lambda）} q_m（\ Psi | x，\ omega）\\＆\ leq \ sum_ {m \ in \ Lambda（n）} q_m（\ Psi | x，\ omega）。 \ end {aligned} \]在根处终止归纳会产生\ [v（h ^ \ Psi | x，\ omega）\ leq \ sum_ {n \ in \ Lambda（T）} q_n（\ Psi | x，\ Ω）= | \ Lambda（T）| q（\ Psi | x，\ omega）。 \]考虑双方对$ D_x \ times D _ {\ omega | x} $的期望，并注意$ | \ Lambda（T）| =（| A |-1）$完成证明。