概览

附录(多手柄老虎机)

计算和理论方面的详细内容

首先,请记住“多手柄老虎机”这一名称描述的是选择众多提议的“解决方案”的问题。如果您挑选一本关于强化学习的书,您会发现多手柄老虎机上的前言中会列出多种途径。这是因为多手柄老虎机问题背后的数学非常难,近似于在实践中使用的启发式解。Peter Whittle的一段名言巧妙地总结了其数学难度(Whittle,1979 年):

[老虎机问题] 是在 [第二次世界] 大战期间制定的,为了解决该问题,几乎耗尽了同盟分析师的能量和心智,所以给出的建议就是将该问题丢给德国,作为智力破坏的终极武器。

我们使用的启发式称为“Thompson Sampling”,或者是“Randomized Probability Matching”,因为它结合了这些启发式当中的许多最佳特性。您可以在 [5] 中详细了解此技术,然后在 [2]、[3] 和 [4] 中查看更多关于其数学性质的详细内容。

效果最佳手柄的概率

Thompson Sampling为各手柄分配的会话次数与它们是效果最佳手柄的概率成比例。这是一项贝叶斯计算。让 θ = (θ1, θ2,..., θk) 表示各手柄的转化率的向量 1, …, k。并让y表示到目前为止,实验所观察到的数据。我们将y模拟成一个单独的二项式结果的向量,并在 θ 上假设独立统一的优先者。让 Ia(θ) 表示a手柄为效果最佳这一事件的指示符。接下来,我们可以写出:

P(Ia) = ∫Ia(θ) p(θ|y) dθ

本部分可以通过封闭形式来完成(但“封闭形式”解决方案涉及到一些复杂的特殊函数,例如不完全函数),或者,也可以通过数值积分来完成。在任何一种情况下,这些计算都会快速趋向不稳定,即使 y 值相对较小也是如此。但可以通过模拟来稳定地计算出效果最佳手柄的概率。θ 中的每个元素都是来自β分布的独立随机变量。模拟一个大型矩阵,其中包含来自相关β分布的 θ 图,矩阵中的行代表随机图,而列代表实验中的 k 支手柄。a手柄效果最佳的概率的 Monte Carlo 估算值是a手柄拥有最大拟合值的行的实验分数。每支手柄是否能够优于原始手柄的概率也可使用类似的方法计算。

剩余价值

生成多手柄概率的模拟同样可以生成实验中的剩余价值分布。剩余价值是(θmax-θ*)/θ*的后验分布,其中θmaxθ的最大值,而θ*是最有可能成为效果最佳的手柄的θ值。为了阐明这项计算,我们假设有三支手柄,它们拥有的会话次数分别为20、30和40,而它们分别生成了12、20和30次转化。它们是效果最佳手柄的概率大概为0.09、0.20和0.71。θ 的 Monte Carlo 模拟的前 6 幅图可能是:

[,1] [,2] [,3]
[1,] 0.54 0.73 0.74
[2,] 0.55 0.66 0.73
[3,] 0.53 0.81 0.80
[4,] 0.57 0.50 0.65
[5,] 0.52 0.67 0.83
[6,] 0.65 0.84 0.63

我们从第3列的元素中减去每行最大的元素,以此来逐行计算(因为第3支手柄最有可能是效果最佳的手柄)。前两行的值为零,因为最大的图产生在第3列中。第3行的值为0.01/0.80,因为第2列比第3列大0.01。如果我们一直逐行计算下去,就可将得出的值的分布情况绘制成一个直方图,就像图A1中的左侧面板一样。第3支手柄有71%的概率成为效果最佳的手柄,所以在71%的案例中,从第3支手柄中切换出来的值为零。该值分布的第95个百分位是实验中的“潜在剩余价值”,其在本案例中计算出的结果约为0.16。您可以将这个数字解释为:“我们仍然无法确定第3支手柄的转化率,但无论怎样,其他手柄中的某一支有16%的概率优于它。”

图A1的右侧面板展示的是在实验进展期间,剩余价值的分布发生了哪些状况。假设每支手柄拥有5倍的样本量(即100、150和200次会话),以及5倍的转化次数(60、100、150)。采用更大的样本量,我们就更有信心确定各手柄的转化率。现在,第3支手柄约有95%概率成为效果最佳的手柄,所以,剩余价值分布的第95个百分位为零。

图A1。 实验中的剩余价值分布。每种情况中的垂直线是第95个百分位,或是“潜在的剩余价值”。
本文是否对您有帮助?
您有什么改进建议?