这是arxiv上最新发表的一篇前沿交叉综述报告。主要讨论了如何使用深度强化学习方法解决智能交通系统问题,特别是智能信号灯控制问题。本公众号将分4次发布本综述报告的翻译,仅供大家参考学习。
系列预告
随着城市化进程的加快和自动技术的最新发展,交通研究逐渐向智能化方向发展,称为智能交通系统(ITS)。人工智能(AI)试图用最少的人工干预来控制系统。智能交通系统与人工智能的结合为21世纪的交通研究提供了有效的解决方案。ITS 的主要目标是为参与者提供安全、有效和可靠的交通系统。为此,优化交通信号控制(TSC)、自动车辆控制、交通流控制等是研究的重点。
未来的交通系统预计将包括完全自动,如自动交通管理和自动驾驶。即使是现在,半自动驾驶汽车也占据了道路,而且在不久的将来,自动水平可能会提高。政府希望在这方面拥有自动权的原因有很多,例如为司机节省时间,为环境节约能源,以及为所有参与者提供安全保障。通过使用自动控制系统,可以更有效地控制协调和连接的交通系统,可以节省出行时间。当车辆在交通上花费更多时间时,油耗会增加,这会对环境和经济产生影响。人类干预被尽量减少的另一个原因是人类行为的不可预测性。预计自动驾驶将减少交通事故,提高交通运输质量。基于上述原因,智能交通系统对自动控制的各个方面都有很高的要求。一种流行的方法是使用基于经验的学习模型,类似于人类的学习。
城市地区人口的增长导致了交通量的增加,2018年,平均一个美国司机每年的拥堵代价为 97 小时和1348美元[1]。因此,利用自适应模块控制交通信号灯是智能交通系统(ITS)的一个研究热点。通过交通信号设计一个自适应的交通管理系统是减少交通拥挤的有效途径。优化红绿灯的最佳方法对研究人员来说仍然是一个悬而未决的问题,但是一个有希望的优化 TSC 的方法是使用基于学习的人工智能技术。
机器学习的模式主要有三种。有监督学习根据训练中提供的输出标签做出决策。无监督学习基于模式发现,不需要预先知道输出标签。第三种机器学习范式是强化学习(RL),它以马尔可夫决策过程(MDP)为基础,以奖励或惩罚为准则,采取序列化的行动。RL 与深度学习相结合,被称为 deep RL,是目前控制系统中最先进的学习框架。RL 可以解决复杂的控制问题,而深度学习有助于从复杂的数据集中逼近高度非线性函数。
近年来,针对不同的应用领域,提出了许多基于深度 RL 的求解方法。基于 RL 的控制机制在交通管理系统和自动驾驶应用中的应用越来越受到人们的关注。综述与 deep RL 相关的所有数据驱动的 ITS 研究,并在一篇论文中讨论这些应用,是为 ITS 研究人员提供关于 deep RL 的信息,以及 deep RL 研究人员提供关于 ITS 的信息。
本文综述了针对智能交通系统提出的 deep RL 应用,主要是针对 交通信号灯控制的 deep RL 应用。讨论了不同于文献中的的 RL 方法。基于传统 RL 技术的 TSC 解决方案在 deep RL 发明之前就已经被研究过。因此,对于智能交通系统,传统的 RL 方法对于启发我们提出 deep RL 的方法也至关重要,特别是智能信号灯控制。由于交通断面模型主要是连通的和分布式的,因此多智能体动态控制技术在基于RL的 ITS 应用中起着关键的作用。
Deep RL 是最成功的人工智能模型之一,也是最接近人类学习模式的机器学习范式。它结合了深层神经网络和强化学习,使得函数逼近更为有效和稳定,特别是对于高维和无限状态问题。本节介绍了传统 RL 的理论背景以及在 ITS 应用中实现的主要深度 RL 算法。
强化学习是一种通用的学习工具。在强化学习中,智能体与环境进行交互,在没有任何先验知识的情况下,通过最大化一个数值定义的奖励(或者最小化惩罚)来学习如何在环境中表现。在每一个时间步 t
采取一个行动后, RL 智能体会从环境中得到一个度量其行动效果的反馈。根据这个反馈(奖励或惩罚),智能体迭代地更新其行动策略直到达到最优控制策略。
RL 从环境的经验中学习,利用的是一种与人类学习类似的不断试错反复尝试(trial-and-error)的学习模式[11]。RL 中基本的探索利用权衡在新的行动和已有行动之间建立平衡。从计算的视角,RL 利用一种数据驱动的方法迭代的计算近似方案来逼近最优控制策略。因此,它也被称为近似动态规划(approximate dynamic programming)[11],是动态规划(DP)中的一类序列优化问题。
在一般的 RL 模型中,智能体由一个算法控制,在每一个时间步 t 观察到系统状态 s_t ,采取行动 a_t 后,从系统/环境得到奖励 r_t 。在当前策略 \pi 下采取行动后,系统转移到下一个状态 s_{t+1} 。每一次交互后,RL 智能体更新它拥有的环境的知识。图1显示了强化学习过程的示意图。
图1 强化学习的控制环路
强化学习方法可以形式化为马尔可夫决策过程(MDP),MDP 是序列决策算法的一般数学框架。MDP 可以表示成一下五元组:
基本的马尔科夫性质告诉我们,给定当前的状态 s_t ,系统的下一个状态 s_{t+1} 与之前的状态 (s_0,s_1,\dots,s_{t-1}) 独立。在交通系统等控制系统中,MDP 模型通常是回合制(episodic)的,系统在每一回合有一个明确的终止点,基于终止时间 T 或终止状态 s_T 。MDP 智能体的目标是寻找最佳策略 \pi^* ,最大化累计奖励期望 \mathbb{E}(R_t|s,\pi) ,其中累计折扣奖励为
折扣因子 \gamma 反映的是未来奖励的重要性。选择大的 \gamma 代表智能体的行动对未来奖励有较大依赖性。小的 \gamma 则代表智能体的行动更关心实时的奖励r_t 。
通常,RL 智能体表现为两种形式:(i) 已知或者学习状态 s_t 到 s_{t+1} 的转移概率 \mathcal{T} ,称为基于模型的强化学习;(ii) 通过探索环境而不直接学习转移模型,称为无模型强化学习。无模型的强化学习算法可以进一步分为两种类型:基于价值的方法和基于策略的方法。在基于价值的强化学习中,智能体的每一步迭代更新将状态行动对映射为一个值的价值函数。在基于策略的方法中,策略在每一步迭代中直接通过策略梯度来更新[11]。下面我们详细地介绍基于价值和基于策略的强化学习方法。
价值函数决定了智能体处于某一个状态的好坏。在某个策略 \pi 下智能体处于状态 s 时的价值(即期望奖励)为
最优价值函数 V^*(s) 描述了在所有的策略中价值函数的最大值,即
考虑行动的影响,状态行动价值函数,也称为质量函数(Q函数),通常用来反映一个状态行动对的期望奖励
最优行动价值函数的计算方法与最优状态价值函数蕾西,通过在每一个状态下,最大化期望奖励来实现。最优状态值函数和最优行动值函数的关系为
Q函数 Q^*(s,a) 通过选择最大化Q值的行动,能够得到最优策略 \pi^* :
基于以上定义,有两种主要的基于价值的强化学习算法:Q-learning[12] 和 SARSA[13],分别为 on-policy 和 off-policy 强化学习算法。在这两个算法中,状态行动对的价值(Q值)都以Q表的形式存储,通过利用贝尔曼方程的递归本质和马尔可夫性质来学习:
在实践中,通常使用一个学习率 \alpha 来优化价值函数的估计:
其中 y_t 是 Q^\pi(s_t,a_t) 的时间差分目标值(TD target)。TD 步数大小是一个待确定的参数,决定了在计算新的对 Q^\pi(s_t,a_t) 的实时估计 y_t 时使用多少经验步数。假设 TD 步数为 n ,则奖励 R^{(n)}_t =\sum_{i=0}^n \gamma^i r_{t+i} 和 n 步以后的Q值 Q^\pi(s_{t+n,} a_{t+n}) 确定了 y_t 。现在可以很明确地看到 Q-learning 和 SARSA 在这个过程中的不同。Q-learning 是一个 off-policy 模型,行动是通过最大化 Q 值来获得的。而 SARSA 是一个 on-policy 模型,智能体的行动是通过从 Q 函数中得到的策略来更新的。
Q-learning 算法使用贪心算法来更新其Q值,SARSA 算法使用同样的策略来更新Q值和采取行动。为了鼓励探索,Q-learning 算法和 SARSA 算法都使用 \epsilon -贪心策略来采取行动。在 \epsilon -贪心策略中,以 \epsilon 的概率随机选取行动,以 1 - \epsilon 的概率根据 Q 表来选取最优行动.
在 Q-learning 和 SARSA 中,最大的时间差分步数,通常记为 n=\infty 代表回合的结束,对应一种完全经验技术称为 蒙特卡洛 RL。在蒙特卡洛 RL 中,每一个回合只在回合的结束时更新一次 Q 值。\text{TD}(\lambda) 技术则进一步推广了 TD 学习,它用一个衰减系数 \lambda 对回合中所有步数的目标值进行平均[11]。
基于策略的 RL 将策略 \pi_{\theta} 当作是状态行动对上的分布,其中 \theta 为参数。策略参数 \theta 通过最大化某个目标函数 J(\theta) (例如期望奖励 \mathbb{E}_{\pi_{\theta}}[r_t|\theta] = \mathbb{E}_{\pi_{\theta}}[Q^{\pi_{\theta}}(s_t,a_t)|\theta] )来进行更新。基于策略的方法在具有无限维动作空间或高维问题的连续控制问题上的性能通常优于基于值的方法,因为策略不需要在一个大的连续空间中探索所有状态并将它们存储在表中。尽管有一些有效的无梯度方法用于优化非 RL 方法中的策略[14],但是基于梯度的方法在所有类型的 RL 算法中都更有用。
这里我们简要地讨论基于策略梯度的强化学习算法,它们通过目标函数 J(\theta) 对于参数 \theta 的梯度(称为策略梯度)来选择行动。在著名的策略梯度算法 REINFORCE 中[15],目标函数是期望奖励,使用对数技巧 \nabla \log \pi_\theta = \frac{\nabla \pi_\theta}{\pi_\theta} 后,策略梯度可以写成
由于直接计算全梯度不高效,REINFORCE 使用随机梯度下降技术来对梯度近似近似。它使用时间 t 下的奖励 R_t 来作为 Q^{\pi_{\theta}}(s_t,a_t) 的估计,在每一步蒙特卡洛迭代中执行以下更新:
其中 \alpha 为学习率。\theta 在 \nabla_\theta \log \pi_\theta 方向上以权重 R_t 进行更新,即如果近似的策略梯度对应一个高的奖励 R_t , 则更新参数时,梯度方向是加强(reinforced)的。
蒙特卡洛策略梯度的一个问题是其高方差。为了在策略梯度估计中较小方差,Actor-Critic 算法使用状态价值函数V^{\pi_\theta(s)} 作为一个基准(baseline)。在策略梯度中,使用优势函数A^{\pi_\theta}(s,a)=Q^{\pi_{\theta}}(s,a) - V^{\pi_\theta}(s') 代替 Q^{\pi_{\theta}}(s,a) :
优势函数是正负决定了更新的方向:朝着比平均值高/低的奖励相同/相反的方向前进。我们将在讨论深度强化学习时进一步讨论 Actor-Critic 算法。
现实世界中的许多问题都需要多个智能体之间的交互来最大化学习性能。多智能体学习是一项具有挑战性的任务,因为每个智能体都应该考虑其他智能体的行为,以达到全局最优解。增加智能体的数量也会增加状态和行动的维度,因此智能体之间的任务分解是大型控制系统可扩展的方法。
多智能体 RL 中高维系统(状态和行动)存在两个主要问题:智能体的稳定性和对环境的适应性[17]。当各智能体在不考虑近邻智能体的情况下对其行动进行优化时,整个系统的最优学习将变得非平稳。在多智能体 RL 系统中,有几种方法可以解决这个问题,如分布式学习、合作学习和竞争学习[17]。
在高维的状态空间,传统的 RL 算法不能有效地为每一个状态计算价值函数和策略函数。虽然在 RL 中有一些线性函数逼近的方法被提出来解决大的状态空间问题,它们的能力还是有限。在高维和复杂系统中,传统的 RL 方法无法学习环境的有信息的特征来进行高效的函数逼近。然而,这个问题可以使用基于深度学习的逼近器很容易地解决。可以训练一个深层神经网络来学习最优策略或价值函数。在大的状态空间,不同的神经网络结构,例如卷积神经网络(CNN)和循环神经网络(RNN)都被用来训练强化学习算法[18]。
深度学习的主要思想是从数据中提取有用的模式。深度学习模型是从人类神经系统的多层结构中获得启发。如今,深度学习在计算机视觉、语音识别、自然语言处理和强化学习等诸多领域得到了广泛的应用。
基于价值的 RL 算法通过填充 Q 表来学习 Q 函数,对于状态空间很大和连续行动问题,逐个访问所有的状态和行动的方法非常低效。一个主要的解决这一问题的方法为深度 Q 网络(DQN),即通过深层神经网络来近似 Q 函数。最初的 DQN 将原始图片输入当作状态,从中使用卷积神经网络估计 Q 值。将神经网络的参数记为 \theta ,则 Q 函数的近似为 Q(s,a;\theta) 。神经网络的输出为根据公式(6)从一个离散的近似行动值中选取的最优行动。
文献[19]的主要贡献是提出了两种新颖的技术稳定深层神经网络中的学习:目标网络和经验回放。最初的 DQN 算法在一系列经典的 Atari 视频游戏上超过了人类的水平。完整的包含经验回放和目标网络的 DQN 算法见算法1。
目标网络:DQN 中稳定学习的主要方法是目标网络。DQN 中包含两个单独的神经网络:近似 Q 函数的主网络和给出 TD 目标值以更新主网络的目标网络。在训练阶段,在每一个行动后更新主网络的参数 \theta ,而目标网络的参数 \theta 则经过一个固定的时间段后再更新。不再每一次迭代更新目标网络是为了调整主网络的更新以保持价值函数可控。如果两个网络同时更新,由于目标网络的反馈回路,主网的变化会被放大,导致网络不稳定。与公式(9)类似,1步时间差分目标 y_t 为:
其中 Q^\pi (s_{t+1}, a_{t+1};\theta_{t}^{-}) 为目标网络。
经验回放:DQN 提出了另外一种不同的特性叫做经验回放(experience replay),在回放存储中存放最近的经验 (s_t,a_t,r_t,s_{t+1}) 。训练神经网络时从回放存储中均匀地采样样本。在 DQN 中使用经验回放主要有两个原因。首先,由于 RL 智能体在连续的样本中容易产生时间相关性,因此通过随机抽样防止智能体陷入最近的轨迹。其次,DQN 可以通过在小批量样本中训练来代替在全部观察中训练,来提高训练效率。在固定大小存储的经验回放中,只存储最近的 M 个样本,更早的样本会用新的样本来取代。同样的技术在其他深度强化学习算法中也被使用[20,21]。
优先经验回放:经验回放从存储中均匀采样,然而对于学习来说,有些样本比其他样本更重要。一种新的方法对于重要的行动给予优先,从而在 DQN 算法中改变了采样的分布[22]。优先经验回放的总体思想是采用比例优先或者排序优先的方法来使 TD 误差 y^{DQN}_{t} - Q^\pi (s_{t}, a_{t};\theta_{t}^{-}) 大的样本采样到的概率会更大。经验样本根据设置的概率来进行采样。
DQN 是传统的 Q-learning 算法的改进版本。由于都只有一个 Q 函数估计器,DQN 和 Q-learning 都会高估某些行动。文献[23]的作者提出使用双网络,用一个主网络进行行动选择,用一个目标网络来对行动进行评价。使用和传统的表格 double Q-learning 算法相同的损失最小化方法[24]。Double DQN 使用主网络来选择行动,目标网络来评价行动,而不是使用目标网络来选择 Q 值(参考公式(14))。为了更好地估计Q值,行动选择与目标网络解耦:
DQN 的另一个改进是每一个行动使用一个竞争网络架构来估计状态价值函数 V^\pi(s) 和使用优势函数 A^\pi(s,a) [25]。这两个网络组合的输出是通过聚合层的离散行动集的 Q 值。通过这种方式竞争 DQN 学习到重要状态的价值而不用去考虑不同行动的影响,因为状态价值 V^\pi(s) 是一个行动无关的估计。
以上这两种 doubling 和 dueling DQN 模型在使用优先经验回放时在离散行动的深度强化学习中取得了当前最好的性能。
Actor-critic 强化学习模型介于基于策略的算法和基于价值的算法之间,因为需要维护两个估计:使用 Q-value 估计的 Actor 和使用状态价值函数估计的 Critic,如图2所示。Actor 基于策略来控制智能体的行为,而 Critic 基于价值函数来对采取的行动进行评价。最新的研究也使用深度强化学习方法来提出 Actor-critic 模型的变种[20,21,26],在这些模型中 Actor 和 Critic 都是基于深层神经网络。
图2 Actor Critic 控制环路
只有一个网络的传统 DQN 适合于低维离散行动空间的问题。最近,一个 Actor-critic 算法 DDPG (deep deterministic policy gradient)被提出来,用于解决高维连续控制问题。DDPG 在状态空间使用确定性的策略梯度方法,而不是同时在状态空间和行动空间都使用随机梯度下降[20]。DDPG 与传统的 DQN 的一个不同是它使用一个新的软性的目标更新模型执行频繁的软性更新。
硬件系统的进展使得强化学习研究人员能够使用多个 CPU 或 GPU 进行并行计算来加快学习速度。首次在 DQN上测试的并行模型提高了智能体的性能,训练时间更短且收敛性更好。例如,文献[27]中提出的异步多 Actor 学习模型在连续和离散行动空间问题上都获得了高性能。多 Actor 学习使得 RL 智能体能够在不同的探索率下对环境进行探索。此外,异步更新不再需要回放存储,学习器在一个预先定义的更新周期 T 下能够利用多个试验累计的梯度。A3C (Asynchronous Advantage Actor-Critic),一种先进的深度强化学习算法,可以在多个并行处理器上异步地更新策略和价值网络。在更新周期 T 内,每一个网络分别进行更新,共享的主网络则根据 \theta^\pi 和 \theta^V 来进行更新。A3C 的同步和简化算法称为 A2C (Advantage Actor-Critic)。
在这一部分中,我们讨论了深度 RL 的背景,包括基于策略和基于价值的 RL 模型。在讨论ITS中deep RL应用的细节之前,值得一提的是,某些 deep RL算法是根据应用域的规格,在不同的应用程序中首选。虽然开发新的深度RL技术是一个活跃的研究领域,但基于Q学习的DQN和 基于 actor-critic 的DDPG 算法仍然是基于 RL 的 ITS 控制的主流。
对于高维状态空间,deep RL 方法优于传统 RL方法。在行动空间方面,基于策略的 deep RL方法比基于值的 deep RL 方法更适合于连续行动空间。对于离散行动空间,其控制器通常使用 DQN 及其变体,因为与基于策略的方法相比,它们的结构更简单。
一般来说,基于 Q 学习的 DQN 模型通常用于具有有限状态空间和行动空间的较不复杂系统,而基于策略或 actor-critic 的算法主要用于大型复杂系统,包括多智能体控制系统。在许多情况下,设计者可以在设置问题时在离散和连续状态空间和行动空间之间进行选择。例如,在 TSC 中,一些作者将连续行动定义为延长绿灯的时间,而另一些作者将离散行动空间定义为选择绿灯方向。