1.1.1 人工智能的历史

要讲述强化学习的历史，首先需要谈一下人工智能的历史，因为从被发明开始，强化学习就一直被认为是实现人工智能的一种重要算法。从计算机诞生以来，人类就对人工智能（Artificial I ntelligence, AI）领域的研究抱有浓厚的兴趣。在人们通常的观念中，人工智能常常被用于描述使用计算机来模拟人类的认知（如对话、学习、解决问题等），并且使计算机能够在外观上表现出一定的智能行为（比如能和人类进行交互，或者解决数学题等）。为了实现使用计算机来表现出一定智能的目标，接下来需要考虑的就是如何设计实用的算法让计算机表现出智能的行为。

人们对于底层算法的设计思想也经历了好几个阶段的变化。在计算机诞生的最初阶段（20世纪六七十年代），因为计算机的运算能力有限，人们最先考虑到的是如何设计一定的数据结构和对应的算法，让人们能够用数据结构来描述知识，并且能够在需要的时候从数据结构中提取相应的知识。在这一阶段，出现了LISP语言，该语言使用链表作为数据结构来存储特定领域的知识（这也是LISP语言的名称来源，LISt Processing Language，即链表处理语言），并且使用这些知识来解决问题（如进行简单的自然语言处理）。同时，在这一阶段，也出现了最简单的神经网络的雏形——感知机（Perceptron），能够解决简单的分类模型。当然，在这一阶段，受限于有限的计算能力，人们的研究主要集中在如何使用这些人工智能算法进行简单的逻辑推理和简单的分类。同时，人们对于这方面研究的热情以及对其未来抱有的希望很大。因此，在这一阶段，大量的资源被投入到了人工智能的研究中。然而物极必反，当人们发现这些层出不穷的算法能够解决的问题十分有限的时候，人工智能的研究在20世纪70年代到20世纪80年代遭遇了“严冬”。当时有科学家指出，人工智能在解决简单问题的时候往往是有效的，但是随着待解决问题规模的扩大（比如问题的输入和限制条件的增加），当时的人工智能算法（以及计算能力）并不能适应问题规模的爆炸性增长（即所谓的“组合性爆炸”问题），所以当时人工智能算法应用的局限性非常大。随着当时人工智能算法的种种局限性被指出来，同时很多人工智能算法也有很好的替代算法，人工智能的研究陷入了“严冬”。在这个时期，原来各国政府投入的资金也被逐渐收回，同时新的人工智能相关的研究很难获得资助。

上述情况一直持续到20世纪80年代初。在这个时间点，人们的兴趣逐渐转移到一类人工智能的系统，即所谓的“专家系统”（Expert System）上。通过结合人类在特定领域的知识，以及一定的逻辑推理，计算机开始能够回答专业领域的一些问题，即表现出一定的人工智能的特性。这些系统一般设计的领域都比较特定，而且对应的查询知识的逻辑也比较简单，易于在计算机上实现，因此得到了蓬勃的发展。在这段时间里，涌现了很多专家系统，包括一些智能的订单处理系统和计算机代数的专家系统，在各自领域得到了广泛应用，而且取得了相当好的成果。专家系统在解决实际问题方面的成功表现让人们认识到了知识的表示和基于知识的推理这两方面算法的重要性，因为专家系统的成功同时依赖于这两个方面。同时，专家系统也打破了人们对于人工智能的初始认识。一开始，人们认为人工智能需要有广泛性，能够通过一个单一的算法解决所有领域的问题。但事实证明，这样的想法在实践上并不可能，反而像专家系统这样的算法在狭窄的知识领域能够取得成功。除了专家系统，人们在2010年后广泛使用的深度学习理论的基础——人工神经网络（Artificial Neural Networks, ANN）也在这段时间中取得了重大进步。其中一个重要的算法就是现阶段用于训练神经网络的反向传播（Backpropagation, BP）算法。通过让梯度在神经网络中进行反向传播，得到所有神经元权重的梯度，并且用基于梯度的优化算法对神经元权重进行优化。反向传播算法的出现为多层感知机（MultiLayer Perceptron, MLP）的发展铺平了道路，也为神经网络（包括现在的深度学习）的广泛应用打下了基础。在这段时间，基于神经网络的人工智能算法也开始逐渐被应用于光学文字识别（Optical Character Recognition, OCR）和语音识别（Acoustic Speech Recognition, ASR）领域上。当然，人工智能领域在这段时间的发展不仅得益于新的算法开发，其实另一个重要的原因是计算机硬件性能的极速增加。超大规模集成电路的应用使得计算机的计算能力得到了飞跃性的提高，这也让很多以前在想象中才能运行的算法逐渐成为现实。结合现阶段（如深度强化学习领域），我们会发现，计算机算力对于很多人工智能算法的实现起着至关重要的作用。

