目录

第Ⅰ部分　导　　论

第1章　序贯决策问题 3

1.1　目标读者 6

1.2　序贯决策问题领域 6

1.3　通用建模框架 8

1.4　序贯决策问题的策略设计 11

1.4.1　策略搜索 12

1.4.2　基于前瞻近似的策略 13

1.4.3　混合和匹配 14

1.4.4　4类的最优性 14

1.4.5　概述 14

1.5　学习 15

1.6　主题 16

1.6.1　混合学习和优化 16

1.6.2　将机器学习桥接到序贯决策 16

1.6.3　从确定性优化到随机优化 17

1.6.4　从单个智能体到多个智能体 19

1.7　建模方法 20

1.8　如何阅读本书 21

1.8.1　主题编排 21

1.8.2　如何阅读每一章 23

1.8.3　练习分类 24

1.9　参考文献注释 25

练习 25

参考文献 28

第2章　典型问题及其应用 29

2.1　典型问题 29

2.1.1　随机搜索——基于导数和无导数 30

2.1.2　决策树 32

2.1.3　马尔可夫决策过程 33

2.1.4　最优控制 35

2.1.5　近似动态规划 37

2.1.6　强化学习 37

2.1.7　最优停止 39

2.1.8　随机规划 41

2.1.9　多臂老虎机问题 42

2.1.10　模拟优化 44

2.1.11　主动学习 44

2.1.12　机会约束规划 45

2.1.13　模型预测控制 45

2.1.14　鲁棒优化 46

2.2　序贯决策问题的通用建模框架 47

2.2.1　序贯决策问题的通用模型 47

2.2.2　紧凑型建模 49

2.2.3　MDP/RL与最优控制建模框架 50

2.3　应用 51

2.3.1　报童问题 51

2.3.2　库存/储存问题 53

2.3.3　最短路径问题 55

2.3.4　一些车队管理问题 57

2.3.5　定价 59

2.3.6　医疗决策 59

2.3.7　科学探索 60

2.3.8　机器学习与序贯决策问题 61

2.4　参考文献注释 62

练习 66

参考文献 68

第3章　在线学习 69

3.1　序贯决策的机器学习 69

3.1.1　随机优化中的观察和数据 70

3.1.2　索引输入xn和响应yn+1 70

3.1.3　正在学习的函数 71

3.1.4　序贯学习：从很少的数据到更多的数据 72

3.1.5　近似策略 72

3.1.6　从数据分析到决策分析 74

3.1.7　批量学习与在线学习 75

3.2　使用指数平滑的自适应学习 75

3.3　使用频率更新的查找表 76

3.4　使用贝叶斯更新的查找表 77

3.4.1　独立信念的更新公式 77

3.4.2　相关信念的更新 78

3.4.3　高斯过程回归 81

3.5　计算偏差和方差* 82

3.6　查找表和聚合* 84

3.6.1　分层聚合 84

3.6.2　不同聚合水平的估计 86

3.6.3　组合多个聚合级别 89

3.7　线性参数模型 91

3.7.1　线性回归 92

3.7.2　稀疏加性模型和Lasso 93

3.8　线性模型的递归最小二乘法 94

3.8.1　平稳数据的递归最小二乘法 95

3.8.2　非平稳数据的递归最小二乘法* 96

3.8.3　使用多次观察的递归估计* 97

3.9　非线性参数模型 98

3.9.1　最大似然估计 98

3.9.2　采样信念模型 99

3.9.3　神经网络——参数* 100

3.9.4　神经网络的局限性 104

3.10　非参数模型* 105

3.10.1　k-最近邻 106

3.10.2　内核回归 106

3.10.3　局部多项式回归 108

3.10.4　深度神经网络 108

3.10.5　支持向量机 109

3.10.6　索引函数、树结构和聚类 110

3.10.7　非参数模型评注 111

3.11　非平稳学习* 112

3.11.1　非平稳学习I——鞅真理 112

3.11.2　非平稳学习II——瞬时真理 113

3.11.3　学习过程 113

3.12　维数灾难 114

3.13　自适应学习中的近似架构设计 116

3.14　为什么有效** 117

3.14.1　递归估计公式的推导 117

