有模型学习和无模型学习

前面介绍的求解MDP的方法属于有模型学习的范畴，我们称为是动态规划(DP)方法，但在实际的强化学习应用场景下，DP方法往往不适用，原因有二：

1. DP方法应用的前提条件是环境完全已知，即环境的转移概率以及回报函数都是已知的，而这点在现实应用场景下往往无法满足
2. 即便环境是已知的，在状态个数非常大，或者是状态空间不是离散的情况下，DP方法也无法发挥作用

基于这两个原因，无模型学习(model-free learning)的方法往往更为适用，无模型学习方法的特点是：

1. 无模型学习直接通过对环境进行抽样来学习最优策略，这里的样本通常是一条轨迹$$s_0,a_0,r_0,s_1,a_1,r_1,\cdots ,s_{T-1},a_{T-1},r_{T-1},s_T$$单个样本是一个由状态，行为和回报组成的三元组，根据抽的样本进行策略评估和策略改进
2. 与DP方法不同，无模型学习或者说强化学习的目标不是追求精确地求出最优策略，而是求出一个近似最优的或者说次优(sub-optimal)的策略。因为即便是在环境完全已知的情况下，使用DP方法也会遇到维度灾难的问题，即求解精确策略的复杂度随状态空间的基数上升，状态空间基数太大或者状态空间是无穷情况下，求解精确最优策略在复杂度上是不可行的。
3. 由于model-free的方法通常基于抽得的样本进行学习，而数据往往是存在噪音的，从这个角度看，无模型学习也无法得到一个精确的最优策略。

本节我们介绍两种无模型学习的方法，Monte Carlo算法 以及时序差分算法(Temporal Difference,TD) ，这两种算法都无模型学习的范畴。回顾一下DP算法，DP方法的策略迭代算法由两部分组成：一部分是策略评估，我们也称为预测，即给定策略$\pi$，求出策略$\pi$的状态价值函数$V^{\pi }(s)$；另一部分是策略改进，我们也称为控制，即求解状态-行为价值函数$Q(a,s)$，在根据$Q$来选择最优行为，进行策略改进。后面我们以预测和控制两个词来指代策略评估 和策略改进 。

Monte Carlo算法

Monte Carlo方法就是直接用平均累积回报来估计状态价值函数和动作行为价值函数，我们先来考虑怎么估计状态价值函数$V^{\pi }$

预测

我们让代理人和环境$E$进行交互，得到长度为$T$的轨迹：
{s0,a0,r0,s1,a1,r1,⋯ ,sT−1,rT−1,sT}\{s_0,a_0,r_0,s_1,a_1,r_1,\cdots,s_{T-1},r_{T-1},s_T\}{s0​,a0​,r0​,s1​,a1​,r1​,⋯,sT−1​,rT−1​,sT​}我们现在有两种累积回报的定义，如果采取折现的方法，此时我们有一个经验累积回报函数
$${\hat{V}}_0^{\pi }(s_0)=\sum _{i=0}^{T-1}{\gamma }^i{r}_i$$通过多次采样，再求均值，就得到状态价值函数的一个估计。如果环境是MDP结构的，那么实际上每次状态转移之后，游戏就重新开始，因此实际上我们可以对这条轨迹上每一步进行统计，求出这一步的状态到最后一步的经验累积回报。即：如果在第$i$条轨迹的$t$时刻经过状态$s_t$，那么可以$V^{\pi }(s_t)$的一个估计，即
$${\hat{V}}^{\pi }(s_t)=\sum _{i=t}^{T-1}{\gamma }^{i-t}{r}_i$$
让其参与到价值函数的估计当中，这样可以充分利用整条轨迹的信息。

控制

