序言
本文源自Medium上的博主Ketan Doshi(配图也源自于此),写的非常nice,本文依照个人角度提炼了知识,有兴趣的小伙伴可以自行前往哦~
本文包含以下内容:
- Markov Decision Process
- Bellman Equation
- Model-free Solutions
- Q-Learning
- Deep Q Networks
- DDPG更新中~
或许读完本文你更能理解莫凡PYTHON的讲解
all right,带上你的脑子一起出发吧!
Markov Decision Process
为了使用RL(Reinforcement Learning),你需要将你的问题建模成为MDP(Markov Decision Process)。MDP包含以下五个部分:
Agent:这是你想训练的一个载体,你可以把他想成一个机器人,你要训练他如何才能把你布置给他的任务做好
Environment:环境是与Agent进行交互的地方,比如你想让机器人在工厂里拿去一个货物,那么这个工厂就是Environment
State:状态是环境和Agent在某一时刻的属性,比如机器人的行进速度、机器人在工厂的位置以及工厂内的风速、摩擦力等等
Action:动作就是Agent以何种方式与环境进行交互,比如机器人可以前后左右运动等等
Reward:当Agent在环境中采取动作以后,从环境中获得的奖励。这里的奖励可以是“正奖励”,也可以是“负奖励”。比如你的机器人向前走了一步之后撞到障碍物了,这就获得了“负奖励”。而如果你的机器人拿到你想要的物品了,这就获得了“正奖励”
那么现在你可能就会问:Agent如何选取Action?毕竟好的Action可以让Agent更高质量的完成任务,而这也是强化学习的终极目标。在回答这个问题之前,我们需要了解3个概念:Return、Policy、Value
Return:回报是Agent在执行任务期间每一步所获得Reward的总和。我们并非简单地将这些Reward相加求和,而是用到了discount factor
注意这里的,这就表明了Agent其实更加注重当前的Reward 。其次,通过定义Return让Agent放长眼光,要综合考虑长时间段的步骤之后来选取Action。
Policy:Policy是Agent在当前Current State下选取Action时所遵循的一种策略。如随机选取动作、选取已知给予最高reward的动作等等。这初听起来比较抽象,其实Policy就像是一张查找表(状态数有限)或者是一个Function(状态数非常多),它给出了给定状态下选取某个动作的概率,可记为,即当前状态为,依照Policy此时选取动作的概率。
我们可以选取非常多种Policy,但是哪一种是可以最大化Return的?这就需要我们了解第三个概念Value
Value:我们假设Agent每次到达同一个State时,都遵循相同的Policy 选取Action,那么经过很多次的迭代之后,average long-term Return或者说expected Return被称为Value。说的直白一点,Value是你对Return的一个预测,一个预期。Return是一个episode内实实在在得到的,Value是经过很多episodes后的期望Return,而这个预测是要不断修正的,这个后面会提到。
我们有两种Value:State Value 和 State-Action Value(Q-Value)
好了,现在你知道了Policy和Value,我们就知道如何来选取Policy了。通过比较每个Policy下的Value Function,看看Agent遵循哪个Policy能获得最大的Return,这个Policy就是Optimal Policy。这也就是强化学习的目标了。
Bellman Equation
(Tips:我们讨论的RL绝大多数都是Model-Free Control problems,具体内容可参见文章顶部连接。)
贝尔曼方程是所有RL算法的基础,接下来我将用R表示immediate(observed) Reward,用G表示Return来了解一下贝尔曼方程
我们假设MDP最后一个状态为S8,从状态S7到状态S8获得的Reward为R8(个人觉得写R7会更好),按照前文所述,那么S7的Return就是
接下来看看状态S6是个什么情况。状态S6的Return G6包含两部分:一是S6到S7的Reward R6,二是S7的Return G7乘以折扣因子。即:
这样我们就得到了一个递归方程,即贝尔曼方程:
如果我们用Q-Value来表示这个方程的话:
贝尔曼方程为何如此有用?一是因为我们可以递归地计算Return,只需要采取一步Action即可,而不要遍历完episode;其次,我们前文说到过Value是一个预期值,是需要修正的,那修正的方法就是通过贝尔曼方程了。我们计算已有的Value和计算得到的Value之间的误差,也就是error,来改进我们的预测值。
Model-free Solutions
好了,现在我们要做的就是如何去找Optimal Policy。在前文已经说过,Optimal Policy对应着最大的Q-Value,也即Optimal Q-Value。那么我们找到Optimal Q-Value也是可以的,因为它对应这Optimal Policy。这样我们就有两种算法:Policy-based和Value-based
Policy-based算法是直接寻找Optimal Policy,而Value-based算法是先找到Optimal Q-Value,然后Optimal Policy从中可以推断出来。如何推断?某状态下采取哪个Action获得的Q值最大,那么采取这个Action的概率就为1(但随机最优策略是有必要的)
常见Model-free算法可分为以下分类:
我们来重点关注一下解决这类问题的4大步骤:
1.Initialize estimates
随机初始化估计值,Q-Value全初始为0
2.Take an Action
Agent想要确保他尝试了所有的途径,找到最佳的一个。这是如何做到的?我们要了解Exploration和Exploitation。
**Exploration——**在刚开始学习时,我们并不知道哪个Action是更好的,所以我们要随机的选取Action观察Reward
**Exploitation——**当Agent被充分训练后,我们已经探索过了所有可能的途径,所以我们选取能产生最大Return的Action
Agent要平衡好这两者之间的程度。对于Policy-based算法,我们用自己的估计概率去选取Action就好:
对于Value-based算法,我们采用策略选取Action:
这是一个动态策略,首先我们初始,让它以某一速率随着迭代次数的增加而衰减。代表随机选取Action的概率,代表选取有最大Q-Value的Action的概率。这就实现了在训练前期更多的Exploration,在训练后期更多的Exploitation。
3.Get feedback from the environment
Agent从当前状态S采取Action,然后从环境中获得了Reward,并且自己到达了下一个状态S’。我们从环境中观测到的数据observation data表示为:
4.Improve estimates
对于Policy-based算法,如果Agent采取了Action之后获得的Reward是“正奖励”,即postive,那么就增加刚刚选取的Action的概率
对于Value-based算法,我们通过Bellman Equation来更新Q-Value。我们计算方程得出的结果与自己的预测值之间的误差,来改进估计值。误差计算为:,更新公式为
我们可以看看以上四个步骤的总览:
算法的核心在于如何改进估计,不同的算法有着细微的差别。我们大致可以从以下三个方面来分辨:
- **Frequency—**Agent每进行多少steps去更新估计
- **Depth—**当发生更新时,往回更新多少steps的估计(propagate)
- **Formula—**计算updated estimates的方式
现在我们来了解一下这三个方面的内涵
Frequency
- **Episode—**Agent每采取一次Action,获得Reward并且储存它们。在每一次迭代周期的最后,算法利用这些Reward来更新估计
- **One Step—**Agent采取Action后获得Reward,然后马上进行更新,再进行下一个step,而不是等到迭代结束
- **N steps—**介于上述两种方式之间,每隔N steps更新
Depth
- **Episode—**Agent向前步进直到迭代结束,算法更新Agent沿路上所有的估计(state-action pairs)
- **One Step—**只会更新当前的估计
- **N Steps—**介于上述两种方式之间,更新沿路上N steps的估计
Update formula
- Value-based用Bellman Equation来更新Q-Value,这里用到了TD Error
- Policy-based根据Agent收获的Reward是否是positive来增加或减少选取概率
这里有个总结:
Q-Learning
Q-Learning算法基于Q-table,行为states,列为actions,表中的值为Q-Value。
①首先初始化Q-table,值全部初始化为0值。
②我们假设某时刻有如下的Q-table:
a1 | a2 | a3 | a4 | |
---|---|---|---|---|
S1 | 4 | 9 | 2 | 3 |
S2 | 0 | 3 | 4 | 7 |
S3 | … | … | … | … |
假如Agent现在的状态为S1,Agent采用从current state(S1)选取current action(假设为a1)。然后Agent执行a1与环境进行交互,并从环境中得到反馈Reward(R1)和next state(我们假设为S2)
③Q-Learning会从S2中选取一个Q-Value来更新current state(S1)和selected action(a1)相对应的estimated Q-Value(Q(S1,a1))。那么在S2中应该选取哪个Action呢?我们选取具有最高Q-Value的动作,即a4,我们用7来更新Q(S1,a1)。这里请注意,a4仅仅是用来更新Q(S1,a1)的,当Agent更新完后来到S2时并不一定要选取a4,a4又被称作为"target action"
④现在我们找到了target Q-Value(Q(S2,a4)=7),我们用前文所述的公式来更新Q(S1,a1)
其中为学习速率,为折扣因子。相信有部分人和我一样当初看到这个式子的时候一脸蒙,现在你应该理解了。
这神奇的Q-Learing为什么会看似在估计对估计的改进中收敛趋于最优策略?因为我们的Q值是包含实际的Reward,这个不是胡乱估计的,经过多次迭代我们就会找到产生最大Return的一个策略。
Q-Learning又被称为"off-policy" learning,因为Agent实际采取的Action与用于学习的target Action不相同
Deep Q Networks
在Q-Learning中,我们的架构大概是这个样子:
但是在现实世界中,状态数和动作数实在是太多了,我们几乎不可能用一张表去记录下它们。我们应该用一个函数Q-Function来实现这个映射关系:
正好,神经网络非常适合用来建模复杂的函数,我们叫它Deep Q Networks(DQN)。我们训练神经网络的参数来让它生成最优的Q-Values
DQN架构中有三个组成部分:Experience Replay、Q Network、Target Network
Experience Replay用于与环境互动,生成数据并训练Q Network。Q Network中的Agent被训练用来产生准确的Q-Value,神经网络是简单的线性网络,如果你的state数据是图像或文字,就得用到CNN和RNN。Target Network和Q Network结构相同,但不被训练,后面会详细讲到。
我们来看看详细的流程图:
①Experience Replay收集训练数据
Agent在current state下采用选择Action,然后与环境交互,得到反馈Reward和next state,将此次observation作为training data的一个样本,并将它存放在记忆库中。所以一项训练数据包含四个要素:
②Q Network predicts Q-value
从记忆库中随机抽取一批训练数据(批训练),它们包含了最近或很久以前的数据。将这些数据传入神经网络,Q Network用其中的current state和action去预测Q-Value。这被称作"Predicted Q Value"
③Target Q Network predits Target Q-Value
Target Network用数据中的next state去预测出这个状态下所有actions中值最高的best Q-Value,并且用它来计算"Target Q-Value"
④计算误差并训练网络参数
Predicted Q-Value、best Q-Value和reward用于计算Loss并训练Q Network,但是Target Network不被训练(切断相关性,为了使Target Q-Value是稳定的,不然就会像追寻一个变化的目标)
Target Q-Value的计算如下:
Loss的计算如下:
⑤每经过T次迭代,将Q Network的参数同步给Target Network,以预测出更加准确的Q-Value