Monte-Carlo Tree Search

蒙特卡洛树搜索

MCTS 通过已知或习得的状态转移模型 $p(\cdot \mid s,\ a)$ 和奖励模型 $\mathcal{R}(s,\ a)$ 在每个时间步上进行多次随机模拟：

Selection	Expansion	Backup

其中每个状态节点 $s$ 维护着动作访问次数 $N(s,\ a)$ 和动作价值函数估计值 $Q(s,\ a)$ 等统计信息。

模拟过程

Selection

MCTS 每次模拟从表示当前规划时间步的状态 $s^{0}$ 的根节点开始不断选择动作向下搜索，选择的策略可以是：

$a^{k} = \argmax_{a} \left[ Q(s,\ a) + c \sqrt{\frac{\ln (1 + N(s))}{1 + N(s,\ a)}} \right] = \argmax_{a} \left[ Q(s,\ a) + c \sqrt{\frac{\ln (1 + \sum_{b} N(s,\ b))}{1 + N(s,\ a)}} \right]$

即最大化置信区间上界（UCB）值，式中的第二项用于鼓励探索，$c > 0$ 为常数，对于 $N(s,\ a)$ 相对较少的动作该项的值较高。在当前节点 $s^{k}$ 和选择的动作 $a^{k}$ 的基础上可以通过 $p(\cdot \mid s,\ a)$ 采样出下一个状态 $s^{k + 1}$。

Expansion + Evaluation

重复上一步直到采样出一个新的状态节点 $s^{l}$ 后，将该状态节点加入搜索树中。为了评估该节点的状态价值 $v(s^{l})$，可以通过一个策略进行快速模拟得到回报或训练额外的价值网络 $v_{w}(s)$ 来近似。

Backup

完成对新建状态节点的评估后沿着第一步的搜索路径向上更新备份每个状态节点的统计信息：

$N(s^{k},\ a^{k}) \leftarrow N(s^{k},\ a^{k}) + 1 \qquad Q(s^{k},\ a^{k}) \leftarrow Q(s^{k},\ a^{k}) + \frac{1}{N(s^{k},\ a^{k})} \Big[ G^{k} - Q(s^{k},\ a^{k}) \Big]$

其中 $G^{k}$ 由 $l - k$ 步的累计折扣奖励和上一步中评估的状态价值组成用于估计动作价值：

$G^{k} = \sum_{\tau = k}^{l - 1} \gamma^{\tau - k} R(s^{\tau},\ a^{\tau}) + \gamma^{l - k} v(s^{l})$

在计算时间允许时重复以上的过程，最终通过根节点的 $N(s^{0},\ a)$ 或 $Q(s^{0},\ a)$ 来选择当前的动作并执行。

实际应用

AlphaGo

在围棋这种对称的扩展式博弈中，可以将对手的策略看作是状态转移模型。同时围棋的奖励信号较为稀疏，只有在一局游戏结束后才会给出，例如赢得棋局则 $r = +1$，输掉棋局则 $r = -1$：

AlphaGo 在 MCTS 的基础上引入了额外的策略网络 $\pi_{\theta}(a \mid s)$ 用于快速模拟评估，考虑到这种评估方式的随机性较大，AlphaGo 在 $\pi_{\theta}(a \mid s)$ 的基础上训练对应的状态价值网络 $v_{w}(s)$ 并取平均：

$v(s^{l}) = \frac{r(\pi_{\theta}) + v_{w}(s^{l})}{2} \Rightarrow G^{k} = v(s^{l})$

AlphaGo 的训练过程可以分为三步：

1. 基于大量的人类专家的游戏数据进行行为克隆以初始化策略网络 $\pi_{\theta}(a \mid s)$
2. 通过策略网络的自我博弈和 REINFORCE 算法进行策略提升
3. 利用训练好的策略网络继续进行自我博弈，并对价值网络 $v_{w}(s)$ 进行回归

AlphaGo Zero

与 AlphaGo 不同，AlphaGo Zero 通过 MCTS 进行自我博弈完成一局游戏，得到行为数据和回报信息：

$\mathcal{X}_{\mathrm{MCTS}} = \{ (s_{0},\ p_{0},\ g_{0}),\ (s_{1},\ p_{1},\ g_{1}),\ \cdots,\ (s_{\mathrm{T}},\ p_{\mathrm{T}},\ g_{\mathrm{T}}) \}$

其中 MCTS 的决策策略基于动作访问次数 $p = \operatorname{normalize}(N(s^{0},\ \cdot))$，使用以上数据对策略网络进行行为克隆：

$\min_{\theta} \sum_{t = 0}^{\mathrm{T}} \mathcal{H} \Big[ p_{t},\ \pi_{\theta}(\cdot \mid s_{t}) \Big] = \sum_{t = 0}^{\mathrm{T}} \sum_{a} p_{t}(a) \ln \pi_{\theta}(a \mid s_{t})$

同时利用回报信息对价值网络进行回归，重复以上训练过程直到收敛。与 AlphaGo 相比，AlphaGo Zero 不再需要人类专家数据和 REINFORCE 的策略提升，而是直接向 MCTS 进行模仿学习，获得了更好的效果。