【700页书稿】《决策算法》2022年MIT

2022 年 11 月 18 日 专知

本书对不确定条件下的决策算法作了广泛的介绍。我们涵盖了与决策有关的各种主题，介绍了基本的数学问题公式和解决这些问题的算法。书中提供了数字、例子和练习，以传达各种方法。

本书适用于高年级本科生和研究生，以及专业人士。它需要掌握一些数学上的知识，并事先接触过多元微积分、线性代数和概率概念。在附录中提供了一些复习材料。本书特别有用的学科包括数学、统计学、计算机科学、航空航天、电气工程和运筹学。

这本教科书的基础是算法，这些算法都是用Julia编程语言实现的。在算法实现的设计中，优先考虑的是可解释性，而不是效率。例如，工业应用可能受益于其他的实现方式。允许免费使用与本书有关的代码片段，但必须注明代码的来源。

引言

许多重要的问题涉及到不确定性下的决策，包括飞机防撞、野火管理和灾难应对。在设计自动决策系统或决策支持系统时，重要的是要考虑到各种不确定性的来源，同时仔细平衡多个目标。我们将从计算的角度讨论这些挑战，旨在提供决策模型和计算方法背后的理论。本章介绍了不确定性下的决策问题，提供了一些应用的例子，并概述了计算方法的空间。然后，它总结了各学科如何促进我们对智能决策的理解，并强调了潜在的社会影响领域。最后，我们对本书的其余部分进行了概述。

1.1 决策

智能体是一个根据对其环境的观察而行动的实体。智能体可能是物理实体，如人类或机器人，也可能是非物理实体，如完全用软件实现的决策支持系统。如图1.1所示，智能体与环境之间的互动遵循观察-行动的周期或循环。

智能体在时间t收到对环境的观察，表示为ot。例如，观察可以通过生物感觉过程进行，如人类，或通过传感器系统，如空中交通控制系统中的雷达。观察通常是不完整的或有噪音的；人类可能没有看到接近的飞机，或者雷达系统可能由于电磁干扰而错过了探测。然后智能体通过一些决策过程选择一个行动at。这种行动，如发出警报，可能对环境产生非决定性的影响。

图 1.1 智能体与其环境之间的交互。

我们的关注重点是在一段时间内智能互动以实现其目标的智能体。考虑到过去的观察序列，o1, ...... ot，以及对环境的了解，智能体必须选择一个行动at，在存在各种不确定性来源的情况下最好地实现其目标，包括以下内容：

结果的不确定性，即我们的行动效果是不确定的。
模型的不确定性，即我们对问题的模型是不确定的。
状态的不确定性，即环境的真实状态是不确定的。
相互作用的不确定性，即在环境中相互作用的其他智能体的行为是不确定的。

本书是围绕这四种不确定性的来源组织的。如第1.4节所述，在不确定的情况下做出决策是人工智能领域的核心，也是许多其他领域的核心。我们将讨论各种算法，或对计算过程的描述，以做出对不确定性具有稳定性的决策。

1.2 应用

上一节介绍的决策框架可以应用于各种领域。本节讨论了一些具有现实世界应用的概念性例子。附录F概述了其他的概念性问题，这些问题在本文中被用来演示我们讨论的算法。

1.2.1 飞机避撞

为了帮助防止飞机之间的空中碰撞，我们想设计一个系统，可以提醒飞行员注意潜在的威胁，并指导他们如何操纵以避免这些威胁。该系统与其他飞机的应答器进行通信，以便在一定程度上准确地识别其位置。决定向飞行员提供什么指导是具有挑战性的。飞行员将如何快速反应以及他们将如何积极地遵守指导，都存在不确定性。此外，其他飞机的行为也存在不确定性。我们希望我们的系统能足够早地发出警报，为飞行员提供足够的时间来操纵他们的飞机以避免碰撞，但我们不希望我们的系统过早地发出警报，这将导致许多不必要的操纵。由于该系统将在全球范围内持续使用，我们需要该系统提供一个特殊的安全水平。

1.2.2 自动驾驶

我们想建造一辆能够在城市环境中安全行驶的自主车辆。该车必须依靠一套传感器来感知其环境，以做出安全的决定。一种类型的传感器是激光雷达，它涉及测量环境中的激光反射，以确定与障碍物的距离。另一种类型的传感器是摄像头，通过计算机视觉算法，它可以检测到行人和其他车辆。这两种类型的传感器都是不完美的，容易受到噪音和遮挡的影响。例如，一辆停在路边的卡车可能会遮挡住正在试图穿过人行横道的行人。我们的系统必须从其他车辆、行人和其他道路使用者的可观察行为中预测他们的意图和未来路径，以便安全地导航到我们的目的地。

