分布式人工智能

第一部分分布式人工智能簡介
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 多智能體規(guī)劃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 當前熱點與挑戰(zhàn)18
1.4.1 超大規(guī)模分布式人工智能系統(tǒng) 18
1.4.2 分布式人工智能系統(tǒng)的魯棒性和安全性 19
1.4.3 分布式人工智能決策的可解釋性 19
1.4.4 將傳統(tǒng)和深度學習的方法結合 20
參考文獻
第二部分分布式規(guī)劃與優(yōu)化
2 分布式規(guī)劃
（吳鋒，中國科技大學）
2.1 研究背景 9
2.2 分布式規(guī)劃的決策模型31
2.3 分布式規(guī)劃的離線算法36
2.3.1 離線精確規(guī)劃算法37
2.3.2 離線近似規(guī)劃算法 39
2.4 分布式規(guī)劃的在線算法46
2.4.1 在線協(xié)調機制 46
2.4.2 在線通信策略 48
2.5 當前熱點與挑戰(zhàn) 52
參考文獻 54
3 分布式約束優(yōu)化
（陳自郁，重慶大學）
3.1 研究背景58
3.2 分布式約束優(yōu)化問題59
3.2.1 約束網(wǎng)絡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 當前熱點與挑戰(zhàn)85
參考文獻 86
第三部分多智能體博弈
4 納什均衡求解
（鄧小鐵，北京大學；劉正陽，北京理工大學）
4.1 研究背景 93
4.2 正規(guī)形式博弈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 當前熱點與挑戰(zhàn)108
參考文獻 110
5 機制設計
（沈蔚然，中國人民大學；唐平中，清華大學）
5.1 研究背景112
5.2 什么是機制 113
5.2.1 社會選擇函數(shù) 113
5.2.2 機制的實現(xiàn)與顯示原理113
5.3 拍賣機制設計 118
5.3.1 性質與設計目標 119
5.3.2 社會福利最大化機制：VCG 機制 121
5.3.3 收益最大化機制：最優(yōu)拍賣 123
5.4 付費搜索拍賣128
5.5 當前熱點與挑戰(zhàn)130
參考文獻131
6 合作博弈與社會選擇
（王崇駿，南京大學）
6.1 研究背景133
6.2 合作博弈論135
6.2.1 合作博弈論的提出 135
6.2.2 合作博弈的一般表示 136
6.2.3 合作博弈的解 138
6.3 核與穩(wěn)定集 139
6.3.1 核的提出139
6.3.2 核的計算方式 140
6.3.3 穩(wěn)定集 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 當前熱點與挑戰(zhàn)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 線性規(guī)劃求解 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 動態(tài)規(guī)劃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 基于值函數(shù)的深度強化學習 220
8.5.2 基于策略梯度的深度強化學習 227
8.5.3 基于行動者-評論家的深度強化學習 230
8.6 基準測試平臺與實際應用234
8.6.1 基準測試平臺 234
8.6.2 實際應用 237
8.7 當前熱點與挑戰(zhàn)238
8.8 小結 242
參考文獻243
9 基于模型的強化學習
（張偉楠，上海交通大學；汪軍，倫敦大學學院）
9.1 Dyna：基于模型的強化學習經典方法 249
9.2 打靶法250
9.3 基于模型的策略優(yōu)化方法253
9.4 基于模型的方法：從單智能體到多智能體255
9.4.1 自適應對手智能體推演策略優(yōu)化算法（AORPO） 256
9.4.2 其他多智能體強化學習的基于模型的方法258
9.5 小結260
參考文獻262
10 多智能體合作學習
（張崇潔，清華大學）
10.1 研究背景263
10.2 合作學習問題描述265
10.3 基于值函數(shù)的合作多智能體強化學習算法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 多智能體小球環(huán)境MPE 280
10.5.2 星際爭霸Ⅱ 多智能體挑戰(zhàn)SMAC 280
10.5.3 谷歌足球 281
10.5.4 多智能體合作測試集MACO 282
10.6 當前熱點與挑戰(zhàn)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 多智能體競爭學習
（郝建業(yè)、鄭巖，天津大學）
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 聯(lián)盟訓練 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 復雜環(huán)境下的安全博弈 339
12.3.1 信息不完全與不確定性 339
12.3.2 復雜策略空間的處理 343
12.3.3 動態(tài)安全博弈 346
12.4 實際應用與成功案例349
12.4.1 重要基礎設施保護 349
12.4.2 交通系統(tǒng)安保調度 351
12.4.3 打擊環(huán)境資源犯罪與城市犯罪353
12.4.4 打擊犯罪網(wǎng)絡 354
12.4.5 其他應用354
12.5 當前熱點與挑戰(zhàn)354
12.5.1 研究熱點 355
12.5.2 未來研究方向 357
12.5.3 未來應用領域 359
參考文獻360
13 社交網(wǎng)絡中的機制設計
（趙登吉，上?？萍即髮W）
13.1 研究背景367
13.2 傳播網(wǎng)絡與傳播機制369
13.3 VCG 在網(wǎng)絡上的擴展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 當前熱點與挑戰(zhàn) 381
參考文獻382