强化学习

一、强化学习概述

在这里插入图片描述

1.强化学习简介

强化学习最早可以追溯到早期控制论以及统计、心理学、神经科学、计算机科学等学科的一些研究。在最近的五到十年中，强化学习在机器学习和人工智能研究者中得到了大量的关注，它描绘了一种在不进行具体指导的情况下通过对智能体进行奖励与惩罚而完成任务的编程方式。但是完成这一想法有着巨大的计算困难。

（1）强化学习是机器学习中的一个领域，强调如何基于环境而行动，以取得最大化的预期利益。其灵感来源于心理学中的行为主义理论，即有机体如何在环境给予的奖励或惩罚的刺激下，逐步形成对刺激的预期，产生能获得最大利益的习惯性行为。

（2）强化学习最早可以追溯到巴甫洛夫的条件反射实验，它从动物行为研究和优化控制两个领域独立发展，最终经Bellman之手将其抽象为马尔可夫决策过程 (Markov Decision Process，MDP)

2.发展历程：

1956年Bellman提出了动态规划方法。

1977年Werbos提出只适应动态规划算法。

1988年sutton提出时间差分算法。

1992年Watkins 提出Q-learning 算法。

1994年rummery 提出Saras算法。

1996年Bersekas提出解决随机过程中优化控制的神经动态规划方法。

2006年Kocsis提出了置信上限树算法。

2009年kewis提出反馈控制只适应动态规划算法。

2014年silver提出确定性策略梯度（Policy Gradients）算法。

2015年Google-deepmind 提出Deep-Q-Network算法。

可见，强化学习已经发展了几十年，并不是一门新的技术。在2016年，AlphaGo击败李世石之后，融合了深度学习的强化学习技术大放异彩，成为这两年最火的技术之一。总结来说，强化学习就是一个古老而又时尚的技术。

3.简述强化学习

在人工智能领域中，强化学习是一类特定的机器学习问题。在一个强化学习系统中，决策者可以观察环境，并根据观测做出行动。在行动之后，能够获得奖励。强化学习通过与环境的交互来学习如何最大化奖励。例如，一个走迷宫的机器人在迷宫里游荡（见图1-1）。机器人观察周围的环境，并且根据观测来决定如何移动。错误的移动会让机器人浪费宝贵的时间和能量，正确的移动会让机器人成功走出迷宫。在这个例子中，机器人的移动就是它根据观测而采取的行动，浪费的时间能量和走出迷宫的成功就是给机器人的奖励（时间能量的浪费可以看作负奖励）。

强化学习的最大特点是在学习过程中没有正确答案，而是通过奖励信号来学习。在机器人走迷宫的例子中，机器人不会知道每次移动是否正确，只能通过花费的时间能量以及是否走出迷宫来判断移动的合理性。
在强化学习中，有两个可以进行交互的对象：智能体和环境。（注意：强化学习问题不一定要借助智能体/环境接口来研究，本文只讨论智能体/环境接口的情况。）

3.1定义各变量

智能体（agent）可以感知外界环境的状态（state）和反馈的奖励（reward），并进行学习和决策。智能体的决策功能是指根据外界环境的状态来做出不同的动作（action），而学习功能是指根据外界环境的奖励来调整策略。一个强化学习系统里可以有一个或多个智能体。我们并不需要对智能体本身进行建模，只需要了解它在不同环境下可以做出的动作，并接受奖励信号。
环境（environment）是智能体外部的所有事物，智能体在环境中执行动作后都会使得自己处于不同的状态，并接受环境反馈的奖励。环境本身可以是确定性的，也可以是不确定性的。环境可能是已知的，也可能是未知的。
在强化学习中的基本要素包括：
状态（state）s：来自于状态空间S，为智能体所处的状态，一个不断变化的量，可以是离散的或连续的。
动作a(action)，来自动作空间A，是对智能体行为的描述，可以是离散的或连续的。
状态转移概率p(s′|s,a)是在智能体根据当前状态s做出一个动作a之后，环境在下一个时刻转变为状态s′的概率；
即时奖励r(s,a,s′)是一个标量函数，即智能体根据当前状态s做出动作a 之后，环境会反馈给智能体一个奖励，这个奖励也经常和下一个时刻的状态s′有关。
策略智能体的策略（policy）就是智能体如何根据环境状态s来决定下一步的动作a，通常可以分为确定性策略（Deterministic Policy）和随机性策略（StochasticPolicy）两组。
确定性策略是从状态空间到动作空间的映射函数π : S → A。随机性策略表示在给定环境状态时，智能体选择某个动作的概率分布
在这里插入图片描述

