4.2　蒙特卡罗评估

蒙特卡罗评估是通过学习智能体与环境交互的完整轨迹来估计值函数的。所谓完整轨迹（Episode）是指，从一个起始状态开始，使用某种策略一步步执行动作，直至结束形成的经验性信息，包含所有时间步的状态、行为、立即回报等。

假设共执行T步，形成的完整轨迹如下：

<s₀，a₀，r₀，s₁，a₁，r₁，s₂，a₂，r₂，…，s_T，a_T，r_T>

使用蒙特卡罗方法评估策略时，对评估方法做了以下三点改变：因为是无模型的方法，无法通过贝尔曼方程迭代获得值函数，因此通过统计多个轨迹中累积回报的平均数对值函数进行估计；在求累计回报平均时采用增量更新的方式进行更新，避免了批量更新方法中对历史数据的存储，提高了计算效率；为了方便直接从估计对象中求解最优策略，蒙特卡罗将估计值函数V改为估计行为值函数Q，这样可通过贪心策略直接获得最优行为。

1．利用平均累积回报估计值函数

回到值函数、行为值函数最原始的定义公式，如下：

可见，值函数、行为值函数的计算实际上是计算累计回报的期望。在没有模型时，我们可以采用蒙特卡罗方法进行采样，产生经验性信息。这些经验性信息经验性地推导出每个状态s的平均回报，以此来替代回报的期望，而后者就是状态值函数。状态值函数的估计通常需要掌握完整的轨迹才能准确计算得到。

当要评估智能体的当前策略π时，可以利用策略π产生多个轨迹，每个轨迹都是从任意的初始状态开始直到终止状态，如下所示为多个完整的轨迹（Episode）：

轨迹1：<s₀，a₀，r₁₁，s₁，a₁，r₁₂，…，s₁，a₂，r_1k，…，s_T，a_T，r_1T>

轨迹2：<s₀，a₀，r₂₁，s₃，a₁，r₂₂，…，s₁，a_k，r_2k，…，s_T，a_T，r_2T>

…

计算一个轨迹中状态处s的累积回报返回值为：

为计算方便，轨迹中用累积回报代替立即回报（回报），则上面的轨迹可表示如下：

轨迹1：<s₀，a₀，G₁₁，s₁，a₁，G₁₂，…，s₁，a₂，G_1k，…，s_T，a_T，G_1T>

轨迹2：<s₀，a₀，G₂₁，s₃，a₁，G₂₂，…，s₁，a_k，G_2k，…，s_T，a_T，G_2T>

…

在状态转移过程中，可能发生一个状态经过一定的转移后又一次或多次返回该状态，此时在多个轨迹里如何计算这个状态的平均回报呢？可以有如下两种方法：第一次访问蒙特卡罗方法（初访）和每次访问蒙特卡罗方法（每访）。

初访法是指，在计算状态s处的值函数时，只利用每个轨迹中第一次访问到状态s时的累积回报。如上式轨迹1中，状态s₁出现了两次，但计算状态s₁处的累计回报均值时只利用s₁初次出现的累积回报G₁₂（不计算s₁第二次出现后的累积回报G_1k）。轨迹2中，状态s₁仅出现了一次，其累积回报为G_2k。因此初访法计算V（s₁）的公式为：

其中，N（s₁）表示包含状态s₁的轨迹数。

每访是指，在计算状态s处的值函数时，利用所有访问到状态s时的累积回报，如轨迹1，计算状态s₁处的均值时需要用到G₁₂和G_1k。因此每访法计算V（s₁）的公式为：

其中，N（s₁）表示状态s₁出现的总次数。

蒙特卡罗方法是用统计的方法求取值函数的，根据大数定律：当样本数量足够多的时候，即N（s₁）无穷大时，根据样本求取的值函数V（s₁）近似于真实值函数V_π（s₁）。

2．增量式更新

通常，蒙特卡罗法在求平均值的时候是采用批处理式进行的，即在一个完整的采样轨迹完成后，对全部的累积回报进行更新。实际上，这个更新过程可以增量式进行，使得在计算平均值时不需要存储所有既往累积回报，而是每得到一个累积回报之后就计算其平均值。

对于状态s_t，不妨假设基于k（初访法k指的是含有状态s_t的轨迹数，每访法指的是状态s_t的数目）个采样数据估计出值函数为V（s_t），增量式公式如下：

则在得到第k+1个采样数据G_t时（s_t状态对应累积回报），有：

可简写为：

显然，只需要给V（s_t）加上即可，更一般地，将替换为常数α，令1>α>0，表示更新步长，α越大，代表越靠后的累积回报越重要。

最终得到蒙特卡罗方法值函数估计的更新公式：

V（s_t）←V（s_t）+α（G_t-V（s_t））

3．估计行为值函数Q代替估计值函数V

动态规划中的策略迭代算法估计的是值函数V，而最终的策略通过行为值函数Q获得，或者下一个状态的V获得。当模型已知的时候，从值函数V到行为值函数Q有一个很简单的转换公式，可以根据此公式求解π'（s）：

同时因为知道和，也可根据如下公式求解π'（s）：

蒙特卡罗这种无模型方法难以通过上面两个方法求解策略，于是考虑将估计对象从值函数V改为行为值函数Q，也就是说蒙特卡罗方法估计的是行为值函数的值。

假设使用初访法，利用每个轨迹中第一次访问到状态s且采取行为a时的累积回报的平均值来计算状态行为对（s，a）的行为值函数。如轨迹1状态行为对（s，a）仅出现1次，其对应的累积回报为G₁₂，则有：

其中，N（s₁，a₁）表示包含状态行为对（s₁，a₁）的轨迹数。结合增量式更新公式，可得到行为值函数为：

Q（s_t，a_t）←Q（s_t，a_t）+α（G_t-Q（s_t，a_t））