强化学习（一）Deep Q-Network

1. 前言

虽然将深度学习和增强学习结合的想法在几年前就有人尝试，但真正成功的开端就是DeepMind在NIPS 2013上发表的 Playing Atari with Deep Reinforcement Learning 一文，在该文中第一次提出Deep Reinforcement Learning 这个名称，并且提出DQN（Deep Q-Network）算法，实现从纯图像输入完全通过学习来玩Atari游戏的成果。之后DeepMind在Nature上发表了改进版的DQN文章Human-level Control through Deep Reinforcement Learning，引起了广泛的关注，Deep Reinfocement Learning 从此成为深度学习领域的前沿研究方向。

智能体 Agent 来表示一个具备行为能力的物体，比如机器人，无人车，人等等。

那么增强学习考虑的问题就是智能体Agent和 环境 Environment 之间交互的任务。

比如一个机械臂要拿起一个手机，那么机械臂周围的物体包括手机就是环境，机械臂通过外部的比如摄像头来感知环境，然后机械臂需要输出动作来实现拿起手机这个任务。再举玩游戏的例子，比如我们玩极品飞车游戏，我们只看到屏幕，这就是环境，然后我们输出动作（键盘操作）来控制车的运动。

那么，不管是什么样的任务，
都包含了一系列的：

• 动作 Action
• 观察 Observation
• 反馈值 Reward

所谓的Reward就是Agent执行了动作与环境进行交互后，环境会发生变化，变化的好与坏就用Reward来表示。

接下来这里用了Observation观察一词而不是环境那是因为Agent不一定能得到环境的所有信息，比如机械臂上的摄像头就只能得到某个特定角度的画面。因此，只能用Observation来表示Agent获取的感知信息。

只能用 Observation 来表示 Agent 获取的感知信息

每个时间片，Agent 都是根据当前的观察来确定下一步的动作。观察 Observation 的集合就作为Agent的所处的 状态 State，因此，状态 State 和 动作 Action 存在映射关系，也就是一个 state 可以对应一个 action，或者对应不同动作的概率（常常用概率来表示，概率最高的就是最值得执行的动作）。状态与动作的关系其实就是输入与输出的关系，而状态 State 到动作 Action 的过程就称之为一个策略 Policy，一般用 \(\pi\) 表示，也就是需要找到以下关系：

$$a=\pi(s)$$

或者

$$\pi(a|s)$$

其中 a 是 action，s 是 state。
第一种是一一对应的表示，第二种是概率的表示。

增强学习的任务就是找到一个最优的策略Policy从而使Reward最多

我们一开始并不知道最优的策略是什么，因此往往从随机的策略开始，使用随机的策略进行试验，就可以得到一系列的状态,动作和反馈：

$$\{s_1,a_1,r_1,s_2,a_2,r_2,…s_t,a_t,r_t\}$$

这就是一系列的 样本 Sample。增强学习的算法就是需要根据这些样本来改进 Policy，从而使得得到的样本中的 Reward 更好。由于这种让 Reward 越来越好的特性，所以这种算法就叫做增强学习Reinforcement Learning。

## 2. 马尔科夫决策过程

MDP只需要用一句话就可以说明白，就是 “未来只取决于当前”，专业点说就是下一步的状态只取决于当前的状态，与过去的状态没有关系。

一个状态 \(S_t\) 是Markov当且仅当：

$$P(s_{t+1}|s_t)=P(s_{t+1}|s_t,s_{t-1},…s_1,s_0)$$

P为概率。简单的说就是下一个状态仅取决于当前的状态和当前的动作。
增强学习的问题都可以模型化为MDP的问题

因此 MDP 可以表示为一个元组 \((S, A, P_{sa}, R)\) ：

