深度强化学习及其在自动驾驶中的应用: DRL&ADS系列之(1): 强化学习概述

深度强化学习及其在自动驾驶中的应用( DRL & ADS )

专栏系列文章规划

---

• DRL&ADS系列之(1): 强化学习概述
• DRL&ADS系列之(2): 深度强化学习及算法讲解
• DRL&ADS系列之(3): ADS软硬件分析及DRL在Torcs中的应用
  

  ---

概述

机器学习是人工智能的一个分支，在近30多年已发展为一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等的学科。强化学习(RL)作为机器学习的一个子领域，其灵感来源于心理学中的行为主义理论，即智能体如何在环境给予的奖励或惩罚的刺激下，逐步形成对刺激的预期，产生能获得最大利益的习惯性行为。它强调如何基于环境而行动，以取得最大化的预期利益。通俗的讲:就是根据环境学习一套策略,能够最大化期望奖励。由于它具有普适性而被很多领域进行研究，例如自动驾驶,博弈论、控制论、运筹学、信息论、仿真优化、多主体系统学习、群体智能、统计学以及遗传算法。

* RL和监督式学习, 非监督学习之间的区别:*
，其主要分为监督学习、非监督学习、深度学习和强化学习(见图1),其中三个之间的区别在于以下三点：

• (1)、RL并不需要出现正确的输入/输出对，也不需要精确校正次优化的行为。它更加专注于在线规划，需要在探索（在未知的领域）和遵从（现有知识）之间找到平衡,其学习过程是智能体不断的和环境进行交互,不断进行试错的反复练习。
• (2)、RL的不同地方在于：其中没有监督者，只有一个reward信号；反馈是延迟的，不是立即生成的；时间在RL中具有重要的意义。
• (3)、 RL并不需要带有标签的数据,有可以交互的环境即可。

基于此,普通机器学习方法和强化学习之间的的关系已描述清楚。我们知道机器学习算法和深度学习可以做分类，回归、时间序列等经典问题，这已经在很多应用场景，例如语音、文字语义等基础性的人类认知方面取得非常大的突破，但是为什么还要学习强化学习呢？不得不从其应用场景说起。

RL目前的应用场景:

• 自动驾驶: 自动驾驶载具（self-driving vehicle）
• 控制论(离散和连续大动作空间): 玩具直升机、Gymm_cotrol物理部件控制、机器人行走、机械臂控制。
• 游戏: Go, Atari 2600(DeepMind论文详解)等
• 理解机器学习: 自然语言识别和处理, 文本序列预测
• 超参数学习: 神经网络参数自动设计
• 问答系统: 对话系统
• 推荐系统: 阿里巴巴黄皮书（商品推荐），广告投放。
• 智能电网: 电网负荷调试, 调度等
• 通信网络: 动态路由, 流量分配等
• 物理化学实验: 定量实验,核素碰撞,粒子束流调试等
• 程序学习和网络安全: 网络攻防等

说了这么多,都是关于其背景和应用场景的话题（相关论文见RL-an overview中）,那么到底什么是RL, 又是怎么工作的? 以及工作过程中会受那些因素的影响呢？ 下文继续回到Rl主题上.

一、强化学习基本组成及原理

1.1、RL结构图:

RL是一种智能体和环境之间不断试错的方法, 通过不断的交互以取得最大的累计期望奖励，它由环境, 智能体和奖励尺度三部分组成，见图：

在图中, 大脑部分代表智能体(Agent), 地球代表环境(Environment)
执行过程： 智能体(Agent)通常从环境中获取一个Ot$O_t$, 然后Agent根据Ot$O_t$调整自身的策略做出一个行为(Action:At$A_t$)反馈给环境, 环境根据Agent的动作给予Agent一个奖励Rt$R_t$,经过这样，智能体和环境之间进行连续的交互学习，得到了一个{O,A,R$O,A,R$}的交互历史序列。通常历史序列由观测、行为、奖励三部分组成，被定义为：

Ht=O1,A1,R1,…,Ot,At,Rt$$H_t=O_1,A_1,R_1,\dots ,O_t,A_t,R_t$$

同时状态被定义为函数f(⋅)$f(\cdot )$的映射： St=f(Ht)$S_t=f(H_t)$，接下来将会对序列通过MDP进行描述：

1.2、马尔科夫决策过程（MDP）

马尔科夫决策过程是一个序列决策问题，它由很多的马尔科夫过程元组组成。 首先了解几个名词:
马尔科夫性： 指系统的下一个状态St+1$S_{t+1}$ 仅与当前状态 st$s_t$有关，表示为：

P[St+1|St]=P[St+1|s1,s2,...,st](1)$$\begin{array}{}\text{(1)}& P[S_{t+1}|S_t]=P[S_{t+1}|s_1,s_2,...,s_t]\end{array}$$