1.2.3 乳腺癌筛查

在世界范围内，乳腺癌是妇女中最常见的癌症。早期发现乳腺癌可以帮助挽救生命，而乳房X光检查是目前最有效的筛查工具。然而，乳房X线照相术也有潜在的风险，包括假阳性，这可能导致不必要的侵入性诊断后续行动。多年来的研究已经产生了基于年龄的各种人群筛查计划，以平衡测试的好处和风险。开发一个能根据个人风险特征和筛查历史提出建议的系统，有可能带来更好的健康结果。这种系统的成功可以在总的预期质量调整寿命年数、乳房X光检查的次数、假阳性的发生率以及未被发现的侵入性癌症的风险等方面与全民筛查计划进行比较。

1.2.4 金融消费与投资组合配置

假设我们想建立一个系统，建议一个人的财富当年应该消费多少，投资多少。投资组合可能包括具有不同风险和预期收益水平的股票和债券。由于赚取和投资收入的不确定性，财富的演变是随机的，通常在投资者接近退休时才会增加，然后稳定地减少。在一年中消费一个单位的财富所带来的享受通常会随着消费数量的减少而减少，从而导致人们希望在个人的一生中平滑消费。

1.2.5 分布式野火监测

在扑灭野火时，对形势的认识是一个重大挑战。火灾的状态随着时间的推移而演变，受到风和环境中的燃料分布等因素的影响。许多野火跨越了大的地理区域。监测野火的一个概念是使用一队配备有传感器的无人机在野火上方飞行。单个无人机的感应范围是有限的，但团队的信息可以被融合，以提供一个统一的情况快照，从而推动资源分配决策。我们希望团队成员能够自主地决定如何相互协作，以提供最佳的火场覆盖。有效的监测需要决定如何机动地覆盖新的传感器信息可能有用的区域；在我们确定火是否在燃烧的区域花费时间将是浪费的。识别要探索的重要区域需要对火灾的随机演变进行推理，因为对其当前状态的了解并不完善。

1.2.6 火星科学探索

探测器在火星上有了重要的发现，并增加了我们对火星的了解。然而，科学探索的一个主要瓶颈是火星车和地球上的操作团队之间的通信联系。传感器信息从火星传到地球，以及命令从地球传到火星，可能需要半小时之久。此外，对漫游车的指导需要提前计划，因为由于作为行星之间信息中继站的轨道器的位置，与火星的上传和下载窗口有限。最近的研究表明，通过引入更高水平的自主性，科学探索任务的效率可以提高五倍。人类操作员仍将提供关于任务目标的高级指导，但漫游者将有灵活性，利用最新的信息选择自己的科学目标。此外，漫游车最好能在没有人类干预的情况下对各种危险和系统故障作出适当的反应。

1.3 方法

有许多设计决策智能体的方法。根据不同的应用，有些可能比其他的更合适。它们在设计者的责任和留给自动化的任务方面有所不同。本节简要地概述了这些方法的集合。本书将主要关注规划和强化学习，但其中一些技术将涉及监督学习和优化的元素。

1.3.1 显式编程

设计决策智能体的最直接的方法是预测智能体可能发现自己所处的所有场景，并明确编程智能体应该对每个场景做出什么反应。明确的编程方法对于简单的问题可能很有效，但它给设计者带来了很大的负担，要提供一个完整的策略。各种智能体编程语言和框架已被提出，以使智能体编程更容易。

1.3.2 监督学习

对于一些问题，向智能体展示该怎么做，而不是写一个程序让智能体遵循，可能会更容易。设计者提供了一组训练实例，而自动学习算法必须从这些实例中进行概括。这种方法被称为监督学习，并被广泛地应用于分类问题。当应用于学习从观察到行动的映射时，这种技术有时被称为行为克隆。当专家设计者实际上知道在一系列有代表性的情况下的最佳行动方案时，行为克隆的效果很好。尽管存在各种不同的学习算法，但在新的情况下，它们通常不能比人类设计师表现得更好。

1.3.3 优化

另一种方法是由设计者指定可能的决策策略空间和需要最大化的性能指标。评估一个决策策略的性能通常需要运行一批模拟。然后，优化算法在这个空间中进行搜索，寻找最佳策略。如果空间相对较小，并且性能指标没有很多局部最优，那么各种局部或全局搜索方法可能是合适的。虽然通常假设动态模型的知识是用来运行模拟的，但它并不是用来指导搜索的，这对复杂的问题可能很重要。

1.3.4 规划

规划是一种优化形式，它使用问题的动态模型来帮助指导搜索。有大量的文献探讨了各种规划问题，其中大部分集中在确定性问题上。对于某些问题，用一个确定的模型来近似动态可能是可以接受的。假设一个确定的模型使我们能够使用更容易扩展到高维问题的方法。对于其他问题，对未来不确定性的考虑是至关重要的。本书完全集中在对不确定性的考虑很重要的问题上。