在接下来的一段时期，人工智能领域经历了一次衰退的低谷。随着桌面计算机的出现，以及计算机硬件的运算速度的飞速提高，导致新型的通用计算机逐渐占据了原来专用的人工智能硬件（如前述的专家系统采用的计算机硬件）市场，进一步导致对应硬件上运行的软件算法逐渐变得无人问津。同时专家系统昂贵的维护费用也使得对应的算法逐渐衰落，因为专家系统的设计需要考虑到许多现实的问题，比如各种边界条件，以及输入的前置条件等。这些现实问题同时也使得专家系统往往只能局限在某一领域发挥作用，无法推广到更广义的通用人工智能领域上。同时，在这段时期，虽然计算机硬件的运算速度已经有了长足的进步，但是受限于神经网络需要消耗大量的计算资源来进行训练，神经网络也没像目前（2010—2020年）一样容易大规模地快速训练和部署。因此，还处在非常初级的阶段，并没有引起很多人的兴趣。这些共同的原因让人工智能的发展进入了第二次低谷。

从20世纪90年代中后期开始，随着计算机技术的发展，以及硬件计算能力的大幅提高，人工智能迎来了第三波快速发展。从这段时间开始，计算机的硬件已经能够支持大规模的计算（尤其是搜索和剪枝算法）。人们也据此发展了一系列新的算法来解决各种现实中的问题。在这段时间最有名的事件莫过于1996年深蓝超级计算机在国际象棋上击败了国际象棋大师卡斯帕罗夫。通过使用Alpha-Beta剪枝算法，深蓝能够平均对某一个局势搜索6～8步，而且能够每秒钟估计1亿次棋盘的局面，基本上已经能和国际象棋大师的水平旗鼓相当。这样的计算量以当时的水平来说，需要同时使用最优秀的算法，并且运行在最快的超级计算机上。可以说，深蓝的成功同时结合了当时人工智能领域在硬件和软件上最先进的水平。基于决策树和剪枝算法的价值在于，通过把人工智能算法抽象为智能体在某一环境下的决策过程，在一定程度上向着通用人工智能的目标迈出了重要的一步。在这段时间内，融合了心理学，最优控制理论等学科的强化学习也逐渐产生了自身的雏形，开始产生一些基础的算法，比如时间差分学习（Temporal-Difference, TD）算法。当然，在这段时间里，人们也逐渐开始对神经网络有了一定的研究，神经网络也逐渐开始在工业界得到一定的应用。

到了21世纪，计算机的算力得到了更加长足的进步。2011年可以认为是深度学习的元年，从这一年开始，人们将传统的神经网络进行了一定的算法和网络连接上的改造，成为现在所说的“深度学习”。深度学习在很多领域超越了之前广泛应用于工业界的机器学习算法，尤其是在计算机视觉和自然语言处理领域。同时，由于大数据概念的出现，深度学习算法更加如虎添翼，颠覆了很多领域。从强化学习的角度来说，深度学习模型的出现也改变了强化学习的生态。很多之前用机器学习完成的任务（比如策略函数、值函数、Q函数等）可以直接使用深度神经网络来近似。同时，深度学习也让强化学习可以直接以图像、视频等数据作为输入，从而避免了使用传统机器学习模型常见的特征工程，可以说大大提高了强化学习算法的通用性。深度学习的出现也使得原来的一些搜索算法的效率有了很大提升，例如，蒙特卡洛树搜索算法（Monte Carlo Tree Search, MCTS），结合深度学习网络对策略和值函数的预测，大大增强了树的搜索深度和宽度，能够被用于各种棋类项目中，其中最著名的例子就是近年来非常热门的AlphaGo和AlphaGoZero算法，结合现阶段的硬件发展（使用大量的GPU和TPU来进行训练），在围棋项目上做到了击败人类的大师级别的选手。本书在初步介绍经典强化学习算法的同时，着重介绍的是结合深度学习的强化学习算法，即深度强化学习算法，并且会在后续章节逐步介绍深度强化学习在不同领域中的作用。