强化学习演进史

本文主要是pinard老师的系列笔记详细请参考系列文章：https://www.cnblogs.com/pinard/p/9385570.html
一年多前看这一系列的文章时对这种一步一步改进的过程感受挺深。所以这篇笔记中，一起去看看得到的东西缺点在哪里，以及针对这种缺点的改进版是怎样。仅供复习吧，有错误欢迎指正谢谢。

机器学习可分三类：监督学习/无监督学习/强化学习，强化学习训练数据没有标签，评价标准是奖励值大小，且奖励值不是事先准备好喂入网络，而是延后处理的。
强化学习可以与环境交互后，依据交互结果奖励值学习。(交互的意思是拿当前数据去神经网络或实现类似功能的模型中模拟计算一把并得到返回结果) 也可以不与环境交互（model-based），或部分与环境交互学习(比如Dyna)
强化学习大体分三类 value-based/policy-based/model-based
强化学习常用于(包括不限于)游戏/机器人/自动驾驶等需要决策的场景其目标主要有求解控制/求解预测也就是求解下一步怎么走/这样走好不好

好吧一般开始强化学习之旅绕不开那些个要素概念的铺路我也没有创新：
如下是简化版：
1 环境的状态S: t时刻环境的状态St是它的环境状态集中某一个状态。
2 个体的动作A: t时刻个体采取的动作At是它的动作集中某一个动作。
3 环境的奖励R: t时刻个体在状态St采取的动作At对应的奖励Rt+1会在t+1时刻得到。
4 个体的策略(policy)π: 它代表个体采取动作的依据，即个体会依据策略π来选择动作。策略常用条件概率分布π(a|s)表示, 即在状态s时采取动作a的概率。即π(a|s)=P(At=a|St=s).此时概率大的动作被个体选择的概率较高。
5 个体在策略π和状态s时，采取行动后的价值（value）: 一般用vπ(s)表示。这个价值一般是一个期望函数, 因为价值要综合考虑当前的延时奖励和后续的延时奖励。强化学习演进史

...

另外，关于容易混淆的这几个概念：奖励R /g(t) 收获r 价值v 可以看看:
https://zhuanlan.zhihu.com/p/57117940

奖励reward: 即时的，每个状态下执行action后立即获得的评价性响应
收获return/Gt: 累计的，累计未来的reward
价值value: 全局的/统计学意义的，是我们希望通过采样进行估计和逼近的。
行为价值函数q：一般与状态相关。

后两者十分相似：其相同不同点分别为：
相同：
都为该步收获+下一状态价值，
不同:
q是在某一状态下某一行为或选定行为的描述，
v是某一状态的描述，包含了某一状态下所有行为的描述

一个状态的价值可以用该状态下所有行为的价值来表达，
一个行为的价值可以用该行为所能到达的后续状态的价值来表达

状态的最优价值等于该状态下的最优行为价值；
行为的最有价值为该行为可能进入的所有后续状态的最优状态价值加权得到

-------------------------------------------------

进入正题啦!

先看model_based

状态转化模型Pass′ 如果按照真实的环境转化过程看，转化到下一个状态s′的概率既与上一个状态s有关，还与上上个状态，以及上上上个状态有关。
其缺点是：依赖的东西太多啦！如果不做马尔科夫假设，难以建模
改进：引入MDP，用动态规划求解MDP
注意 MDP与马尔科夫链MC 不同点在于：MDP考虑了当前采取的动作带来的价值

首先我们递推st st+1的关系同样的可以得到动作价值函数 qπ(s)
vπ(s) = Eπ(Rt+1 + vπ(St+1) | st =s )

这些递推式子叫贝尔曼方程。贝尔曼方程是动态规划这类数学最优化方法能够达到最优化的必要条件

我们想要求一个最好的策略以便得到最好的收获或价值在最初期，可以定义最优状态价值函数为 v*(s) = max vπ(s) 即取所有此策略下的状态价值中最大一个。这里有缺点，呆会说。

求解最优策略基本解法有也三种：它们也是一个接一个的改进.
动态规划法
蒙特卡洛法
时序差分法

先看DP：
之前说过 RL 目标是求解控制/求解预测
策略评估求解预测或说价值：
通过贝尔曼方程来完成：

我们每一轮可以对计算得到的新的状态价值函数再次进行迭代，直至状态价值的改变很小（收敛），就得出了预测问题的解，即给定策略的状态价值函数v(π)