• \(S\) ：所有可能状态的集合， \(s \in S\)，\(s\) 表示某个特定状态
• \(A\) ：针对每个状态，我们都要做出动作，这些动作的集合就是 \(A\)； \(a \in A\)，有限动作 action 集合， \(a\) 表示某个特定动作
• \(P_{sa}\) ：状态转换分布（statetransition distribution），如果我们在状态 \(s\) 中采取了动作 \(a\) ，系统会转移到一个新的状态，状态转换分布描述了转移到哪个状态的概率分布。
• \(R\) ：回馈函数（rewardfunction），增强学习的核心概念，描述了动作能够产生的回报。比如 \(R_π(s,a)\) 描述了在状态 \(s\) 下采用策略 \(\pi\) 所对应的动作 \(a\) 的回报，也叫做立即回报，回馈函数可以有不同的表达形式。
• \(\pi(s)\rightarrow a\)： 策略 policy，根据当前 state 来产生 action，可表现为 \(a=\pi(s) \) 或 \( \pi(a|s) = P[a|s]\)，后者表示某种状态下执行某个动作的概率

一个基本的 MDP 可以用 \((S,A,P)\) 来表示， \(S \) 表示状态， \(A\) 表示动作， \(P \) 表示状态转移概率，也就是根据当前的状态 \(s_t\) 和 \(a_t\) 转移到 \(s_{t+1}\) 的概率。

如果我们知道了转移概率 P，也就是称为我们获得了 模型 Model，有了模型，未来就可以求解，那么获取最优的动作也就有可能，这种通过模型来获取最优动作的方法也就称为 Model-based 的方法。但是现实情况下，很多问题是很难得到准确的模型的，因此就有 Model-free 的方法来寻找最优的动作。

## 3. 价值函数

既然一个状态对应一个动作，或者动作的概率，而有了动作，下一个状态也就确定了。这就意味着每个状态可以用一个确定的值来进行描述。可以由此判断一个状态是好的状态还是不好的状态。

但是在选取最优策略的过程中，我们只看立即回报并不能判定哪种策略更优，我们希望的是在采取了策略 \(\pi\) 以后，可以使得整个状态序列的折扣回馈最大。

状态的好坏其实等价于对未来回报的期望，回报 Return 来表示某个时刻 t 的状态将具备的回报：

$$G_t = R_{t+1} + \lambda R_{t+2} + … = \sum_{k=0}^\infty\lambda^kR_{t+k+1}$$

• R 是 Reward 反馈
• \(λ\) 是 discount factor 折扣因子，一般小于 1，就是说一般当下的反馈是比较重要的，时间越久，影响越小。

其中 \(λ\) 被称为折扣因子，在经济学上的解释叫做无风险折现率（risk-freeinterest rate），意思是马上得到的钱（回馈）比未来得到钱更有价值。

以上概念就组成了增强学习的完整描述：找到一种策略，使得我们能够根据状态 \(s_0, s_1, s_2, …\) 采取策略中对应的动作 \(a_0, a1, a2…，\) 并使 \(G_t\) 的期望值最大化

引出价值函数，对于获取最优的策略Policy这个目标，我们就会有两种方法：

• 直接优化策略 \(\pi(a|s)\) 或者 \(a = \pi(s)\) 使得回报更高
• 通过估计 value function 来间接获得优化的策略。道理很简单，既然我知道每一种状态的优劣，那么我就知道我应该怎么选择了，而这种选择就是我们想要的策略。

但是现在为了理解DQN，我们将只关注第二种做法，就是估计value function的做法，因为DQN就是基于value function的算法。

1. 状态价值函数 \(V\) ：从状态 \(x_0\) 开始, 所有的动作 \(a\) ，都是执行某个策略 \(π\) 的结果，最后求每个动作带来累积奖赏
2. 动作价值函数 \(Q\) ：从状态 \(x_0\) 开始，先执行动作 \(a_0\) ， 然后再执行某个策略 \(π\) ，再求相应的积累奖赏

### 3.1 State-Value function 状态价值函数

那么实际上除非整个过程结束，否则显然我们无法获取所有的 reward 来计算出每个状态的Return，因此，再引入一个 概念价值函数 Value Function，用 value function \(v(s)\) 来表示一个状态未来的潜在价值。

从定义上看，value function 就是回报的期望：

$$v(s) = \mathbb E[G_t|S_t = s]$$

$$V^{\pi}(s) =\mathbb E_{\pi}[ R(s_0, a_0) + γR(s_1, a_1)+ γ^2R(s_2, a_2) + … | s_0= s ]$$

这个函数也被称为状态价值函数(statevalue function)，记为 \(V_{\pi}(s)\)。 因为初始状态 \(s\) 和策略 \(\pi\) 是我们给定的，动作 \(a = \pi(s)\) 。

