序言

本文源自Medium上的博主Ketan Doshi(配图也源自于此),写的非常nice,本文依照个人角度提炼了知识,有兴趣的小伙伴可以自行前往哦~

本文包含以下内容:

  • Markov Decision Process
  • Bellman Equation
  • Model-free Solutions
  • Q-Learning
  • Deep Q Networks
  • DDPG更新中~

或许读完本文你更能理解莫凡PYTHON的讲解

all right,带上你的脑子一起出发吧!

robots

Markov Decision Process

MDP

为了使用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 γ\gamma

Return=r0+γr1+γ2r2+γnrn\text{Return} = r_0 + \gamma r_1 + \gamma^2 r_2 + \cdots \gamma^n r_n

注意这里的γ<1\gamma <1,这就表明了Agent其实更加注重当前的Reward r0r_0。其次,通过定义Return让Agent放长眼光,要综合考虑长时间段的步骤之后来选取Action。

Policy:Policy是Agent在当前Current State下选取Action时所遵循的一种策略。如随机选取动作、选取已知给予最高reward的动作等等。这初听起来比较抽象,其实Policy就像是一张查找表(状态数有限)或者是一个Function(状态数非常多),它给出了给定状态下选取某个动作的概率,可记为π(a2S3)\pi(a_2|S_3),即当前状态为S3S_3,依照Policy此时选取动作a2a_2的概率。

Policy

Policy2

我们可以选取非常多种Policy,但是哪一种是可以最大化Return的?这就需要我们了解第三个概念Value

Value:我们假设Agent每次到达同一个State时,都遵循相同的Policy π\pi选取Action,那么经过很多次的迭代之后,average long-term Return或者说expected Return被称为Value。说的直白一点,Value是你对Return的一个预测,一个预期。Return是一个episode内实实在在得到的,Value是经过很多episodes后的期望Return,而这个预测是要不断修正的,这个后面会提到。

我们有两种Value:State Value 和 State-Action Value(Q-Value)

State-Value

Q-Value

好了,现在你知道了Policy和Value,我们就知道如何来选取Policy了。通过比较每个Policy下的Value Function,看看Agent遵循哪个Policy能获得最大的Return,这个Policy就是Optimal Policy。这也就是强化学习的目标了。

OptimalPolicy

Bellman Equation

(Tips:我们讨论的RL绝大多数都是Model-Free Control problems,具体内容可参见文章顶部连接。)

贝尔曼方程是所有RL算法的基础,接下来我将用R表示immediate(observed) Reward,用G表示Return来了解一下贝尔曼方程

我们假设MDP最后一个状态为S8,从状态S7到状态S8获得的Reward为R8(个人觉得写R7会更好),按照前文所述,那么S7的Return就是G7=R8G7=R8

Bellman1

接下来看看状态S6是个什么情况。状态S6的Return G6包含两部分:一是S6到S7的Reward R6,二是S7的Return G7乘以折扣因子。即:G6=R6+γG7G6=R6+\gamma G7

Bellman2

这样我们就得到了一个递归方程,即贝尔曼方程:

Gt=Rt+γGt+1G_t=R_t+\gamma G_{t+1}

如果我们用Q-Value来表示这个方程的话:

Q(St,at)=E[Rt+γQ(St+1,at+1)]Q(S_t,a_t) = \mathbb{E}[R_t + \gamma Q(S_{t+1},a_{t+1})]

Bellman3

贝尔曼方程为何如此有用?一是因为我们可以递归地计算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-value-based

Policy-based算法是直接寻找Optimal Policy,而Value-based算法是先找到Optimal Q-Value,然后Optimal Policy从中可以推断出来。如何推断?某状态下采取哪个Action获得的Q值最大,那么采取这个Action的概率就为1(但随机最优策略是有必要的)

Value-based

常见Model-free算法可分为以下分类:

modelfree

我们来重点关注一下解决这类问题的4大步骤:

RLSolution

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就好:

policypick

对于Value-based算法,我们采用ϵgreedy\epsilon-greedy策略选取Action:

greedy

这是一个动态策略,首先我们初始ϵ=1\epsilon=1,让它以某一速率随着迭代次数的增加而衰减。ϵ\epsilon代表随机选取Action的概率,1ϵ1-\epsilon代表选取有最大Q-Value的Action的概率。这就实现了在训练前期更多的Exploration,在训练后期更多的Exploitation。

3.Get feedback from the environment