1.3.5 强化学习

强化学习放宽了规划中的假设，即一个模型是提前知道的。相反，决策策略是在智能体与环境互动时学习的。设计者只需提供一个性能指标；由学习算法来优化智能体的行为。强化学习中出现的一个有趣的复杂性是，行动的选择不仅影响到智能体在实现其目标方面的直接成功，而且还影响到智能体对环境的学习能力和确定它可以利用的问题的特征。

1.4 历史发展

决策过程自动化的理论起源于早期哲学家、科学家、数学家和作家的梦想。早在公元前800年，古希腊人就开始将自动化纳入神话和故事中。自动机这个词最早出现在荷马的《伊利亚特》中，其中提到了自动机的概念，包括用于招待晚宴客人的机械三脚架。在十七世纪，哲学家们提出使用逻辑规则来自动解决分歧。他们的想法为机械化推理打下了基础。

从十八世纪末开始，发明家们开始创造自动机器来完成劳动。特别是，纺织业的一系列创新导致了自动织机的发展，这反过来又为第一批工厂机器人奠定了基础。十九世纪初，使用智能机器来实现劳动自动化，开始进入科幻小说。机器人一词起源于捷克作家卡雷尔-恰佩克的剧本《R.U.R.》，即《罗苏姆的万能机器人》的简称，讲述了机器可以完成人类不愿做的工作。这部剧启发了其他科幻作家将机器人纳入他们的写作中。二十世纪中期，著名作家和教授艾萨克-阿西莫夫在其著名的《机器人》系列中阐述了他对机器人的看法。

在自动化决策的实际实施中，一个主要的挑战是对不确定性的考虑。即使在二十世纪末，因开发单线算法而最著名的乔治-丹齐格（George Dantzig）也在1991年表示：回过头来看，有趣的是，开始我研究的最初问题仍然很突出--即随着时间的推移动态地计划或安排的问题，特别是在不确定性下动态地计划。如果这样的问题能够被成功解决，它可以（最终通过更好的规划）为世界的福祉和稳定作出贡献。

虽然不确定性下的决策仍然是一个活跃的研究领域，但在过去的几个世纪中，研究人员和工程师已经更接近于使这些早期梦想家提出的概念成为可能。目前最先进的决策算法依赖于多个学科的概念的融合，包括经济学、心理学、神经科学、计算机科学、工程学、数学和运筹学。本节重点介绍这些学科的一些主要贡献。学科之间的交叉渗透导致了许多最近的进步，并可能在未来继续支持增长。

1.5 社会意义

决策算法方法已经改变了社会，并可能在未来继续改变。本节简要地强调了决策算法可以为社会做出贡献的几种方式，并介绍了在试图确保广泛受益时仍然存在的挑战。

算法方法对环境的可持续性做出了贡献。例如，在能源管理方面，贝叶斯优化已经被应用于自动家庭能源管理系统。来自多智能体系统领域的算法被用来预测智能电网的运行，设计能源交易市场，以及预测屋顶太阳能发电的采用。算法也被开发出来以保护生物多样性。例如，神经网络被用于野生动物普查的自动化，博弈论方法被用于打击森林偷猎，优化技术被用于分配栖息地管理的资源。

几十年来，决策算法已经在医学领域取得了成功。这种算法已经被用于将居民与医院以及器官捐赠者与需要的病人相匹配。贝叶斯网络的一个早期应用是疾病诊断，我们将在本书的第一部分介绍。从那时起，贝叶斯网络就被广泛用于医学中的疾病诊断和预后。医学图像处理领域已经被深度学习所改变，算法思想最近在理解疾病的传播方面发挥了重要作用。

算法使我们能够了解城市地区的发展并促进其设计。数据驱动的算法已被广泛用于改善公共基础设施。例如，随机过程被用来预测输水管道的故障，深度学习改善了交通管理，马尔科夫决策过程和蒙特卡洛方法被用来改善应急反应。来自分散的多智能体系统的想法优化了旅行路线，路径规划技术被用来优化货物的交付。决策算法已被用于自动驾驶汽车和改善飞机安全。

优化决策算法可以放大其用户的影响，无论其意图如何。例如，如果这些算法的使用者的目标是在政治选举期间传播错误信息，那么优化过程可以帮助促进这一目标。然而，类似的算法也可以用来监测和抵制虚假信息的传播。有时，这些决策算法的实施会导致其用户无意中的下游后果。

