16. 蒙特卡洛强化学习基本概念与算法框架

1. 是什么

蒙特卡洛强化学习(简称MC强化学习）是一种无模型强化学习算法，该算法无需知道马尔科夫决策环境模型，即不需要提前获得立即回报期望矩阵R（维度为(nS,nA)）、状态转移概率数组P（维度为(nA,nS,nS)），而是通过与环境的反复交互，使用统计学方法，利用交互数据直接进行策略评估和策略优化，从而学到最优策略。

2. 有何优点

• 无需环境模型
• 易于编程、通用性强。

3. 基本概念

为了更好的描述MC方法，深入理解如下概念非常必要。

3.1 立即回报

• 在某状态$s_t$下，智能体执行某行为$a_t$后，获得的一次来自环境的即时奖励，例如，在格子世界中寻宝的实验中，智能体在距离宝藏较远的距离时，向右移动后，获得来自环境的即时奖励为-1,在智能体位于宝藏左边时，向右移动1格后，获奖来自环境的即时奖励为0.
• 立即回报是随机变量，为了反映它的特征，可以用立即回报期望来描述，符号为$R_s^a=E_{\pi }(R_{t+1}|s_t=s,a_t=a)$

3.2 累积回报

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots =\sum _{k=1}^T{\gamma }^{k-1}{R}_{t+k}$$

• $G_t$：从某个状态s开始，遵循某个策略时从状态s开始直到最后终止状态$s_T$的带折扣的累积回报
• 由于$R_{t+k}$为随机变量，故$G_t$为随机变量；

3.3 状态值函数

• 为衡量状态s下遵循策略$\pi$的价值，取状态值函数$V_{\pi }(s)=E_{\pi }(G_t|s_t=s)$作为度量标准
• 为了从交互产生的统计数据中计算得到接近真实的状态值函数$V_{\pi }(s)$，可以取足够多回合的交互获得的$G_t$的样本的平均值

3.4 行为值函数

行为值函数是策略改进的依据，理论上，它可以通过状态值函数计算得到：
$$Q(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^{a}V(s^{\prime })$$
然而，实际上，由于$R_s^a$与$P_{s{s}^{\prime }}^a$未知，因此，MC方法通常不会通过估计状态值函数$V(s)$,然后使用Q(s,a)进行策略改进。
MC方法是利用交互数据直接估计Q(s,a),然后再基于Q(s,a)进行策略改进的。

3.4 回合（或完整轨迹，episode）

• 由3.3可知，要获得1个$G_t$样本，可以让智能体从任意某初始状态出发，一直遵循某种策略$\pi$与环境交互，直至状态转移到环境的终止状态$s_T$才结束。
• 我们把从某状态$\forall s\in S$出发，到终止状态$s_T$之间的完整状态、动作、立即回报的转换过程，称为1次完整的轨迹或1个回合，英文单词为Episode

3.5 多个回合（或完整轨迹）的描述

假设以任意起始状态开始的完整轨迹有多条条，则这多条完整轨迹可以表示为：
轨迹0：$s_{0,0},a_{0,0},r_{0,1},s_{0,1},a_{0,1},r_{0,2},\cdots ,s_{0,L_0},a_{0,L_0},r_{0,L_0+1},s_T,a_{0,L_0+1},r_{0,L_0+2}$
轨迹1：$s_{1,0},a_{1,0},r_{1,1},s_{1,1},a_{1,1},r_{1,2},\cdots ,s_{1,L_1},a_{1,L_1},r_{1,L_1+1},s_T,a_{1,L_1+1},r_{1,L_1+2}$
…
轨迹k：$s_{k,0},a_{k,0},r_{k,1},s_{k,1},a_{k,1},r_{k,2},\cdots ,s_{k,L_k},a_{k,L_k},r_{k,L_k+1},s_T,a_{k,L_k+1},r_{k,L_k+2}$
…

上述每条轨迹中的三元组$(s_{k,m},a_{k,m},r_{k,m+1}$表示轨迹k中，状态为$s_{k+m}$,执行行为$a_{k+m}$后获得的立即回报的采样值为$r_{k,m+1}$，$r_{k,L_k+1}$表示轨迹k时，智能体观测到的环境状态为终止状态的上一状态$s_{k,L_k}$下，执行动作$a_{k,L_k}$的立即回报采样。
可见，一条完整轨迹（回合或episode）,必须满足：

• 最后一个状态值$s_T$对应终止状态
• $L_k\ge 0$

4.MC强化学习问题的正式描述

已知：一个MDP（马尔科夫决策过程）环境的折扣系数$\gamma$、环境与智能体的交互接口，利用这个接口，智能体可以获得从任意状态$s_t\in S$下，执行行为空间中的某个行为$a_t\in A$后，来自环境的即时回报$r_{t+1}$和转移后的状态$s_{t+1}$、该新的状态是否为终止状态。
$$
求解：智能体如何利用环境的对外接口与环境交互，如何通过交互获得最优策略${\pi }^{\ast }(a|s)$？

5. 蒙特卡洛（MC）强化学习算法的基本框架

$$\begin{array}{rl}& \pi (a|s)=初始策略\\ & {\pi }_{sample}(a|s)=蒙特卡诺采样策略(可以和初始策略一样）\\ & Q(s,a)=0\\ & whileTrue:\\ & 依据{\pi }_{sample}与环境交互生成完整轨迹\\ & 利用轨迹数据进行策略评估以更新Q(s,a)\\ & 利用Q(s,a)进行策略控制以改进\pi (a|s)\\ & if满足结束条件:\\ & break\end{array}$$
可见，MC强化学习的关键在于策略评估与策略控制