### 3.2 Action-Value function 动作价值函数

我们更关心在某个状态下的不同动作的价值。显然。如果知道了每个动作的价值，那么就可以选择价值最大的一个动作去执行了。

这就是 Action-Value function \(Q^\pi(s,a)\) 。那么同样的道理，也是使用 reward 来表示，只是这里的 reward 和之前的 reward 不一样：

这里是执行完动作 action 之后得到的 reward，之前 state 对应的 reward 则是多种动作对应的 reward 的期望值。显然，动作之后的 reward 更容易理解。

那么，有了上面的定义，动作价值函数就为如下表示：

$$ Q^{\pi}(s,a) = \mathbb E[R_{t+1}+\lambda R_{t+2} + \lambda ^2R_{t+3} + …|S_t = s,A_t=a]$$

$$
\begin{align}
Q^\pi(s,a) & = \mathbb E[r_{t+1} + \lambda r_{t+2} + \lambda^2r_{t+3} + … |s,a] \\
& = \mathbb E_{s^\prime}[r+\lambda Q^\pi(s^\prime,a^\prime)|s,a]
\end{align}
$$

这里要说明的是动作价值函数的定义，加了 \(\pi\) ,也就是说是在策略下的动作价值。因为对于每一个动作而已，都需要由策略根据当前的状态生成，因此必须有策略的支撑。而前面的价值函数则不一定依赖于策略。当然，如果定义 \(v^\pi(s)\) 则表示在策略 \(\pi\) 下的价值。

那么事实上我们会更多的使用动作价值函数而不是价值函数，因为动作价值函数更直观，更方便应用于算法当中。

## 4. Bellman 方程

在上文我们介绍了 Value Function 价值函数，所以为了解决增强学习的问题，一个显而易见的做法就是我们需要估算 Value Function。是的，只要我们能够计算出价值函数，那么最优决策也就得到了。因此，问题就变成了如何计算 Value Function？

$$P^a_{ss\prime} = P(S_{t+1}=s\prime|S_t =s, A_t =a)$$

还记得回报 Result 的基本定义吗？就是所有 Reward 的累加（带衰减系数 discount factor）

$$G_t = R_{t+1} + \lambda R_{t+2} + … = \sum_{k=0}^\infty\lambda^kR_{t+k+1}$$

那么 Value Function 该如何定义？也很简单，就是期望的回报啊！期望的回报越高，价值显然也就越大，也就越值得去选择。用数学来定义就是如下：

$$v(s) = \mathbb E[G_t|S_t = s]$$

$$v_{\pi}=\sum_{a\in A}P(a|s)\left(R^a_s+\lambda\sum_{s\prime \in S}P^a_{ss\prime}v_{\pi}(s\prime)\right)$$

接下来，我们把上式展开如下：

$$
\begin{align}
v(s) & = \mathbb E[G_t|S_t = s] \\
& = \mathbb E[R_{t+1}+\lambda R_{t+2} + \lambda ^2R_{t+3} + …|S_t = s] \\
& = \mathbb E[R_{t+1}+\lambda (R_{t+2} + \lambda R_{t+3} + …)|S_t = s] \\
& = \mathbb E[R_{t+1} + \lambda G_{t+1}|S_t = s] \\
& = \mathbb E[R_{t+1} + \lambda v(S_{t+1})|S_t = s]
\end{align}
$$

因此，

$$v(s) = \mathbb E[R_{t+1} + \lambda v(S_{t+1})|S_t = s]$$

上面这个公式就是Bellman方程的基本形态。从公式上看，当前状态的价值和 下一步的价值以及当前的反馈Reward有关。

它表明Value Function是可以通过迭代来进行计算的!!!

总结一下：

$$v_{\pi}(s) = \mathbb E[R_{t+1} + \lambda v_{\pi}(S_{t+1})|S_t = s]$$

$$ q_{\pi}(s,a) = \mathbb E_{\pi}[R_{t+1} +\lambda q_\pi(S_{t+1},A_{t+1})|S_t =s,A_t = a]$$

## 5. 最优化

动态规划

先简单介绍一下动态规划，因为严格来说，值迭代与策略迭代是用来解决动态规划问题的两种规划方法。而强化学习又有另外一个昵称——就是拟动态规划。说白了强化学习就是模拟动态规划算法。