* 马尔科夫过程：* 它是一个二元组(S,P)$(S,P)$, 其中S$S$为有限状态机，P$P$为状态转移概率。且状态转移概率矩阵为：

P=⎡⎣⎢⎢⎢P11..Pn1……P1n..Pnn⎤⎦⎥⎥⎥(2)$$\begin{array}{}\text{(2)}& P=\left[\begin{array}{ccc}{P}_{11}& \dots & P_{1n}\\ .& & .\\ .& & .\\ P_{n1}& \dots & P_{nn}\end{array}\right]\end{array}$$

举个例子说明一下（如图）：如果给定状态转移概率矩阵P,即每个点到下一个点的状态转移概率，那么从Start出发到End结束存在多条马尔科夫链（多条路径），其中每个链上就是马尔科夫过程的描述。但马尔科夫过程中并不存在action和奖励。因此，从Start开始到end是一个序列决策问题，需要不断的选择路线，以取得最大收益。接下来是MDP

马尔科夫决策过程（MDP）：
通常情况马尔科夫决策过程用元组<S,A,P,R,γ$S,A,P,R,\gamma$>描述:
S$S$: 有限状态集
A$A$：有限动作集
P$P$：状态转移概率
R$R$：回报函数
γ$\gamma$：折扣因子，用来计算累计回报。

上述是MDP的组成，而我们关心的是它如何工作，继续前面的走方格例子，从Start开始，有两个行为（向右走，向南走），走不通的方向都有P=14$P=\frac{1}{4}$的概率且有不同的奖励，一直反复的走，直到走到End结束，在这个过程中会形成不同的序列,例如序列1：

{(Start,Right,P,R1),(A,Right,P,R2),(B,South,P,R3),(E,South,P,R4),(End,South,P,R5)}$$\left\{(Start,Right,P,R1),(A,Right,P,R2),(B,South,P,R3),(E,South,P,R4),(End,South,P,R5)\right\}$$

这只是其中一条路径，那从Start到End那条路劲带来的收益最大呢？就需要每一步进行决策，而决策就需要用到策略。下文继续：

1.3、强化学习的目标及Agent的要素：

目标： 根据环境状态序列，找到一套最优控制策略，以实现最大累计期望奖励。

1.3.1 第一要素 —- 策略

那么什么是策略呢？ 通常情况下被定义为是从状态到行为的一个映射，直白说就是每个状态下指定一个动作概率，这个可以是确定性的（一个确定动作），也可以是不确定性的。
(1)非确定策略： 对于相同的状态，其输出的状态并不唯一，而是满足一定的概率分布，从而导致即使是处在相同的状态，也可能输出不同的动作，表示为：

π(a|s)=P[At=a|St=s](3)$$\begin{array}{}\text{(3)}& \pi (a|s)=P[A_t=a|S_t=s]\end{array}$$

(2)确定行策略： 在相同的状态下，其输出的动作是确定的，表示为：

a=π(s)(4)$$\begin{array}{}\text{(4)}& a=\pi (s)\end{array}$$

如果给定一个策略，就可以计算最大化累计期望奖励了，通常奖励分为及时奖励和长久累计期望奖励，
及时奖励：实时反馈给Agent的奖励rt$r_t$，举例：当玩具直升机根据当前的作态做出一个飞行控制姿势时，好坏会立即得到一个奖励。
累计期望奖励：通常指一个过程的总奖励的期望，比如直升机从飞起到降落整个过程。
通常累计期望奖励被定义为：

Gt=R1+γR2+γ2R3+⋯+γk−1Rk=∑k=0γkRt+k+1(5)$$\begin{array}{}\text{(5)}& G_t=R_1+\gamma R_2+{\gamma }^2{R}_3+\cdots +{\gamma }^{k-1}{R}_k=\sum _{k=0}^{}{\gamma }^k{R}_{t+k+1}\end{array}$$

假如在策略π$\pi$下，从前文的Start出发，则有不同的路径

Start→A→B→E→EndStart→C→D→G→End....$$\begin{gathered} Start\to A\to B\to E\to End \\ Start\to C\to D\to G\to End \\ .... \end{gathered}$$

每个路径的累计回报Gt$G_t$不同，且在随机策略下Gt$G_t$是随机变量，但它们的期望是一个确定值，因此而被用作值函数的估计。

1.3.2 第二要素 —- 值函数

当Agent采用某个策略π$\pi$时，累计回报服从一个分布，通常将状态S处的期望定义为* 状态值函数*，数学表示为：

