[隐藏左侧目录栏][显示左侧目录栏]

蒙特卡洛法估计价值函数#

蒙特卡洛方法（Monte-Carlo methods）简单来说就是先做重复随机采样，然后根据大量的采样结果使用概率统计估计出目标值（类似大数定律）。下面说一下如何使用蒙特卡洛方法估计马尔可夫决策过程中的价值函数。

马尔可夫决策过程的状态价值函数公式为 V^\pi(s)=E[G_t|S_t=s]。可以看出这里是在对 G_t 求期望，那么可以通过采样得到尽量多的 G_t 之后对其求均值，使用均值近似期望值。这个思路的公式为：

\begin{equation}V^\pi(s) = E[G_t|S_t=s] \approx \frac{1}{N} \sum_{i=1}^N G_t^{(i)}\end{equation}

这里的回报 G_t 表示 t 时刻从状态 s 开始直到终止状态所有奖励的衰减之和。

在实际采样时得到的是一个个序列，在每个序列中，状态 s 可能没有出现过、可能出现过一次、可能出现过多次。对于出现过多次的情况，在使用蒙特卡洛方法估计价值函数时可能有不同的选择：a）可以是仅使用第一次出现的该状态计算 G_t，之后再出现就全部忽略；b）还可以是每次出现的该状态都用于计算 G_t。下面描述的蒙特卡洛算法采用的是（b）方案。整个算法如下：

（1）使用策略 \pi 采样若干个序列，每个序列如下所示：

s_0^{(i)} \xrightarrow{a_0^{(i)}} r_0^{(i)}, s_1^{(i)} \xrightarrow{a_1^{(i)}} r_1^{(i)}, s_2^{(i)} \xrightarrow{a_2^{(i)}} r_2^{(i)}, ..., \xrightarrow{a_{T-1}^{(i)}} r_{T-1}^{(i)}, r_T^{(i)}

（2）对每一条序列中的每个状态 s 做以下操作：

  • 更新状态 s 的计数器：N(s) \leftarrow N(s) + 1
  • 更新状态 s 的回报：M(s) \leftarrow M(s) + G_t

（3）求每个状态 s 的回报的平均值：V(s) = M(s) / N(s)

最后，根据大数定律可知，当 N(s) \rightarrow \infty 时，有 V(s) \rightarrow V^{\pi}(s)。

以上就是使用蒙特卡洛方法估计马尔可夫决策过程的价值函数的整个算法，在上面的算法中需要保存全部的回报，最后求均值，还有一种实时求均值的方法，就是把上面的第（2）步的两个公式和第（3）步的公式合并为如下两个公式：

  • 更新状态 s 的计数器：N(s) \leftarrow N(s) + 1
  • 更新状态 s 的价值：V(s) = V(s) + \frac{1}{N(s)} (G - V(s))

至于为什么变换之后和变换之前是等价的，可以看下面的这个证明过程：

假设现在有 n 个数值：x_1, x_2, ..., x_n。定义这 n 个数值的均值为 \text{Avg}_n=\frac{1}{n}\sum_{i=1}^n x_i。求证 \text{Avg}_n = \text{Avg}_{n-1} + \frac{1}{n}(x_n - \text{Avg}_{n-1})。

证明：

\begin{split} \text{Avg}_n &= \frac{1}{n}\sum_{i=1}^n x_i \\ &= \frac{1}{n} (x_n + \sum_{i=1}^{n-1}x_i) \\ &= \frac{1}{n} (x_n + (n-1) \cdot \text{Avg}_{n-1}) \\ &= \frac{1}{n} (x_n + n \cdot \text{Avg}_{n-1} - \text{Avg}_{n-1}) \\ &= \text{Avg}_{n-1} + \frac{1}{n} (x_n - \text{Avg}_{n-1}) \end{split}

Reference#