序言

本文源自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（状态数非常多），它给出了给定状态下选取某个动作的概率，可记为π(a2∣S3)\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+γmax⁡Q(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+γ∗max⁡Q(S′)\text{Target Q-Value}=R+\gamma * \max Q(S')

Loss的计算如下：

Loss=MSE(Predicted Q Value,Target Q Value)=∑(Predict−Target)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