Vπ(s)=Eπ[R1+γR2+γ2R3+⋯+γk−1Rk|St=s](6)$$\begin{array}{}\text{(6)}& V_{\pi }(s)=E_{\pi }[R_1+\gamma R_2+{\gamma }^2{R}_3+\cdots +{\gamma }^{k-1}{R}_k|S_t=s]\end{array}$$

其中γ∈[0,1)$\gamma \in [0,1)$ 是折扣因子，用来估算未来对现在的影响，如果γ=0$\gamma =0$,即短视，只看当前的，不关注长期的回报。

仅仅在状态值函数下求解期望奖励是不够的，我们还需要在某一个状态下，采取某个行为带来的期望回报。用状态-行为值函数衡量当前行为的好坏，其数学表达为：

qπ(s,a)=Eπ[∑t=0∞γkRt+k+1|St=s,At=a](7)$$\begin{array}{}\text{(7)}& q_{\pi }(s,a)=E_{\pi }[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}|S_t=s,A_t=a]\end{array}$$

为了能够计算在某个状态S下的值函数或者在状态S下采取行为的状态-行为值函数评估累计期望奖励，我们根据下图列出公式组：

Vπ(s)=∑a∈Aπ(a|s)qπ(s,a)(8)$$\begin{array}{}\text{(8)}& V_{\pi }(s)=\sum _{a\in A}\pi (a|s)q_{\pi }(s,a)\end{array}$$

注：根据公式（7），从状态s处施加行为a有两种操作，在不同的策略下来估计未来的期望奖励，故采用求和均差得到公式（8），同时从第一幅图左下角得到公式（9），从第二幅图左下角得到公式（10）

qπ(s,a)=Ras+γ∑a∈APass′vπ(s′)(9)$$\begin{array}{}\text{(9)}& q_{\pi }(s,a)=R_s^a+\gamma \sum _{a\in A}{P}_{s{s}^{{}^{\prime }}}^a{v}_{\pi }(s^{{}^{\prime }})\end{array}$$

vπ(s′)=∑a′∈Aπ(a′|s′)qπ(s‘,a′)(10)$$\begin{array}{}\text{(10)}& v_{\pi }(s^{{}^{\prime }})=\sum _{a^{{}^{\prime }}\in A}\pi (a^{{}^{\prime }}|s^{{}^{\prime }})q_{\pi }(s^{‘},a^{{}^{\prime }})\end{array}$$

将等式(9)代入等式（8），得到等式（11);将(10)代入（9）得到（12）

vπ(s)=∑a∈Aπ(a|s)(Ras+γ∑s‘∈SPass′Vπ(s′))(11)$$\begin{array}{}\text{(11)}& v_{\pi }(s)=\sum _{a\in A}\pi (a|s)\left(R_s^a+\gamma \sum _{s^{‘}\in S}{P}_{s{s}^{{}^{\prime }}}^a{V}_{\pi }(s^{{}^{\prime }})\right)\end{array}$$

qπ(s,a)=Ras+γ∑s‘∈SPass′∑a∈Aπ(a′|s′)qπ(s′,a′)(12)$$\begin{array}{}\text{(12)}& q_{\pi }(s,a)=R_s^a+\gamma \sum _{s^{‘}\in S}{P}_{s{s}^{{}^{\prime }}}^a\sum _{a\in A}\pi (a^{{}^{\prime }}|s^{{}^{\prime }})q_{\pi }(s^{{}^{\prime }},a^{{}^{\prime }})\end{array}$$

由上文公式我们可以总结出：状态值函数和状态-行为值函数的Bellman方程：