3.14.2　谢尔曼-莫里森更新公式 119

3.14.3　分层估计中的相关性 120

3.14.4　命题3.14.1的证明 122

3.15　参考文献注释 124

练习 125

参考文献 128

第4章　随机搜索简介 129

4.1　基本随机优化问题阐释 130

4.2　确定性方法 133

4.2.1　“随机”最短路径问题 133

4.2.2　具有已知分布的报童问题 133

4.2.3　机会约束优化 134

4.2.4　最优控制 134

4.2.5　离散马尔可夫决策过程 135

4.2.6　备注 136

4.3　采样模型 136

4.3.1　建立采样模型 137

4.3.2　收敛性 139

4.3.3　创建采样模型 140

4.3.4　分解策略* 142

4.4　自适应学习算法 143

4.4.1　建模自适应学习问题 143

4.4.2　在线与离线的应用 144

4.4.3　用于学习的目标函数 145

4.4.4　设计策略 148

4.5　小结 148

4.6　参考文献注释 149

练习 150

参考文献 154

第Ⅱ部分　随机搜索

第5章　基于导数的随机搜索 156

5.1　一些示例应用程序 158

5.2　建模不确定性 160

5.2.1 　训练不确定性160

5.2.2　模型不确定性S0 160

5.2.3　测试不确定性 161

5.2.4　策略评估 162

5.2.5　结束语 162

5.3　随机梯度法 162

5.3.1　随机梯度算法 163

5.3.2　步长简介 164

5.3.3　评估随机梯度算法 165

5.3.4　符号注释 166

5.4　梯度样式 166

5.4.1　梯度平滑 166

5.4.2　二阶方法 167

5.4.3　有限差分 168

5.4.4　SPSA 169

5.4.5　约束问题 170

5.5　神经网络参数优化* 171

5.5.1　计算梯度 172

5.5.2　随机梯度算法 173

5.6　作为序贯决策问题的随机梯度算法 174

5.7　实证问题 175

5.8　瞬态问题* 176

5.9　理论性能* 176

5.10　为什么有效 177

5.10.1　概率论基础知识 177

5.10.2　一个旧证明* 178

5.10.3　更现代的证明** 181

5.11　参考文献注释 186

练习 187

参考文献 191

第6章　步长策略 192

6.1　确定性步长策略 194

6.1.1　收敛性 194

6.1.2　确定性策略集锦 196

6.2　自适应步长策略 199

6.2.1　自适应步长的情况 200

6.2.2　收敛条件 200

6.2.3　随机策略集锦 201

6.2.4　实验笔记 204

6.3　最优步长策略* 204

6.3.1　平稳数据的最佳步长 205

6.3.2　非平稳数据的最佳步长1 207

6.3.3　非平稳数据的最佳步长2 208

6.4　近似值迭代的最佳步长* 212

6.5　收敛 214

6.6　如何选择步长策略 214

6.7　为什么有效* 216

6.8　参考文献注释 218

练习 218

参考文献 222

第7章　无导数随机搜索 223

7.1　无导数随机搜索概述 225

7.1.1　应用和时间尺度 225

7.1.2　无导数随机搜索领域 226

7.1.3　多臂老虎机故事 226

7.1.4　从被动学习到主动学习再到老虎机问题 228

7.2　无导数随机搜索建模 229

7.2.1　通用模型 229

7.2.2　示例：优化制造过程 231

7.2.3　主要问题类别 232

7.3　设计策略 232

7.4　策略函数近似 235

7.5　成本函数近似 236

7.6　基于价值函数近似的策略 238

7.6.1　最优策略 239

7.6.2　贝塔-伯努利信念模型 240

7.6.3　后向近似动态规划 241

7.6.4　稳态学习的Gittins指数* 243

7.7　基于直接前瞻模型的策略 247

7.7.1　何时需要前瞻策略 247

7.7.2　单周期前瞻策略 248

7.7.3　有约束的多周期前瞻 250

7.7.4　多周期确定性前瞻 252

7.7.5　多周期随机前瞻策略 253

7.7.6　混合直接前瞻 256

7.8　知识梯度(续)* 257

7.8.1　信念模型 257

7.8.2　使最终回报最大化的知识梯度 258