用一句话来总结动态规划就是，对一个复杂问题给出一个一般性的解决办法。它主要由两个性质:

• 最优子结构：最优解法能被分解到多个子问题中
• 重叠子问题：子问题能重复多次且解法能被重复利用、

马尔科夫决策过程（MDP）满足以上两个性质，所以任何 MDP 都可以用动态规划来解。动态规划与强化学习的区别就是动态规划假设 MDP 模型是全知的（即参数可知） 而 强化学习可以使 MDP 未知。

MDP需要解决的问题有两种：

• 第一种是 prediction，它已知MDP的 \(S,A,P,R,γ\) 以及 policy，目标是算出在每个状态下的 value function(值函数其实就是问题的目标，一般都是跟 reward 有关的函数，例如 Atari 小游戏，一般值函数就是累计的得分的期望。目标一般就是最大化这个值函数。
• 而第二种是control，它已知 MDP 的 \(S,A,P,R,γ\) 但是 policy 未知（即动作 \(a_t\) 未知），因此它的目标不仅是计算出最优的 value function 而且要给出最优的 Policy。

5.1 Optimal value function 最优价值函数

能计算动作价值函数是不够的，因为我们需要的是最优策略，现在求解最优策略等价于求解最优的 value function，找到了最优的 value function，自然而然策略也就是找到。（当然，这只是求解最优策略的一种方法，也就是 value-based approach，由于 DQN 就是 value-based，因此这里只讲这部分，以后我们会看到还有 policy-based 和 model-based 方法。一个就是直接计算策略函数，一个是估计模型，也就是计算出状态转移函数，从而整个MDP过程得解）

首先是最优动作价值函数和一般的动作价值函数的关系：

$$V^*(s,a) = \max_\pi V^\pi(s,a)$$

$$Q^*(s,a) = \max_\pi Q^\pi(s,a)$$

也就是最优的动作价值函数就是所有策略下的动作价值函数的最大值。通过这样的定义就可以使最优的动作价值的唯一性，从而可以求解整个MDP。

那么套用上一节得到的 value function，可以得到

$$Q^*(s,a) = \mathbb E_{s^\prime}[r+\lambda \max _{a^\prime}Q^*(s^\prime,a^\prime)|s,a]$$

因为最优的Q值必然为最大值，所以，等式右侧的Q值必然为使 \(a′\) 取最大的Q值。

下面介绍基于Bellman方程的两个最基本的算法，策略迭代和值迭代。

 

5.2 Policy Iteration 策略迭代

策略迭代就是在policy未知的情况下，根据每次的reward学到最优policy。

对一个具体的 MDP 问题，每次先初始化一个策略，根据这个策略计算值函数 \(v(s)\) , 通过这个re值函数来根据贪心策略更新策略，不断迭代最终得到最优策略与最优值函数。总结下来就两个阶段。

• Policy evaluation ：根据每一次的给出策略估计 \(v_π\)
• Policy improvement：根据 Greedy poilcy 和之前得到的 \(v_π\) 获得当前策略 \(π′\)

Policy Iteration的目的是通过迭代计算value function 价值函数的方式来使policy收敛到最优。

给一个例子：

下图是一个叫 Small Gridworld 的例子，左上角和右下角是终点， \(γ=1\) ，移动一步 reward 减少1，起始的 random policy 是朝每个能走的方向概率相同，先单独看左边一列，它表示在第 \(k\) 次迭代每个 state上value function 的值，这一列始终采用了 random policy，这里的 value function 就是通过 Bellman Expectation Equation 得到的，考虑 \(k=2\) 的情况， \(-1.7 = -1.0 + 2\times (1/3.0)(-1)\)，\(-2.0 = -1.0 + 4(1/4.0)\times (-1)\) 。而右边一列就是在当前的 value function 情况下通过 greedy 算法找到当前朝哪个方向走更好。

Policy Iteration 本质上就是直接使用 Bellman 方程而得到的：


5.3 Value Iteration 价值迭代

Value Iteration 则是使用 Bellman 最优方程得到：


然后改变成迭代形式：


值迭代就是在已知 policy 和 MDP 模型的情况下，根据策略获得最优值函数和最优策略。 只不过这是确定策略，在值函数 \\(v\_π\\) 取得最大值的 \\(a\_t\\) (策略) 通过每次迭代bellman方程获得 \\(v\_i\\) , 知道值函数收敛。图解如下：


## 6. Q-Value (Quality-Value)

Q Learning的思想完全根据value iteration得到。但要明确一点是value iteration每次都对所有的Q值更新一遍，也就是所有的状态和动作。但事实上在实际情况下我们没办法遍历所有的状态，还有所有的动作，我们只能得到有限的系列样本。因此，只能使用有限的样本进行操作。那么，怎么处理？Q Learning提出了一种更新Q值的办法：

$$Q(S_{t},A_{t}) \leftarrow Q(S_{t},A_{t})+\alpha({R_{t+1}+\lambda \max _aQ(S_{t+1},a)} - Q(S_t,A_t))$$

虽然根据value iteration计算出target Q值，但是这里并没有直接将这个Q值（是估计值）直接赋予新的Q，而是采用渐进的方式类似梯度下降，朝target迈近一小步，取决于α,这就能够减少估计误差造成的影响。类似随机梯度下降，最后可以收敛到最优的Q值。

具体的算法如下：


大致代码流程如下：

def update():
    # 学习 100 回合
    for episode in range(100):
        # 初始化 state 的观测值
        observation = env.reset()

        while True:
            # 更新可视化环境
            env.render()

            # RL 大脑根据 state 的观测值挑选 action
            action = RL.choose_action(str(observation))

            # 探索者在环境中实施这个 action, 并得到环境返回的下一个 state 观测值, reward 和 done (是否是掉下地狱或者升上天堂)
            observation_, reward, done = env.step(action)

            # RL 从这个序列 (state, action, reward, state_) 中学习
            RL.learn(str(observation), action, reward, str(observation_))

            # 将下一个 state 的值传到下一次循环
            observation = observation_

            # 如果掉下地狱或者升上天堂, 这回合就结束了
            if done:
                break

    # 结束游戏并关闭窗口
    print('game over')
    env.destroy()

if __name__ == "__main__":
    # 定义环境 env 和 RL 方式
    env = Maze()
    RL = QLearningTable(actions=list(range(env.n_actions)))

    # 开始可视化环境 env
    env.after(100, update)
    env.mainloop()

注意：

每一组 (state, action, reward, state_) 为一次序列

以我们回到之前的流程, 根据 Q 表的估计, 因为在 s1 中, a2 的值比较大, 通过之前的决策方法, 我们在 s1 采取了 a2, 并到达 s2, 这时我们开始更新用于决策的 Q 表, 接着我们并没有在实际中采取任何行为, 而是再想象自己在 s2 上采取了每种行为, 分别看看两种行为哪一个的 Q 值大, 比如说 Q(s2, a2) 的值比 Q(s2, a1) 的大, 所以我们把大的 Q(s2, a2) 乘上一个衰减值 gamma (比如是0.9) 并加上到达s2时所获取的奖励 R (这里还没有获取到我们的棒棒糖, 所以奖励为 0), 因为会获取实实在在的奖励 R , 我们将这个作为我现实中 Q(s1, a2) 的值, 但是我们之前是根据 Q 表估计 Q(s1, a2) 的值. 所以有了现实和估计值, 我们就能更新Q(s1, a2) , 根据 估计与现实的差距, 将这个差距乘以一个学习效率 alpha 累加上老的 Q(s1, a2) 的值 变成新的值.

但时刻记住, 我们虽然用 maxQ(s2) 估算了一下 s2 状态, 但还没有在 s2 做出任何的行为, s2 的行为决策要等到更新完了以后再重新另外做. 这就是 off-policy 的 Q learning 是如何决策和学习优化决策的过程.


$$\text{update = learing_rate * (q_target - q_predict)}$$

$$\text{学习率 * (真实值 - 预测值)}$$

我们想象 Qlearning 的机器人天生近视眼, \(\gamma= 1\) 时, 机器人有了一副合适的眼镜, 在 s1 看到的 Q 是未来没有任何衰变的奖励, 也就是机器人能清清楚楚地看到之后所有步的全部价值, 但是当 \(\gamma= 0\) , 近视机器人没了眼镜, 只能摸到眼前的 reward, 同样也就只在乎最近的大奖励, 如果 \(\gamma\) 从 0 变到 1, 眼镜的度数由浅变深, 对远处的价值看得越清楚, 所以机器人渐渐变得有远见, 不仅仅只看眼前的利益, 也为自己的未来着想.

## 7. Exploration and Exploitation 探索与利用

在上面的算法中，我们可以看到需要使用某一个policy来生成动作，也就是说这个policy不是优化的那个policy，所以Q-Learning算法叫做Off-policy的算法。另一方面，因为Q-Learning完全不考虑model模型也就是环境的具体情况，只考虑看到的环境及reward，因此是model-free的方法。

回到policy的问题，那么要选择怎样的 policy 来生成 action 呢？有两种做法：

• 随机的生成一个动作
• 根据当前的Q值计算出一个最优的动作，这个 policy \(\pi\) 称之为 greedy policy 贪婪策略。也就是 \(\pi(S_{t+1}) = arg\max _aQ(S_{t+1},a)\)

使用随机的动作就是 exploration，也就是探索未知的动作会产生的效果，有利于更新Q值，获得更好的policy。

而使用 greedy policy 也就是 target policy 则是 exploitation，利用policy，这个相对来说就不好更新出更好的Q值，但可以得到更好的测试效果用于判断算法是否有效。

将两者结合起来就是所谓的 \(\epsilon\ greedy\) 策略， \(\epsilon\) 一般是一个很小的值，作为选取随机动作的概率值。可以更改 \(\epsilon\) 的值从而得到不同的 exploration 和 exploitation 的比例。例如 \(\epsilon = 0.1\) 表示 90% 的时间是选择最优策略, 10% 的时间来探索.

要注意一点就是 egreedy 的 \(\epsilon\) 是不断变小的，也就是随机性不断变小。怎么理解呢？就是一开始需要更多的探索，所以动作偏随机，慢慢的我们需要动作能够有效，因此减少随机。也就是越来越贪婪。
例如：
INITIAL_EPSILON = 0.5 # starting value of epsilon
FINAL_EPSILON = 0.01 # final value of epsilon

这里需要说明的一点是使用 \(\epsilon-greedy\) 策略是一种极其简单粗暴的方法，对于一些复杂的任务采用这种方法来探索未知空间是不可取的。因此，最近有越来越多的方法来改进这种探索机制。

## 8. 详解Q-Learning

8.1 Value Function Approximation 价值函数近似

在简单分析中，我们使用表格来表示Q(s,a)，但是这个在现实的很多问题上是几乎不可行的，因为状态实在是太多。使用表格的方式根本存不下。

我们有必要对状态的维度进行压缩，解决办法就是 价值函数近似 Value Function Approximation

就是用一个函数来表示Q(s,a)，即：

$$Q(s,a) = f(s,a)$$

f可以是任意类型的函数，比如线性函数：

$$Q(s,a) = w_1s + w_2a + b$$
其中 \(w_1,w_2,b\) 是函数 \(f\) 的参数。

通过函数表示，我们就可以无所谓 \(s\) 到底是多大的维度，反正最后都通过矩阵运算降维输出为单值的 \(Q\) 。这就是价值函数近似的基本思路。

如果我们就用 \(w\) 来统一表示函数f的参数，那么就有

$$Q(s,a) = f(s,a,w)$$

为什么叫近似，因为我们并不知道 \(Q\) 值的实际分布情况，本质上就是用一个函数来近似 \(Q\) 值的分布，所以，也可以说是

$$Q(s,a)\approx f(s,a,w)$$

### 8.2 Q值神经网络化！

用一个深度神经网络来表示这个函数 \(f\)，即我们可以将状态和动作当成神经网络的输入, 然后经过神经网络分析后得到动作的 Q 值, 这样我们就没必要在表格中记录 Q 值, 而是直接使用神经网络生成 Q 值.还有一种形式的是这样, 我们也能只输入状态值, 输出所有的动作值, 然后按照 Q learning 的原则, 直接选择拥有最大值的动作当做下一步要做的动作。一般使用第二种形式。

以DQN为例，输入是经过处理的4个连续的84x84图像，然后经过两个卷积层，两个全连接层，最后输出包含每一个动作Q值的向量。

用神经网络来表示Q值非常简单，Q值也就是变成用Q网络（Q-Network）来表示。接下来就到了很多人都会困惑的问题，那就是怎么训练Q网络？？？

我们知道，神经网络的训练是一个最优化问题，最优化一个损失函数loss function，也就是标签和网络输出的偏差，目标是让损失函数最小化。为此，我们需要有样本，巨量的有标签数据，然后通过反向传播使用梯度下降的方法来更新神经网络的参数。

所以，要训练Q网络，我们要能够为Q网络提供有标签的样本。

所以，问题变成：

如何为 Q 网络提供有标签的样本？
答案就是利用 Q-Learning 算法。

回想一下 Q-Learning 算法，
$$Q(S_{t},A_{t}) \leftarrow Q(S_{t},A_{t})+\alpha({R_{t+1}+\lambda \max _aQ(S_{t+1},a)} - Q(S_t,A_t))$$

Q值的更新依靠什么？依靠的是利用 Reward 和 Q 计算出来的目标Q值：

$$\text{Target-Q : }\ \ R_{t+1}+\lambda \max _aQ(S_{t+1},a)$$

因此，我们把目标Q值作为标签不就完了？我们的目标不就是让Q值趋近于目标Q值吗？
因此，Q网络训练的损失函数就是：

 \\(s^\`,a^`\\) 即下一个状态和动作

既然确定了损失函数，也就是cost，确定了获取样本的方式。那么DQN的整个算法也就成型了！接下来就是具体如何训练的问题了！

**前边提到**，每一组 `(state, action, reward, state_)` 为一次序列：

• state (observation) 为目前状态，传递给 q-eval net 得到预计值 (即输入状态值, 输出所有的动作值)；
• state_ 为下一步状态，传递给 q-target net 得到目标值，之后可以得到 \(\max _aQ(S_{t+1},a)\) ，在之后得到 \(R_{t+1}+\lambda \max _aQ(S_{t+1},a)\)

最终的 \(loss\) 为：

self.loss = tf.reduce_mean(tf.squared_difference(self.q_target, self.q_eval))

再次注意，q-eval net 和 q-target net 网络结构完全一样，只不过参数更新不同！(即 Fixed Q-targets 方法)



最基本的DQN，也就是NIPS 13版本的DQN：


那么上面的算法看起来那么长，其实就是反复试验，然后存储数据。接下来数据存到一定程度，就每次随机采用数据，进行梯度下降！

也就是在DQN中增强学习 Q-Learning 算法和深度学习的 SGD 训练是同步进行的！
通过 Q-Learning 获取无限量的训练样本，然后对神经网络进行训练。

整体代码结构大致如下：

def run_maze():
    step = 0    # 用来控制什么时候学习
    for episode in range(300):
        # 初始化环境
        observation = env.reset()

        while True:
            # 刷新环境
            env.render()

            # DQN 根据观测值选择行为
            action = RL.choose_action(observation)

            # 环境根据行为给出下一个 state, reward, 是否终止
            observation_, reward, done = env.step(action)

            # DQN 存储记忆
            RL.store_transition(observation, action, reward, observation_)

            # 控制学习起始时间和频率 (先累积一些记忆再开始学习)
            if (step > 200) and (step % 5 == 0):
                RL.learn()

            # 将下一个 state_ 变为 下次循环的 state
            observation = observation_

            # 如果终止, 就跳出循环
            if done:
                break
            step += 1   # 总步数

    # end of game
    print('game over')
    env.destroy()


if __name__ == "__main__":
    env = Maze()
    RL = DeepQNetwork(env.n_actions, env.n_features,
                      learning_rate=0.01,
                      reward_decay=0.9,
                      e_greedy=0.9,
                      replace_target_iter=200,  # 每 200 步替换一次 target_net 的参数
                      memory_size=2000, # 记忆上限
                      # output_graph=True   # 是否输出 tensorboard 文件
                      )
    env.after(100, run_maze)
    env.mainloop()
    RL.plot_cost()  # 观看神经网络的误差曲线

### 8.3 Experience Replay 经验回放

Q learning 是一种 off-policy 离线学习法, 它能学习当前经历着的, 也能学习过去经历过的, 甚至是学习别人的经历. 所以每次 DQN 更新的时候, 我们都可以随机抽取一些之前的经历进行学习. 随机抽取这种做法打乱了经历之间的相关性, 也使得神经网络更新更有效率。

其将系统探索环境得到的数据储存起来，然后随机采样样本更新深度神经网络的参数（有了一个记忆库之后再开始学习）。


Experience Replay 的动机是：

• 深度神经网络作为有监督学习模型，要求数据满足独立同分布，
• 但 Q Learning 算法得到的样本前后是有关系的。为了打破数据之间的关联性，Experience Replay 方法通过存储-采样的方法将这个关联性打破了。

之所以加入 experience replay 是因为样本是从游戏中的连续帧获得的，这与简单的 reinforcement learning 问题（比如maze）相比，样本的关联性大了很多，如果没有 experience replay，算法在连续一段时间内基本朝着同一个方向做 gradient descent，那么同样的步长下这样直接计算 gradient 就有可能不收敛。因此 experience replay 是从一个 memory pool 中随机选取了一些 experience，然后再求梯度，从而避免了这个问题。

原文的实验中指出mini batch是32，而replay memory存了最近的1000000帧。

### 8.4 Fixed Q-targets

Fixed Q-targets 也是一种打乱相关性的机理, 如果使用 fixed Q-targets, 我们就会在 DQN 中使用到两个结构完全相同但参数不同的神经网络 (有时差), 预测 Q 估计 的神经网络 (evaluate net) 具备最新的参数, 而预测 Q 现实 的神经网络 (target net) 使用的参数则是很久以前的。

例如一开始有两个完全一样的网络，一个进行训练，另一个不训练，到了训练10000次后，把训练过的网络参数完全复制给冻结的网络，之后仍是一个训练，持续更新参数，一个冻结，每10000次才更新一次。

target_net 用于预测 q_target 目标值, 他不会及时更新参数.

eval_net 用于预测 q_eval 估计值, 这个神经网络拥有最新的神经网络参数


8.5 总结

在 Q-Learning 算法中，计算经验得分的公式如下：

$$\text{Q(state, action) = Q(state, action) + }\alpha\text{ (R(state, action) + }\gamma \text{ Max[Q(next state, all actions)] - Q(state, action))}$$

当 \(\alpha\) 的值是 \(1\) 时，公式如下：

$$\text{Q(state, action) = R(state, action) +} \gamma\text{ Max[Q(next state, all actions)]}$$

• state： 表示 Agent 当前状态。
• action： 表示 Agent 在当前状态下要做的行为。
• next state： 表示 Agent 在 state 状态下执行了 action 行为后达到的新的状态。
• Q(state, action)： 表示 Agent 在 state 状态下执行了 action 行为后学习到的经验，也就是经验分数。
• R(state, action)： 表示 Agent 在 state 状态下做 action 动作后得到的即时奖励分数。
• Max[Q(next state, all actions)]： 表示 Agent 在 next state 状态下，自我的经验中，最有价值的行为的经验分数。
• Gamma： \(\gamma\) ，表示折损率，也就是未来的经验对当前状态执行 action 的重要程度。

**算法流程:**

Agent 通过经验去学习。Agent将会从一个状态到另一个状态这样去探索，直到它到达目标状态。我们称每一次这样的探索为一个场景（episode）。

每个场景就是 Agent 从起始状态到达目标状态的过程。每次 Agent 到达了目标状态，程序就会进入到下一个场景中。

1. 初始化 Q 矩阵，并将初始值设置成 0

2. 设置好参数 γ 和得分矩阵 R

3. 循环遍历场景（episode）：

   1. 随机初始化一个状态 s

   2. 如果未达到目标状态，则循环执行以下几步：

      1. 在当前状态 s 下，随机选择一个行为 a
      2. 执行行为 a 得到下一个状态 s`
      3. 使用 \(\text{Q(state, action) = R(state, action) +} \gamma\text{ Max[Q(next state, all actions)]}\) 公式计算 \(\text{Q(state, action)}\)
      4. 将当前状态 s 更新为 s`

参考

1. DQN 从入门到放弃
2. 经验回放（Experience replay）
3. 强化学习系列之九:Deep Q Network (DQN)
4. 莫烦 PYTHON 强化学习 Reinforcement Learning