在有模型的过程中，从状态价值函数$V$（后面简称为$V$函数）到状态行为价值函数$Q$（后面简称为$Q$函数）有一个很简单的转换规则：
$$Q^{\pi }(s,a)=E^{\pi }[R(s,a,s_1)|s_0=s,a_0=a]+\gamma E^{\pi }[V^{\pi }(s_1)|s_0=s,a_0=a]$$
然而，在无模型的条件下，我们既没有期望单步回报的信息，也没有转移概率的信息，所以无法从$V$函数直接转化成$Q$函数，因此我们选择直接去估计$Q$函数。我们有$Q$函数的定义：
$$Q^{\pi }(s,a)=E^{\pi }\left[\sum _{i=0}^{T-1}{\gamma }^i{r}_i|s_0=s,a_0=a\right]$$
所以我们同样可以用经验累积回报去估计$Q$函数，然后进行策略改进。

我们现在有两种方案：

第一种方案： 第一种方案我们只统计初始状态和初始行为的经验累积回报，然后求平均，这样，我们允许第一步偏离策略$\pi$，后面完全按照策略$\pi$进行，这样一条轨迹只会被利用一次

第二种方案： 利用轨迹每一步的状态行为对的信息

如果采用第二种方案：如果采用确定性策略，对于一个状态$s$，就只能选择一个状态，我们没有办法探索更多的状态-行为对。

这样的问题在强化学习中称为探索-利用困境(exploration-exploitation dilemma)，在无模型学习过程中，代理人要和环境进行交互，通常要进行两种操作：

• 探索(exploration)：代理人采取了某种行为，即便已经取得了较高的回报，但仍有可能存在其他更高回报的行为，代理人要尝试不同的行为来尽可能最大化累积回报
• 利用(exploitation)：直接简单重复已经学习到的高回报的行为，而不是冒着尝试更小回报的风险去探索

如果我们仅仅进行探索，即采取所有行为的机会都是均等的，那么就会失去很多选择最优摇臂的机会；但仅仅进行利用则相反，因为这样就没办法对累计回报函数进行有效的估计；因此走两个极端都对最大化累积回报函数不利，因此从要在两者之间进行这种。

