Monte Carlo Tree Search(MCTS)

Description

MCTS 适用于离散动作空间和连续动作空间，这里以离散动作空间举例。

初始状态为 $s_1$ ，如果遍历了所有从 $s_1$ 出发的路径，那么自然可以选出哪条路径是最佳路径。 这样做的缺陷是遍历空间太大，而且浪费时间。 我们需要选择那些有较高奖励（这个目的很明显）的状态，同时也会选经过很少次的状态（经过很少，说明对这个状态探索很少）。具体算法如下： MCTS:

1. 使用 TreePolicy(s_1) 得到一个叶子节点（新状态）$s_l$
2. 使用 DefaultPolicy(s_l) 计算叶子节点的得分（Q 值）
3. 更新从 $s_1$ 到 $s_l$ 之间的所有 Q 值，从 s_1 选取最佳动作

TreePolicy($s_t$): 如果 $s_t$ 没有完全被探索，那么就选取新动作 $a_t$ ；否则选取具有最优 Q 值的动作。

$$Q\left(s_t\right)=\frac{Q\left(s_t\right)}{N\left(s_t\right)}+2C\sqrt{\frac{2\ln N\left(s_{t-1}\right)}{N\left(s_t\right)}}$$