Agent从当前状态S采取Action,然后从环境中获得了Reward,并且自己到达了下一个状态S’。我们从环境中观测到的数据observation data表示为:(S,a,R,S)(S,a,R,S')

4.Improve estimates

对于Policy-based算法,如果Agent采取了Action之后获得的Reward是“正奖励”,即postive,那么就增加刚刚选取的Action的概率

PolicyImprove

对于Value-based算法,我们通过Bellman Equation来更新Q-Value。我们计算方程得出的结果与自己的预测值之间的误差,来改进估计值。误差计算为:TD Error=(R1+γQ(S3,a3))Q(S1,a1)\text{TD Error}=(R_1 + \gamma Q(S_3,a_3))-Q(S_1,a_1),更新公式为Q(S1,a1)=Q(S1,a1)+αErrorQ(S_1,a_1)=Q(S_1,a_1)+\alpha * \text{Error}

ValueImprove

我们可以看看以上四个步骤的总览:

overview

算法的核心在于如何改进估计,不同的算法有着细微的差别。我们大致可以从以下三个方面来分辨:

  • **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更新

Frequency

Depth

  • **Episode—**Agent向前步进直到迭代结束,算法更新Agent沿路上所有的估计(state-action pairs)
  • **One Step—**只会更新当前的估计
  • **N Steps—**介于上述两种方式之间,更新沿路上N steps的估计

Depth

Update formula

  • Value-based用Bellman Equation来更新Q-Value,这里用到了TD Error
  • Policy-based根据Agent收获的Reward是否是positive来增加或减少选取概率

这里有个总结:

conclusion

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采用ϵgreedy policy\epsilon-\text{greedy policy}从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(S,A)=Q(S,A)+α(R+γmaxQ(S,a)Q(S,A))Q(S,A)=Q(S,A)+\alpha(R+\gamma \max Q(S',a)-Q(S,A))

其中α\alpha为学习速率,γ\gamma为折扣因子。相信有部分人和我一样当初看到这个式子的时候一脸蒙,现在你应该理解了。

这神奇的Q-Learing为什么会看似在估计对估计的改进中收敛趋于最优策略?因为我们的Q值是包含实际的Reward,这个不是胡乱估计的,经过多次迭代我们就会找到产生最大Return的一个策略。

​ Q-Learning又被称为"off-policy" learning,因为Agent实际采取的Action与用于学习的target Action不相同

Deep Q Networks

在Q-Learning中,我们的架构大概是这个样子:

Q-Learning

但是在现实世界中,状态数和动作数实在是太多了,我们几乎不可能用一张表去记录下它们。我们应该用一个函数Q-Function来实现这个映射关系:

Q-Function

正好,神经网络非常适合用来建模复杂的函数,我们叫它Deep Q Networks(DQN)。我们训练神经网络的参数来让它生成最优的Q-Values

DQN1

DQN架构中有三个组成部分:Experience Replay、Q Network、Target Network

DQN2

Experience Replay用于与环境互动,生成数据并训练Q Network。Q Network中的Agent被训练用来产生准确的Q-Value,神经网络是简单的线性网络,如果你的state数据是图像或文字,就得用到CNN和RNN。Target Network和Q Network结构相同,但不被训练,后面会详细讲到。

我们来看看详细的流程图:

DQN3

①Experience Replay收集训练数据

DQN0

Agent在current state下采用ϵgreedy policy\epsilon-\text{greedy policy}选择Action,然后与环境交互,得到反馈Reward和next state,将此次observation作为training data的一个样本,并将它存放在记忆库中。所以一项训练数据包含四个要素:(S,a,R,S)(S,a,R,S')

②Q Network predicts Q-value

DQN4

从记忆库中随机抽取一批训练数据(批训练),它们包含了最近或很久以前的数据。将这些数据传入神经网络,Q Network用其中的current state和action去预测Q-Value。这被称作"Predicted Q Value"

③Target Q Network predits Target Q-Value

DQN5

Target Network用数据中的next state去预测出这个状态下所有actions中值最高的best Q-Value,并且用它来计算"Target Q-Value"

④计算误差并训练网络参数

DQN6

Predicted Q-Value、best Q-Value和reward用于计算Loss并训练Q Network,但是Target Network不被训练(切断相关性,为了使Target Q-Value是稳定的,不然就会像追寻一个变化的目标)

Target Q-Value的计算如下:

Target Q-Value=R+γmaxQ(S)\text{Target Q-Value}=R+\gamma * \max Q(S')

Loss的计算如下:

Loss=MSE(Predicted Q Value,Target Q Value)=(PredictTarget)2batch size\text{Loss}=\text{MSE}(\text{Predicted Q Value},\text{Target Q Value})=\cfrac{\sum(\text{Predict}-\text{Target})^2}{\text{batch size}}

⑤每经过T次迭代,将Q Network的参数同步给Target Network,以预测出更加准确的Q-Value