BBIN明星游戏学习初探-从多臂老虎机问题说起

2018年我开始了机器学习相关领域的博士生涯，相比于目前流行的深度学习以及类似的需要大量训练数据来生成模型的监督学习方法，强化学习一个重要的不同点是利用训练的数据去评估（evaluate）下一步的行动（action），而不是仅仅指示（instruct）出正确的行动。

导师提供了一个有趣的问题作为切入点来深入理解“强化学习”，那就是多臂老虎机问题（multi-armed bandit）。

多臂老虎机实验本质上是一类简化的强化学习问题，这类问题具有非关联的状态（每次只从一种情况输或赢中学习），而且只研究可评估的反馈。

假设有一台N个摇臂老虎机，每拉一个摇臂都会有一定的概率获得回报，这样我们有了N种可能的行动（每个摇臂对应一种action），并且每次行动的结果只和当前的状态关联而不受历史行动的结果影响（每次拉摇臂的回报只和老虎机设置的概率相关，之前输赢的结果不会影响本次行动）。

我们可以正式定义这种问题是具有单一状态的马尔科夫决策过程。

我们玩了一轮后发现其中一个摇臂回报最好，接下来该如何玩？这里也涉及强化学习一个有趣的主题：“如何在探索（exploration）和利用（exploitation）之间找到更好的平衡”。

我们的目标是通过探索和利用使收益最大化，多年来有多种算法被应用到这类问题中，在接下来的部分我会展示几种策略，并提供python的实现来验证每种策略的表现。BBIN明星游戏

实验部分我们以N=3为例，并且设定老虎机的回报满足伯努利分布，即回报结果为0/1. 在初始状态S0时，三个摇臂（A、B、C）每次回报为1的概率分别是30%, 50%和80%.

针对每种策略我们在每一轮运行1000次的拉摇臂行为，一共模拟2000轮。

同时我们用实验统计的每个摇臂的回报率与真实回报率的方均根差（RMSE）来评估探索（exploration）的表现。

如果平均回报总数和方均根差都很低，可以认为该策略是偏重探索的策略；反之如果两者结果都很高，BBIN明星游戏则是偏重利用的策略。

假设你已经知道回报率80%的那台老虎机，那最直接的策略就是一直玩这一台，每一轮玩1000次后回报应该是800. 这里列出该策略也是先明确一下平均回报总数的上界，

以上的程序执行了一轮的模拟（1000次拉摇臂的行为），一轮结束后将回报总数存到cumulatedreward中。

针对随机策略，实际上是每个摇臂都有1/3的概率被选到，所以拉1000次摇臂后理论上结果应该接近与（300+500+800）/ 3 = 533.3。

每一轮的统计结果可能有一些小波动，所以我们运行2000轮模拟计算平均回报总数来中和这些波动。

以下是2000轮之后的结果，完整代码请见github中的random_agent_bandit.py文件。

这里的平均回报总数已经非常接近理论上的回报值了，同时RMSE也非常的低，说明该策略过于偏重探索，在利用方面相较于最优的回报800是明显失衡的。

这也是一种很直接的策略，先把所有的摇臂都拉一次，然后选择回报最好的老虎机一直玩下去。

这种策略很明显不鼓励进行探索，而且很容易被每个摇臂第一遍的回报结果误导。

同样在2000轮模拟，每轮拉1000次的程序（greedy_agent_bandit.py）运行后，结果如下：

测试结果明显高于之前的随机策略，尽管如此，RMSE的结果接近0.18，说明在探索方面是失衡的。

该策略结合了之前两种算法，通过设置一个较小的?值，玩家在每次选择摇臂时，选择当前回报最高的摇臂去玩的概率是1-?（即exploitation的概率），而随机选择任意一个摇臂的概率是?（即exploration的概率）。

?的值通常设置为0.1，模拟程序（epsilon_greedy_agent_bandit.py）运行的结果如下：

平均回报的结果要高于之前的策略，而且RMSE的值也降到了0.005，BBIN明星游戏说明在随机的探索有效的收敛到了接近真实的回报概率分布，该策略维持了较好的平衡。

在前一种?-贪婪策略中，玩家在探索时总是按相同的概率随机选择一个摇臂，而使用softmax方法探索新的摇臂时，可能获取更多回报的摇臂会有更大的概率被选中。

softmax的函数实现如下：

在实验中，我们设置一个 σ 值，使玩家利用当前回报最高的摇臂的概率是σ，而继续探索的概率是1 - σ。