3.2马尔科夫决策

延迟奖励问题可以用马尔可夫决策过程（Markov decision process，MDPs）来建模。一个马尔可夫决策过程包含：
（1）状态集合 $S$ ;
（2）动作集合 $A$ ;
（3）奖励函数 $R ： S \times A \to R$
（4）状态转移函数 $T : S \times A \to Π （ S)$ 作映射为概率。用 $T (s, a, s^{'})$ 表示在状态 $s$ 采取动作 $a$ 后，进入状态 $s^{'}$ 的概率。

状态转移函数说明下一个状态是当前状态和所采取的动作的函数。奖励函数说明期望的及时奖励是当前状态的函数。模型具有马尔可夫性，也就是说，下一个状态只与当前的状态和动作有关，与之前的都无关（一阶马尔可夫），可以参考Bellman（1957），Bertsekas（1987），Howard（1960），Puterman（1994）。

详述请见：马尔可夫决策过程（MDP）

3.3 WHY RL?

强化学习与监督学习在很多方面有着不同的地方。最重要的一点就是没有“输入-输出”这样的成对数据。取而代之的是，智能体采取某个动作后，会立马得到一个奖励，而且并不知道哪个动作从长远角度来说可以获得更多的奖励总和。因此智能体很有必要汇聚系统所有的状态、动作、转移概率、奖励进而取得最优的表现。另一个区别于监督学习的的重要方面是，在线学习效果很重要，因为强化学习中评估和学习经常是交替进行的。

强化学习的一些方面与人工智能（AI）中的搜索和规划问题比较相近。AI算法通过图和状态产生一条满足要求的轨迹。规划问题的方法与之类似，但是规划问题中的约束（原文为construct，应为constriction更为合理）比图更为复杂，通常是一些逻辑表达而不是一些基本的符号。相比强化学习模型，上述AI算法不是那么通用，因为它们需要事先定义好的转移概率模型和确定的期望假设。另一方面，强化学习认为整个状态空间是可以穷举并在内存中存储的——这使得它不会受到传统的一些方法束缚。（这篇文章是1996年发表的，现在的的深度Q学习就是用深度网络来拟合Q函数，应对状态无限的情况）

强化学习 (Reinforcement Learning) 是一个机器学习大家族中的分支, 由于近些年来的技术突破, 和深度学习 (Deep Learning) 的整合, 使得强化学习有了进一步的运用。比如让计算机学着玩游戏, AlphaGo 挑战世界围棋高手, 都是强化学习在行的事。强化学习也是让你的程序从对当前环境完全陌生, 成长为一个在环境中游刃有余的高手。

深度强化学习全称是 Deep Reinforcement Learning（DRL），其所带来的推理能力是智能的一个关键特征衡量，真正的让机器有了自我学习、自我思考的能力。

深度强化学习(Deep Reinforcement Learning，DRL)本质上属于采用神经网络作为值函数估计器的一类方法，其主要优势在于它能够利用深度神经网络对状态特征进行自动抽取，避免了人工定义状态特征带来的不准确性，使得Agent能够在更原始的状态上进行学习。

二：强化学习分类与算法

1.根据强化学习的任务和环境，可以将强化学习任务作以下分类

单智能体任务（single agent task）和多智能体任务（multi-agent task）：顾名思义，根据系统中的智能体数量，可以将任务划分为单智能体任务和多智能体任务。单智能体任务中只有一个决策者，它能得到所有可以观察到的观测，并能感知全局的奖励值；多智能体任务中有多个决策者，它们只能知道自己的观测，感受到环境给它的奖励。当然，在有需要的情况下，多个智能体间可以交换信息。在多智能体任务中，不同智能体奖励函数的不同会导致它们有不同的学习目标（甚至是互相对抗的）。在本书没有特别说明的情况下，一般都是指单智能体任务。

回合制任务（episodic task）和连续性任务（sequential task）：对于回合制任务，可以有明确的开始状态和结束状态。例如在下围棋的时候，刚开始棋盘空空如也，最后棋盘都摆满了，一局棋就可以看作是一个回合。下一个回合开始时，一切重新开始。也有一些问题没有明确的开始和结束，比如机房的资源调度。机房从启用起就要不间断地处理各种信息，没有明确的结束又重新开始的时间点。

离散时间环境（discrete time environment）和连续时间环境（continuoustime environment）：如果智能体和环境的交互是分步进行的，那么就是离散时间环境。如果智能体和环境的交互是在连续的时间中进行的，那么就是连续时间环境。

离散动作空间（discrete action space）和连续动作空间（continuousaction space）：这是根据决策者可以做出的动作数量来划分的。如果决策得到的动作数量是有限的，则为离散动作空间，否则为连续动作空间。例如，走迷宫机器人如果只有东南西北这4种移动方式，则其为离散动作空间；如果机器人向360°中的任意角度都可以移动，则为连续动作空间。

确定性环境任务（deterministic environment）和非确定性环境（stochastic environment）：按照环境是否具有随机性，可以将强化学习的环境分为确定性环境和非确定性环境。例如，对于机器人走固定的某个迷宫的问题，只要机器人确定了移动方案，那么结果就总是一成不变的。这样的环境就是确定性的。但是，如果迷宫会时刻随机变化，那么机器人面对的环境就是非确定性的。

完全可观测环境（fully observable environment）和非完全可观测环境（partially observable environment）：如果智能体可以观测到环境的全部知识，则环境是完全可观测的；如果智能体只能观测到环境的部分知识，则环境是非完全可观测的。例如，围棋问题就可以看作是一个完全可观测的环境，因为我们可以看到棋盘的所有内容，并且假设对手总是用最优方法执行；扑克则不是完全可观测的，因为我们不知道对手手里有哪些牌。

2.从算法角度，可以对强化学习算法作以下分类

同策学习（on policy）和异策学习（off policy）：同策学习是边决策边学习，学习者同时也是决策者。异策学习则是通过之前的历史（可以是自己的历史也可以是别人的历史）进行学习，学习者和决策者不需要相同。在异策学习的过程中，学习者并不一定要知道当时的决策。例如，围棋AI可以边对弈边学习，这就算同策学习；围棋AI也可以通过阅读人类的对弈历史来学习，这就算异策学习。

有模型学习（model-based）和无模型学习（model free）：在学习的过程中，如果用到了环境的数学模型，则是有模型学习；如果没有用到环境的数学模型，则是无模型学习。对于有模型学习，可能在学习前环境的模型就已经明确，也可能环境的模型也是通过学习来获得。例如，对于某个围棋AI，它在下棋的时候可以在完全了解游戏规则的基础上虚拟出另外一个棋盘并在虚拟棋盘上试下，通过试下来学习。这就是有模型学习。与之相对，无模型学习不需要关于环境的信息，不需要搭建假的环境模型，所有经验都是通过与真实环境交互得到。

回合更新（Monte Carlo update）和时序差分更新（temporal differenceupdate）：回合制更新是在回合结束后利用整个回合的信息进行更新学习；而时序差分更新不需要等回合结束，可以综合利用现有的信息和现有的估计进行更新学习。

基于价值（value based）和基于策略（policy based）：基于价值的强化学习定义了状态或动作的价值函数，来表示到达某种状态或执行某种动作后可以得到的回报。基于价值的强化学习倾向于选择价值最大的状态或动作；基于策略的强化学习算法不需要定义价值函数，它可以为动作分配概率分布，按照概率分布来执行动作。

深度强化学习：在强化学习中，一般需要建模策略π(a|s)和值函数V π(s),Qπ(s,a)。早期的强化学习算法主要关注于状态和动作都是离散且有限的问题，可以使用表格来记录这些概率。但在很多实际问题中，有些任务的状态和动作的数量非常多。比如围棋的棋局有 $3^{361}≈10^{170}$ 种状态，动作（即落子位置）数量为361。还有些任务的状态和动作是连续的。比如在自动驾驶中，智能体感知到的环境状态是各种传统器数据，一般都是连续的。动作是操作方向盘的方向（−90∼90度）和速度控制（0∼300公里/小时），也是连续的。为了有效地解决这些问题，可以一个复杂的函数（比如深度神经网络）来使得智能体可以感知更复杂的环境状态以及建立更复杂的策略，提高强化学习算法的能力，并提高泛化能力。深度强化学习（deep reinforcement learning）是将强化学习和深度学习结合在一起，用强化学习来定义问题和优化目标，用深度学习来解决策略和值函数。的建模问题，然后使用误差反向传播算法来优化目标函数。深度强化学习在一定程度上具备解决复杂问题的通用智能，并在很多任务上都取得了很大的成功。

3.具体算法

具体讲一下时间差分法(TD)，Deep-Q-Net(DQN),DDPG这三种算法。

3.1时间差分算法（TD）

动态规划法：
需要一个完全已知的环境，需要状态之间的转换概率，并且V(S)状态值函数的估计是自举的(bootstrapping)，即当前状态值函数的更新依赖于已知的其他状态值函数，也就是使用bellman方程求解值函数。

$V(s)←E_Π[R_{t+1}+γV(s')]$

蒙特卡罗法：
动态规划方法，是一种较为理想的状态，即所有的参数都提前知道，比如状态转移概率，及奖励等等。然而显示情况是未知的，这时候有一种手段是采用蒙特卡洛采样，基于大数定律，基于统计计算出转移概率值；比如当你抛硬币的次数足够多，那么正面和反面的概率将会越来越接近真实情况。

$V(s)←V(s)+α(G_t-V(s))$

所以可以看出使用蒙特卡罗法需要回合结束才能更新，时间差分方法结合了蒙特卡罗的采样方法和动态规划方法的bootstrapping(利用后继状态的值函数估计当前值函数)使得他可以适用于model-free的算法并且是单步更新，速度更快。结合以上两者的优势就得到了TD算法

$V(s)←V(s)+α(R_{t+1}+γV(s')-V(s))$

其中 $R_{t+1}+γV(s')$ 被称为TD目标,$ δ_t = R_{t+1}+γV(s’)-V(s)$称为TD偏差。

我们可以发现其实就是把蒙特卡罗法中估计的 $G_t$ 替换成了TD目标，因为TD目标使用了bootstrapping方法估计当前值函数，所以这样就结合了动态规划的优点避免了回合更新的尴尬。
借鉴一下

3.2DQN

深度学习与强化学习结合有如下问题：

DL是监督学习需要学习训练集，强化学习不需要训练集只通过环境进行返回奖励值reward，同时也存在着噪声和延迟的问题，所以存在很多状态state的reward值都是0也就是样本稀疏
DL每个样本之间互相独立，而RL当前状态的状态值是依赖后面的状态返回值的。
当我们使用非线性网络来表示值函数的时候可能出现不稳定的问题

DQN中的两大利器解决了以上问题

通过Q-Learning使用reward来构造标签
通过experience replay（经验池）的方法来解决相关性及非静态分布问题
使用一个MainNet产生当前Q值，使用另外一个Target产生Target Q

首先来看Q-learning算法：QLearning是强化学习算法中value-based的算法，Q即为Q（s,a）就是在某一时刻的 s 状态下(s∈S)，采取动作a (a∈A)动作能够获得收益的期望，环境会根据agent的动作反馈相应的回报reward r，所以算法的主要思想就是将State与Action构建成一张Q-table来存储Q值，然后根据Q值来选取能够获得最大的收益的动作。
experience replay 经验池
经验池DQN中的记忆库用来学习之前的经历，又因为Q learning 是一种 off-policy 离线学习法, 它能学习当前经历着的, 也能学习过去经历过的, 甚至是学习别人的经历，所以在学习过程中随机的加入之前的经验会让神经网络更有效率。
所以经验池解决了相关性及非静态分布问题。他通过在每个timestep下agent与环境交互得到的转移样本 $s_t,a_t,r_t,s_{t+1}$ 储存到回放记忆网络，要训练时就随机拿出一些（minibatch）来训练因此打乱其中的相关性。

Q-target 目标网络
Q-targets的作用其实也是一种打乱相关性的机制，使用Q-targets会使得DQN中出现两个结构完全相同但是参数却不同的网络，预测Q估计的的网络MainNet使用的是最新的参数，而预测Q现实的神经网络TargetNet参数使用的却是很久之前的， $Q ( s , a ; θ_i)$ 表示当前网络MainNet的输出，用来评估当前状态动作对的值函数； $Q ( s , a ; θ _i)$ 表示TargetNet的输出，可以解出targetQ并根据LossFunction更新MainNet的参数，每经过一定次数的迭代，将MainNet的参数复制给TargetNet。
引入TargetNet后，再一段时间里目标Q值使保持不变的，一定程度降低了当前Q值和目标Q值的相关性，提高了算法稳定性。

算法流程

DQN的更新方式和Qlearning一样，

$Q(s,a)←Q(s,a) + α[r+γmax_{a'}Q(s',a')-Q(s,a)]$

DQN的损失函数如下 θ表示网络参数为均方误差损失

$L(θ）= E[(TargetQ-Q(s,a;θ))^2]$

$TargetQ = r + γmax_{a'}Q(s',a';θ)$

这里写图片描述

DQN中存在两个结构完全相同但是参数却不同的网络，预测Q估计的网络MainNet使用的是最新的参数，而预测Q现实的神经网络TargetNet参数使用的却是很久之前的， $Q ( s , a ; θ _i)$ 表示当前网络MainNet的输出，用来评估当前状态动作对的值函数； $Q ( s , a ; θ_i^-)$ 表示TargetNet的输出，可以解出targetQ，因此当agent对环境采取动作a时就可以根据上述公式计算出Q并根据LossFunction更新MainNet的参数，每经过一定次数的迭代，将MainNet的参数复制给TargetNet。这样就完成了一次学习过程。

3.3DDPG

因为Actor-Critic收敛慢的问题所以Deepmind 提出了 Actor Critic 升级版 Deep Deterministic Policy Gradient，后者融合了 DQN 的优势, 解决了收敛难的问题。

Deep：首先Deep我们都知道，就是更深层次的网络结构，我们之前在DQN中使用两个网络与经验池的结构，在DDPG中就应用了这种思想。
PolicyGradient：顾名思义就是策略梯度算法，能够在连续的动作空间根据所学习到的策略（动作分布）随机筛选动作
Deterministic : 它的作用就是用来帮助Policy Gradient不让他随机选择，只输出一个动作值

随机性策略， $\sum π (a ∣ s) = 1$ 策略输出的是动作的概率，使用正态分布对动作进行采样选择，即每个动作都有概率被选到；优点，将探索和改进集成到一个策略中；缺点，需要大量训练数据。
确定性策略， $π (s) S \to A$ 策略输出即是动作；优点，需要采样的数据少，算法效率高；缺点，无法探索环境。然而因为我们引用了DQN的结构利用offPolicy采样，这样就解决了无法探索环境的问题

从DDPG网络整体上来说：他应用了 Actor-Critic 形式的, 所以也具备策略 Policy 的神经网络和基于价值 Value 的神经网络，因为引入了DQN的思想，每种神经网络我们都需要再细分为两个, Policy Gradient 这边，我们有估计网络和现实网络，估计网络用来输出实时的动作, 供 actor 在现实中实行，而现实网络则是用来更新价值网络系统的。再看另一侧价值网络, 我们也有现实网络和估计网络, 他们都在输出这个状态的价值, 而输入端却有不同, 状态现实网络这边会拿着从动作现实网络来的动作加上状态的观测值加以分析，而状态估计网络则是拿着当时 Actor 施加的动作当做输入。

DDPG 在连续动作空间的任务中效果优于DQN而且收敛速度更快，但是不适用于随机环境问题。

伪代码：

在这里插入图片描述

首先是定义actor和critic的这两个网络结构并初始化网络中的参数（网络模型均一致），之后定义经验池的存放和采样过程（ER buffer），最后是将完整的DDPG算法过程放到一个大的类中（面向对象的定义方法比较方便）。在伪代码中最需要关注的就是这两种网络分别是怎么更新参数的。对于actor网络来说，它的更新方法是基于梯度上升的。该网络的损失函数就是从critic网络中获取的Q值的平均值，在实现的过程中，需要加入负号，即最小化损失函数，来与深度学习框架保持一致。用数学公式表示其损失函数就是：

$J(θ^μ) = E[Q(s,a|θ^Q)|_{s=st,a= μ(st|θ^μ)}]$

至于Policy Gradient可以看一下

3.4这几种算法的区别

Q-learning、DQN：学习奖惩值, 根据自己认为的高价值选行为。

Policy Gradients：不通过分析奖励值, 直接输出行为的方法。

Policy Gradients：直接输出动作的最大好处就是, 它能在一个连续区间内挑选动作, 而基于值的, 比如 Q-learning, 它如果在无穷多的动作中计算价值, 从而选择行为, 这, 它可吃不消.

Actor-critic :结合了 Policy Gradient (Actor) 和 Function Approximation (Critic) 的方法. Actor 基于概率选行为, Critic 基于 Actor 的行为评判行为的得分, Actor 根据 Critic 的评分修改选行为的概率.Policy gradient是回合后进行奖惩计算，前期没有值函数，需要后向推算；Actor-critic多了一个critic方法，可以用来每一步进行一个好坏判断；Actor Critic 方法的劣势: 取决于Critic的价值判断, 但是 Critic 难收敛, 再加上Actor 的更新, 就更难收敛. 为了解决收敛问题, Google Deepmind 提出了Actor Critic 升级版 Deep Deterministic Policy Gradient. 后者融合了 DQN 的优势, 解决了收敛难的问题.