策略迭代求解控制：
循环如下两步得到收敛的策略π* 和状态价值V*
1 策略评估：利用贝尔曼公式 vπ(s) 迭代直到vπ(s)收敛
2 策略更新：用贪婪策略选取使v(s)最大的策略
注意策略迭代只有在状态价值更新到收敛后，才更新策略。

价值迭代求解控制：

没有等到状态价值收敛后，才调整策略，而是随着状态价值的迭代及时调整策略，更快。
动态规划法：利用贝尔曼方程迭代更新状态价值，用贪婪法迭代更新最优策略。

动态规划算法使用全宽度（full-width）的回溯机制来进行状态价值的更新，
在每一次回溯更新某一个状态的价值时，都要回溯到该状态的所有可能的后续状态，并利用贝尔曼方程更新该状态的价值。
其缺点是： 1：状态数较多问题规模较大时计算量太大啦! 2: 要求转化模型P已知，这个在实际中经常难以得到。
改进：蒙特卡洛法。注意，这里已经是不基于模型的强化学习问题，转到value_based啦。

蒙特卡罗法通过采样若干经历完整的状态序列(episode)来估计状态的真实价值。所谓的经历完整，就是这个序列必须是达到终点的。
有了很多这样(越多越接近真实值)经历完整的状态序列，可以近似的估计状态价值：只需求出所有的完整序列中该状态出现时候的收获再取平均值即可近似求解，也就是：
Gt=Rt+1+γRt+2+γ2Rt+3+...γT−t−1RT
vπ(s)≈average(Gt),s.t.St=s

V(St)=V(St)+α(Gt−V(St))
Q(St,At)=Q(St,At)+α(Gt−Q(St,At))
系数α 功能类似于用来取平均的N(St)

和动态规划比，蒙特卡罗法不同之处体现在三点：
1 预测问题策略评估的方法不同
2 蒙特卡罗法一般是优化最优动作价值函数q∗，而不是状态价值函数v∗。(没有P 转而计算q？？)
3 动态规划一般基于贪婪法更新策略。而蒙特卡罗法一般采用ϵ−贪婪法更新。 (因为想要更多的动作被计算q(s, a))
一般ϵ会随着算法的迭代过程逐渐减小，并趋于0。这样在迭代前期，我们鼓励探索，而在后期，由于我们有了足够的探索量，开始趋于保守，以贪婪为主，使算法可以稳定收敛。

蒙特卡罗法
其缺点是：它每次采样都需要一个完整的状态序列。
改进：时序差分TD (Temporal-Difference)

用Rt+1+γv(St+1)来近似的代替收获G(t), 前者又称TD目标值
时序差分法在知道结果之前就可以学
时序差分法在更新状态价值时使用的是TD目标值，即基于即时奖励和下一状态的预估价值来替代当前状态在状态序列结束时可能得到的收获，是当前状态价值的有偏估计，而蒙特卡罗法是无偏估计
n步时序差分当n越来越大，趋于无穷，或者说趋于使用完整的状态序列时，n步时序差分就等价于蒙特卡罗法了。

时序差分法求解控制分在线算法(代表者SARSA) 和离线算法(代表者Q-learing) 分别为行动策略和要评估的策略是不是同一个策略的场景。
再解释一下：
在线控制一般只有一个策略(常用ϵ−贪婪法)
离线控制一般有两个策略其中一个策略(常用ϵ−贪婪法) 用于选择新的动作另一个策略(常用贪婪法)用于更新价值函数

除了收获G(t)不同 SARSA其他同蒙特卡罗法
对于价值函数的更新，Q-Learning用贪婪法，SARSA用ϵ−贪婪法。这是SARSA和Q-Learning本质的区别。
Q-Learning直接学习最优策略，而SARSA在学习最优策略的同时还在做探索。但SARSA学习过程会比较平滑， Q-Learning可能受到训练数据方差的影响，或遇到一些特殊的最优“陷阱”。

SARSA和Q-Learning的缺点是：
Q(S, A)的值使用一张大表来存储的可能溢出

对于资格迹，刘建平老师的文章是先在TD算法中讲的，那时还没说到价值逼近函数。所以我当时没看太明白。我觉得这个问题的BourneLin答主说的比较好：
https://www.zhihu.com/question/60612010/answer/214118815 强化学习演进史