因此，我们必须采用随机策略进行估计$Q$函数，并且每种行为都要有一定的概率取到，这样在$N\to \infty$时，我们能取到各种状态行为对，从而实现对$Q$的有效估计。我们可以采用$ϵ$贪心策略：
$$\begin{array}{r}{\pi }^{ϵ}(a|s)=\{\begin{array}{ll}1-ϵ+ϵ/|A|& a=\pi (s)\\ ϵ/|A|& otherwise\end{array}\end{array}$$
$ϵ$通常取一个比较小的数值，$ϵ$越大，说明策略越偏向于利用而不是进行探索。进行$Q$函数估计时，我们采取${\pi }^{ϵ}$策略来进行估计，但最终确定的策略采用一个最优的确定性的策略。在这里，用来评估和被改进的策略都是同一个策略${\pi }^{ϵ}$，因此这种算法是一种 同策略(on-policy) 的算法。

在这里，我们进行探索和改进的策略都${\pi }^{ϵ}$，但是最终使用的策略却是$\pi$，那么现在我们能不能用两个策略来进行策略评估和策略改进呢？也就是说，我们进行评估和改进的都是一个确定性策略，但是这样会陷入探索-利用困境当中，所以我们借用$ϵ$贪心策略进行辅助，对这个确定性策略进行评估和改进。

一个随机变量的函数的期望往往通过以下方式计算
$$\int f(x)p(x)dx$$我们现在有两个分布$p(x)$,$q(x)$，我们如何利用分布$q(x)$，得到$f(x)$在分布$p(x)$下的期望呢，很简单，做一个简单的变换即可
$$\int f(x)\frac{p(x)}{q(x)}q(x)dx$$这样我们可以按照$q(x)$进行抽样$x_1,\cdots ,x_n$，再计算$\frac{1}{n}{\sum }_{i=1}^{n}f(x_i)\frac{p(x_i)}{q(x_i)}$，这就是$f(x)$在分布$p(x)$下的估计。现在，我们要求能够穷尽所有的$(s,a)$，所以必须按照$ϵ$贪心策略进行抽样，但我们想要估计的却是在确定性策略下的$Q$函数，那么我们就可以采取上面的抽样方法，这就是monte carlo异策略算法的基本思路。在这里$x$应该理解成一条轨迹，也就是轨迹出现的概率，我们知道给定随机策略$\pi$，某条轨迹$\tau :s_0,a_0,s_1,a_1,\cdots ,s_T$的概率为
$$p^{\pi }(\tau )=\prod _{i=0}^{T-1}\pi (a_i|s_i)p(s_{i+1}|a_i,s_i)$$注意到上面的连乘式的转移概率是环境决定的，和策略无关，换另外一个随机策略${\pi }^{\prime }$，就有
$$p^{{\pi }^{\prime }}(\tau )=\prod _{i=0}^{T-1}{\pi }^{\prime }(a_i|s_i)p(s_{i+1}|a_i,s_i)$$这样两个概率相除就有
$$\frac{p^{\pi }(\tau )}{p^{{\pi }^{\prime }}(\tau )}=\prod _{i=0}^{T-1}\frac{\pi (a_i|s_i)}{{\pi }^{\prime }(a_i|s_i)}$$
这样我们无须计算任何的转移概率，而策略是我们已知的，这样，我们计算
$\frac{1}{n}{\sum }_{i=1}^n{R}_i{\prod }_{t=0}^{T-1}\frac{\pi (a_t|s_t)}{{\pi }^{\prime }(a_t|s_t)}$即可，这就得到了 异策略(off-policy) 的蒙特卡洛算法，${\pi }^{\prime }$是参考策略，$\pi$是我们要评估和改进的策略。当然在$\pi$是确定性策略的情况下，连乘式子分子部分非0即1，即$\pi (a_i|s_i)=I(a_i=\pi (s_i))$。

现在我们来总结一下同策略强化学习和异策略强化学习的区别，同策略强化学习是策略评估和策略改进都用同一种策略，而异策略强化学习则是使用两个策略进行策略评估和策略改进，一个策略用来进行抽样，作为参考策略，另外一个策略用于评估和改进，是输出的策略。

MC方法的收敛性分析

显然，MC方法的理论基础是大数定律；大数定律要求所有的样本是独立同分布的，在$N\to \infty$的情况下就会以概率1收敛到价值函数或状态价值函数的真实值。

我们以预测问题为例：我们要估计一个策略$\pi$的状态价值函数$V^{\pi }(s)$，如果是有限步的MDP，我们只走有限步这个估计当然是无偏估计，并且以概率1收敛到状态价值函数的真实值。但如果是无限步的MDP，那我们只能采集有限步的轨迹，那参与求均值的估计量就不是无偏，如果我们采用的MC算法是只统计第一步的状态的状态价值函数，并且采集多条轨迹，并且保证每个初始状态都能采集到足够多的长度为$T$的轨迹（如果条件允许的话），状态$i$的第$j$条轨迹得到的价值函数的估计值为
$${\hat{V}}_j^{\pi }(i)=\sum _{t=0}^{T-1}{\gamma }^t{r}_{i,j,t}$$其中$r_{i,j,t}$表示以$i$为初始状态的第$j$条轨迹在第$t$步得到的单步经验回报。实际上，如果是无穷步的MDP，那么游戏还远远没有结束，也就是实际上我们没能统计到$T$时刻以后的所有收益，实际无偏的价值函数估计应该是
$${\hat{V}}_j^{\pi ,u}(i)=\sum _{t=0}^{\infty }{\gamma }^t{r}_{i,j,t}$$这些估计都是真实价值函数$V^{\pi }(i)$的无偏估计，且不同轨迹得到的估计独立同分布，依据大数定理，这些估计求均值以概率1收敛到真实的价值函数$V^{\pi }(i)$，我们有限步的估计和真实的无偏估计的误差是
$${\hat{e}}_j(i)={\hat{V}}_j^{\pi ,u}(i)-{\hat{V}}_j^{\pi }(i)=\sum _{t=T}^{\infty }{\gamma }^t{r}_{i,j,t}={\gamma }^T\sum _{t=T}^{\infty }{\gamma }^{t-T}{r}_{i,j,t}$$而这个误差的均值显然不为0，因此，${\hat{V}}_j^{\pi }(i)$显然不是$V^{\pi }(i)$的无偏估计，偏差是${\gamma }^{T}E[{\sum }_{t=T}^{\infty }{\gamma }^{t-T}{r}_{i,j,t}]$，由于MDP都是有界回报，只要$T$足够大，这个偏差能足够小，这个偏差就取决于我们的轨迹长度，为了控制这个偏差，我们需要让轨迹的长度足够大。

实际上，我们用来估计的$V^{\pi }(i)$的估计量是
$${\hat{V}}^{\pi }(i)=\frac{1}{n_i}\sum _{j=1}^{n_i}{\hat{V}}_j^{\pi }(i)=\frac{1}{n_i}\sum _{j=1}^{n_i}{\hat{V}}_j^{\pi ,u}(i)+\frac{1}{n_i}\sum _{j=1}^{n_i}{\hat{e}}_j(i)$$由强大数定理，有
$$\frac{1}{n_i}\sum _{j=1}^{n_i}{\hat{V}}_j^{\pi ,u}(i)\to V^{\pi }(i)a.s.$$也就是当$n_i\to \infty$时，第一项以概率1收敛到$V^{\pi }(i)$

现在我们来看第二项，第二项有一个上界，设单步回报函数绝对值的最大值为$M>0$，那么$|{\hat{e}}_j(i)|\le {\gamma }^T{\sum }_{t=T}^{\infty }{\gamma }^{t-T}|r_{i,j,t}|\le \frac{{\gamma }^{T}M}{1-\gamma }$，所以
$$\left|\frac{1}{n_i}\sum _{j=1}^{n_i}{\hat{e}}_j(i)\right|\le \frac{1}{n_i}\sum _{j=1}^{n_i}|{\hat{e}}_j(i)|\le \frac{{\gamma }^{T}M}{1-\gamma }$$
只要$T$足够大，那么第二项就足够小，这样$N\to \infty$时，${\hat{V}}^{\pi }(i)$和$V^{\pi }(i)$的误差在概率意义下足够小，所以这种算法的误差控制有两个关键：第一，我们要求取的轨迹足够多，第二，我们要求取的轨迹足够长。前者控制方差，取得轨迹足够多则方差足够小，后者控制偏差，轨迹足够长偏差足够小。

如果我们采用充分利用每条轨迹的方法，由于每条轨迹中同一状态可能出现很多次，那么我们有两种方案，第一种方案是first-visit：尽管这个状态出现了很多次，但我们只利用一次，另一种方案是every-visit，即这个状态每次出现我们都利用起来。

前者当然能保证参与求均值的估计都是独立的（但由于轨迹长度不相同，所以不一定是同分布），而后者轨迹是有重叠的，所以独立性也无法得到保证，所以强大数定理并不适用。如果采用first-visit：每条轨迹会利用多次，偏差取决于轨迹的最短长度，最短长度轨迹的长度越长，偏差越小。

在下一节，我们将以一个实际的案例，来看MC方法对实际价值函数的逼近效果。

时序差分(TD)算法

Monte Carlo RL的一个优点是它不需要对环境作任何的假设，但与此同时也就没有用到环境的MDP结构，而时序差分算法则将Monte Carlo和环境的MDP结构充分结合起来，进行预测和控制

预测

在MDP结构下，就有如下的Bellman方程
$$V^{\pi }(s)=E^{\pi }\left[r(s,a_0,s_1)+\gamma V^{\pi }(s_1)|s_0=s\right]$$所以我们可以把中间的式子$r(s,a_0,s_1)+\gamma V^{\pi }(s_1)$作为$V^{\pi }(s)$的一个估计，和原有$V^{\pi }(s)$进行一个加权
$$\begin{array}{rl}{V}^{\pi }(s_t)\leftarrow & \alpha [r_t+\gamma V^{\pi }(s_{t+1})]+(1-\alpha )V^{\pi }(s_t)\\ =& V^{\pi }(s_t)+\alpha [r_t+\gamma V^{\pi }(s_{t+1})-V^{\pi }(s_t)]\end{array}$$
我们可以这样看上面的迭代式：按照Bellman方程我们对$V^{\pi }(s)$重新进行估计，即$r_t+\gamma V^{\pi }(s_{t+1})$，和原来的估计的误差是$\delta (s_t)=r_t+\gamma V^{\pi }(s_{t+1})-V^{\pi }(s_t)$，再乘以一个系数$\alpha$进行修正，即$V^{\pi }(s_t)\leftarrow V^{\pi }(s_t)+\alpha \delta (s_t)$。

这样进行更新的好处是，我们可以进行 在线学习(on-line learning) ，即不用等待整条轨迹采样完毕，整个游戏进行一步，就可以更新一次。

控制

同样地，在无模型的情况下，我们没办法从$V$转换到$Q$，但在最优策略的情况下
$$V^{\pi }(s)=Q(s,\pi (s))\forall s\in \mathcal{S}$$就有Bellman最优方程
$$Q^{\pi }(s,a)=E^{\pi }[r+\gamma V(s_1)|s,a]=E^{\pi }[r+\gamma Q^{\pi }(s_1,a_1)|s,a]$$所以同样地，可以这样更新$Q$函数
$$Q^{\pi }(s_t,a_t)\leftarrow Q^{\pi }(s_t,a_t)+\alpha [r(s_t,a_t,s_{t+1})+\gamma Q^{\pi }(s_{t+1},a_{t+1})-Q^{\pi }(s_t,a_t)]$$
然后再按照$Q$函数来进行策略改进。同样地，这种更新也是进行一步，更新一次，无须等待整条轨迹采样完毕，也是一种 在线学习 的算法。

SARSA算法的全称是State、Action、Reward、State、Action，第一个State指代前一刻的状态，第二个Action指代前一刻的行为，第三个Reward指代这一步的单步回报，后面两个State、Action分别是后一刻的状态和后一刻的行为，知道这五元组，就可以进行一次更新，得到Q-table。因此称为SARSA算法。当然，为了算法能对环境有足够的探索，我们还是要采用$ϵ$贪心算法

SARSA算法是一种on-policy的算法，也就是说：SARSA算法评估和改进的都是$ϵ$贪心策略，而最终使用的确是一个确定性的策略。那么同样地，也有一个off-policy的版本，称为Q-learning算法，Q-learning算法用$ϵ$贪心策略进行抽样，再更新原策略的Q-table，是一种off-policy的算法；与SARSA算法不同的是，Q-learning下一时刻的行为是由已有的Q-table最大化的$Q(s_{t+1},a)$决定的，而不是由$ϵ$贪心策略决定的。Q-learning的更新准则如下：
$$Q(s_t,a_t)\leftarrow \alpha (r_t+\gamma \underset{a}{\max }Q(s_{t+1},a)-Q(s_t,a_t))$$

以上的算法中的$\alpha$也不是固定的，而应该随着迭代过程衰减，以预测问题为例，我们的迭代式可以写成
$$V_{t+1}(s_t)\leftarrow {\alpha }_t(r_t+\gamma V_t(s_{t+1})-V_t(s_{t+1}))$$
只要${\sum }_{t=0}^{\infty }{\alpha }_t=+\infty ,{\sum }_{t=0}^{\infty }{\alpha }_t^2<+\infty$，那就会以概率1收敛到真实的状态价值函数。