分佈式人工智能

安波是南洋理工大學校長委員會講席副教授和南洋理工大學人工智能研究院聯席院長。
主要研究領域包括人工智能、多智能體系統、算法博弈論、強化學習、及優化。
有100餘篇論文發表在國際頂級會議AAMAS、IJCAI、AAAI、KDD、UAI、
EC、WWW、ICLR、NeurIPS、ICML以及著名學術期刊JAAMAS和AIJ。
曾獲IFAAMAS傑出博士論文獎、 美國海岸警衛隊的卓越運營獎、AAMAS最佳應用論文獎、IAAI創新應用論文獎，
DAI最佳論文獎，INFORMS Daniel H. Wagner傑出運籌學應用獎，以及南洋青年研究獎等榮譽。
受邀在IJCAI'17上做Early Career Spotlight talk。獲得2017年微軟合作AI挑戰賽的冠軍。
入選2018年IEEE Intelligent Systems"AI's 10 to Watch”。
他是AIJ, JAAMAS, IEEE Intelligent Systems, JAIR， ACM TIST的Associate Editor。
他是AAMAS'20的程序委員會主席。
當選國際智能體及多智能體系統協會理事會成員及AAAI 高級會員。

第一部分分佈式人工智能簡介
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