分布式人工智能

第一部分分布式人工智能简介
1 概述
（安波，新加坡南洋理工大学）
1.1 研究背景3
1.1.1 前深度学习时代 3
1.1.2 深度学习时代6
1.2 主要研究领域8
1.2.1 算法博弈论8
1.2.2 分布式问题求解9
1.2.3 多智能体规划10
1.2.4 多智能体学习 11
1.2.5 分布式机器学习 12
1.3 相关应用14
1.3.1 足球14
1.3.2 安全博弈15
1.3.3 扑克和麻将 16
1.3.4 视频游戏 17
1.4 当前热点与挑战18
1.4.1 超大规模分布式人工智能系统 18
1.4.2 分布式人工智能系统的鲁棒性和安全性 19
1.4.3 分布式人工智能决策的可解释性 19
1.4.4 将传统和深度学习的方法结合 20
参考文献
第二部分分布式规划与优化
2 分布式规划
（吴锋，中国科技大学）
2.1 研究背景 9
2.2 分布式规划的决策模型31
2.3 分布式规划的离线算法36
2.3.1 离线精确规划算法37
2.3.2 离线近似规划算法 39
2.4 分布式规划的在线算法46
2.4.1 在线协调机制 46
2.4.2 在线通信策略 48
2.5 当前热点与挑战 52
参考文献 54
3 分布式约束优化
（陈自郁，重庆大学）
3.1 研究背景58
3.2 分布式约束优化问题59
3.2.1 约束网络59
3.2.2 基础概念 60
3.3 求解算法分类63
3.4 完备求解算法65
3.4.1 基于搜索的完备求解算法：ADOPT 65
3.4.2 基于推理的完备求解算法：DPOP 69
3.5 非完备求解算法72
3.5.1 基于决策的局部搜索算法72
3.5.2 基于信念传播的推理算法：Max-sum 75
3.6 基准测试问题和典型应用 80
3.6.1 基准测试问题和评价指标 80
3.6.2 典型应用 82
3.7 当前热点与挑战85
参考文献 86
第三部分多智能体博弈
4 纳什均衡求解
（邓小铁，北京大学；刘正阳，北京理工大学）
4.1 研究背景 93
4.2 正规形式博弈94
4.3 纳什均衡与纳什定理95
4.4 二人博弈纳什均衡求解算法97
4.4.1 二人博弈的表示形式 98
4.4.2 支持枚举算法 98
4.4.3 Lemke-Howson 算法 99
4.4.4 Lipton-Markakis-Mehta 算法103
4.4.5 三种算法的总结与对比106
4.5 纳什均衡的计算复杂性106
4.6 当前热点与挑战108
参考文献 110
5 机制设计
（沈蔚然，中国人民大学；唐平中，清华大学）
5.1 研究背景112
5.2 什么是机制 113
5.2.1 社会选择函数 113
5.2.2 机制的实现与显示原理113
5.3 拍卖机制设计 118
5.3.1 性质与设计目标 119
5.3.2 社会福利最大化机制：VCG 机制 121
5.3.3 收益最大化机制：最优拍卖 123
5.4 付费搜索拍卖128
5.5 当前热点与挑战130
参考文献131
6 合作博弈与社会选择
（王崇骏，南京大学）
6.1 研究背景133
6.2 合作博弈论135
6.2.1 合作博弈论的提出 135
6.2.2 合作博弈的一般表示 136
6.2.3 合作博弈的解 138
6.3 核与稳定集 139
6.3.1 核的提出139
6.3.2 核的计算方式 140
6.3.3 稳定集 141
6.4 核仁143
6.4.1 核仁的提出 143
6.4.2 核仁的计算方式 144
6.4.3 计算实例 145
6.5 Shapley 值150
6.5.1 Shapley 值的提出 150
6.5.2 Shapley 值的计算方式 151
6.5.3 计算实例 152
6.6 社会选择153
6.6.1 社会选择理论的提出 155
6.6.2 阿罗不可能性定理156
6.6.3 森的帕累托自由不可能定理 158
6.7 应用场景 161
6.7.1 合作博弈应用场景 161
6.7.2 社会选择应用场景 163
6.8 当前热点与挑战164
6.8.1 合作博弈研究趋势165
6.8.2 社会选择研究趋势 167
参考文献170
7 博弈学习
（高阳、孟林建、葛振兴，南京大学）
7.1 不完美信息扩展式博弈177
7.2 均衡计算179
7.2.1 纳什均衡 179
7.2.2 纳什均衡的计算 181
7.2.3 线性规划求解 182
7.2.4 遗憾最小化算法182
7.2.5 虚拟遗憾最小化算法 185
7.2.6 基于深度学习的方法 190
7.3 对手利用191
7.3.1 对手建模 192
7.3.2 对手利用的安全性 197
7.4 小结199
参考文献200
第四部分多智能体学习
8 单智能体强化学习
（章宗长、俞扬，南京大学）
8.1 研究背景207
8.2 强化学习的基本设定208
8.2.1 强化学习模型 208
8.2.2 马尔可夫决策过程 210
8.3 动态规划212
8.3.1 值迭代 213
8.3.2 策略迭代 214
8.4 表格式的强化学习215
8.4.1 免模型的学习 215
8.4.2 基于模型的学习217
8.5 深度强化学习219
8.5.1 基于值函数的深度强化学习 220
8.5.2 基于策略梯度的深度强化学习 227
8.5.3 基于行动者-评论家的深度强化学习 230
8.6 基准测试平台与实际应用234
8.6.1 基准测试平台 234
8.6.2 实际应用 237
8.7 当前热点与挑战238
8.8 小结 242
参考文献243
9 基于模型的强化学习
（张伟楠，上海交通大学；汪军，伦敦大学学院）
9.1 Dyna：基于模型的强化学习经典方法 249
9.2 打靶法250
9.3 基于模型的策略优化方法253
9.4 基于模型的方法：从单智能体到多智能体255
9.4.1 自适应对手智能体推演策略优化算法（AORPO） 256
9.4.2 其他多智能体强化学习的基于模型的方法258
9.5 小结260
参考文献262
10 多智能体合作学习
（张崇洁，清华大学）
10.1 研究背景263
10.2 合作学习问题描述265
10.3 基于值函数的合作多智能体强化学习算法265
10.3.1 值分解学习框架 266
10.3.2 线性值分解 268
10.3.3 单调值分解 269
10.3.4 IGM 完备值分解 270
10.4 基于策略的合作学习算法272
10.4.1 反事实策略梯度 272
10.4.2 多智能体深度确定性策略梯度 275
10.4.3 可分解的离策略多智能体策略梯度 277
10.5 基准测试集280
10.5.1 多智能体小球环境MPE 280
10.5.2 星际争霸Ⅱ 多智能体挑战SMAC 280
10.5.3 谷歌足球 281
10.5.4 多智能体合作测试集MACO 282
10.6 当前热点与挑战282
10.6.1 探索282
10.6.2 学习交流 283
10.6.3 共享学习 285
10.6.4 分层多智能体强化学习 286
10.6.5 离线多智能体强化学习 287
10.6.6 基于模型的多智能体合作学习 287
10.6.7 多智能体合作学习的理论分析 288
10.7 小结289
参考文献290
11 多智能体竞争学习
（郝建业、郑岩，天津大学）
11.1 研究背景298
11.2 竞争式问题描述 299
11.3 基于对手建模的竞争学习算法300
11.3.1 隐式的对手建模方法 300
11.3.2 显式的对手建模方法 309
11.4 基于群体自博弈的竞争学习算法315
11.4.1 自博弈机制 315
11.4.2 联盟训练 318
11.5 实际应用319
11.6 小结321
参考文献322
第五部分 分布式人工智能应用
12 安全博弈
（安波，新加波南洋理工大学；甘家瑞，牛津大学）
12.1 研究背景327
12.2 安全博弈模型与均衡329
12.2.1 Stackelberg 均衡 330
12.2.2 均衡求解333
12.2.3 Stackelberg 安全博弈模型及求解 334
12.2.4 安全博弈实例 337
12.3 复杂环境下的安全博弈 339
12.3.1 信息不完全与不确定性 339
12.3.2 复杂策略空间的处理 343
12.3.3 动态安全博弈 346
12.4 实际应用与成功案例349
12.4.1 重要基础设施保护 349
12.4.2 交通系统安保调度 351
12.4.3 打击环境资源犯罪与城市犯罪353
12.4.4 打击犯罪网络 354
12.4.5 其他应用354
12.5 当前热点与挑战354
12.5.1 研究热点 355
12.5.2 未来研究方向 357
12.5.3 未来应用领域 359
参考文献360
13 社交网络中的机制设计
（赵登吉，上海科技大学）
13.1 研究背景367
13.2 传播网络与传播机制369
13.3 VCG 在网络上的扩展373
13.3.1 具有传播激励的VCG 拍卖 373
13.3.2 传播拍卖的不可能性定理 374
13.4 基于关键传播路径的拍卖机制375
13.4.1 关键传播序列 375
13.4.2 信息传播机制 376
13.4.3 关键传播机制 378
13.4.4 阈值邻接机制 380
13.5 当前热点与挑战 381
参考文献382