一直想写一系列关于对于RL各类思想和算法的总结性的文章，亦或者说是笔记吧； 之前在学校的时候，基于awjuliani的blog 从Q-Table到A3C进行实现了各类RL算法，但是也只是实现 对于其中的算法的分类和关系其实也还是似是而非的感觉，平时的时候 能体会到和感觉到，但是一直没有用语言进行仔细的总结出来，趁这个机会 来说一下吧；
第一篇文章并不会涉及太多的算法实现的问题，更多的还是对于各类RL算法的关系进行一个描述框架，最后归于一个简单的Q-Table实现为止；
RL的分类
如果要对强化学习下一个定义，那么有几个关键词肯定是少不了的：交互性、马尔科夫过程、机器学习等，但为什么会有这些个关键词呢？他们之间的联系和关系呢，以往的书里往往都是直接从马尔科夫过程开始说起，直接大谈state，action，reward等，并不够本质，这里 微微谈一些自己的浅见 不一定对，只是这段时间看的书的一些想法
交互「与SL的区别」
如果说到强化学习的起源，那就需要追溯到动物学习心理学有关“试错”学习，即 强调在与环境中的交互进行学习，并基于环境对于不同行为的评价反馈信号用于改变自身的动作选取策略来达到学习的目标；这里就出现了一个关键词：交互性；
没错，对于RL(reinforcement learning)来说，毋庸置疑的一点就是：RL的重点在于交互；那么交互的双方呢？参考先前的动物学习心理学里面，我们可以用agent和environment两类来代指交互双方；实际上，在实际编程过程中， 我们往往需要设置两部分：agent和environment；前者负责各类RL算法的内容：基于策略选取action、优化更新策略等，后者需要根据agent选取出来的action 进行做出反应「给予回报和环境状态变化情况等」；这里 可以引出有关强化学习的第二个关键词机器学习；
强化学习是机器学习的一种，但某种意义上又是最不像机器学习的一种，它更像是一种控制算法「不要在意这些说法，后面了解多了就知道了」；众所周知，机器学习可以分为监督学习和非监督学习，我们常用的也大多是监督学习；而说到它和经典机器学习算法——监督学习最大的不同之处，也就是上面说到agent和environment交互时候，environment给出的「agent获取的」并不是确定的教师信号 而只是评价信号；
这也正是RL和SL(supervise learning)的区别所在，SL确定性的给出在不同状态下的教师信号 而SL的这个学习优化过程 其实更像是学习拟合到这个：从状态到教师信号的映射 的过程，而事实上对于一些复杂的控制问题来说，往往是需要分阶段考虑的，很难给出一个确定的 最优的 分解好的过程，用于其来学习这个映射关系 比如机械臂，「联系后面的多步预测和单步预测的不同来理解」；
这样的话 对于SL来说，直接学习到一个从初始状态到最终拿起东西的这样一个映射 成为了一个很困难的事情，毕竟SL 本质上也还是分类，当分类的类别都不清楚的时候 SL也就无能为力了；恩 这里我们就是说从状态分布到action之间的关系，action就是一个个的类别，为了实现目的来吧不同状态归于不同action，来实现决策的目的；于是就像是机械臂问题 就无法直接的找到一个action或者说类别来吧当前的state放入，完成任务；这里所说的action也还是low-level的action选择，真选择一个足够high-level的来完成任务，学习映射也可以，想想看这些low-level的action能够组成多少high-level吧，都差不多是能看做是continued的了，而且还可能没有常见continued action的内在关系；而对于RL不同，无论RL的算法如何，最终只有一个目的：让折扣累计的reward最大化；每个reward看做对应一个state或者一个action的选择 那么就完成一系列的action的选择了，如果把整体完成任务看做一个high-level action，这些一个个的选择看做了low-level的话，这也 可以看做就是RL和SL的区别了吧；
当然 其他的不同之处的话，还可以从其中的训练数据来进行理解，RL需要有reward的交互数据，而SL只是单纯的标签数据就好；
这么一想其实IRL也是一样，毕竟对于全部的state都需要给出来reward，这么也就需要遍历全部的state了；对于大状态空间来说 这么看和SL「或者说模仿学习」是一样的问题；但是其实也还有不同之处在于 毕竟不是直接学习到那样的高级action的选择，具体到示范里面 还是需要拆解成对应state-action对的关系，所以也还是对当前state对于low-level的action选择的学习罢了； 碎碎念一堆关于RL和SL的区别之后，其实也就是对于RL至关重要的特性『交互』；毕竟上面也说道 RL的目的是寻找到最大累计回报，而这个回报：reward 也正是来自于环境所给予的反馈之一「基于目的性的不同 导致的优化函数的定义的区别，其实也能看出强化学习和SL的区别」，对于强化学习来说 在与环境的一次次交互过程中，不断尝试与优化动作选择的策略，最终才能达到这一个目的；于是我们可以看出对于强化学习来说，可交互性 的重要性；或者说最大特点也正是：在交互中学习（Learning from Interaction）；
分类
进而 基于学习系统和环境交互的类型，强化学习算法可以分为非联想强化学习(non-associative RL)和联想强化学习(associative RL)；前者的学习系统仅从环境中获取回报，而不区分环境的状态；
研究成果包括 Thathachar等针对n臂赌博机问题提出来的基于行为值函数的估计器方法和追赶方法(pursuit method)和SUtton提出的增强信号比较方法(reinforcement comparison)
后者在获取回报的同时，具有环境的状态信息反馈 类似于反馈控制系统; 同时可以进一步细分，也就是可以分为：即时回报联想强化学习和序贯决策强化学习两种；顾名思义 即时回报的就是强化学习的回报信号没有延迟特性，学习系统直接最大化期望的即时回报 比如联想搜索(associative search)、可选自主方法等；
进而后者的序贯决策强化学习方法，才是我们日常所常说的强化学习的方法，毕竟大部分实际问题都具有延迟回报的特点，进而在解决这样的序贯决策问题中 采用了markov决策过程模型；
这里也终于引出了markov建立的意义：是为了解决现实中序贯决策的实际问题，而建立的模型；
分类的话，根据学习目标 可以将其分为折扣性回报指标和平均回报指标两种；「最终目标式子的区别」
然后 根据markov决策过程行为选择策略的平稳性「概率分布的不变性」强化学习算法可以分为求解平稳策略markov决策过程值函数的学习预测「learning prediction」，和求解markov决策过程中最优值函数和最优策略的学习控制「learning control」
prediction和control
这里想先区分一波关于prediction和control；
上面对于强化学习整体的分类有所介绍，紧接着对于我们经常需要解决的序贯决策问题 常常需要建立起来markov过程进行求解，这样的话 对于常见的强化学习问题可以分为学习预测和学习控制两类问题，前者的求解为实现以优化决策为目的的后者提供了基础；
具体的来说话，对于强化学习来说 一个绕不开的问题就是关于：计算平稳行为策略markov决策过程的状态值函数的问题「策略评估」；换句话说就是 在一个确定性的行为策略下如何确定其值函数；毕竟啊 确定好一个policy之后，也就相当于确定了一个markov链，那么如何计算这个markov链上的状态值函数也就成为了一大问题；
这时候就需要分：model-based 和model-free两种情况下了，「关于这两者的定义区别，直白的的说就是转移概率知不知道，也就是选取某个action后 能否直接推导下一个state 而不需要借助environment」对于model-based的情况下，直接借助动态规划就好了 具体可以分为：策略迭代、值迭代、策略搜索等；「已知模型了 那么就知道了转移概率 就可以直白的计算值函数；具体参考深入浅出P36」而实际问题中 更多的依旧是model-free 「某一个状态的之后状态的转移概率未知 那么就无法根据贝尔曼方程来直白的计算，于是我们就需要先知道当前这条markov链」于是对于这一类markov链的状态值函数的求解 也就是一类多步学习预测问题，常见的方法包括蒙特卡洛方法 时域差值学习；
首先是对于蒙特卡洛的首先进行介绍，简单的说就是基于经验（experience）进行学习，这个经验包括样本序列的状态（state）、动作（action）和奖励（reward）。得到若干样本的经验后，通过平均所有样本的回报（return）来解决强化学习的任务。
但显然能看出蒙特卡洛的方法，尽管可以作为一种类似监督学习的方法「基于历史数据 进行预测」可以解决多步预测的问题，但是有着效率低下的特点；而时域差分的方法 利用连续两个时刻预测值的差值来更新模型；
如果继续往下看的话，包括Qlearning、SARSA等控制学习算法的基础 也都是在这里，进而我们常见的强化学习中所分类得到的表格式和值函数逼近式的，也正是因为这里的TD算法的分类而导致的；进一步的还有对于单步预测和多步预测还有着：TD(0)、TD(λ)；具体的可以翻阅Reinforcement Learning: An Introduction ；
顺带说一句：根据观测数据的时间特性 预测可以分为单步预测和多步预测「基于历史数据预测现在和未来的区别」；关于监督学习和时间差分的区别，传统监督学习是根据预测值和实际观测值的误差来修正预测模型，而TD是根据时间上连续两次预测之间的差值来修正预测误差；具体的来说 前者需要得到全部观测数据后 才能通过计算预测误差来修正预测模型，后者 只需要某两个时刻的预测值和局部观测数据来修正预测模型；所以可以实现在线学习 减少存储量和计算量 有着更高效的学习效率；同时 也可以看出 监督学习只能实现单步学习预测 也就是只能基于当前信息来对于当前时刻的输出进行预测，而TD可以实习多步预测；
时域差分算法 往往被看组学习控制算法 如sarsa和qlearning的一部分 就像多步预测被看做为多步控制的一部分一样；
大致介绍了关于学习预测的内容之后，紧接着可以介绍关于学习控制的问题；
在上面也提到过学习预测可以看做学习控制的一个子问题，原因也就是在于 常见的强化学习算法的目的毕竟还是为了优化决策求解出来一个合适的行动策略；而学习预测本质上依旧是为了给学习控制提供出来一个评判标准：评判出来当前的优化得到的策略是好亦或是坏；这句话也指明了学习控制本质的作用：求解策略，而学习预测本质目的：求解出来一个评价函数；
通过上面的总结 我们可以直白的说 大部分强化学习都还是为了解决序贯决策问题而诞生的，而解决的方式就是先建立markov模型，同样的动态规划方法也可以用于解决markov模型 于是可以一起被用来解决序贯决策问题，不过后者需要提前知道模型情况 也就是状态转移概率，于是用来解决model-based问题；其余的RL算法被用来求解model-free的；可以这么说动态规划的思想是无模型强化学习的起源；这些也正是之间的关系：序贯决策$\rightarrow$markov决策$\rightarrow$动态决策/RL；「其实从markov决策出发 进而引到RL会更为直观」
所以我们知道 强化学习和动态规划是求解markov决策问题的两大方法，而这里的求解 也就是上面说的学习控制；类似于动态规划中的策略迭代需要先有着对于策略评价方法的策略评价，强化学习中 需要先得到一种适合的用于评价策略的方法 这也正是学习预测了，进而才有着类似动态规划中策略迭代一样的学习控制方法；
表格式和大状态空间
所以说 动态规划和RL都是用于解决马尔科夫决策问题，进而解决序贯决策问题 也就是大多说的强化学习问题；而强化学习本身中算法，对于他们的分类，可以分为：离散表格式的和大状态空间 两大类，进一步的分的话 对于后面那一种大状态空间的问题 有着基于值函数近似和策略梯度两类方法；
当然了 是并不代表前面的离散表格式的和后面两种毫无关系，事实上 如果总是从解决流程上来看，近似函数逼近和离散表格其实更像，毕竟都是先确定好用于表达策略好坏的值函数，然后基于值函数的好坏来选择最优策略；两者的区别只是在于这个值函数表达的方式不同而已，对于大状态空间中 常喜欢采用神经网络的方式来近似表达值函数；而策略梯度的方法就是直白的对markov决策构成的策略空间进行搜索和逼近，取消了描述策略的值函数这一步「这算是取消了学习预测的过程？」
以上 差不多对于整个强化学习的体系进行了简单的分类，我们要知道除了常见的序贯决策问题之外，本身序贯策略问题基于reward的是否延迟 来源于联想强化学习，同时又有着非联想强化信息；而序贯策略本身为了解决它，采用markov模型来处理，基于指标的不同 还会分为折扣型的和平均型的；在折扣型的里面 基于交互环境的模型是否已知「markov中的转移概率」对于已知的 我们直接采用动态规划来解决这一markov过程；未知的才是我们常见的各类强化学习算法，对于强化学习算法本身，我们根据其中过程可以分为学习预测部分和学习控制部分；紧接着根据问题环境的不同，对于小状态空间 我们采用表格式的方法，大状态空间就是采用值函数近似或者策略梯度的方法；
好了，以上就是对于强化学习整体的分类，接下来就是一些对于强化学习的实现了；
表格式的实现
这里选取的是qlearning的表格式的实现，毕竟对于强化学习 常说的: Deep Reinforcement Leaning，最开始的应用也正是来自于 DeepMind的DQN算法，于是这里我们就从qlearning的表格方式来实现，进而转到神经网络实现的qnet，以此类推；
就像上面提到的将：基于值函数和基于策略梯度 分类，对于值函数迭代计算 本质上是也是策略的一种体现和衡量；进而再回到上面说道的prediction和control，分别完成对于值函数的评估 再用值函数改善策略获取最优策略；
参考下面的qlearning的算法描述：
借助于TD预测 完成了对于Q值的更新，进而完成对于动作选取策略ε-greedy的优化；而当状态和动作都是有限集的时候，这里的状态-动作对和q值就可以看做是一个字典，状态-动作对是索引，得到对应的代表的数值，而我们对某个状态$S$应该选取什么动作 也就是通过查询这个字典中 某状态$S$包括的各个状态-动作对$S-A$ 对应的q值，根据策略要求 完成对于动作的选取；
因而对于表格式的强化学习算法，选取action的好坏 或者说策略的好坏，完全就是取决于这个字典的情况，表格式强化学习算法就是完成对于这个表（字典）的更新；
FrozenLake实现
# FrozenLake 问题的规则
SFFF (S: 起始点, 安全)
FHFH (F: 冰层, 安全)
FFFH (H: 空洞, 跌落危险)
HFFG (G: 目的地, 飞盘所在地)
这里 我们基于OpenAI gym尝试解决上述的FrozenLake问题。OpenAI gym给定了描述这个简单游戏的数组，人们可以让agent基于此进行学习。FrozenLake问题发生在一个4*4的网格区域上，其中包括起始区，安全冰层区，危险空洞区和目标地点，，在任意的时刻agent可以上下左右移动，我们的目标是让agent在不跌落至空洞的前提下到达目的地。这里有一个特殊的问题就是偶尔会有一阵风吹过，使agent被吹到并非它选择的区域。因此在这个问题中每一时刻都作出最优解是不可能的，但是避开空洞抵达目的地还是可行的。只有到达目的地才可以得到1分，除此之外都是0分。
就像上面所说的 为了获取动作选取策略，我们需要一个表格，来包含问题中所有可能的发生情况，表格中的值表征着我们在当前情况下应当作出什么行动。在FrozenLake问题中，有16个状态（每一个表格单元对应一个情况），4个可选行动，这产生了一个16*4的Q值表格。我们首先将表格初始化为全0，当有行动得分之后我们据此对表格进行更新。
q值的更新方法也正是时间差分算法中的异策略的qlearning，$Q(S,A) \leftarrow Q(S,A)+\alpha[R+\gamma max_{a}Q(S’,a)-Q(S,A)]$
恩 这里又涉及一个同策略和一个异策略的概念；其实在之前的A3C中也详细说过，这里只是直白的说一下就是：行动的策略「选取action时候的策略($Q(S,A)$)」和评估策略「TD算法更新时候的target value的获取（$Q(S’,A’)$）」是不是同一个策略；
以下为实现，具体来说 实现需要下面这么步骤
- 建立起一个包含全部状态和对应动作的table 用于存放对应的q值；
- 基于qlearning算法，基于ε-greedy来选择动作a
- 与环境交互得到新状态 回报 is_terminal等信息；
- 基于当前情况来更新q表
- 状态next_s=s
# Q-Table Learning
import gym
import numpy as np
# 加载实验环境
env = gym.make('FrozenLake-v0')
# 集成Q表学习算法
# 初始表（全0）
Q = np.zeros([env.observation_space.n,env.action_space.n])
# 设定超参数
lr = .8
y = .95
num_episodes = 2000
# 创建episodes中包含当前奖励值和步骤的列表
rList = []
for i in range(num_episodes):
# 初始化环境，得到第一个状态观测值
s = env.reset()
rAll = 0
d = False
j = 0
# Q表学习算法
while j < 99:
j += 1
# 根据Q表和贪心算法(含噪)选定当前的动作
a = np.argmax(Q[s,:] + np.random.randn(1, env.action_space.n) * (1./(i+1)))
# 获取新的状态值和奖励值
s1, r, d, _ = env.step(a)
# 更新Q表
Q[s,a] = Q[s,a] + lr * (r + y*np.max(Q[s1,]) - Q[s,a])
rAll += r
s = s1
if d == True:
break
rList.append(rAll)
print("Score over time: " + str(sum(rList)/num_episodes))
print("Final Q-Table Values")
print(Q)
最终的qtable为：
Final Q-Table Values
[[9.41993597e-02 9.49445527e-02 1.66270191e-01 4.12876595e-01]
[2.64839957e-02 3.14139493e-01 6.46655034e-02 3.51268302e-01]
[9.69715064e-02 1.91942789e-01 8.67157149e-02 1.02361611e-01]
[2.39187744e-02 2.44309554e-02 1.24823728e-01 2.89440315e-01]
[1.03953351e-01 2.26246336e-03 8.74537166e-03 2.87500922e-02]
[0.00000000e+00 0.00000000e+00 0.00000000e+00 0.00000000e+00]
[1.07798877e-04 8.08157542e-04 1.60674921e-01 0.00000000e+00]
[0.00000000e+00 0.00000000e+00 0.00000000e+00 0.00000000e+00]
[5.16244511e-03 1.39876315e-01 9.87590601e-02 1.12049855e-01]
[1.01601757e-01 2.95052574e-01 5.78777923e-02 1.55720755e-01]
[7.89239109e-01 3.51498956e-03 2.77489966e-02 4.94422943e-02]
[0.00000000e+00 0.00000000e+00 0.00000000e+00 0.00000000e+00]
[0.00000000e+00 0.00000000e+00 0.00000000e+00 0.00000000e+00]
[3.90982602e-01 4.29529709e-04 5.30372469e-01 1.45534935e-01]
[3.88263528e-01 9.10091349e-01 4.28368605e-01 3.80856817e-01]
[0.00000000e+00 0.00000000e+00 0.00000000e+00 0.00000000e+00]]
