【详细原理】蒙特卡洛树搜索

创作时间:

作者:

@小白创作中心

【详细原理】蒙特卡洛树搜索

引用

CSDN

https://m.blog.csdn.net/qq_51957239/article/details/142301015

蒙特卡洛树搜索（MCTS）是一种用于决策过程的启发式搜索算法，特别适用于具有巨大搜索空间的游戏和问题，例如围棋、国际象棋和复杂的组合优化问题。本文将从单一状态蒙特卡洛规划、上限置信区间（UCB）策略，再到MCTS的核心概念和关键组件，层层递进，详细解析这一重要算法的原理和应用。

单一状态蒙特卡洛规划：多臂赌博机

多臂赌博机问题（Multi-Armed Bandit）是强化学习中的经典问题，涉及在有限的时间内，从多台赌博机（即“臂”）中选择，以最大化累积奖励。单一状态蒙特卡洛规划是一种解决该问题的有效方法。

问题描述

假设有K个臂的赌博机，每个臂k的奖励分布未知。目标是在T次尝试中，选择臂a_t，使得累积奖励R = \sum_{t=1}^{T} r_{a_t}最大，其中r_{a_t}是在时间步t选择臂a_t获得的奖励。

探索与利用的权衡

在多臂赌博机问题中，需要在探索（尝试不同的臂以了解其潜在奖励）和利用（选择当前估计最优的臂以获取高奖励）之间取得平衡。

如果有k个赌博机，这k个赌博机产生的操作序列为X_{i,1}, X_{i,2}, \dots（i = 1, 2, \dots, k）。在时刻t = 1, 2, \dots，选择第I_t个赌博机后，可得到奖赏X_{I_t,t}，则在n次操作后定义悔值函数：

R_n = \max_{i=1,\dots,k} \sum_{t=1}^{n} X_{i,t} - \sum_{t=1}^{n} X_{I_t,t}

悔值函数表示了如下意思：在第t次对赌博机操作时，假设知道哪个赌博机能够给出最大奖赏（虽然在现实生活中这是不存在的），则将得到的最大奖赏减去实际操作第I_t个赌博机所得的奖赏。将n次操作的差值累加起来，就是悔值函数的结果。

很显然，一个良好的多臂赌博机操作的策略是在不同人进行了多次玩法后，能够让悔值函数的方差最小。

上限置信区间

在多臂赌博机的研究过程中，上限置信区间（Upper Confidence Bound, UCB）成为一种较为成功的策略学习方法，因为其在探索-利用（exploration-exploitation）之间取得平衡。

在 UCB 方法中，使X_{i,T_i(t-1)}来记录第i个赌博机在过去t-1时刻内的平均奖赏，则在第t时刻，选择使如下具有最佳上限置信区间的赌博机：

I_t = \arg\max_{i \in {1, \dots, k}} \left{ X_{i,T_i(t-1)} + c_{t-1,T_i(t-1)} \right}

其中，c_{t,s}取值定义如下：

c_{t,s} = \sqrt{\frac{2 \ln t}{s}}

T_i(t) = \sum_{s=1}^{t} \mathbf{1}(I_s = i)为在过去时刻（初始时刻到第t时刻）过程中选择第i个赌博机的次数总和。

当选择第i个赌博机的次数越少，s越小，c_{t,s}越大，即第i个赌博机获得的奖励越不确定，c_{t-1,T_i(t-1)}的意义在于摇动那些选择次数较少的赌博机以博取更大的奖励。

也就是说，在第t时刻，UCB 算法一般会选择具有如下最大值的第j个赌博机：

UCB = \overline{X}_j + \sqrt{\frac{2 \ln n}{n_j}} \quad \text{或者} \quad UCB = \overline{X}_j + C \times \sqrt{\frac{2 \ln n}{n_j}}

其中，\overline{X}_j是第j个赌博机在过去时间内所获得的平均奖赏值，n_j是在过去时间内拉动第j个赌博机臂膀的总次数，n是过去时间内拉动所有赌博机臂膀的总次数。C是一个平衡因子，其决定着在选择时偏重探索还是利用。

从这里可看出，UCB算法如何在探索-利用（exploration-exploitation）之间寻找平衡：既需要拉动在过去时间内获得最大平均奖赏的赌博机，又希望去选择拉动臂膀次数最少的赌博机。

蒙特卡洛树搜索

蒙特卡罗树搜索（Monte Carlo Tree Search，简称 MCTS）是一种用于决策过程的启发式搜索算法，特别适用于具有巨大搜索空间的游戏和问题，例如围棋、国际象棋和复杂的组合优化问题。MCTS 通过在决策树中进行随机模拟（也称为蒙特卡罗模拟），逐步构建搜索树，从而找到最优的决策路径。