尽管算法有可能带来巨大的好处，但在社会中实施这些算法也存在着挑战。由于数据收集的方式，数据驱动的算法往往存在着固有的偏见和盲点。随着算法成为我们生活的一部分，重要的是了解如何减少偏见的风险，以及如何以公平和公正的方式分配算法进步的好处。算法也可能容易受到对手的操纵，关键是我们要设计出对这种攻击具有鲁棒性的算法。同样重要的是，要扩展道德和法律框架，以防止意外后果和分配责任。

1.6 本书概述

本书分为五个部分。第一部分讨论了在单一时间点的简单决策中对不确定性和目标进行推理的问题。第二部分将决策扩展到顺序问题，在这个问题上，我们必须根据我们行动的结果的信息做出一连串的决定，随着我们的行动进行。第三种是针对模型的不确定性，即我们不是从一个已知的模型开始，必须通过与环境的互动来学习如何行动。第四部分讨论了状态的不确定性，不完善的感知信息使我们无法了解完整的环境状态。最后一部分讨论了涉及多个智能体的决策环境。

1.6.1 概率推理

理性的决策需要对我们的不确定性和目标进行推理。本书的这一部分首先讨论了如何将不确定性表示为一种概率分布。现实世界的问题需要对许多变量的分布进行推理。我们将讨论如何构建这些模型，如何利用它们进行推理，以及如何从数据中学习它们的参数和结构。然后，我们将介绍效用理论的基础，并说明它如何通过最大期望效用原则构成不确定情况下的理性决策的基础。然后我们讨论如何将效用理论的概念纳入本章前面介绍的概率图形模型中，形成所谓的决策网络。

1.6.2 序列问题

许多重要的问题需要我们做出一系列的决定。最大期望效用的原则仍然适用，但在顺序背景下的最佳决策需要对未来的行动和观察顺序进行推理。本书的这一部分将讨论随机环境下的顺序决策问题，在这种环境下，我们行动的结果是不确定的。我们将重点讨论在模型已知和环境完全可观察的假设下的顺序决策问题的一般表述。我们将在本书的后面放宽这两个假设。我们的讨论将从介绍马尔科夫决策过程（MDP）开始，这是顺序决策问题的标准数学模型。我们将讨论为这些类型的问题寻找精确解决方案的几种方法。由于大型问题有时不允许有效地找到精确解，我们将讨论一系列离线和在线的近似解法，以及一种涉及直接搜索参数化决策策略空间的方法。最后，我们将讨论验证我们的决策策略在现实世界中部署时将发挥预期作用的方法。

1.6.3 模型不确定性

在我们对顺序决策问题的讨论中，到目前为止，我们已经假定过渡和奖励模型是已知的。然而，在许多问题中，动态和奖励并不完全知道，智能体必须通过经验学习行动。通过观察其行动的结果，以状态转换和奖励的形式，智能体要选择使其长期积累的奖励最大化的行动。解决这种存在模型不确定性的问题是强化学习领域的主题，也是本书这一部分的重点。我们将讨论解决模型不确定性的几个挑战。首先，智能体必须仔细平衡对环境的探索和对通过经验获得的知识的利用。第二，奖励可能在重要的决定作出后很久才收到，所以必须将后来的奖励的功劳分配给早期的决定。第三，智能体必须从有限的经验中进行概括。我们将回顾解决这些挑战的理论和一些关键算法。

1.6.4 状态不确定性

在这一部分，我们将不确定性扩展到包括状态。我们不是准确地观察状态，而是接收与状态只有概率关系的观察。这样的问题可以被建模为部分可观察的马尔科夫决策过程（POMDP）。解决POMDP的常见方法是推断出当前时间步长的基础状态的信念分布，然后应用一个将信念映射到行动的策略。这一部分首先讨论了如何更新我们的信念分布，给定一个过去的观察和行动序列。然后，它讨论了解决POMDP的各种精确和近似方法。

1.6.5 多智能体系统

到目前为止，只有一个智能体在环境中做决定。本部分将前四部分扩展到多个智能体，讨论互动的不确定性所带来的挑战。我们首先讨论了简单的游戏，即一组智能体同时各自选择一个行动。其结果是基于联合行动的每个智能体的个体奖励。马尔科夫博弈（MG）代表了简单博弈对多状态和MDP对多智能体的概括。因此，智能体选择的行动可以随机地改变共享环境的状态。由于其他智能体的策略的不确定性，MG的算法依赖于强化学习。部分可观察马尔科夫博弈（POMG）引入了状态的不确定性，进一步概括了MGs和POMDPs，因为智能体现在只收到了有噪声的局部观察。分布式的部分可观察马尔可夫决策过程（Dec-POMDP）将POMG集中在一个合作的、多智能体的团队上，在这个团队中，智能体之间有一个共同的奖励。本书的这一部分介绍了这四类问题，并讨论了解决它们的精确和近似算法。