在探索时，根据当前每个摇臂的回报率，我们通过softmax函数计算出一个概率分布[p1, p2, p3], 基于此分布来选取下一步要探索的摇臂。

这种采样方式相当于在探索中有更高概率选取回报率较高的摇臂，即在探索中不忘利用。

在模拟程序（softmax_agent_bandit.py）中，BBIN明星游戏σ = 0.1，运行的结果：

可以看出利用的结果比前一种策略(Epsilon-greedy)稍好一点，但探索的错误率却较之略高（0.007 vs 0.005）。

可见探索与利用之间的平衡关系很微妙也很脆弱。

在Epsilon-greedy算法中我们设置了固定的? = 0.1，这不是一个理想的选择， 因为经过多次测试后，我们已经得到了所有摇臂相对准确的回报率的分布估计，此时我们应该适当减少探索，即降低epsilon的值，使得利用当前最好回报的摇臂的概率增加。

这里我们设置初始的? = 0.1，并采用线性下降的方法使得?最后降到0.0001，使得在每轮1000次测试中，从开始最多10%的概率去探索到最后一次几乎完全变为利用（此时? 接近于 0）。

这种策略下程序（epsilon_decreasing_agent_bandit.py）运行的结果：

平均回报略高于之前的策略，但错误率也变高了。

这样的结果再一次印证了利用和探索之间微妙的平衡关系。

感兴趣的读者可以尝试更快的下降方法，如指数级的下降，这样的策略会更多偏向于利用，理论上应该有更好的回报，但RMSE的错误率会更高。

理解该策略需要概率论和贝叶斯统计的一些知识，尤其是常见的概率分布和贝叶斯定理的基本原理。

在本实验中，我们通过拉一个摇臂赢和输的次数来评估所谓的效用函数，从统计学角度来说该效用函数就是多臂老虎机的伯努利回报分布的一个近似估计。

其中P(q)代表某个摇臂取得正回报的概率，f是输的次数。

这里最大似然估计有一个明显的问题就是在只有少量实验样本的时候回报概率的结果会有很大的偏差。

这样问题就变成了基于目前已有的实验数据，如何找到一个优化的伯努利分布的近似估计。

利用贝叶斯方法，我们可以定义当前各摇臂的回报率分布为先验分布，进而通过计算下一步行动的最佳后验概率去采样下一步的行动，这种方法就叫汤普森采样法，BBIN明星游戏 由William Thompson在1933年发表。

下面我们根据实验设定简单推导一下。

我们设定实验老虎机的回报满足伯努利分布（即1/0），每台摇臂获胜的概率为q，则输的概率是1-q。

同时我们定义s 和 f 分别是之前以一系列实验中收集的该摇臂获胜和输钱的次数，这样我们关心的是每个摇臂下一次可能获胜的后验概率分布，即P(qs,f)。

在贝叶斯定理中后验概率通过如下公式计算：

从这个公式中我们需要进一步计算P(s,fq) 和 P(q)，其中 P(s,fq)的含义是基于摇臂的胜率q，在s+f次实验中获胜s次的概率。

这里我们可以用二项式分布来计算一系列独立实验后获胜的次数，公式如下：

而另一部分P(q)代表与P(qs,f)属于共轭分布的先验分布，在伯努利分布中共轭先验分布是Beta 分布：

这里α,β代表胜率和失败率的大于0的参数， B是Beta分布中的正则化常量，以确保整体概率为1.

该结果从形式上是一个新的Bate分布，只是参数变成了α+s和β+f。

这样通过Bate分布和目前的各摇臂的胜负次数，我们能计算出每个摇臂当前最好的获胜概率，从而选择下一步的行动。

我们可以设定α=β=1，在没有先验知识的时候（s=f=0）相当于开始随机探索；胜负次数累积的越多，后验胜率就会评估的越准确。BBIN明星游戏

在python实现中，我们把三个摇臂当前的获胜次数(1+s)和失败次数（1+f）作为参数传入numpy.random.beta()方法中计算各摇臂的后验货胜率，然后选择当前胜率最大的摇臂去玩下一次。

Tompson sampling策略的平均回报是目前策略中最好的，0.05的错误率在效用函数中算是相对低的。BBIN明星游戏

从目前的设定看Thompson应该是最好的策略。

但是如果在更复杂的场景下，计算后验分布的复杂度也会相应增加。

所以需要更全面的评估某一算法的应用。

这里有更详细的Thompson Sampling的最新教程，我会在接下来的文章中进行更深入的分析。