蒙特卡罗策略评估
对于一个问题，没有明确的状态转移概率，那么可以从两个方案解决这个问题，一是应用机器学习算法学习一个状态转移概率；二是应用免模型的强化学习算法，也就是用策略迭代去求解一个最优策略
蒙特卡罗策略评估
前几节讲到是动态规划的策略迭代，它在策略评估中应用了贝尔曼最优方程，使用到了状态转移概率，但现在没有了状态转移概率，所有要抛弃掉动态规划的策略评估，而使用
基于蒙特卡罗法的策略评估假设现在有一个策略 $\pi$，要用蒙特卡罗去评估它，有几个概念
(1). 经历完整的 $MDP$ 序列对于一个策略 $\pi$，去随机采样 $m$ 次，会产生 $m$ 条 $MDP$ 序列
$$
M_1:S_0^{<1>},A_0^{<1>},R_1^{<1>},S_1^{<1>},A_1^{<1>},R_2^{<1>},...,S_t^{<1>},A_t^{<1>},R_{t+1}^{<1>},..,S_{T-1}^{<1>},A_{T-1}^{<1>},R_T^{<1>},S_T^{<1>} \\
~\\
M_2:S_0^{<2>},A_0^{<2>},R_1^{<2>},S_1^{<2>},A_1^{<2>},R_2^{<2>},..,S_t^{<2>},A_t^{<2>},R_{t+1}^{<2>},..,S_{T-1}^{<2>},A_{T-1}^{<2>},R_T^{<2>},S_T^{<2>} \\
~\\
\vdots \\
~\\
M_m:S_0^{<m>},A_0^{<m>},R_1^{<m>},S_1^{<m>},A_1^{<m>},R_2^{<m>},..,S_t^{<m>},..,S_{T-1}^{<m>},A_{T-1}^{<m>},R_T^{<m>},S_T^{<m>}
$$
(2). 动作值函数的样本均值目标是：评估策略 $\pi$，就需要计算动作值函数 $Q(s,a)$，根据动作值函数的定义公式（2-2）
$$
Q(s,a)=E_\pi \left[R_{t+1}+\gamma\cdot R_{t+1}+\cdots+\gamma^{T-t-1} \cdot R_T \mid S_t=s,A_t=a\right]
$$
由于现在却不知道概率表达式，无法直接去求期望，所以退而求其次，根据上面的采样序列去求
样本均值，用样本均值近似代表期望
$$
G^{<i>}(s,a)=R_{t+1}+\gamma\cdot R_{t+1}+\cdots+\gamma^{T-t-1} \cdot R_T,\ \ i=1,2,\cdots,m \tag{8-1}
$$
代表从状态 $s$ 出发，执行动作 $a$，序列 $(s,a)$ 产生的第 $i$ 条 $MDP$ 序列的累计折扣奖励
$$
Q(s,a)\approx \bar{Q}(s,a)=\frac{\sum G^{i}(s,a)}{m},\ \ i=1,2,\cdots,m \tag{8-2}
$$
对于不同的 $(s,a)$，都要产生 $m$ 条完整的 $MDP$ 序列
(3). 访问方式1.首次访问
如上述所示，是每一个 $(s.a)$ 都产生 $m$ 条 $MDP$ 序列
2.每次访问
对上述采样方法进行优化，对于一个比较长的完整的 $MDP$ 序列，其中的子序列也可以单独拿出来作为一个新的 $MDP$ 序列，只要序列 $(s,a)$ 出现在第 $i$ 条 $MDP$ 序列中，那么就算作一次，这样就只用提前产生 $m$ 条序列，然后计算里面 $(s,a)$ 出现的次数
$$
I^i(s,a)=
\begin{cases}
1 &(s,a)\in M_i \\
~\\
0 &(s,a)\notin M_i\\
\end{cases} \ \ \ \ \ i=1,2,\cdots,m \\
~\\
Q(s,a)\approx \bar Q(s,a)=\frac{\sum G^i(s,a)}{\sum_{i=1}^m I^i(s,a) },\ \ i=1,2,\cdots,m \tag{8-3}
$$
(4).
首次访问蒙特卡罗策略评估算法（8-4）- 输入：环境模型 $MDP(S,A,R,\gamma)$，待评估的策略 $\pi$，要生成的 $MDP$ 序列条数 $m$
- 初始化：累积回报 $Gsum(s,a)=0$，计数器 $K(s,a)=0$
- 过程：随机抽样，根据当前策略 $\pi$，抽样产生 $m$ 条经历完整的 $MDP$ 序列
- $\qquad$ 循环：$i=1\sim m$
- $\qquad \qquad$ 循环：依次遍历第 $i$ 条 $MDP$ 序列中的所有状态动作对 $(s,a)$
- $\qquad \qquad \qquad$ 若 $(s,a)$ 首次出现在 $MDP$ 序列中，根据公式（8-1）计算累积折扣奖励
- $\qquad \qquad \qquad$ 累计回报：$Gsum(s,a)\leftarrow Gsum(s,a)+G^i(s,a)$
- $\qquad \qquad \qquad$ 更新计数：$K(s,a)\leftarrow K(s,a)+1$
- $\qquad$ 策略评估：$\bar Q_\pi(s,a)\leftarrow Gsum(s,a)/K(s,a)$
- 输出：样本均值 $\bar Q_\pi$ 作为动作值函数的近似
增量式蒙特卡罗策略评估
不要产生全部序列后再进行策略评估，而是产生一条序列，就计算到目前为止的样本均值
(1). 计算样本均值的增量法对于一个序列 $\{x_i\},i=1,2,\cdots,k$
$$
\begin{split}
\bar x_k=\frac{1}{k}\sum_{i=1}^k x_i&=\frac{1}{k}\left(\sum_{i=1}^{k-1}x_i+x_k \right)=\frac{1}{k}\left(\bar{x}_{k-1}\cdot(k-1)+x_k \right) \\
~\\
&=\frac{k-1}{k}\cdot \bar{x}_{k-1}+\frac{1}{k}x_k=\bar{x}_{k-1}+\frac{1}{k}(x_k-\bar{x}_{k-1})
\end{split} \tag{8-5}
$$
(2). 增量法计算动作值的样本均值采样到了第 $k$ 条链，就计算前 $k$ 条链的样本均值
$$
\bar{Q_\pi}^k(s,a)=\bar{Q_\pi}^{k-1}(s,a)+\frac{1}{n_k}\left(G^i(s,a)-\bar{Q_\pi}^{k-1}(s,a) \right) \\
~\\
n_k=\sum_{j=1}^iI^j(s,a) \tag{8-6}
$$
其中 $i$ 代表当前统计到第 $i$ 条链，若 $(s,a)$ 没有在第 $i$ 条链统计到，则为 $0$；$n_k$ 表示 $(s,a)$ 在 $1,2,\cdots,i$ 条链中出现的次数
(3). 增量式首次访问蒙特卡罗策略评估算法（8-7）- 输入：环境模型 $MDP(S,A,R,\gamma)$，待评估的策略 $\pi$，要生成的 $MDP$ 序列条数 $m$
- 初始化：动作值 $\bar{Q}_\pi(s,a)=0$，计数器 $K(s,a)=0$
- 过程：
- $\qquad$ 循环：$i=1\sim m$
- $\qquad \qquad$ 随机抽样，根据当前策略 $\pi$，抽样产生一条经历完整的 $MDP$ 序列
- $\qquad \qquad$ 循环：依次遍历序列中的所有状态动作对 $(s,a)$
- $\qquad \qquad \qquad$ 若 $(s,a)$ 首次出现在 $MDP$ 序列中，根据公式（8-1）计算累积折扣奖励
- $\qquad \qquad \qquad$ 更新计数：$K(s,a)\leftarrow K(s,a)+1$
- $\qquad \qquad \qquad$ 策略评估：$\bar Q_\pi(s,a)\leftarrow Gsum(s,a)/K(s,a)$
- 输出：样本均值 $\bar Q_\pi$ 作为动作值函数的近似
蒙特卡罗和动态规划策略评估的对比
（1）动态规划策略评估比蒙特卡罗策略评估更准确高效
（2）蒙特卡罗策略评估比动态规划策略评估适用范围更广
（3）蒙特卡罗策略评估中动作值的计算是相互独立，$Q(s1,a1)$ 和 $Q(s2,a2)$ 互不影响，而且可以只计算一部分动作值，而动态规划策略评估中动作值之间是相互影响的，必须计算所有动作值
（4）动态规划策略评估的迭代是以时间步为单位的（$Step-by-Step$），每一个时间步都会更新动作值，更新频率更高；而蒙特卡罗法的迭代式以交互回合为单位的 ($Episode-by-Episode$)，必须要完成至少一个回合的交互，得到一条经历完 整的 $MDP$ 序列才能更新动作值，更新频率更低
参考
这个夜晚，怎能安眠？