一、免模型控制

在不知道马尔可夫决策过程模型的情况下，可以把策略迭代进行广义推广，得到广义策略迭代。其由2个步骤组成：

1. 根据给定的当前策略$\pi$来估计价值函数$V_{\pi }$；
2. 得到估计的价值函数后，通过贪心的方法改进策略，即
   $${\pi }^{\prime }=贪心函数(V_{\pi })$$二者相互迭代
   $${\pi }_{i+1}(s)=\underset{a}{\mathrm{argmax}}{Q}_{{\pi }_i}(s,a)$$可以计算出策略$\pi$的动作价值函数$Q(s,a)$，然后根据上式计算新策略。然而如果知道状态价值函数$V$，由于并不知道奖励函数$R$和状态转移$P$，因此无法根据下式计算$Q$函数
   $$Q_{{\pi }_i}(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P\left(s^{\prime }|s,a\right)V_{{\pi }_i}(s^{\prime })$$在此情况下，对策略评估部分修改，用蒙特卡洛方法代替动态规划方法，来估计Q函数。先进行策略评估，用蒙特卡洛方法估计策略$Q=Q_{\pi }$，然后策略更新：
   $$\pi (s)=\underset{a}{\mathrm{argmax}}Q(s,a)$$
   

通过蒙特卡洛方法产生很多轨迹，每条轨迹可以计算出价值，然后平均来估计Q函数。
为保证蒙特卡洛方法能够有足够的探索，采用$\epsilon$-贪心探索，指有$1-\epsilon$的概率按照Q函数来决定动作，有$\epsilon$的概率是随机的。$\epsilon$一般很小，且会随时间递减。
在一开始，由于不知道哪个动作是好的，因此会花费较多时间探索。随着训练次数增加，比较确定哪个动作是好的之后，会减少探索，把$\epsilon$的值变小，主要根据Q函数决定动作，而不怎么依赖随机。

对于任何$\epsilon$贪心策略$\pi$，关于$Q_{\pi }$的$\epsilon$-贪心策略${\pi }^{\prime }$都是一个改进，有$V_{\pi }(s)\le V_{{\pi }^{\prime }}(s)$：
$$\begin{array}{rl}{Q}_{\pi }(s,{\pi }^{\prime }(s))& =\sum _{a\in A}{\pi }^{\prime }(a|s)Q_{\pi }(s,a)\\ & =\frac{\epsilon }{|A|}\sum _{a\in A}{Q}_{\pi }(s,a)+(1-\epsilon )\underset{a}{\max }{Q}_{\pi }(s,a)(有1-\epsilon 的概率取到Q中最大)\\ & \ge \frac{\epsilon }{|A|}\sum _{a\in A}{Q}_{\pi }(s,a)+(1-\epsilon )\sum _{a\in A}\frac{\pi (a|s)-\frac{\epsilon }{|A|}}{1-\epsilon }{Q}_{\pi }(s,a)\\ & =\sum _{a\in A}\pi (a|s)Q_{\pi }(s,a)=V_{\pi }(s)\end{array}$$

1. SARSA – 同策略时序差分控制

SARSA算法是使用时序差分的框架来估计Q函数的算法。
它把原本时序差分方法更新V的过程，变成了更新Q，即
$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left[r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)\right]$$上式中的Q原来均为V。

可以看出，SARSA直接更新Q表格，然后更新策略。

其时序差分目标为$r_{t+1}+\gamma Q(s_{t+1},a_{t+1})$，时序差分误差为$r_{t+1}+\gamma Q(s_{t+1},a_{t+1})-Q(s_t,a_t)$。用$Q(s_t,a_t)$逼近$G_t$，则$r_{t+1}+\gamma Q(s_{t+1},a_{t+1})$就是目标值。
采用软更新的方式进行逼近，每次更新一点点，慢慢逼近目标值。

由于每次更新需要用到当前的$s,a,r$与下一步的$s^{\prime },a^{\prime }$，即$(s_t,a_t,r_t,s_{t+1},a_{t+1})$，估称为SARSA。