7.8.3　累积回报最大化的知识梯度 262

7.8.4　采样信念模型的知识梯度* 263

7.8.5　相关信念的知识梯度 267

7.9　批量学习 272

7.10　模拟优化* 273

7.10.1　无差异区域算法 273

7.10.2　最优计算预算分配 274

7.11　评估策略* 276

7.11.1　备选方案性能指标* 276

7.11.2　最优视角* 281

7.12　设计策略 283

7.12.1　策略的特点 283

7.12.2　缩放效果 284

7.12.3　调整 285

7.13　扩展* 286

7.13.1　非平稳环境中的学习 286

7.13.2　设计策略的策略 287

7.13.3　瞬态学习模型 288

7.13.4　瞬态问题的知识梯度 288

7.13.5　使用大型或连续选择集学习 289

7.13.6　利用外部状态信息学习——上下文老虎机问题 291

7.13.7　状态相关问题与状态无关问题 293

7.14　参考文献注释 294

练习 296

参考文献 304

第Ⅲ部分　状态相关问题

第8章　状态相关的应用 307

8.1　图问题 308

8.1.1　随机最短路径问题 309

8.1.2　漂泊的货车司机 309

8.1.3　变压器更换问题 310

8.1.4　资产评估 311

8.2　库存问题 313

8.2.1　基本库存问题 313

8.2.2　进阶库存问题 314

8.2.3　滞后资产收购问题 315

8.2.4　批量补货问题 316

8.3　复杂的资源配置问题 318

8.3.1　动态分配问题 318

8.3.2　血液管理问题 321

8.4　状态相关的学习问题 326

8.4.1　医疗决策 327

8.4.2　实验室实验 327

8.4.3　广告点击竞价 328

8.4.4　信息收集最短路径问题 328

8.5　问题类序列 329

8.6　参考文献注释 330

练习 330

参考文献 333

第9章　序贯决策问题建模 334

9.1　简单建模 337

9.2　符号风格 340

9.3　时间建模 342

9.4　系统的状态 344

9.4.1　定义状态变量 344

9.4.2　系统的三种状态 347

9.4.3　初始状态与后续状态“” 349

9.4.4　滞后状态变量* 350

9.4.5　决策后状态变量* 351

9.4.6　最短路径图解 353

9.4.7　信念状态* 354

9.4.8　潜在变量* 355

9.4.9　滚动预测* 356

9.4.10　平面与因子状态表示* 357

9.4.11　程序员对状态变量的看法 357

9.5　建模决策 358

9.5.1　决策类型 359

9.5.2　初始决策与后续决策“” 360

9.5.3　战略、战术和执行决策 360

9.5.4　约束 361

9.5.5　策略介绍 362

9.6　外生信息过程 362

9.6.1　信息过程的基本符号 362

9.6.2　结果和场景 364

9.6.3　滞后的信息过程* 365

9.6.4　信息过程模型* 366

9.6.5　监督过程* 368

9.7　转移函数 368

9.7.1　通用模型 369

9.7.2　无模型动态规划 370

9.7.3　外生转移 370

9.8　目标函数 371

9.8.1　性能指标 371

9.8.2　优化策略 372

9.8.3　最优策略对的依赖性 372

9.8.4　状态相关的变量 373

9.8.5　不确定算子 374

9.9　示例：能量储存模型 375

9.9.1　使用时间序列价格模型 376

9.9.2　使用被动学习 376

9.9.3　使用主动学习 377

9.9.4　使用滚动预测 377

9.10　基本模型和前瞻模型 378

9.11　问题的分类* 379

9.12　策略评估* 381

9.13　高级概率建模概念** 383

9.13.1　信息的测度论视角** 383

9.13.2　策略和可测量性 386

9.14　展望 387

9.15　参考文献注释 388

练习 390

参考文献 399

第10章　不确定性建模 400

10.1　不确定性来源 401

10.1.1　观察的误差 402

10.1.2　外生的不确定性 403

10.1.3　预测的不确定性 404

10.1.4　推断(或诊断)的不确定性 405

10.1.5　实验的可变性 406

10.1.6　模型的不确定性 407

10.1.7　转移的不确定性 408

10.1.8　控制/实现的不确定性 409

