机器学习系列（一）：在赌场怎么玩老虎机收益最大？

假设某一天，你进入赌场，前面有一排的老虎机，每个老虎机都有一个拉杆，拉一下，就会有一定的随机概率吐出价值不一的硬币。那么，你应该怎么去玩这些老虎机，才能在，比如，1000次，或是一天之内，或是几天之内的收益最大呢？

思考一分钟，你有什么想法？

这个问题，就是机器学习，实际上，是强化学习中的著名的多臂老虎机问题。很多的人都研究过这个问题，而且发明了一些很好的算法。今天，我们就来回顾一下这些算法。希望读者看完之后，下次去赌场能学以致用，发大财：）。

最直观的想法。如果维护一个每台老虎机每次拉杆吐出的硬币价值的估算值，那么每次选择估计值最大的老虎机，然后拉杆，想必结果不错。这个就是贪婪算法。当我们每次选择估计值最大的老虎机，我们是充分利用了前面积累的知识。但是如果我们选择一个不是当前最大估计值的老虎机，那么我们是在探索，也许能发现不是当前最好估计值的老虎机的估计值，也许能得到更好的结果。那么如何平衡利用当前最好估计值的老虎机，和探索其它非最佳估计值的老虎机，是这些算法的核心。

前面说到了估计值，那么如何估算一台老虎机在某个时刻t的拉杆吐出的硬币的可能价值？显而易见的办法是计算之前每个老虎机总共吐出的硬币的价值，除以这个老虎机被拉杆了多少次。这个和我们的常识很一致，蛮合理的。如下所示。

得到了每台老虎机在某个时刻t的拉杆吐出的硬币的估算值，事情就好办了。在时刻t，我们就选择估算值最大的老虎机，然后拉杆就行了。如下所示。

现在，根据前面的估算公式，换一种表示方法，就是把前几次的收益（硬币的价值）相加，然后除以拉杆次数。

上面这个公式显而易见。接下来，我们看看如何通过第n次的估算值来估算第n+1次的估算值，过程如下，也容易理解。

啊哈，推导结果，原来可以用一个简单的式子来表述。

直白点，就是新的估算值，是老的估算值经过简单的修正得到的。而其中的修正，是当前拉杆吐出的硬币的价值和老的估算值的差异打个折。大了减点，少了加点。

至此，我们知道了怎么来估算每个老虎机的将要吐出的硬币的价值，也知道了我们必须有一定的机会来探索当前非最佳估算值的老虎机（ε-greedy）。这样，就有了简单的多臂老虎机的算法。

我们看到，探索时，使用的是以某种概率ε随机的选择一个非最佳估计值的老虎机来尝试。实际上，可以做得更好，如果我们选择那些非最佳的老虎机，不是随机，而是根据谁最有可能今后成为最优，就选择谁。也就是说，如果一个老虎机已经被选择了很多次，那么它下次被选中的机会就应该减少。如果一个老虎机还没有被选中很多次，那么它下次被选中的机会就应该增大。于是，著名的UCB（upper confidence bound）算法发明了。如下所示。