multi-armed 强盗运动的反直觉结果

Question

我正在学习 Sutton & Barto 的 强化学习：简介 的第 2 章第 7 节，其中涉及 multi-armed 老虎机问题中的梯度方法。（我意识到第 2 版是草稿，似乎这些部分移动了一点，但我的文件中有标题为 "Gradient Bandits" 的第 2.7 节。）我成功地使用了第 2.3-2.5 节中的方法，没有问题，但我始终使用令人困惑的梯度方法获得结果。我将遍历我的代码并展示一个示例。

这里只是初始化一切：

import random
import math
import numpy as np, numpy.random

# number of arms (k) and step-size (alpha)
k = 10
alpha = 0.1

# initialize preference function (H), and reward distribution (R)
H = {i: 0 for i in range(k)}
R = {i: [random.uniform(-100,100), 1] for i in range(k)}

我正在使用固定奖励分布，并且我正在使用字典来表示这些分布。我假设每个奖励都由高斯描述，所以我使用以下函数将动作映射到奖励：

def getReward(action, rewardDistribution):
  return random.gauss(rewardDistribution[action][0], rewardDistribution[action][1])

判断动作概率的so-called"preference function"H也是字典给出的。我将选择分布在一个非常广泛的范围内，因为每个奖励都由高斯分布描述，标准差 1 位于 -100 和 100 之间。我这样做是因为我的直觉告诉我，这会让算法选择 sub-optimal，但我发现情况正好相反。

此代码在每次迭代时选择我的操作：

def selectAction(policy):
  return np.random.choice(list(policy.keys()), p=list(policy.values()))

接下来是运行算法迭代的代码。请注意，pi 是策略，已初始化为每个动作赋予概率 1/k。

avgReward = 0
for i in range(100000):
  pi = {i: math.exp(H[i])/sum([math.exp(H[j]) for j in range(k)]) for i in range(k)}
  A = selectAction(pi)
  R_A = getReward(A, R)
  avgReward += (R_A - avgReward)/(i + 1)
  H = {i: H[i] + alpha*(R_A - avgReward)*((i == A) - pi[i]) for i in range(k)}

请注意，我正在运行进行 100,000 次迭代，这对我来说似乎有点过头了。这是我第一次尝试解决这个问题，所以我的直觉可能不对，但我试图设置它以使算法更容易找到最佳选择。所以我期望的是收敛于具有最高期望值的分布的动作的过程，并且随着迭代的进行将继续达到它。但是，当我打印出与强盗的每个可能动作相关的结果时，这就是我所看到的：

for i in range(k):
  print("Expected reward: " + str(R[i][0]) + " | Selection probability: " + str(pi[i]) + " | Preference: " + str(H[i]))

Expected reward: -50.62506110888989 | Selection probability: 3.617077909489526e-13 | Preference: -7.82992533515
Expected reward: 11.866419726345484 | Selection probability: 1.2337498052271344e-10 | Preference: -1.99777839484
Expected reward: 75.41139657867947 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966
Expected reward: -72.44467653824414 | Selection probability: 3.4267025247257986e-13 | Preference: -7.88399339198
Expected reward: -43.466561447399 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966
Expected reward: -75.99171566420297 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966
Expected reward: -82.11920932060593 | Selection probability: 3.120658098513757e-13 | Preference: -7.97754791911
Expected reward: 95.00643386364632 | Selection probability: 1.5933517476231946e-09 | Preference: 0.560588358966
Expected reward: 31.384022070017835 | Selection probability: 1.2605442916195123e-08 | Preference: 2.62887724114
Expected reward: 49.83925652065625 | Selection probability: 0.9999999808967586 | Preference: 20.8180143641

最后一个动作的预期奖励为49.8，而且强盗几乎每次都选择它。这是 10 个选项中第三好的选项，但它忽略了一个预期回报为 75.4 的选项和另一个预期回报为 95.0[= 的选项42=].

所以，我的问题是：为什么这个强盗缺少最佳选择？这只是一个例子，当我运行程序时，这在相当一致的基础上发生。我对强盗应该做什么的直觉是错误的，还是我对这个算法的编码不正确？

Answer 1

问题是许多武器（或动作；我使用武器是因为这是 MAB 问题中最常见的术语）在您当前的设置下根本不会玩一次。您可以通过打印每只手臂的选择频率来轻松验证情况是否如此。

发生这种情况是因为您的奖励具有相当高的绝对值。在关于 MAB 问题的文献中，他们通常假设奖励在 [0, 1] 或 [-1, 1] 中。这不是绝对必要的（尽管它是为了一些与算法的理论性能相关的证明......但现在你可能对此并不感兴趣）。不管怎样，有几种方法可以解决这个问题：

1) 将首选项列表 (H) 初始化为高值，而不是 0s。这与本书前面描述的 epsilon-greedy 的乐观初始化有类似的效果，因为它激励算法在更早的时候做更多的探索。

2) 大幅降低学习率的值alpha。尝试更像 0.00001，而不是 0.1。这种变化的影响是 H 中的偏好值以较小的速率远离 0，因此 pi 中的概率也远离初始 1/k降低利率。

3) 重新缩放奖励值以使其位于例如 [-1, 1]（如果您不希望问题变得更加复杂。

multi-armed 强盗运动的反直觉结果

Counterintuitive results on multi-armed bandit exercise

python

machine-learning

gradient-descent

reinforcement-learning