10.1.9　通信误差和偏差 409

10.1.10　算法的不稳定性 409

10.1.11　目标的不确定性 410

10.1.12　政治/监管的不确定性 410

10.1.13　讨论 411

10.2　建模案例研究：COVID-19疫情 411

10.3　随机建模 412

10.3.1　外生信息采样 412

10.3.2　分布类型 413

10.3.3　建模样本路径 413

10.3.4　状态动作相关过程 414

10.3.5　相关性建模 415

10.4　蒙特卡洛模拟 416

10.4.1　生成均匀分布[0,1]随机变量 416

10.4.2　均匀和正态随机变量 417

10.4.3　从逆累积分布生成随机变量 419

10.4.4　分位数分布的逆累积 420

10.4.5　不确定参数分布 420

10.5　案例研究：电价建模 422

10.5.1　均值回归 423

10.5.2　跳跃—扩散模型 423

10.5.3　分位数分布 424

10.5.4　机制转变 424

10.5.5　交叉时间 425

10.6　采样与采样模型 426

10.6.1　迭代采样：一种随机梯度算法 426

10.6.2　静态采样：求解一个采样模型 427

10.6.3　贝叶斯更新采样表示 427

10.7　结束语 428

10.8　参考文献注释 428

练习 429

参考文献 431

第11章　策略设计 432

11.1　从优化到机器学习再到序贯决策问题 433

11.2　策略类别 434

11.3　策略函数近似 437

11.4　成本函数近似 439

11.5　价值函数近似 440

11.6　直接前瞻近似 441

11.6.1　基本理念 441

11.6.2　前瞻问题建模 443

11.6.3　策略中的策略 444

11.7　混合策略 445

11.7.1　成本函数近似与策略函数近似 445

11.7.2　具有价值函数近似的前瞻策略 446

11.7.3　具有成本函数近似的前瞻策略 447

11.7.4　具有卷展栏启发式和查找表策略的树搜索 447

11.7.5　兼具策略函数近似的价值函数近似 447

11.7.6　使用ADP和策略搜索拟合价值函数 448

11.8　随机策略 449

11.9　示例：重新审视储能模型 450

11.9.1　策略函数近似 450

11.9.2　成本函数近似 450

11.9.3　价值函数近似 451

11.9.4　确定性前瞻 451

11.9.5　混合前瞻—成本函数近似 451

11.9.6　实验测试 451

11.10　选择策略类 452

11.10.1　策略类 453

11.10.2　策略复杂性——计算权衡 456

11.10.3　筛选问题 458

11.11　策略评估 459

11.12　参数调整 460

11.12.1　软问题 461

11.12.2　跨策略类搜索 462

11.13　参考文献注释 463

练习 463

参考文献 466

第Ⅳ部分　策略搜索

第12章　策略函数近似和策略搜索 469

12.1　作为序贯决策问题的策略搜索 470

12.2　策略函数近似的分类 471

12.2.1　查找表策略 472

12.2.2　离散动作的玻尔兹曼策略 472

12.2.3　线性决策规则 473

12.2.4　单调策略 473

12.2.5　非线性策略 474

12.2.6　非参数/局部线性策略 475

12.2.7　上下文策略 476

12.3　问题特征 476

12.4　策略查询的类型 477

12.5　基于数值导数的策略搜索 479

12.6　无导数策略搜索方法 480

12.6.1　信念模型 480

12.6.2　通过扰动PFA学习 481

12.6.3　学习CFA 483

12.6.4　使用知识梯度的DLA 484

12.6.5　说明 486

12.7　连续序贯问题的精确导数* 486

12.8　离散动态规划的精确导数** 487

12.8.1　随机策略 488

12.8.2　目标函数 489

12.8.3　策略梯度定理 489

12.8.4　计算策略梯度 490

12.9　监督学习 491

12.10　有效的原因 493

12.11　参考文献注释 495

练习 496

参考文献 501

第13章　成本函数近似 502

13.1　参数CFA的一般公式 504

13.2　目标修正的CFA 504

13.2.1　线性成本函数修正 504

13.2.2　动态分配问题的CFA 505

13.2.3　动态最短路径 506

13.2.4　动态交易策略 509