v(st)=Eπ[Rt+1+γv(st+1)]q(st,at)=Eπ[Rt+1+γq(st+1,at+1)(13)$$\begin{gathered} \begin{array}{}\text{(13)}& v(s_t)=E_{\pi }[R_{t+1}+\gamma v(s_{t+1})] \\ q(s_t,a_t)=E_{\pi }[R_{t+1}+\gamma q(s_{t+1},a_{t+1})\end{array} \end{gathered}$$

通常计算值函数的目的是为了构建学习从数据中得到最优策略，每个策略对应一个值函数，最优策略对应最优值函数。当且仅当：π≥π∗$\pi \ge {\pi }^{\ast }$ and Vπ(s)≥V∗(s)$V_{\pi }(s)\ge V^{\ast }(s)$时，最优状态值函数V∗(s)$V^{\ast }(s)$为所有策略中值函数最大的，表示为：

v∗(s)=maxπvπ(s)(14)$$\begin{array}{}\text{(14)}& v^{\ast }(s)=\underset{\pi }{max}{v}_{\pi }(s)\end{array}$$

最优状态-行为值函数是所有策略中状态-行为值最大的，表示为：

q∗(s,a)=maxπqπ(s,a)(15)$$\begin{array}{}\text{(15)}& q^{\ast }(s,a)=\underset{\pi }{max}{q}_{\pi }(s,a)\end{array}$$

同理得到（推导省略），最优的状态值函数和状态-行为值函数如下：

Vπ(s)=maxaRas+γ∑s‘∈SPass′V∗(s′)(16)$$\begin{array}{}\text{(16)}& V_{\pi }(s)=\underset{a}{max}{R}_s^a+\gamma \sum _{s^{‘}\in S}{P}_{s{s}^{{}^{\prime }}}^a{V}^{\ast }(s^{{}^{\prime }})\end{array}$$

qπ(s,a)=Ras+γ∑s‘∈SPass′maxa′q∗(s′,a′)(17)$$\begin{array}{}\text{(17)}& q_{\pi }(s,a)=R_s^a+\gamma \sum _{s^{‘}\in S}{P}_{s{s}^{{}^{\prime }}}^a\underset{a^{{}^{\prime }}}{max}{q}^{\ast }(s^{{}^{\prime }},a^{{}^{\prime }})\end{array}$$

最后，如果已知最优状态-行为值函数，最优策略可以直接通过最大化q∗(s,a)$q^{\ast }(s,a)$得到。

π∗(a|s)={10a=argmaxπq∗(s,a)otherwise(18)$$\begin{array}{}\text{(18)}& {\pi }^{\ast }(a|s)=\{\begin{array}{rlr}1& & a=\arg \underset{\pi }{max}{q}^{\ast }(s,a)\\ 0& & otherwise\end{array}\end{array}$$

---

总结： 到目前为止，关于强化学习的序列问题和贝尔曼方程已经描述完毕，并且上文所有的均是针对小规模MDP过程的求解{在程序中怎么使用也没有讲解(实际编程单独用一节讲解)），且所有的序列都采用表的形式存储，但是针对大规模空间或者连续性动作空间的问题，由于空间存储资源浪费和检索速率低下而无法适用！接下来的三种方法则可以解决该问题，特别是TD方法。

---

三、大规模MDP的三种解决方法

注： 关于部分公式详细的推导过程不详解，具体参David课程或者参考文献[8]

3.1 动态规划法(Dynamic progarmming)

动态规划是一种在数学、管理科学、计算机科学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它常常适用于有重叠子问题和最优子结构性质的问题，在解决子问题的时候，其结果通常需要存储起来被用来解决后续复杂问题。当问题具有下列特性时，通常可以考虑使用动态规划来求解：第一个特性是一个复杂问题的最优解由数个小问题的最优解构成，可以通过寻找子问题的最优解来得到复杂问题的最优解；子问题在复杂问题内重复出现，使得子问题的解可以被存储起来重复利用。
马尔科夫决定过程（MDP）具有上述两个属性：Bellman方程把问题递归为求解子问题，价值函数就相当于存储了一些子问题的解，可以复用。因此可以使用动态规划来求解MDP。

这里的规划一般包括两个步骤：“Prediction”和“Control”
+ Prediction是指根据当前的MDP和策略输出一个当前策略下的值函数：
* ++Input:++ * MDP<S,A,P,R,γ$S,A,P,R,\gamma$>和策略π$\pi$
* ++ Output:++ * Vπ$V_{\pi }$
+ Control是指根据给定MDP找到最优V∗$V^{\ast }$和π∗${\pi }^{\ast }$
* ++Input:++ * MDP<S,A,P,R,γ$S,A,P,R,\gamma$>
* ++Output: ++* V∗$V^{\ast }$和 π∗${\pi }^{\ast }$

3.1.1、策略评估

在一个序列中每一步决策都需要一个策略，即每一步都有值函数。

V1,V2,V3,V4,…,Vπ$$V_1,V_2,V_3,V_4,\dots ,V_{\pi }$$

策略评估需要解决的问题是对给定的策略π$\pi$进行评估，找到：* optimal policy *, 在策略评估过程中，我们通常采用迭代法进行策略评估。
* 解决的方法 *：反向迭代应用状态值函数Bellman期望方程
* 具体过程 *：同步反向迭代，即在每次迭代过程中，对于第 k+1 次迭代，所有的状态s的价值用vs(s′)$v_s(s^{{}^{\prime }})$ 计算并更新该状态第 k+1 次迭代中使用的价值vk(S)$v_k(S)$ ，其中s′$s^{{}^{\prime }}$是s的后继状态。此种方法通过反复迭代最终将收敛至 Vπ$V_{\pi }$ 。

Vk+1(s)=Rπ+γPπVk(s)(19)$$\begin{array}{}\text{(19)}& V^{k+1}(s)=R^{\pi }+\gamma P^{\pi }{V}^k(s)\end{array}$$

首先我们在一个给定的策略下迭代更新价值函数,为了能够优化策略，贪婪选取行为是一种比较常见的方法。

π′=greedy(Vπ)(20)$$\begin{array}{}\text{(20)}& {\pi }^{{}^{\prime }}=greedy(V_{\pi })\end{array}$$

基于给定策略的价值迭代最终收敛得到的策略就是最优策略，但通过一个回合的迭代计算价值联合策略改善就能找到最优策略不是普遍现象。通常，还需在改善的策略上继续评估，反复多次多次迭代。不过这种方法总能收敛至最优策略π∗${\pi }^{\ast }$,接下来是策略迭代。

3.1.2、策略迭代

在当前策略上迭代计算V值，再根据V值贪婪地更新策略，如此反复多次，最终得到最优策略 π∗${\pi }^{\ast }$ 和最优状态价值函数 V∗$V^{\ast }$, 如下图：

上图是大神David Sliver的slide,

3.1.3 值迭代

问题：寻找最优策略π
解决方法：从初始状态价值开始同步迭代计算，最终收敛，整个过程中没有遵循任何策略。
注意： ++与策略迭代不同，在值迭代过程中，算法不会给出明确的策略，迭代过程其间得到的价值函数，不对应任何策略。++

一个最优策略可以被分解为两部分：从状态s到下一个状态s’采取了最优行为 A∗$A^{\ast }$ ；在状态s’时遵循一个最优策略。
定理： 一个策略能够使得状态s获得最优价值，当且仅当：对于从状态s可以到达的任何状态s’，该策略能够使得状态s’的价值是最优价值：

V∗(s)=maxa∈ARas+∑s′∈SPass′V∗(s′)(21)$$\begin{array}{}\text{(21)}& V^{\ast }(s)=\underset{a\in A}{max}{R}_s^a+\sum _{s^{{}^{\prime }}\in S}{P}_{s{s}^{{}^{\prime }}}^a{V}^{\ast }(s^{{}^{\prime }})\end{array}$$

接下来采用树的思想解释一下：

价值迭代虽然不需要策略参与，但仍然需要知道状态之间的转移概率，也就是需要知道模型。

* 总结：*
预测问题：在给定策略下迭代计算价值函数。控制问题：策略迭代寻找最优策略问题则先在给定或随机策略下计算状态价值函数，根据状态函数贪婪更新策略，多次反复找到最优策略；单纯使用价值迭代，全程没有策略参与也可以获得最优策略，但需要知道状态转移矩阵，即状态s在行为a后到达的所有后续状态及概率。使用状态价值函数或行为价值函数两种价值迭代的算法时间复杂度都较大，为 O(mn2)$O(m{n}^2)$ 或 O(m2n2)$O(m^2{n}^2)$ 。

3.2 蒙特卡罗法(Monte Calo)

通过先前的讲解，我们明白了如何从理论上解决一个已知的MDP：通过动态规划来评估一个给定的策略，并且得到最优价值函数，根据最优价值函数来确定最优策略；也可以直接进行不基于任何策略的状态价值迭代得到最优价值函数和最优策略。接下来则是解决被认为是MDP、但却不掌握MDP具体细节的问题，也就是讲述如何直接从Agent与环境的交互来得得到一个估计的最优价值函数和最优策略。直白的说就是在给定的策略同时不清楚MDP细节的情况下，估计Agent会得到怎样的最终奖励。

3.2.1 蒙特卡罗Introduction

蒙特卡罗思想: 当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。
* MC强化学习：* 指在不清楚MDP状态转移及即时奖励的情况下，直接从经历完整的Episode来学习状态价值，通常情况下某状态的价值等于在多个Episode中以该状态算得到的所有收获的平均。
* MC强化学习特点：* 不基于模型本身，直接从经历过的Episode中学习，必须是完整的Episode，使用的思想就是用平均收获值代替价值。理论上Episode越多，结果越准确。

3.2.1 MC策略评估

前文已经讲了关于策略评估，其实质是求解值函数，在MC中同样需要一系列完整的Episode(与后文的TD不同)去求解当前策略下的值函数。
在一个特定的策略π$\pi$下，完整的Episode的序列表示如下：

S1,A1,R2,S2,A2,R3,⋯,St,At,Rt+1,⋯,Sk∼π$$S_1,A_1,R_2,S_2,A_2,R_3,\cdots ,S_t,A_t,R_{t+1},\cdots ,S_k\sim \pi$$

那么，在t时刻状态St$S_t$的收获我们可以描述为：

Gt=Rt+1+γRt+2+⋯+γTRT(22)$$\begin{array}{}\text{(22)}& G_t=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^T{R}_T\end{array}$$

其中T表示为终止状态，根据前文对值函数的描述，同理状态值函数为：

Vπ(s)=Eπ[Gt|St=s](23)$$\begin{array}{}\text{(23)}& V_{\pi }(s)=E_{\pi }[G_t|S_t=s]\end{array}$$

在给定一个策略，使用一系列完整Episode评估某一个状态s时，对于每一个Episode，仅当该状态第一次出现时列入计算:
* 第一次出现时列入计算:*
(1)状态出现的次数+1：

N(s)←N(s)+1(24)$$\begin{array}{}\text{(24)}& N(s)\leftarrow N(s)+1\end{array}$$

(2)总的收获值更新：

S(s)←S(s)+Gt(25)$$\begin{array}{}\text{(25)}& S(s)\leftarrow S(s)+G_t\end{array}$$

(3)状态s的价值：

V(s)=S(s)/N(s)(26)$$\begin{array}{}\text{(26)}& V(s)=S(s)/N(s)\end{array}$$

(4)当N(s)→∞时，V(s)→vπ(s)$N(s)\to \mathrm{\infty }时，V(s)\to v_{\pi }(s)$

每次访问蒙特卡洛策略评估
在给定一个策略，使用一系列完整Episode评估某一个状态s时，对于每一个Episode，状态s每次出现在状态转移链时，计算的具体公式与上面的一样，但具体意义不一样。
（1）状态出现的次数加1：同公式（24）
（2）总的收获值更新：同公式（25）
（3）状态s的价值：同公式（26）
（4）当 N(s)→∞时，V(s)→vπ(s)$N(s)\to \mathrm{\infty }时，V(s)\to v_{\pi }(s)$

提到了在实际操作时常用的一个实时更新均值的办法，使得在计算平均收获时不需要存储所有既往收获，而是每得到一次收获，就计算其平均收获。

理论公式如下：

μk=1k∑j=1kxj=1k[xk+∑j=1k−1xj]=1k[xk+(k−1)μk−1]=μk−1+1k(xk−μk−1)(27)$$\begin{array}{}\text{(27)}& \begin{array}{rl}{\mu }_k& =\frac{1}{k}\sum _{j=1}^k{x}_j\\ & =\frac{1}{k}\left[x_k+\sum _{j=1}^{k-1}{x}_j\right]\\ & =\frac{1}{k}\left[x_k+(k-1){\mu }_{k-1}\right]\\ & ={\mu }_{k-1}+\frac{1}{k}(x_k-{\mu }_{k-1})\end{array}\end{array}$$

因此根据以下伪代码进行MC累计更新： **
对于一系列Episodes中的每一个： S1,A1,R2,...,ST$S_1,A_1,R_2,...,S_T$
对于Episode里的每一个状态 St$S_t$，有一个收获Gt$G_t$ ，每碰到一次St$S_t$ ,使用下式计算状态的平均价值 Gt$G_t$
      N(St)←N(St)+1$N(S_t)\leftarrow N(S_t)+1$
      V(st)←V(st)+1N(st)[Gt−V(st)]$V(s_t)\leftarrow V(s_t)+\frac{1}{N(s_t)}[G_t-V(s_t)]$
非静态问题时，使用这个方法跟踪一个实时更新的平均值是非常有用的，可以扔掉那些已经计算过的Episode信息。此时可以引入参数 α$\alpha$来更新状态价值：
      V(St)←V(St)+α(Gt−V(St))$V(S_t)\leftarrow V(S_t)+\alpha (G_t-V(S_t))$

3.3 时间差分学习(TD-learning)

时序差分学习简称TD学习，它的特点如下：和蒙特卡洛学习一样，它也从Episode学习，但不需要了解模型本身；且它可以学习不完整的Episode，通过自身的引导（bootstrapping，自举）猜测Episode的结果，同时持续更新这个猜测。

目标：从策略π$\pi$中学习Vπ$V_{\pi }$
过程：通过估计量: Rt+1+γV(St+1)$R_{t+1}+\gamma V(S_{t+1})$, 更新策略π$\pi$，依据公式：

V(St)←V(St)+α[Rt+1+γV(St+1)−V(St)](28)$$\begin{array}{}\text{(28)}& V(S_t)\leftarrow V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]\end{array}$$

其中: TD−error=[Rt+1+γV(St+1)−V(St)]$TD-error=[R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$

---

DP、MC、TD三种方法对比：

• 1、DP基于模型; MC、TD基于无模型
• 2、DP采用bootstrapping(自举), MC采用采样，TD采用bootstrapping+采样
• 3、DP用后继状态的值函数估计当前值函数，MC利用经验平均估计状态的值函数，TD利用后继状态的值函数估计当前值函数
• 4、MC和TD都是利用样本估计值函数，其中MC为无偏估计，TD为有偏估计
• 5、最明显的就是下图的值函数的计算方法的不同

---

至此，基础RL知识已经讲完，上文对所有的序列信息均通过表的形式存储，这是一种比较对于小状态空间的搞笑解决方法，但是围棋有1070${10}^{70}$（非常大）个状态空间，机械臂连续控制等问题无法在表中存储，这些问题总结为两个缺点：
+ 表空间特别大，存储资源的浪费；
+ 由于表特别大，导致检索一次查询效率特别低。

因此不得不采用一中解决上述缺点的方法进行强化学习，目前比较实用的就是近似价值函数方法.

四、近似价值函数

近似值函数：从字面上看就是无限逼近真实值函数（状态值函数Vπ(s)$V_{\pi }(s)$、 状态-行为值函数Qs,q$Q_{s,q}$）的意思，用数学表示为下面公式（29)[未标注]：

V^(s,w)≈Vπ(s)$$\hat{V}(s,w)\approx V_{\pi }(s)$$

Q^(s,a,w)≈Qπ(s,a)$$\hat{Q}(s,a,w)\approx Q_{\pi }(s,a)$$

其中我们的目的就是找到合适的 w$w$ 来近似值函数，w$w$可以是参数化逼近和非参数化逼近，非参数可以理解为通过核函数等方式，参数化后文会讲解。基于此，根据强化学习的输入，输出被表示为三种近似方法，如图：

• 图(1)表示根据状态本身，输出这个状态的近似价值；
• 图(2)表示根据状态行为对，输出状态行为对的近似价值；
• 图(3)表示根据状态本身，输出一个向量，向量中的每一个元素是该状态下采取一种可能行为的价值。

我们可以将上述的三个正方形盒子视为黑盒子，它就是一个函数近似器，可以将其想象为任何东西，比如l它是一个* 神经网络、决策树、泰勒多项式、线性函数、Fourier/Wavelet base等 *。或者为一切可描述或者无法描述的东西。本文讲介绍神经网络，其他其中方法后续将单独做详解。

4.1 递增方法 Incremental Methods

本部分讲述采用神经网络方法进行近似值函数,因为神经网络可以拟合任何一个函数。神经网络j结构如图，对于反向传播更新方式此处不讲：

我们定义一个目标函数J(w)$J(w)$(该函数可微),w$w$为vector, 那么目标函数关于w$w$的梯度表示为：

∇wJ(w)=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢∂J(w)∂w1...∂J(w)∂wn⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥(30)$$\begin{array}{}\text{(30)}& {\mathrm{\nabla }}_{w}J(w)=\left[\begin{array}{c}\frac{\mathrm{\partial }J(w)}{\mathrm{\partial }{w}_1}\\ .\\ .\\ .\\ \frac{\mathrm{\partial }J(w)}{\mathrm{\partial }{w}_n}\end{array}\right]\end{array}$$

为了能够达到 minJ(w)$minJ(w)$ ,只需在梯度下降或者上身的方向调整W$W$,使其达到局部最小值

△w=−12α∇wJ(w)(31)$$\begin{array}{}\text{(31)}& \mathrm{△}w=-\frac{1}{2}\alpha {\mathrm{\nabla }}_{w}J(w)\end{array}$$

* 目标*： 找到参数w$w$,最小化状态值函数Vπ(s)$V_{\pi }(s)$ 和近似器 V^(s，w)$\hat{V}(s，w)$之间的均方差和状态-行为值函数Qπ(s,a)$Q_{\pi }(s,a)$和近似器 Q^(s,a,w)$\hat{Q}(s,a,w)$之间的的均方差。
以状态值函数为例：定义目标函数：

J(w)=Eπ[(Vπ(s)−V^(s,w))2](32)$$\begin{array}{}\text{(32)}& J(w)=E_{\pi }[(V_{\pi }(s)-\hat{V}(s,w){)}^2]\end{array}$$

通过梯度下降找到当地最小值：

△w=−12α∇wJ(w)=αEπ[Vπ(s)−V^(s,w)]⋅∇wV^(s,w)(33)$$\begin{array}{rl}\mathrm{△}w& =-\frac{1}{2}\alpha {\mathrm{\nabla }}_{w}J(w)\\ \text{(33)}& & =\alpha E_{\pi }[V_{\pi }(s)-\hat{V}(s,w)]\cdot {\mathrm{\nabla }}_w\hat{V}(s,w)\end{array}$$

其实，目前所列的公式都不能直接用于强化学习(看了这么多数学公式，尽然说没用), 因为公式里都有一个实际价值函数 vπ(S)$v_{\pi }(S)$，而强化学习没有监督数据，因此不能直接使用上述公式。对于只有即时奖励，没有监督数据的强化学习。我们需要找到能替代vπ(S)$v_{\pi }(S)$的目标值，以便来使用监督学习的思路学习到近似函数的参数。

因此对于强化学习的两个基本问题之一：* Prediction*
* 方法：*
（1）对于MC，target是返回值Gt$G_t$， 即：

△w=α(Gt−V^(s,w)∇wV^(s,w))(34)$$\begin{array}{}\text{(34)}& \mathrm{△}w=\alpha (G_t-\hat{V}(s,w){\mathrm{\nabla }}_w\hat{V}(s,w))\end{array}$$

(2) 对于TD(0)，target是TD-target Rt+1+γV^(St+1,w)$R_{t+1}+\gamma \hat{V}(S_{t+1},w)$,即：

△w=α(Rt+1+γV^(St+1,w)−V^(s,w)∇wV^(s,w))(35)$$\begin{array}{}\text{(35)}& \mathrm{△}w=\alpha (R_{t+1}+\gamma \hat{V}(S_{t+1},w)-\hat{V}(s,w){\mathrm{\nabla }}_w\hat{V}(s,w))\end{array}$$

因此对于强化学习的两个基本问题之一：* Control*
那么如何把近似函数引入到控制过程中呢？我们需要能够近似状态-行为值函数对价值函数近似而不是仅针对状态价值函数近似。为什么呢？
因为* Model-free控制需要满足两个条件：*
+ 1、在模型未知的条件下无法知道当前状态的所有后续状态，进而无法确定在当前状态下采取怎样的行为更合适。通常使用状态行为对下的价值Q(s,a)来代替状态价值， 即：π′(s)=argmaxa∈AQ(S,a)${\pi }^{{}^{\prime }}(s)=\arg \underset{a\in A}{max}Q(S,a)$
+ 2、探索（Exploration）：即使满足条件（1），至少还存在一个问题，即当我们每次都使用贪婪算法来改善策略的时候，将很有可能由于没有足够的采样经验而导致产生一个并不是最优的策略，因此需要不停的探索（Exploration）新行为，即：π=ϵ$\pi =ϵ$-greedy(Qw)$greedy(Q_w)$

从一系列参数开始，得到一个近似的状态-行为值函数，在Ɛ-greedy执行策略下产生一个行为，执行该行为得到一个即时奖励，以此数据计算目标值，进行近似函数参数的更新。再应用这个策略得到后续的状态和对应的目标值，每经历一次状态就更新依次参数，如此反复进行策略的优化，同时逼近最优价值函数。

因此对于* 策略评估 *，即近似策略评估：

q^(s,a,w)≈qπ(s,a)(36)$$\begin{array}{}\text{(36)}& \hat{q}(s,a,w)\approx q_{\pi }(s,a)\end{array}$$

策略改善： 采用Ɛ-greedy

状态-行为值函数的近似过程类似与状态值函数（此处不描述，直接给结论）：

△w=α(qπ(s,q)−q^(s,a,w))⋅∇wq^(s,a,w)(37)$$\begin{array}{}\text{(37)}& \mathrm{△}w=\alpha (q_{\pi }(s,q)-\hat{q}(s,a,w))\cdot {\mathrm{\nabla }}_w\hat{q}(s,a,w)\end{array}$$

至此，第一篇结束！

第二篇《深度强化学习及算法讲解》

声明:
1 本文内容均属原创,受知识水平有限,如有错误之处,请联系作者以便于修改纠正.
2 本文所有参考他人论文, 书籍,知识栏目, 图片等一切有关知识均在Blog末尾以引用格式进行标注, 再次表示致谢. 如有他人内容未标明引用的请联系本文作者,以添加引用,在此表示歉意!

参考文献:

[1]. Richard S.Sutton and Andrew G. Barto,Reinforcement learning: An Introduction,second edition.2017.
[2]. Lucian Busontu et al, Reinforcement learning and dynamic programming using function approximators.
[3]. 郭宪 方勇纯, 深入浅出强化学习:原理入门
[4]. Howard M.Schwartz 连晓峰(译), 多智能体机器学习:强化学习方法
[5]. David Sliver, Introduction to Reinforcement learning
(UCL:https://www.youtube.com/channel/UCP7jMXSY2xbc3KCAE0MHQ-A)
[6]. 阿里技术, 从虚拟世界走进现实应用,强化学习在阿里的技术演进与业务创新.
[7]. Deep Reinforcements Learnin- An Overview()
[8].https://zhuanlan.zhihu.com/reinforce
[9]. https://mp.weixin.qq.com/s/aAHbybdbs_GtY8OyU6h5WA##
[10].https://www.youtube.com/watch?v=W_gxLKSsSIE&list=PL5nBAYUyJTrM48dViibyi68urttMlUv7e
[11]. https://www.youtube.com/watch?v=CIF2SBVY-J0