相对剪枝条件

10.3.2　相对剪枝条件

在对相对剪枝条件进行说明之前，我们先给出访问上界u_i的定义：我们假设，从给定时刻起之后的模拟中，如果a_i每次被访问时都得到胜利的结果，而其余节点被访问时都得到失败的结果，则在这样的条件下，u_i被定义为a_i即将被访问次数的上限。如果在这样的假设条件下，a_i上的总访问次数仍然不能多于a_max节点上的访问次数的话，它就可以被剪枝。

相对剪枝条件：如果使得v_j＞v_i＋u_i，其中j∈｛1，…，k｝∩i≠j，则a_i可以被剪枝。

当然，上面的假设是极端的，因为我们不可能奢望经过一段时间观察后收效不好的节点a_i在之后出现极端优秀的表现。所以，在实际应用中，我们给每个a_i赋予了一个相对较优的胜率值：a_i原始的胜率为r_i＝w_i/v_i，在接下来的模拟中，我们将a_i的胜率以1-α×（1-r_i）代替，α∈［0，1］。令

f（r_i）＝1-α×（1-r_i）-r_i＝（1-r_i）×（1-α）≥0　　　　　（10.5）

则

f′（r_i）＝α-1≤0　　　　　（10.6）

从式（10.5）和式（10.6）两式可以看出，我们将让原本效果不好的节点的胜率发生更大的变化。这样做的目的是显然的，对于本身效果不好的节点而言，只有胜率较大幅度的提高，才能使得剪枝的条件变得安全，而不至于把某些可能突变的点过早地剪掉。

现在我们给出u_i的计算方法。在Auer 2002年的论文中，对后悔度的证明过程中有

其中Δ_i＝μ^＊-μ_i，μ_i代表第i个手臂上的胜率，而μ^＊代表最大胜率。我们认为不等式（10.7）右侧即是我们要求的u_i。

现令

g（r_i）＝1-α×（1-r_i）　　　　　（10.8）

则

g′（r_i）＝α＞0　　　　　（10.9）

即如果原本节点A的胜率高于节点B，则经过变化后的节点胜率仍然满足这个关系，这就保证了变化之后的胜率不会让节点间的大趋势发生较大变化，也就总体上保证了原有算法的结果。