13.2.5　讨论 511

13.3　约束修正的CFA 511

13.3.1　约束修正CFA的通用公式 512

13.3.2　血液管理问题 513

13.3.3　滚动预测的储能示例 514

13.4　参考文献注释 520

练习 520

参考文献 522

第Ⅴ部分　前瞻策略

第14章　精确动态规划 527

14.1　离散动态规划 528

14.2　最优方程 529

14.2.1　贝尔曼方程 530

14.2.2　计算转移矩阵 533

14.2.3　随机贡献 533

14.2.4　使用算子符号的贝尔曼方程* 534

14.3　有限时域问题 535

14.4　具有精确解的连续问题 537

14.4.1　赌博问题 537

14.4.2　持续预算问题 539

14.5　无限时域问题* 540

14.6　无限时域问题的值迭代* 542

14.6.1　高斯-塞德尔变体 543

14.6.2　相对值迭代 543

14.6.3　收敛界限和速度 544

14.7　无限时域问题的策略迭代* 546

14.8　混合值—策略迭代* 548

14.9　平均回报动态规划* 549

14.10　动态规划的线性规划方法** 550

14.11　线性二次调节 550

14.12　有效的原因** 552

14.12.1　最优方程 552

14.12.2　值迭代的收敛性 556

14.12.3　值迭代单调性 560

14.12.4　从值迭代中界定误差 561

14.12.5　随机化策略 562

14.13　参考文献注释 563

练习 563

参考文献 570

第15章　后向近似动态规划 571

15.1　有限时域问题的后向近似动态规划 572

15.1.1　准备工作 572

15.1.2　使用查找表的后向ADP 574

15.1.3　具有连续近似的后向ADP算法 575

15.2　无限时域问题的拟合值迭代 578

15.3　价值函数近似策略 579

15.3.1　线性模型 579

15.3.2　单调函数 580

15.3.3　其他近似模型 582

15.4　计算观察 582

15.4.1　后向ADP的实验基准 582

15.4.2　计算注意事项 586

15.5　参考文献注释 586

练习 587

参考文献 590

第16章　前向ADP I：策略价值 591

16.1　对策略价值进行采样 592

16.1.1　有限时域问题的直接策略评估 592

16.1.2　无限时域问题的策略评估 593

16.1.3　时间差分更新 595

16.1.4　TD(𝜆) 596

16.1.5　TD(0)和近似值迭代 597

16.1.6　无限时域问题的TD学习 598

16.2　随机近似方法 600

16.3　使用线性模型的贝尔曼方程* 601

16.3.1　基于矩阵的推导** 602

16.3.2　基于模拟的实现 604

16.3.3　最小二乘时间差分学习 604

16.3.4　最小二乘法策略评估 605

16.4　使用单一状态分析TD(0)、LSTD和LSPE* 605

16.4.1　递归最小二乘法和TD(0) 606

16.4.2　LSPE 607

16.4.3　LSTD 607

16.4.4　讨论 607

16.5　基于梯度的近似值迭代方法* 608

16.5.1　线性模型的近似值迭代** 608

16.5.2　线性模型的几何视图* 612

16.6　基于贝叶斯学习的价值函数近似* 613

16.6.1　最小化无限时域问题的偏差 614

16.6.2　具有相关信念的查找表 614

16.6.3　参数模型 615

16.6.4　创建先验 615

16.7　学习算法和步长 616

16.7.1　最小二乘时间差分 616

16.7.2　最小二乘法策略评估 617

16.7.3　递归最小二乘法 617

16.7.4　近似值迭代的1/n收敛界 618

16.7.5　讨论 619

16.8　参考文献注释 620

练习 621

参考文献 623

第17章　前向ADP II：策略优化 624

17.1　算法策略概述 625

17.2　使用查找表的近似值迭代和Q学习 627

17.2.1　使用决策前状态变量的值迭代 627

17.2.2　Q学习 628

17.2.3　使用决策后状态变量的值迭代 630

17.2.4　使用反向传播的值迭代 632

17.3　学习方式 635

17.3.1　离线学习 635

17.3.2　从离线到在线 636

17.3.3　评估离线学习策略和在线学习策略 637

