「博弈智能」最新2023研究综述-爱代码爱编程
源自:信息科学
作者:郝建业 邵坤 李凯 李栋 毛航宇 胡舒悦 王震
博弈智能是一个涵盖博弈论, 人工智能等方向的一个交叉领域, 重点研究个体或组织间的交 互作用, 以及如何通过对博弈关系的定量建模进而实现最优策略的精确求解, 最终形成智能化决策和 决策知识库. 近年来, 随着行为数据的海量爆发和博弈形式的多样化, 博弈智能吸引了越来越多学者 的研究兴趣, 并在现实生活中得到广泛应用. 本文围绕博弈智能这一研究领域, 分别从三个方面进行 了系统的调研. 首先, 回顾了博弈智能的相关背景, 涵盖了单智能体马尔可夫决策过程, 基于博弈论 的多智能体建模技术, 以及强化学习, 博弈学习等多智能体求解方案. 其次, 本文依照智能体之间的 博弈关系不同, 将博弈分为合作博弈, 对抗博弈以及混合博弈这三大类范式, 并分别介绍每种博弈智 能范式下的主要研究问题, 主流研究方法以及当前典型应用. 最后, 本文总结博弈智能的研究现状, 以 及亟待解决的主要问题与研究挑战, 并给出学术界和工业界的未来展望, 为更多的相关研究人员提供 参考, 进一步推动国家人工智能发展战略。
1. 引言
博弈论 (game theory) [1,2] 作为 20 世纪经济学伟大的成果之一, 主要研究个体或群体在特定约 束下的策略优化问题, 在经济学, 运筹学, 政治学, 信息技术, 数理科学以及军事战略领域具有广泛应 用. 人工智能 (artificial intelligence, AI) 自从 1956 年在达特茅斯会议上被提出, 经过六十多年地 快速发展, 已在现代人类生活的方方面面取得了应用, 世界各主要国家也分别指定了国家人工智能战 略. 博弈智能作为一门新兴交叉领域, 其融合了人工智能和博弈论各自方法的优势, 通过对博弈关系 的定量建模进而实现最优策略的精确求解, 最终形成决策智能化和决策知识库. 近年来, 随着行为数 据的海量爆发和博弈形式的多样化 (例如, 人机博弈, 非对称博弈, 非完全信息博弈等), 博弈智能受 到了不同领域学者的广泛关注, 并在现实生活中得到广泛应用. 博弈智能主要研究多智能体系统中的博弈策略学习与求解问题, 一个典型的多智能体系统 (multi-agent system, MAS[3] ) 是由多个智能 体组成的博弈系统, 其中每个智能体均在决策上具有一定独立性和自主性. 博弈智能旨在对复杂动 态多智能体系统内的各智能体之间的交互关系进行建模, 实现对不同博弈参与方最优目标或策略的 有效求解.
近年来, 以深度神经网络为代表的机器学习研究提升了决策系统的感知和认知能力, 进而极大加 速了博弈智能的发展. 在以围棋为代表的两人零和博弈中, DeepMind 团队研发的 AlphaGo[4,5] 综合 深度神经网络, 蒙特卡洛树搜索和自博弈等技术, 击败了人类围棋冠军并引起学术界的广泛关注. 在 以星际争霸, Dota2 为代表的不完美信息博弈中, AlphaStar[6] 和 OpenAI Five[7] 也达到了人类顶级 专家水平, 将博弈智能的研究推到了一个新的高度. 这也为后续博弈智能技术发展提供了新的思路, 例如, 在训练过程中引入对抗训练和基于种群的训练, 大幅提升了策略的鲁棒性. 此外, 在早期双重 预言机 (double oracle[8] ) 技术的基础上, 结合强化学习 (reinforcement learning, RL[9] ) 衍生出了一系 列对抗博弈的求解方法, 例如, 策略空间的应对预言机 (policy space response oracle, PSRO[10] ) 等. 虽然两人博弈研究取得了快速进展, 但是在多人对抗博弈中如何提升策略的鲁棒性和多样性, 高效求 解均衡, 目前仍是一个开放问题. 此外, 棋类, 视频游戏和现实世界中的群体决策问题尚存在较大差 异, 现有博弈智能方法的实际应用也面临诸多挑战. 例如, 复杂动态的自动驾驶路口交互场景下, 交 通参与者均有其各自目标, 且相互间的博弈关系存在空间和时间上的动态性, 导致各交通参与者的最 优博弈策略难以求解. 因此, 如何缩短虚拟环境下博弈智能技术到现实物理世界落地的差距, 实现大 规模实际场景的博弈关系建模与策略求解, 是博弈智能发展的重要目标.
根据智能体间的博弈关系, 博弈智能可分为合作博弈智能, 对抗博弈智能和混合博弈智能等形 式. 在合作博弈智能中, 所有智能体共享一个全局奖励函数, 所有智能体需要相互合作来最大化整体 的求解效率和性能. 从学习范式角度, 合作博弈可划分为独立学习[11] , 联合学习[12] , 协作学习[13] , 集 中训练分布执行[14] 等形式. 由于所有智能体共享同一个奖励函数, 如何划分每个智能体的贡献, 设 计各智能体间的信誉分配和通信机制, 是学习最优合作策略的挑战问题. 此外, 由于实际问题中往往 涉及大量智能体, 如何实现大规模多智能体高效合作是未来的一个重要研究方向. 在对抗博弈智能 中, 博弈双方处于对抗竞争的关系, 每方优化自身的收益都会降低对方的收益. 根据博弈参与方数量 的不同又可分为两人零和博弈, 两队零和博弈和多人零和博弈. 不同于合作博弈以明确的收益作为 优化目标, 对抗博弈以更为复杂的隐含均衡作为目标, 从而对策略求解的高效性, 多样性和鲁棒性提 出了挑战. 在混合博弈智能中, 所有智能体都有各自的优化目标, 参与方之间需要进行有机地协作, 既要保证优化个体目标, 也要实现系统整体收益的最大化 [15,16] . 混合博弈研究重点关注社会困境和 自主协作两大难题, 前者研究如何鼓励智能体学习更加符合群体利益的行为, 或是如何惩罚逾越道德 规则的行为. 后者研究在最优策略难以快速求解的情况下, 如何实现各独立智能体在最大化自身收 益的同时进行自主协作.
本文围绕博弈智能, 首先总结相关技术背景, 涵盖强化学习, 多智能体系统建模求解, 博弈论等 基础知识. 其次, 本文按照现有博弈智能范式 [17] , 将博弈智能分为合作博弈, 对抗博弈以及混合博弈 这三大类, 分别介绍每一类下的主要研究问题, 主流研究方法以及当前典型应用. 具体而言, 针对合 作博弈的研究, 介绍主要学习范式, 智能体间通信, 信誉分配等基础研究问题和主流方法. 对于多智 能体系统的可扩展性, 分析几种主要可扩展架构. 同时从游戏 AI, 求解器参数优化, 无线通信性能优 化, 推荐系统等四个代表性场景介绍合作博弈的实际应用. 对于对抗博弈, 根据博弈参与方的智能体数量划分为两人零和博弈, 两队零和博弈, 多人零和博弈, 并分别介绍三种类型博弈的主流研究方法, 以及对抗博弈在游戏, 网络攻防, 军事推演等领域的应用. 针对混合博弈, 介绍以社会困境求解和群 体协作博弈为代表的混合博弈主要研究问题和方法, 并分析能源分配和自动驾驶两种代表性的混合 博弈应用. 最后, 本文总结当前博弈智能技术的研究现状, 以及复杂任务训练慢, 行为策略迁移难, 基 线构建不充分, 推理架构待优化等亟待解决的主要挑战, 并给出学术界和工业界的未来展望, 为博弈 智能提供系统性的参考.
2. 博弈智能
本文围绕 博弈智能,首先总结相关技术背景,涵盖强化学习、多智能体系统建模求解、博弈论等基础知识。其次,本文按照现有博弈智能范式,将博弈智能分为合作博弈、对抗博弈以及混合博弈这三大类,分别介绍每一类下的主要研究问题、主流研究方法以及当前典型应用。
2.1 合作博弈智能
任何博弈的研究范畴都主要包含博弈建模和博弈求解. 从博弈建模的角度看, 马尔可夫博弈[21] 是用来建模多智能体博弈的一般性框架 (详细定义参考第2节), 图1则展示了典型的合作式马尔可夫 博弈的流程. 与其它博弈相比, 合作式博弈最大的特点是, 所有智能体的奖励函数完全相同, 即 r = r1 = r2 = ... = rn. 从博弈求解的角度看, 由于所有智能体共享奖励函数, 这就要求所有智能体相互配合, 学习一种最优的联合策略 π(a|s) = π(〈a1, a2, ..., an〉|s) 来最大化共同的累积奖励, 这本质上是 寻找一种社会最优解 (social optimal solution). 合作博弈在现实社会中有着广泛的应用, 例如在交通 信号灯自主控制问题中, 所有信号灯组成合作多智能体, 需要观测不同的车流情况, 即 〈s1, ..., sn〉, 一 起决定每个信号灯的显示颜色, 即 〈a1, ..., an〉, 从而最大化整个城市的交通安全和通行效率, 即 r. 本 章主要关注合作博弈的求解方案, 将首先详细调研合作博弈智能的主要研究热点, 在此基础上探索合 作博弈技术在实际中的应用. 本章的架构和涉及到的代表算法如表1所示.
2.2 对抗博弈智能
对抗博弈描述的是参与多方的利益相互冲突, 一方所得收益等于其他参与方所失的博弈场景. 各方在利益的驱动下会展开激烈的竞争. 对抗场景在现实中广泛存在, 从棋牌类对局到即时策略类 游戏, 对抗博弈是检验智能程度的 “试金石”; 从网络攻防到军事推演, 对抗博弈是安全领域重要的演 练场[92] . 对抗博弈智能不仅可以用于这些现实中的对抗场景, 以获得博弈参与方的最优策略; 也可以 构造性地用于诸如图像生成、鲁棒优化等问题中, 将优化问题转化为均衡求解. 因此, 对抗博弈智能 研究不仅可以在动态且复杂的对抗场景中得出最优决策, 还可以为传统优化问题提供新的思路, 对学 术界和产业界的应用均有重要意义.
在博弈论中, 完全对抗的交互场景往往用零和博弈来刻画, 即各方的收益加和为零. 以两方博弈 为例, 作为博弈中的一方, 在面对特定的对手时, 最优策略往往是直接探测对手的弱点并加以利用. 然而, 一方面, 对手的策略是动态变化的, 在利用对手的策略时常常会暴露自身的弱点反而被对手利 用[93] ; 另一方面, 现实中的对抗博弈场景往往是非常复杂的, 很难实现对手建模并根据博弈收益作出 最优应对. 这些挑战要求博弈参与方具有高级别的对抗博弈智能, 在面对多样化的对手时都能有优 异的表现. 在博弈论中, 通用方案是求解零和博弈的均衡, 即博弈双方均不断优化各自收益后得到 的一对稳态策略. 博弈双方的均衡策略互为彼此的最优应对, 并且均衡也是关于对手行为的合理预 测[94] . 考虑参与方 X 和 Y 的两人零和博弈, 根据均衡的定义可知, 当参与方 X 采用均衡策略, 面对 参与方 Y 的任意策略时, X 至少可以获得均衡收益; 并且当 Y 偏离均衡时, X 可能取得优势从而获 得超过均衡的收益; 而当参与方 Y 采用均衡策略时也有类似的效果. 这些性质确保博弈参与方可以 使用均衡策略来面对多样化的对手, 为实现对抗博弈智能提供了理论保证. 因此在本章中, 会首先探讨两人零和博弈均衡求解相关技术的发展.
在对抗博弈中, 博弈的一方不仅可以是单个智能体, 还可以是团体, 例如团队作战的军事对抗. 团体对抗不仅涉及与对手的竞争, 还需考虑团体内部智能体的分布式执行、智能体间的合作等与完 全合作博弈类似的问题. 然而, 相比于完全合作博弈以明确的团体收益作为优化目标, 团体对抗以更 为复杂的两队博弈的均衡作为目标, 需要研究解决团体策略性能鲁棒提升、团队成员策略的多样性 等特殊问题. 因此, 本章还会详细讨论两队零和博弈的具体技术及其发展. 多方对抗也是现实中常见的场景, 例如多人德州扑克、麻将、军事对抗等. 当对抗博弈中存在多 个参与方时, 博弈的解概念相对于两人零和或两队零和博弈会有较大差异. 因此, 在本章最后, 会简 要介绍多人零和博弈的求解思路和相关成果. 对抗博弈涉及到的算法众多, 在经典算法的基础上不断创新的工作也层出不穷, 为了更系统地理 解对抗博弈的求解思路, 选取一些代表性算法进行分类总结, 如表 2所示.
混合博弈智能
在上述章节介绍的合作与对抗博弈中,参与者通常为具有固定形式奖励(payoff)函数的纯动机 智能体,此时参与者们的收益关系具有固定形式,即彼此目标一致或完全相反. 然而,现实场景中也 普遍存在着大量混合动机参与者,即奖励函数形式不固定,即组成奖励的关键权重可能随环境动态 变化;或者不同参与者间的目标关系各不相同,既无法应用合作博弈智能中参与者目标与系统整体 目标一致的假设,也无法应用对抗博弈智能中参与者间目标彼此相反的假设. 因此,本文将此类场 景定义为“混合博弈(mixed-motive games)”,其中各个博弈参与者保持自身奖励最大化的目标,但 彼此间独立,不共享自身状态与参数. 在这类博弈中,多智能体系统的求解目标往往比较复杂,需要 根据实际场景具体分析. 除了以纳什均衡为博弈求解目标外, 多智能体系统往往需要考虑参与方的 协作, 以帕累托最优 (Pareto optimality) 为系统的求解目标。
针对混合博弈的相关理论, 目前绝大多数研究工作基于博弈论中的均衡解概念 (如: 纳什均衡), 使用一般和博弈的形式来表示混合博弈问题, 即一种可能存在多个纳什均衡点的矩阵博弈模型. 以 猎鹿博弈 (stag hunt game) 为例, 在参与者奖励函数 r 明确的情况下, 一个亲社会的 (prosocial) 参 与者 i 的收益函数如下:
其中 α 代表参与者的亲社会程度, 即参与者对其它参与者目标的“妥协”程度. 对于不同的边界条 件, α = 0 表示参与者是完全自私的, α = 1 表示参与者是完全无私的. 此时, 两参与者同时选择 “狩猎”所对应的概率大小随着双方参与者亲社会级别的增加而增加. 从纳什均衡求解的角度, 存在 α¯ ∈ (0, 1], 使得当任意参与者的收益函数中亲社会程度满足 α ⩾ α¯, 上述问题均能唯一收敛到由参与 者共同“狩猎”所主导的纳什均衡 [149] . 由于上述亲社会等级等复杂概念的引入, 一般和博弈与零和 博弈和合作博弈相比, 在求解理论与具体应用角度上均具有更大的挑战性. 从理论角度来说, 以较为 简单的一般和正规形式博弈为例. 一方面, 虽然纳什定理确保该类博弈存在混合纳什均衡, 但在该类 博弈中求解纳什均衡是一个 PPAD 完全问题 [122,123] , 即目前不存在一个多项式时间算法能高效求 解该类博弈的纳什均衡. 另一方面, 该类博弈的纳什均衡往往也不具有价值唯一性, 即如果同时存在 多个纳什均衡, 参与者在不同的纳什均衡中可能会得到不同奖励. 从应用角度来说, 早期一般和博弈 的相关算法主要面向表格式的有限状态空间, 例如, 纳什 Q 学习 [150]、相关 Q 学习 [151]、朋友或敌 人 Q 学习 [152] . 然而, 面向现实世界中普遍存在的高维或连续的状态空间, 以及交互参与者间复杂多 变的行为空间, 上述算法难以直接应用
近年来, 针对如何构建面向实际问题的混合博弈智能, 学术界主要存在以下两个研究热点: • 社会困境: 混合博弈可用于描述个体利益与集体利益相冲突的情况, 即社会困境问题. 此类场景 中通常容易出现更接近人类的复杂行为, 如: 在一个大团队中, 某参与者采用欺骗 (deception)、搭便 车 (free-riding) 等方式获得更高的个体奖励, 但损害了团队整体利益. 因此, 如何鼓励参与者学习更 加符合群体利益的行为, 或如何惩罚具有上述逾越道德规则行为的参与者, 都是目前社会困境面临的 技术难题.
• 协作博弈 在混合博弈中, 不同于一般的合作博弈, 某一参与者通常不仅需要对其他参与者的 行为做出最佳反应, 同时也需要预测其它参与者对自身行为可能的最佳反应, 此时需引入递归推理的 决策范式, 这极大增加了参与者间交互行为的灵活度与建模难度. 以自动驾驶场景为例, 车辆在多车 交互场景中既需要动态推理其他车辆的意图, 还需要针对其他车辆的策略作出最优应对. 因此, 如何 实现各个独立参与者在最大化自身奖励的同时自主地进行协作, 是另一个亟待解决的技术难题. 接下来, 本文将从混合博弈智能的上述两个研究热点出发, 介绍相关的最新学术进展、尚未解决 的问题和未来研究方向. 本章的架构和涉及到的代表算法如表3所示.
3. 总结与展望
本文围绕着博弈智能这一前沿交叉领域, 总结了博弈智能的相关技术背景, 涵盖马尔可夫决策过 程、基于博弈论的交互建模等多智能体建模技术, 以及强化学习、博弈学习等多智能体求解方案. 本 文按照博弈问题中智能体之间的不同关系, 依次介绍了合作博弈、对抗博弈、混合博弈这三大范式的 博弈智能技术的发展现状与典型应用, 并总结了目前研究的成果与不足.
博弈智能是一个具有重大前景的研究方向, 在现实生活中有着广泛的应用. 该领域的研究发展有助于理解群体认知规律和运行规则, 也有助于实现更接近人类水平或超越人类水平的群体智能. 然而, 现有博弈智能取得的成果是初步的, 在解决真实世界的复杂问题时, 仍面临着复杂任务训练慢、 行为策略迁移难、基线构建不充分、推理架构待优化等多方面的挑战. 未来的博弈智能研究将带来 很多崭新的研究方向.
有模型博弈智能. 基于模型的方法通过学习博弈过程的动力学模型或多智能 体交互模型, 可以提升训练样本的利用率, 实现博弈过程的高效推演.
层次化博弈智能.通过对复杂 的多智能体决策问题进行逐级解耦, 或引入专家先验进行层次划分, 有效降低多智能体决策的计算复 杂度.
元学习博弈智能. 从模型参数初始化或上下文学习角度, 元学习技术有助于实现大规模场景下 博弈智能的迁移泛化.
表征博弈智能.通过结合基础模型的多模态和多任务学习技术, 实现博弈智能 在高维复杂场景下的通用表征学习.
鲁棒博弈智能.真实问题往往存在大量的鲁棒安全性要求, 通过 约束带入或者严格惩罚等方式发展鲁棒安全的博弈智能技术对于真实应用至关重要.
离线博弈智能.现有博弈智能技术需要在仿真环境中不断演练推理, 然而构建和真实应用匹配的仿真环境非常困难. 发展基于离线数据的博弈智能技术有助于降低对仿真环境的依赖.
认知博弈智能.认知博弈智能的发展离不开研究人机博弈、意识理论等前沿智能技术, 这也是决策智能上升到认知 智能的关键.
本文希望通过相关介绍, 对该领域研究提供一些帮助, 引导研究人员继续加大力度去解 决博弈智能的基础问题, 建立博弈智能理论研究和应用实践的协同发展, 推动博弈智能技术的真实落 地, 更好地让博弈智能技术赋能人类社会。
声明:公众号转载的文章及图片出于非商业性的教育和科研目的供大家参考和探讨,并不意味着支持其观点或证实其内容的真实性。版权归原作者所有,如转载稿涉及版权等问题,请立即联系我们删除。
“人工智能技术与咨询” 发布。