SARSA属于单步更新算法，如果不进行单步更新，而是$n$步更新，则为n步SARSA。
$$Q_t^n=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots +{\gamma }^{n}Q(s_{t+n},a_{t+n})$$

如果加上资格衰减函数$\lambda$并求和，就得到SARSA($\lambda$)的Q回报
$$Q_t^{\lambda }=(1-\lambda )\sum _{n=1}^{\infty }{\lambda }^{n-1}{Q}_t^n$$其更新策略为
$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left(Q_t^{\lambda }-Q(s_t,a_t)\right)$$
SARSA是一种同策略（on-policy）算法，优化的就是它要实际执行的策略，也直接使用下一步会执行的动作来优化Q表格。

2. Q-learning

Q-learning是一种异策略（off-policy）算法。

异策略有2种不同的策略：目标策略$\pi$和行为策略$\mu$。
（1）目标策略$\pi$不和环境交互，行为策略$\mu$用来探索环境。
（2）行为策略$\mu$尝试各种动作，结果有好有坏，再把所有动作喂给目标策略$\pi$。目标策略$\pi$只考虑采取最好的策略。
（3）轨迹都是行为策略$\mu$与环境交互产生的，利用这些轨迹来更新目标策略$\pi$。

异策略学习的好处：
（1）利用探索策略来学到最佳的策略，学习效率高；
（2）可以学习其他智能体的动作，即模仿学习；
（3）可以重用旧的策略产生的轨迹，节省资源。

Q-learning的目标策略$\pi$：
直接在Q表格上使用贪心策略，取它下一步可以得到的所有状态
$$\pi (s_{t+1})=\underset{a^{\prime }}{\mathrm{argmax}}Q(s_{t+1},a^{\prime })$$而目标策略$\pi$可以是随机的策略，但这里采取$\epsilon$-贪心策略，使其不至于完全随机。

构造Q-learning目标：
$$\begin{array}{rl}{r}_{t+1}+\gamma Q(s_{t+1},A^{\prime })& =r_{t+1}+\gamma Q(s_{t+1},\mathrm{argmax}Q(s_{t+1},a^{\prime }))\\ & =r_{t+1}+\gamma \underset{a^{\prime }}{\max }Q(s_{t+1},a^{\prime })\end{array}$$注意到：
（1）这里第一个等号右边的Q括号内，原本是动作的元素被写成了$\mathrm{argmax}Q(s_{t+1},a^{\prime })$，即：Q-learning的下一个动作都是通过$\mathrm{argmax}$操作选出来的。
换句话说：
原本是：$r_{t+1}+\gamma Q(s_{t+1},a_{t+1})$
现在是：$r_{t+1}+\gamma Q(s_{t+1},\mathrm{argmax}Q(s_{t+1},a^{\prime }))$
即：$a_{t+1}$是通过下列方式选出的：它使得Q最大，即$Q\to \max Q$，在找到$\max Q$之后，反向求出使得$Q$达到$\max Q$的那个$a_{t+1}$即可。这里的“反向求出a”的操作即为$\arg$。
（2）从第一个等号到第二个等号的原理：$r_{t+1}+\gamma Q(s_{t+1},\mathrm{argmax}Q(s_{t+1},a^{\prime }))$中采取的动作a，是让Q最大的那个a。那么在采取了这个a之后，Q自然就变成了$\max Q$，也就是第二个等号。

把Q-learning写成增量式学习的方式，时序差分目标变成$r_{t+1}+\gamma {\max }_{a}Q(s_{t+1},a)$，即
$$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left[r_{t+1}+\gamma \underset{a}{\max }Q(s_{t+1},a)-Q(s_t,a_t)\right]$$下图列出了SARSA和Q-learning的区别。