17.3.4　前瞻策略 638

17.4　使用线性模型的近似值迭代 638

17.5　在线策略学习与离线策略学习以及探索—利用问题 640

17.5.1　术语 641

17.5.2　使用查找表学习 641

17.5.3　使用广义信念模型学习 642

17.6　应用 644

17.6.1　美国期权定价 644

17.6.2　逆向井字棋 647

17.6.3　确定性问题的近似动态规划 648

17.7　近似策略迭代 648

17.7.1　使用查找表的有限时域问题 649

17.7.2　使用线性模型的有限时域问题 650

17.7.3　使用线性模型求解无限时域问题的LSTD 651

17.8　演员—评论家范式 653

17.9　最大算子的统计偏差* 655

17.10　使用线性模型的线性规划方法* 657

17.11　稳态应用的有限时域近似 660

17.12　参考文献注释 661

练习 662

参考文献 666

第18章　前向ADP III：凸性资源分配问题 667

18.1　资源分配问题 669

18.1.1　报童问题 669

18.1.2　两阶段资源分配问题 671

18.1.3　一个通用多周期资源分配模型* 672

18.2　价值与边际价值 674

18.3　标量函数的分段线性近似 675

18.3.1　调平算法 676

18.3.2　CAVE算法 677

18.4　回归方法 678

18.5　可分的分段线性近似 680

18.6　非可分近似的Benders分解** 682

18.6.1　两阶段问题的Benders分解 682

18.6.2　具有正则化的Benders的渐近分析** 686

18.6.3　正则化Benders 688

18.7　高维应用的线性近似 689

18.8　具有外生信息状态的资源分配 690

18.9　结束语 691

18.10　参考文献注释 691

练习 693

参考文献 697

第19章　直接前瞻策略 698

19.1　使用前瞻模型的最优策略 700

19.2　创建近似前瞻模型 703

19.2.1　前瞻模型建模 704

19.2.2　近似前瞻模型策略 704

19.3　前瞻模型中的修改目标 708

19.3.1　风险管理 708

19.3.2　多目标问题的效用函数 712

19.3.3　模型折扣 713

19.4　评估DLA策略 713

19.4.1　在模拟器中评估策略 714

19.4.2　评估风险调整策略 715

19.4.3　在现场评估策略 716

19.4.4　调整直接前瞻策略 716

19.5　使用DLA的原因 717

19.6　确定性前瞻 718

19.6.1　确定性前瞻：最短路径问题 719

19.6.2　参数化前瞻策略 721

19.7　随机前瞻策略简介 722

19.7.1　前瞻PFA 722

19.7.2　前瞻CFA 723

19.7.3　前瞻模型的前瞻VFA 724

19.7.4　前瞻模型的前瞻DLA 724

19.7.5　讨论 725

19.8　离散决策的蒙特卡洛树搜索 725

19.8.1　基本思路 725

19.8.2　蒙特卡洛树搜索的步骤 726

19.8.3　讨论 729

19.8.4　乐观蒙特卡洛树搜索 731

19.9　向量决策的两阶段随机规划* 732

19.9.1　基本两阶段随机规划 732

19.9.2　序贯问题的两阶段近似 734

19.9.3　讨论 736

19.10　对DLA策略的评论 736

19.11　参考文献注释 737

练习 739

参考文献 741

第Ⅵ部分　多智能体系统

第20章　多智能体建模与学习 744

20.1　多智能体系统概述 745

20.1.1　多智能体系统维度 745

20.1.2　通信 746

20.1.3　多智能体系统建模 747

20.1.4　控制架构 750

20.2　学习问题——流感缓解 751

20.2.1　模型1：静态模型 751

20.2.2　流感模型的变体 752

20.2.3　双智能体学习模型 755

20.2.4　双智能体模型的转移函数 757

20.2.5　流感问题的策略设计 758

20.3　POMDP角度* 762

20.4　双智能体报童问题 764

20.5　多个独立智能体——HVAC控制器模型 768

20.5.1　建模 768

20.5.2　设计策略 769

20.6　合作智能体——空间分布血液管理问题 771

20.7　结束语 773

20.8　有效的原因 774

20.9　参考文献注释 775

练习 776

参考文献 780