AlphaGo 的棋局，与人工智能有关，与人生无关

这是强化学习里最简单的一个问题，在很多地方都有应用，比如互联网广告(https://support.google.com/analytics/answer/2844870?hl=en)，游戏厅有一个 K 臂的老虎机，你可以选择其中的一个投币，每个手臂都是一个产生一个随机的奖励，它们的均值是固定的（也有 Nonstationary 的多臂老虎机，我这里只考虑 Stationary 的）。你有 N 次投币的机会，需要想办法获得最大的回报(reward)。

当然如果我们知道这个 K 个手臂的均值，那么我们每次都选择均值最大的那个投币，那么获得的期望回报应该是最大的。

可惜我们并不知道。那么我们可能上来每个都试一下，然后接下来一直选择最大的那个。不过这样可能也有问题，因为奖励是随机的，所以一次回报高不代表真实的均值回报高。当然你可以每个都试两次，估计一下奖励的均值。如果还不放心，你可以每个都试三次，或者更多。根据大数定律，试的次数越多，估计的就越准。最极端的一种做法就是每个手臂都投一样多的次数；另外一种极端就是碰运气，把所有的机会都放到一个手臂上。后一种如果运气好是最优的，但是很可能你抽到的是回报一般的甚至很差的手臂，期望的回报其实就是 K 个手臂的平均值。前一种呢？回报也是 K 个手臂的平均值！我们实际的做法可能是先每个手臂都试探几次，然后估计出比较好的手臂（甚至几个手臂），然后后面重点尝试这个（些）手臂，当然偶尔也要试试不那么好的手臂，太差的可能就不怎么去试了。但这个“度”怎么控制就是一个很复杂的问题了。这就是 exploit-explore 的困境(dilemma)。利用之前的经验，优先“好”的手臂，这就是 exploit；尝试目前看不那么“好”的手臂，挖掘“潜力股”，这就是 explore。

一种策略(Policy)的 Regret （损失）为：

(from A Survey of Monte Carlo tree Search Methods)

我觉得 mu_j 应该放到求和符号里面的。

不要被数学公式吓到了，用自然语言描述就是：最理想的情况是 n 次都试均值最大的那个手臂(mu star)，不过我们并不知道，E[Tj(n)] 是这个策略下选择第 j 个手臂的期望。那么 R 就是期望的损失，如果我们的策略非常理想，这个策略只尝试最好的手臂，其它不试，那么 R 就是 0。

但是这样的理想情况存在吗？很明显不太可能存在（存在的一种情况是k个手臂的均值一样）。那么我们的策略应该尽量减少这个损失。

Lai and Robbins 证明了这个损失的下界是 logn，也就是说不存在更好的策略，它的损失比 logn 小（这类似于算法的大 O 表示法）。

所以我们的目标是寻找一种算法，它的损失是 logn 的。

UCB 就是其中的一种算法：

每次决策之前，它都用上面的公式计算每个手臂的 UCB 值，然后选中最大的那个手臂。公式右边的第一项是 exploit 项，是第 j 个手臂的平均回报的估计。这个值越大我们就越有可能再次选中它。第二项是 explore 项，n_j 是第 j 个手臂的尝试次数，n_j 越小这个值就越大，也就是说尝试次数越少的我们就越应该多尝试。当 n_j=0 时，第二项为无穷大，所以这个算法会首先尝试完所有的手臂（explore），然后才会选择回报最大的那个(exploit)，试了之后这个手臂的平均值可能变化，而且 n_j 增加，explore 值变小，接着可能还是试最大的那个，也可能是第二大的，这要看具体情况。

我们来分析一些极端的情况，一种情况是最好的（假设下标是 k)比第二好的要好很多，那么第一项占主导，那么稳定了之后大部分尝试都是最好的这个，当然随着 n_k 的增加 explore 项在减少(其它手表不变)，所以偶尔也试试其它手臂，但其它手臂的回报很少，所以很快又会回到第 k 个手臂。但是不管怎么样，即使 n 趋于无穷大，偶尔也会尝试一下其它的手臂的。不过因为大部分时间都在第 k 个手臂上，所以直觉上这个策略还是可以的。

另一种极端就是 k 个手臂都差不多（比如都是一样的回报），那么 exploit 项大家都差不多，起决定作用的就是 explore 项，那么就是平均的尝试这些手臂，由于 k 各手臂回报差不多，所以这个策略也还不错。 出于中间的情况就是有一些好的和一些差的，那么根据分析，大部分尝试都是在好的手臂上，偶尔也会试一试差的，所以策略的结果也不会太差。

当然这个只是简单的直觉的分析，事实上可以证明这个算法的 regret 是 logn 的，具体证明细节请参看论文《Finite-time Analysis of the Multiarmed Bandit Problem》。

MCTS（Monte Carlo tree Search）和 UCT（Upper Confidence Bound for trees）

(from A Survey of Monte Carlo tree Search Methods)

MCTS 算法就是从根节点（当前待评估局面）开始不断构建搜索树的过程。具体可以分成 4 个步骤，如上图所示。

1. Selection

使用一种 Policy 从根节点开始，选择一个最“紧急”(urgent)的需要展开(expand)的可以展开(expandable)的节点。

说起来有点绕口，可以展开的节点是非叶子节点（非游戏结束局面），而且至少还有一个孩子没有搜索过。比如上图展示的选择过程，最终选择到的节点不一定是叶子节点（只有它还有没有搜索过的孩子就行）。具体的选择策略我们下面会讨论。

2. Expansion

选中节点的一个或者多个孩子被展开并加入搜索树，上图的 Expansion 部分展示了展开一个孩子并加入搜索树的过程。

3. Simulation

从这个展开的孩子开始模拟对局到结束，模拟使用的策略叫 Default Policy。

4. Backpropagation

游戏结束有个得分（胜负），这个得分从展开的孩子往上回溯到根节点，更新这些节点的统计量，这些统计量会影响下一次迭代算法的 Selection 和 Expansion。

经过足够多次数的迭代之后（或者时间用完），我们根据某种策略选择根节点最好的一个孩子（比如访问次数最多，得分最高等等）。

上面的算法有两个 policy：tree policy 和 default policy。tree policy 决定怎么选择节点以及展开；而 default policy 用于 simulation（也有文献叫 playout，就是玩下去直到游戏结束)

在讨论 MCTS 和 UCT 之前，我们来分析一下人在下棋时的搜索过程。

（编辑：应用网_丽江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!