（1）SARSA在更新Q表格时用的是$A^{\prime }$，上图(a)提及“从$S^{\prime }$中选择$A^{\prime }$”。即：在获取下一个Q值的时候，$A^{\prime }$是下一步一定执行的动作，该动作可能是$\epsilon$-贪心算法得出的，也可能是Q最大化得出的，也可能单纯随机出来的，但$A^{\prime }$一定会被执行。简单记为“知行合一”，on-policy。
把$a^{\prime }$代入到$Q\leftarrow Q+\alpha [\cdot ]$这个结构中了，就表明$a^{\prime }$被执行了。
（2）Q-learning在更新Q表格时用的是$Q(S^{\prime },a)$而不是$Q(S^{\prime },a^{\prime })$，用的是老动作（不带上标一撇的a）。上图(b)提及“从$S$中选择$A$”。这个$A$不一定是下一步会执行的动作，因为下一步可能会探索。Q-learning的下一个动作不是由行为策略$\mu$选取的，它直接看Q表格，选最大值。
在$Q\leftarrow Q+\alpha [\cdot ]$这个结构中，只用$a$，因为$a^{\prime }$还没探索出来。一旦$a^{\prime }$经过行为策略探索出来了，那就是最好的，下一步直接查Q表选最大的，直接采用它即可。
$Q(S^{\prime },a)$是用$s^{\prime }$中的最大值计算的，和$a$无关。
（3）从Q表更新方式上理解：SARSA是把$s^{\prime }$行、$a^{\prime }$列的Q值代入到$Q\leftarrow Q+\alpha [\cdot ]$这个结构中，更新整个Q表；Q-learning是把$s^{\prime }$行、但仍为$a$列的Q值代入到$Q\leftarrow Q+\alpha [\cdot ]$这个结构中更新Q表。
（4）SARSA和Q-learning的更新公式是一样的，区别只在于目标计算的部分，SARSA是$r_{t+1}+\gamma Q(s_{t+1},a_{t+1})$，Q-leraning是$r_{t+1}+\gamma {\max }_{a}Q(s_{t+1},a)$。
（5）SARSA用自己的策略产生了$S,A,R,S^{\prime },A^{\prime }$这条轨迹，然后用$Q(s_{t+1},a_{t+1})$更新原本的Q值$Q9s_t,a_t)$。但是Q-learning并不知道实际上选择哪一个动作，它默认下一个动作就是在当前的Q表中找Q最大值即可，用的不是$a^{\prime }$，用的还是当前的$a$。
（6）SARSA：用下一个$s^{\prime }$、下一个$a^{\prime }$查找Q表；
Q-learning：在下一个$s^{\prime }$下的所有$a$中，找一个Q最大的，用这个Q值计算。
因为Q-learning用下一状态的最大Q做估计，只想着用最大，因此表现更贪心、更大胆一些。这里的大胆指的是Q-learning不会把$a^{\prime }$执行一下看看效果，它直接默认：如果该Q值最大，那么对应的该$a$就最好。
（7）二者的核心都是：$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha \left[Q目标值-Q(s_t,a_t)\right]$，区别在于目标值不同。
（8）Q-learning不需要提前知道$a^{\prime }$，就能更新$Q(s,a)$，且在学习之前不需要获取下一个动作$a^{\prime }$，只需要前面的$(s,a,r,s^{\prime })$。

3. 同策略和异策略

（1）SARSA是同策略算法，只用了一个策略$\pi$，使用它学习，也使用它与环境交互产生经验。如果策略采用$\epsilon$贪心算法，则需要兼顾探索和利用，因此为了保全自己，会显得有些胆小。另外由于$\epsilon$不断变小，因此策略不稳定。
（2）Q-learning是异策略算法，有两种策略——目标策略$\pi$和行为策略$\mu$，可以大胆使用行为策略探索得到的经验轨迹来优化目标策略，即用$\mu$优化$\pi$。行为策略$\mu$可以采用$\epsilon$贪心算法，但目标策略$\pi$采用的是普通的贪心算法，直接根据最大值找最佳策略。Q-learning不需要兼顾探索。
（3）SARSA相对保守，选择一条相对安全的迭代路线；Q-learning相对基金，希望每一步都获得最大利益。