立帖要读paper，已经过了快两周了，还一篇博文都没发出来，略汗。
今天第一篇，读的是今年ICML的十年Test of Time Award得奖论文Combining Online and Offline Knowledge in UCT，来自Sylvain Gelly和David Silver，发表于十年前的ICML 2007（所以，我还是没有开始讨论今年的paper...）。作者Sylvain Gelly现在Google Brain。David Silver现在在DeepMind任职，是AlphaGo的主要领导者之一，也是AlphaGo的Nature论文的并列第一作者。这篇获奖文章中提出的想法，后来被广泛运用到围棋程序中，AlphaGo也从中得到了很多养分。这届ICML的十年大奖颁给这篇文章，应当多少也有向AlphaGo致意的意思吧。
这篇文章提出了经典的UCT算法的三个改进，让其性能得到了大幅提升。这里的UCT算法开创了Monte-Carlo Tree Search，其想法也很简单易懂，由下面两个式子决定：
$$Q_{UCT}^{igoplus}(s, a) = Q_{UCT}(s, a) + csqrt{frac{log n(s)}{n(s, a)}}$$
$$pi_{UCT}(s) = argmax_a Q_{UCT}^igoplus (s, a)$$
这里(Q_{UCT}) 是UCT的value function，(n(s))和(n(s, a))分别是状态s和状态-动作对(s, a)的访问计数，(n(s)=sum_a n(s, a))，即在搜索或者学习的过程中经历s或者(s, a)的次数，(pi_{UCT}(s))是UCT算法的最终策略，在状态s处选择执行动作(pi(s))。(Q_{UCT}(s, a))通过下面的Monte-Carlo学习方法来学：
$$Q_{UCT}(s, a)leftarrow Q_{UCT}(s, a) + frac{1}{n(s, a)}[R - Q_{UCT}(s, a)]$$
这里R是在状态s执行动作a之后得到的reward。每一个episode(s_1, a_1, s_2, a_2, ..., s_T, a_T)结束之后，可以用这个式子来更新所有的(Q_{UCT}(s_t, a_t))。
UCT的树搜索算法保留三个表(Q_{UCT}(s, a))，(n(s, a))和(n(s))，然后每到一个状态s，就开始按照自己的policy进行simulation，simulation一直进行到episode结束，得到simulated reward，据此更新这三个表，当设定的思考时间到之后，再根据UCT计算出应当选择的动作。UCT算法基于更之前的Upper Confidence Bound (UCB)方法，value function (Q_{UCT})保证了算法的正确性，即看过足够量的数据之后根据这个value function进行决策保证最优；另一方面(sqrt{log n(s) / n(s, a)})一项鼓励尝试各种不同的动作，而分子中的(log n(s))同时保证最终这一鼓励探索的一项将会变得可以忽略。
再回到这篇获奖文章本身，它提出了三个想法，所有的想法都在当时尚未解决的9x9围棋上进行验证：
第一，默认策略。在UCT算法中，如果某一个状态s尚有未被探索过的动作，则在simulation进行到该处或环境状态变为该状态后，UCT会在未被探索过的所有a中随机选择一个。这篇文章提出，使用这样的随机策略远非最优，我们可以使用一个默认策略，用它进行决策。而这个默认策略可以通过offline的self-play学到。这是个很简单的想法，实验验证这一想法对效果提升有少量帮助。
第二，Rapid Action Value Estimation (RAVE)。这个想法的提出是为了快速的得到一个不错的value function estimate。在大状态空间的环境中，要想有效地探索所有的状态非常困难，一个agent无法用足够多的经验去准确估计大部分状态的value function。RAVE这个想法说的是，在一个episode(s_1, a_1, s_2, a_2, ..., s_T, a_T)中，我们并不单单只是用最后的reward R去更新所有对应的((s_t, a_t))对，而是同时也更新((s_t, a_{t'}), forall t'>t)。即把所有t时刻以后的适用的动作都当做是直接作用在(s_t)上，即便它可能发生在很远以后才遇到的(s_{t'})状态中。这样就能显著地提高每一个((s, a))对的数据量，快速的得到一个较好的Q函数。RAVE这个办法对于围棋非常有效，因为某一盘面后的很多着法对于当前的盘面都是不错的选择。但对于其他更通用的场景这个想法不一定能很好的适用。而且，这个方法虽然能够快速得到准确的Q函数估计，但它实质上会引入一些bias，毕竟后面发生的事情并不能直接当做发生在当下，所以使用时还需要一些合适的weighting，才能让其能不跑偏。
第三，node prior。在UCT中(Q(s, a))通常初始化为第一次的reward，(n(s, a))通常初始化为1，这篇文章提出可以用一个prior，特别是Q可以通过offline的self-play学到，并作为prior。实验中这个想法的效果也很突出。
读这篇文章的时候最大的感觉就是，十年前AlphaGo的雏形Monte-Carlo Tree Search其实已经出来了，当时距离最近的AlphaGo最主要的差别就是神经网络。而现在神经网络加上MCTS已经成为了完整信息game play的标配。