machine-learning - 什么是 epsilon/k 它是如何出现在 epsilon 贪婪算法中的

Question

据说它会选择概率为 1-epsilon 的经验平均值最高的臂，在第 no 页中为概率编写的方程中，epsilon/k 是如何添加到它的(以及用于随机概率选择的 epsilon/k) :6篇论文Algorithms for multi armed bandits .等式中的 epsilon/k 是什么意思

Answer 1

此答案取自here :

假设您站在 k = 3 台老虎机前。每台机器根据不同的概率分布支付，而这些分布对您来说是未知的。假设您总共可以玩 100 次。

你有两个目标。第一个目标是用一些硬币进行试验，以确定哪台机器的支付效果最好。第二个相关目标是获得尽可能多的钱。 “探索”和“利用”这两个术语用来表示你必须使用一些硬币来探索才能找到最好的机器，并且你想在最好的机器上使用尽可能多的硬币来利用你的知识。

Epsilon-greedy 几乎太简单了。当您玩机器时，您可以跟踪每台机器的平均支出。然后，您选择当前平均支出最高的机器，概率 = (1 – epsilon) + (epsilon/k)，其中 epsilon 是一个很小的值，例如 0.10。您选择的机器当前支付平均值不最高，概率 = epsilon/k。通过一个具体的例子就更容易理解了。假设在前 12 次抽奖后，您玩了 1 号机器四次，两次赢得 1 美元，两次赢得 0 美元。机器 #1 的平均值为 $2/4 = $0.50。

假设您已经玩了 2 号机器五次，并赢得了 3 次 1 美元和两次 0 美元。机器 #2 的平均支出为 $3/5 = $0.60。

假设您玩过 3 号机器 3 次，一次赢得 1 美元，两次赢得 0 美元。机器 #3 的平均支出为 $1/3 = $0.33。

现在您必须选择一台机器来玩第 13 号尝试。您生成一个介于 0.0 和 1.0 之间的随机数 p。假设您设置 epsilon = 0.10。如果 p > 0.10(90% 的情况都是如此)，您会选择机器 #2，因为它具有当前最高的平均支出。但如果 p < 0.10(只有 10% 的情况)，您将选择一台随机机器，因此每台机器有 1/3 的机会被选中。

请注意，机器 #2 可能会被选中，因为您从所有机器中随机选择。

随着时间的推移，最好的机器会越来越多地被玩，因为它会更频繁地支付。简而言之，epsilon-greedy 意味着大多数时候选择当前最佳选项(“贪婪”)，但有时选择概率较小(epsilon)的随机选项。

对于多臂老虎机问题还有许多其他算法。但 epsilon-greedy 非常简单，并且通常比 UCB(“置信上限”)变体等更复杂的算法效果更好，甚至更好。