机器学习之——强化学习中的Bandit算法

强化学习是机器学习领域的一个重要分支，已在围棋（AlphaGo）、德州扑克、视频游戏等领域取得很大成功，并且已经被一些学者认为是实现强人工智能的关键。

基于强化学习玩FlappyBird游戏

Bandit算法是强化学习中的基础模型，理解这一模型，对理解强化学习的关键概念有很大的帮助。

图示为6-摇臂赌博机

Bandit又称为摇臂赌博机，根据摇臂数量又可以称为K-摇臂赌博机。上图显示了一个6-摇臂赌博机。这种赌博机的规则是：每次可以往机器里投入一枚硬币，然后按下K个中的一个摇臂，然后对应的机器会吐出若干硬币，也可能不吐。按下每个摇臂吐出硬币的概率都是未知的，有些摇臂吐硬币的概率高，有些则概率低。

在进行游戏时，有两种极端的策略：

1、仅探索（explore）：为了获知每个摇臂吐硬币的概率，每个摇臂都按下相同的次数，统计吐硬币的频率。

2、仅利用（exploit）：根据现有条件，总是选择吐硬币最多的那个摇臂。

显然，两种方式都不能获得最大的收益。现实中，在两种策略中进行折中是最好的，那么如何进行折中呢？

ε-贪心策略

这是一种最为常用的策略，其过程为：

1、随机选择一个0到1之间的实数，记为ε

2、以概率ε执行：从所有摇臂中随机选择一个（即探索）；以概率1-ε执行：选择平均收益最大的那个摇臂（即利用）。

上面过程中，通过ε的值可以在探索和利用之间进行折中。

ε-贪心法实际运行曲线

上图为实际运行中的ε-贪心策略的曲线，可以看到，ε越低，收敛越慢，达到同样的奖赏需要更多的尝试次数。

除了ε-贪心之外，还有其他的可行策略，例如softmax方法、置信区间上界（Upper Confidence Bound）方法、Thompson采样方法等，本文就不一一列举了。