蒙特卡洛方法

蒙特卡罗估计是指依靠重复随机抽样来解决近似问题的一大类技术。凡是需要做大量的采样实验，最后用实验的结果近似的方法，都可以称为蒙特卡洛估计的方法。

在之前介绍的策略迭代算法中，计算：

$$q_{{\pi }_k}(s,a)=\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_{{\pi }_k}\left(s^{\prime }\right)$$

时，$p(r\mid s,a)$、$p(s^{\prime }\mid s,a)$ 都是模型给定的，但如果没有给出概率模型（状态转移概率矩阵 $\mathbf{P}$）呢？

回到 $q_{{\pi }_k}(s,a)$ 最初的定义：

$$q_{{\pi }_k}(s,a)=\mathbb{E}[G_t\mid S_t=s,A_t=a]$$

定义折扣回报 $g(s,a)$ 为随机变量 $G_t$ 的一个采样，我们有 $N$ 个采样，有：

$$q_{{\pi }_k}(s,a)=\mathbb{E}[G_t\mid S_t=s,A_t=a]\approx \frac{1}{N}\sum _{i=1}^N{g}^{(i)}(s,a)$$

基于蒙特卡洛的强化学习

MC $\epsilon$-greedy （MC Epsilon-Greedy 算法）

$\epsilon$-greedy policy：

$$\pi (a\mid s)=\{\begin{array}{ll}1-\frac{\epsilon }{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1)& \text{for the greedy action}\\ \frac{\epsilon }{|\mathcal{A}(s)|}\end{array}$$

其中，$\epsilon \in [0,1]$，$|\mathcal{A}(s)|$ 是 $s$ 对应的动作数量。

$${\pi }_{k+1}(s)=\underset{\pi \in {\mathrm{\Pi }}_{\epsilon }}{\text{argmax}}\sum _a\pi (a\mid s)q_{{\pi }_k}(s,a)$$

其中，${\mathrm{\Pi }}_{\epsilon }$ 是所有 $\epsilon$-greedy policy 的集合，此时：

$${\pi }_{k+1}(a\mid s)=\{\begin{array}{ll}1-\frac{\epsilon }{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1)& a=a_k^{\ast }\\ \frac{\epsilon }{|\mathcal{A}(s)|}& a\ne a_k^{\ast }\end{array}$$