强化学习与简单多臂老虎机问题

基础

我在series hub中介绍过最基本的强化学习的内容。在强化学习里有四个基本的概念会经常出现在相关的文章中，策略、奖励、价值函数以及环境模型。我会跳过模型这个部分，因为我们现在讨论的是不基于模型的学习理论。
策略：是强化学习机的核心，代表着决策进行的方式。它可能是一个表格，一个函数或者一个复杂的深度神经网络。
奖励信号：一个数值，代表着强化学习机采取行动后的即时奖励。最大化所得奖励是强化学习机的最终目标，为了完成这个目标，我们不断地调整策略。这就像是训练狗狗一样。
价值函数：一个函数，用于描述给定状态下的可能获得的远期奖励。这样看来，一个较小的但恒定的常数有可能会优于浮动范围很大的结果。当然，也可能是相反的情况。

探索与利用

Exploration（探索）会放弃一些已知的奖励信息，而去尝试一些新的选择——即在某种状态下，算法也许已经学习到选择什么行动让奖励比较大，但是并不能每次都做出同样的选择，也许另外一个没有尝试过的选择会让奖励更大，即Exploration希望能够探索更多潜在的信息。
Exploitation（利用）指根据已知的信息最大化奖励。
其区别也可以简单地理解成，Exploration 算法在搜索全局最优解，是不基于已有经验的；Exploitation 在搜索局部最优解，且最大程度地利用已有经验信息。
强化学习机就像是个小宠物。它们能够发现第二个碗中包含的东西比第一个碗里的更好，但是当它们开始进食后，就难以发现藏在角落里的大牛排。贪婪的学习机行为也差不多。它会死抓住第一桶金，为自己“谋利”。它总是采取最大化奖励的行动，但是从不会考虑采取其他行为能否在几步之后获得更大的奖励。这就是为什么我们需要探索，因为很有可能一些偶然因素导致我们的学习系统采取了一些随机的行为。
然而，这里有个问题。我们不能只是盲目地探索最大奖励，因为一个学习机会浪费太多的时间来寻找答案，却没有利用它所学习的经验。一个解决办法就是以高探索率开始，然后在系统积累一定经验后逐渐降低探索率。这种权衡也是很著名的数学问题，没有最合理的答案。

多臂老虎机

你肯定知道著名的单臂老虎机，如果你没有达到目标，你不会得到任何奖励。不管怎样，你都是要拉一下杠杆，然后我们假设能随机地获得金钱奖励。由于结果是完全随机的，所以我们训练强化学习机只拉这一个杠杆也无济于事。但是假设一台老虎机有K个杠杆，并且每个杠杆都有随机的奖励，只不过有细微的金额差距。这样的话，一些杠杆和其他杠杆会有些许不同。我们就可以训练一个学习机来帮助我们，而且此处我们还想测试贪婪算法和探索算法的好坏。

数据

假设我们考虑的老虎机有十个杠杆，我假定了两个效用函数来生成数据。数据基本都是基于正态分布来获得的，这样以来一些策略行为可能会比其他行为更好，更有区分度。

def generate_problem(k):
    return np.random.normal(loc=0.0, scale=1, size=10)
def generate_reward(problem, action):
    return np.random.normal(loc=problem[action], scale=1)

算法

再次强调一下，问题与想法都来自一本书：强化学习简介 (Reinforcement Learning: An Introduction) 。
在介绍代码之前还是要提一些东西。价值函数我们记作q*(a)是一个实值函数。它是给定行动下获得的平均奖励。但是如果学习机知道了价值函数，就没有训练的必要了。这个算法中，我们将要估计价值函数并且利用它来进行决策指导。估计的函数我们记作Q(A)（注意：我试着让数学公式尽量少而简单，所以更多地使用代码来）。

def k_bandit(problem, k, steps, exploration_rate):
    Q = {i: 0 for i in range(k)} # 1. Value function
    N = {i: 0 for i in range(k)} # 2. Number of actions, for update rule

    for i in range(steps): # 3. Main loop
        explore = random.uniform(0, 1) < exploration_rate 
        if explore:
            action = random.randint(0, k - 1) # 5. Exploration: Choosing random action
        else:
            action = max(Q, key=Q.get) # 6. Choose action with maximum mean reward

        reward = generate_reward(problem, action) # 7. Get reward for current action
        N[action] += 1 # 8. Update action number
        Q[action] += (1 / N[action]) * (reward - Q[action]) # 9. Update value dict

这个算法适用于每个多臂老虎机问题。

创建价值字典。我们把行动编号当做关键词，平均奖励作为数值，这是最简单的方式。把所有关键词的数值初始化为0。
创建行动记录字典。我们需要它来更新价值字典的规则。同样都初始化为0.
for循环，给定循环次数；或者利用while循环，直到停止规则。
探索步骤。我们考虑算法是否需要进一步探索。为了达到目的，我生成一个0到1之间的随机数，并且用它来和探索率进行比较。
如果代码需要进一步探索，就随机选择一个行动。
另一种方法，我们选择用Q字典中具有最大数值的关键词所代表的行动。
得到相应的回报奖励。
增加行动记录词典中对应的行动次数。
更新规则。书的作者强调了这很重要，在后续的强化学习任务中都会用到。
这样就完成了我们的第一个简单的强化学习机。我知道学会强化学习是个很困难的过程，但是这个入门级的例子非常简单且有启发性。

结果

我使用不同的探索率运行了这个算法：0.0（贪婪算法），0.01，0.02，0.1，0.2. 而且结果给出了非常有趣的现象，让我们来看几个单独的运行结果：

但是我们没法从这些孤立的运行结果得到合理的结论。探索算法似乎表现的更好，但也不是一直都好。如果贪婪算法在第一次尝试中就成为最优的方法，就很难说明探索算法的优势。接下来应该参考2000次运行的平均结果：

现在结论很明显了。在训练的前期，所有算法都几乎一致；接下来，学习速率最快的方法更占优；在训练的后期，那些基于已有经验的方法达到最优。贪婪算法是效果最差的。
完整的代码见Vsnipp。