吴恩达机器学习 course3 week3 强化学习
1.1 什么是强化学习
使用强化学习控制遥控直升飞机做特技动作(斯坦福大学) 来源：http://heli.stanford.edu/
“强化学习(reinforcement learning)”已经被应用于直升机控制，可以让其做“倒飞”等各种特技动作(aerobatic maneuvers)，如上图。显然我们不可能使用“有监督学习”来控制直升机，因为整个飞行空间是连续的，标签数据空间会非常庞大进而制造困难大。而“强化学习”的关键思想在于，并不告诉算法对于每个输入的正确输出(事实上也做不到)，而是指定一个“奖励函数(reward function)”，来告诉算法执行的结果如何，“强化学习”算法的工作就是自动找出“最大化奖励”的动作。也就是，在训练时只给出“奖励函数(reward function)”，而不是最佳动作。这可以在设计系统时具有更多的灵活性。比如对于“直升机控制”来说，可以设置奖励为：
- 正向反馈(positive reward)：直升机飞行稳定时，+1分。
- 负向反馈(negative reward)：直升机坠毁，-1000分。
“强化学习”的应用场景有：
- 机器人控制。比如直升机特技飞行、机器狗跨越障碍等。
- 工厂优化。如何安排工厂中流程来最大限度的提升 吞吐量/效率。
- 金融(股票)交易。比如要想在10天内抛售100万手股票，如何效益最大化的完成股票交易。
- 玩游戏。比如挑起、国际象棋、纸牌、电子游戏等等。
尽管“强化学习”不如“有监督学习”应用广泛，目前尚未在商业界取得广泛应用，但也是机器学习算法的“支柱”之一。下面是目前“强化学习”的一些缺点：
- 很多研究成果都是针对模拟环境的，而针对“实际机器人”的“强化学习”要困难的多。
- 应用场景少。相比于“有/无监督学习”，“强化学习”的应用场景很少，目前大多数局限在机器人控制领域。
注：“强化学习”既不是“有监督学习”，也不是“无监督学习”。
1.2 示例：火星探测器
“火星探测器”：找出火星车在每个状态应该执行的最佳动作，直到到达“状态1”或“状态6”。最终目标是最大化奖励
- 状态(state)：假设有6个状态。每个状态可以认为是不同的地点，“状态1”或“状态6”为“任务终点(terminal state)”。下图中火星车的起始位置为“状态4”。
- 动作(action)：每个状态都可以执行“向左”、“向右”两种状态。
- 奖励(reward)：到达“状态1”奖励100、到达“状态6”奖励40、其他状态奖励为0。
- 折扣因子：$\gamma=0.5$
数学符号
下面是这节会用到的一些数学符号，简单看一眼，用到的时候来查就行。
- $s/ \vec s$ : 机器人的当前状态。
- $a/ \vec a$: 机器人在当前状态执行的动作。
- $R(s)$: 机器人在当前状态得到的奖励。
- $s’$: 机器人执行动作 a 后进入的的下一状态。
- $a’$: 机器人在下一状态执行的动作。
- $\gamma$: 0~1之间，奖励的折扣因子(discount factor)。很多算法会定义为0.9左右。
- $\pi(s)=a$: 强化学习的策略，表示在“状态s”下应该执行的“最佳动作a”。
- $p$: 0~1之间，表示机器人执行动作后，没有到达预期状态，反而由于某些随机因素到达相反状态的概率。
- 强化学习四大核心要素：当前状态、动作、奖励、下一状态。
1.3 强化学习的回报
强化学习的“回报(return)”是每一步所获得的 “奖励(reward)”的加权和，权重就是步数幂次的“折扣因子 γ ”，“奖励”显然取决于每一次的“动作(action)”。比如下面从“状态1”不断执行动作，最终到达任务终点“状态n”，回报为：
$$
Return = R_1 + \gamma R_2 + \gamma^2 R_3 +…+ \gamma^n R_n(terminal \ state)
$$
折扣因子 $\gamma $ 越大，表示有“耐心”走向更远的“大奖励”。下图给出了折扣因子对最佳策略(黄色箭头)的影响，可以发现 $\gamma $ 较大时，状态5的最佳策略会是更远处的“大奖励”。
若系统中出现“负奖励”，折扣因子实际上会激励系统将负奖励尽可能推迟到未来，算法会尽可能的推迟该“负奖励”。
1.4 决策：强化学习中的策略
策略 $\pi$ (policy/controler)”是一个“状态”到“动作”的映射函数，表示在“状态$s$”下，为了“最大化回报”所应该执行的“最佳动作$a$”：
$$
\pi(s) =a
$$
上述决策过程被称为“马尔可夫决策过程(Markov Decision Process, MDP)”。“马尔可夫决策过程”是指未来只取决于当前状态，而不取决于任何之前的状态。
1.5 审查关键概念
通过火星探测器的例子，我们了解了强化学习问题的状态、行动、奖励和折扣系数等关键概念，并解释了如何计算回报。同时，我们还探讨了如何将这些概念应用于其他领域，如驾驶自主直升机和下棋等。
【问题1】“火星探测器”：找出火星车在每个状态应该执行的最佳动作，直到到达“状态1”或“状态6”。最终目标是最大化奖励
- 状态(state)：假设有6个状态。每个状态可以认为是不同的地点，“状态1”或“状态6”为“任务终点(terminal state)”。下图中火星车的起始位置为“状态4”。
- 动作(action)：每个状态都可以执行“向左”、“向右”两种状态。
- 奖励(reward)：到达“状态1”奖励100、到达“状态6”奖励40、其他状态奖励为0。
- 折扣因子：$\gamma=0.5$
【问题2】“直升机控制”：根据当前状态自动选择动作，以保证直升机的平稳运行。
- 状态：直升机的空间位置。
- 动作：如何移动直升机遥控上的控制杆。
- 奖励：飞行平稳+1，坠毁-1000。
- 折扣因子：$\gamma=0.99$
【问题3】“国际象棋”【简化描述】：根据棋盘上所有棋子的位置，自动选择最佳的下一步棋。
- 状态：棋盘上所有棋子的位置。
- 动作：可能的移动方式。
- 奖励：赢了+1，胜负未分0，输了-1。
- 折扣因子：$\gamma=0.995$
【问题4】“登月器”：控制登月器成功实现软着陆。
- 3.1 节会介绍
2.1 状态-动作价值函数
整个强化学习最关键的一点就是计算“状态-动作价值函数(state-action value function)”，也称为Q函数、$Q^*$、最优Q函数(optimal Q function)。“状态-动作价值函数”就是在 “当前状态s” 下，执行 “某动作a” 后所能获得的“最大回报”。也就是说，“某动作a”不一定是当前状态的最佳动作，但执行 a之后会一直执行最佳动作($\gamma=0.5$)：
$$
Q(s,a)=max(Return) \ at \ s \ after \ a
$$
显然，在计算出所有状态下所有动作的Q取值后，在每个状态只需选取Q取值较大的“动作”，就是“最佳动作$\pi(s)=a$“，比如上述在“状态4”，因为$Q(4,\leftarrow) > Q(4,\rightarrow)$, 所以在“状态4”应该执行最佳动作 “向左←”,
$$
\textbf{Example 1:} \quad
Q(2, \rightarrow) = R(2) + 0.5 \max_{a’} Q(3, a’) = 0 + 0.5 \cdot 25 = 12.5
$$
$$
\textbf{Example 2:} \quad Q(4, \leftarrow) = R(4) + 0.5 \max_{a’} Q(3, a’) = 0 + 0.5 \cdot 25 = 12.5
$$
2-2 贝尔曼方程
将前几个小节的内容总结一下，就可以给出 Q(s,a) 的计算公式——“贝尔曼方程(Bellman Equation)”，也就是在 状态 s 执行 动作 a 的最大回报=“即时奖励(immediate reward)”+下一状态的最大回报：
- $s$ : 当前状态。
- $a$: 在当前状态执行的动作。
- $R(s)$: 在当前状态得到的奖励。
- $s’$: 执行动作 a 后进入的的下一状态。
- $a’$: 在下一状态执行的动作。
- $\gamma$: 折扣因子(discount factor)。
$$
Bellman \ Equation: \ Q(s,a) = R(s)+ \gamma \max_{a’}Q(s’,a’)
$$
2-3 随机环境(可选)
本节介绍“随机马尔可夫决策过程(Stochastic Markov Decision Processes)”。和前面内容的区别是，实际中机器并不总是可靠，比如命令“火星车”从“状态3”执行“动作向左”，大多数情况都会如预期到达“状态2”，但是也可能因为岩石滑坡、沙暴、车轮打滑等小概率随机事件，导致其到达“状态4”。这种情况下，我们就需要定义“出错概率p ”，来描述到达相反状态的概率。此时，由于整个过程是随机的，我们就不能单纯地追求“最大化回报”，而是要追求“最大化回报的期望”。于是“随机环境”下的“贝尔曼方程”更改为：
$$
(Stochastic) \ Bellman \ Equation : Q(s,a)=R(s)+\gamma E[\max_{a’}Q(s’,a’)]
$$
老师在视频中给出的求解期望的方法时暴力穷举，不断模拟出所有的可能，最后用平均值表示期望。但显然还有更聪明的方法没介绍。下面是在“jupyter notebook”中的仿真，说明了“出错概率”对最佳决策的影响：
较小的“出错概率”不会改变最佳策略。
较大的“出错概率”会使得最佳策略完全相反，相当于反向操作火星车。
随机越接近0.5，火星车的移动越趋于随机(不受控制)。p = 0.5 时不存在最佳策略，因为指定火星车向哪走都一样，可以看到每个状态的Q函数完全相同。
3-1 连续状态空间
很多机器人控制的实际应用都有连续的状态空间。在之前的火星车问题中，我们将问题简化成6个状态，每个状态表示一个地点。但实际上我们想做的是控制火星车在地面上的移动，所以我们应该俯瞰火星车，将地面看成二维坐标，火星车的状态应该包括：位置$[x,y] $(二维坐标)、角度$\theta$、运动速度$[\dot{x},\dot{y}]$(两个方向的速度)、偏转速度$\dot{\theta}$共6个变量：
$$
\vec{s} = [x, y, \theta, \dot{x}, \dot{y}, \dot{\theta}]^T
$$
另外，火星车的移动可以看成是二维平面的运动，而直升机的运动则是在三维空间的运动。于是直升机的状态应该包括：位置$[x,y,z]$ 、姿态信息$[\phi,\theta,\omega]$, 位置变化速度$[\dot{x},\dot{y},\dot{z}]$、姿态变化的角速度$[\dot{\phi},\dot{\theta},\dot{\omega}]$共12个变量：
$$
\vec{s} = [x, y, z, \phi, \theta, \omega, \dot{x}, \dot{y}, \dot{z}, \dot{\phi}, \dot{\theta}, \dot{\omega}]^T
$$
注：“姿态信息”的三维向量分别表示滚动(roll)、俯仰(pitch)、偏航(yaw)的角度，可以唯一确定刚体的姿态。
3.2 登月器
于是我们对“火星车探测”问题进行改进，来使用“登月器”这个二维连续空间问题进行举例。下面是问题介绍：
【问题1】“登月器”：控制登月器的运动，使其成功“立着”降落在两个黄旗之间(如下图)。
状态：是二维平面的小游戏，登月器的状态包括8种变量：$\vec s=[x,y,\dot{x},\dot{y},\theta,\dot{\theta},l,r]^T$
- $[x,y]$:连续取值，表示登月器的二维坐标。
- $\dot{x},\dot{y}$:连续取值，表示登月器在两个方向的速度。
- $\theta$ :连续取值，表示登月器的偏转角度。
- $\dot{\theta}$ : 连续取值，表示登月器的偏转速度。
- $[l,r]$: 二进制取值，分别表示左、右支撑脚是否着地。帮助确认登月器是否为“倒栽葱”或者“躺着”着陆的。
动作：包括四个动作，什么都不做/向左点火/向右点火/向下点火。
- 什么都不做(nothing)，登月器由于重力自然下坠。
- 向左点火(fire left)，点燃左推进器，登月器向右移动。
- 向右点火(fire right)，点燃右推进器，登月器向左移动。
- 向下点火(fire main)，点燃主推进器，减缓登月器的下降速度。
奖励：考虑到整个着陆过程，定义以下7种奖励。前4个都是降落后判定，后3个是降落过程中持续判定
- 【+100~+140】别管是“立着”/“倒栽葱”/“躺着”，只要到达两黄旗之间就给奖励。离中心越近奖励越多。
- 【-100】不管降落在哪里，只要不是“立着”降落，就判定为“坠毁”给惩罚。
- 【+100】不管降落在哪里，只要成功实现“立着”降落(软着陆)就给奖励。
- 【+10】不管降落在哪里，只要有一个支撑腿着地，就+10；两个就+20。
- 【额外奖励】降落过程中，水平方向离两黄旗中心越近就给一点小奖励。
- 【-0.3】为了节省燃料，每点燃一次主推进器(向下点火)，就给一点惩罚。
- 【-0.03】为了节省燃料，每点燃一次左/右推进器，就给一点惩罚。
折扣因子：对于登月器来说，通常会令折扣因子较大, 如$\gamma$ = 0.985
上述奖励函数算是一个“中等复杂”的定义，花时间仔细定义“奖励”是合理的。因为即使看上去有点复杂，也比手动确定每个状态的最佳动作要简单许多。
3-2 DQN算法：拟合Q函数
Q函数对于最佳动作的选择至关重要。对于离散状态空间来说，可以手动计算甚至穷举；但对于连续状态空间来说，Q 函数取值连续且几乎没有显式表达式，于是需要训练神经网络来拟合Q函数.
输入层：12维向量，包括状态向量$\vec s$(长度为9) + 动作向量$\vec a$ (4个动作的独热码)
中间层：不妨定义两个中间层，每个中间层都有64个神经元
输出层：Q函数的输出，也就是在 状态$\vec s$ 下采取 动作$\vec a$ 所能得到的最大回报
注意：神经网络最开始的输出“y”并没有什么意义，只是随机初始化的参数。
那如何得到最开始的训练集呢？答案是利用神经网络的初始化参数。比如在某个时刻 i 可以得到下面所示的“四要素”
$(\vec{s}^{(i)},\vec{a}^{(i)},R(\vec s^{(i)}),\vec{s’}^{(i)})$, 根据“四要素”可以直接得到是神经网络的输入$\vec{x}^{(i)} = (\vec{s}^{(i)},\vec{a}^{(i)})$;而由于神经网络有随机初始化参数，所以可以计算出在下一状态$\vec{s’}^{(i)}$下所有的动作的Q 值，选出最大的Q便可以计算出神经网络的输出$y^{(i)}=R(\vec{s}^{(i)})+\gamma \max_{\vec a’}Q(\vec s’^{(i)},\vec a’ )$。
于是就计算出来单个训练样本 $(\vec x^{(i)},\vec y^{(i)})$。不断重复这个过程(比如10000次)，便可得到大量的训练集：
和前面“有监督学习”的神经网络不同的地方在于，“强化学习”的神经网络迭代更新一次需要使用两次神经网络。一次用于计算训练样本，一次用于更新参数。这个训练过程虽然看起来优点玄学，但能逐渐迭代出理想参数，但显然比“有监督学习”更慢。
DQN具体算法如下：
初始化神经网络参数，作为Q函数的拟合
不断重复
计算“四要素”。采取动作，计算 $(\vec{s}, \vec{a}, R(\vec{s}), \vec{s}’)$， 仅存储最近10000个元组。（Replay Buffer(重放缓存区)）
训练神经网络，迭代设定次数
计算训练集。利用神经网络计算所有训练样本 $\vec{x} = (\vec{s}, \vec{a})$, $y = R(\vec{s}) + \gamma \max_{\vec{a}’} Q(\vec{s}’, \vec{a}’)$
训练神经网络参数。使新的神经网络 $Q_{new} \approx y$
更新神经网络参数，$Q = Q_{new}$
交给神经网络训练的参数y中一部分是随机初始化神经网络生成的，但还有一部分是包含了当前状态的信息的，所以当训练次数增多后，外部的输入信息会逐步冲刷掉初始化的随机信息，给出真正的Q函数估计
虽然一开始Q是随机的，但你的R(s)是自己设置的奖励，随着迭代Q会逐渐准确
3-3 算法改进：改进的神经网络架构
我们使用神经网络来拟合$Q(\vec s,\vec a)$. 但在上一节中，对于每个状态$\vec s$, 我们都需要推理4次来逐个计算所有动作对应的Q值，并挑出最大值。这显然很麻烦，我们可以省略这一重复性的工作，直接令神经网络输出当前状态$\vec s$下所有动作对应的$Q$值 ，此时我们推理1次便可以得到当前状态$\vec s$ 所有的Q值：
按照上面这种结构改进，会使得神经网络更加高效。
3-4 算法改进 $\epsilon$-贪婪策略
在强化学习中，即使算法还在学习阶段，也需要采取行动。最常见的方法是使用epsilon贪婪策略。该策略在处于某个状态时，选择最大化Q的动作，但有时会随机选择一个动作以探索。这种策略被称为epsilon贪婪政策。
$\varepsilon$-贪婪策略(ε- greedy policy)可以避免神经网络永远也不会尝试某个动作。因为神经网络初始化的参数不准确，若在拟合$Q(\vec s,\vec a)$ 时总是直接选取Q值最大的动作，可能会导致某些动作永远也尝试不到(万一是好动作呢)。所以对动作的选取做出改进：
- 【原始方法❌】在每一个状态选取下一个动作时，总是选取当前神经网络输出最大Q值的动作。但由于神经网络一开始的初始化参数不好，可能会导致其永远不会尝试好动作。
- 【ε-贪婪策略✅】每次进行选取动作时(假设ε = 0.05)，以1−ε 的概率选取最大化Q值的动作 (greedy/exploitation)、以 ε 的概率随机选择动作(exploration)。在神经网络初始训练时，可以令ε 较大，随着训练的进行逐步减小，比如从 1.0逐步减小到 0.01 。
上述也就是说，ε-贪婪策略是“贪婪(exploitation)”和“探索(exploration)”之间的折衷，通过偶尔不选取最佳策略为代价，来学习更多的信息。
3-5 算法改进：小批量和软更新（可选）
“小批量(mini-batches)”是一种用于加速神经网络训练的方法，应用该思想也可以加速“线性回归”、“逻辑回归”。假设训练集中有一亿个训练样本，此时计算代价函数时，若直接计算所有样本的均方误差会使得计算量非常庞大。所以对单次迭代过程进行改进：
- 【原始方法❌】计算所有训练样本的均方误差，然后更新一小步。梯度下降方向相对准确，但计算成本非常大。
- 【小批量✅】将一亿个训练样本拆分成1000个为一批(bitch)，然后对每一批，都计算一次均方误差并更新参数。梯度下降的过程相对“混乱”，但也会逐渐趋向代价极小点，并且计算成本大大降低。
“软更新(soft updates)”可以避免神经网络性能突然变差，进而帮助算法更好的收敛。所以对神经网络参数的更新做出改进：
- 【原始方法❌】直接更新。假设新的神经网络碰巧性能更差，那么直接更新会导致神经网络性能突然变差。
- 【软更新✅】比如设置 $Q = 0.1Q_{new}+0.9Q$ ，可以避免“强化学习”的参数振荡或具有其他不良特性。
相比于“有监督学习”，“强化学习”对于参数的选取更加苛刻，这也是为什么“强化学习”还不成熟的原因。比如“有监督学习”中，即使“学习率α ”的选取较小，可能可只是多花三倍时间进行训练；而在“强化学习”中，若“ε ”等参数选取不合适，那可能会多花上10倍甚至100倍时间进行训练。
