目录

第1章  折扣问题——理论 1

1.1  总费用最小化——介绍 1

1.1.1  有限阶段动态规划算法 3

1.1.2  符号简写与单调性 4

1.1.3  无穷阶段结果的预览 6

1.1.4  随机的和依赖历史的策略 7

1.2  折扣问题——各阶段费用有界 9

1.3  调度与多柄老虎机问题 15

1.3.1  项目的指标 16

1.3.2  项目逐个退出策略 17

1.4  折扣连续时间问题 23

1.5  压缩映射的作用 32

1.5.1  极大模压缩 33

1.5.2  折扣问题——单阶段费用无界 38

1.6  折扣动态规划的一般形式 40

1.6.1  压缩与单调性的基本结论 44

1.6.2  折扣动态博弈 49

1.7  注释、参考文献及习题 50

习题 51

第2章  折扣问题——计算方法 57

2.1  马尔可夫决策问题 57

2.2  值迭代 59

2.2.1  值迭代的单调误差界 59

2.2.2  值迭代的变形 65

2.2.3  Q-学习 67

2.3  策略迭代 69

2.3.1  针对费用的策略迭代 69

2.3.2  Q-因子的策略迭代 72

2.3.3  乐观策略迭代 73

2.3.4  有限前瞻策略和滚动 75

2.4  线性规划方法 79

2.5  一般折扣问题的方法 81

2.5.1  采用近似的有限前瞻策略 83

2.5.2  推广的值迭代 85

2.5.3  近似值迭代 86

2.5.4  推广的策略迭代 87

2.5.5  推广的乐观策略迭代 90

2.5.6  近似策略迭代 94

2.5.7  数学规划 97

2.6  异步方法 98

2.6.1  异步值迭代 98

2.6.2  异步策略迭代 102

2.6.3  具有均一不动点的策略迭代 105

2.7  注释、资源和习题 110

习题 112

第3章  随机最短路问题 122

3.1  问题建模 122

3.2  主要结论 124

3.3  基本压缩性质 130

3.4  值迭代 131

3.4.1  有限步终止的条件 131

3.4.2  异步值迭代 133

3.5  策略迭代 134

3.5.1  乐观策略迭代 135

3.5.2  近似策略迭代 136

3.5.3  具有不合适策略的策略迭代 137

3.5.4  具有均一不动点的异步策略迭代 140

3.6  可数状态问题 143

3.7  注释、资源和习题 145

习题 146

第4章  无折扣问题 151

4.1  每阶段的费用无界 151

4.1.1  主要结论 152

4.1.2  值迭代 158

4.1.3  其他计算方法 163

4.2  线性系统和二次费用 163

4.3  库存控制 165

4.4  最优停止 167

4.5  最优博弈策略 171

4.6  连续时间问题——排队的控制 177

4.7  非平稳和周期性问题 183

4.8  注释、资源和习题 187

习题 188

第5章  每阶段平均费用问题 196

5.1  有限空间平均费用模型 196

5.1.1  与折扣费用问题的关系 198

5.1.2  Blackwell 最优策略 203

5.1.3  最优性条件 210

5.2  所有初始状态的平均费用相等的条件 213

5.3  值迭代 217

5.3.1  单链值迭代 219

5.3.2  多链值迭代 231

5.4  策略迭代 236

5.4.1  单链策略迭代 236

5.4.2  多链策略迭代 240

5.5  线性规划 244

5.6  无穷空间平均费用模型 248

5.6.1  最优性的充分条件 254

5.6.2  有限状态空间和无限控制空间 255

5.6.3  可数状态——消失的折扣方法 262

5.6.4  可数状态——压缩方法 264

5.6.5  具有二次费用的线性系统 267

5.7  注释、资源和习题 268

习题 270

第6章  近似动态规划：折扣模型 279

6.1  基于仿真的费用近似的一般性问题 280

6.1.1  近似结构 280

6.1.2  基于仿真的近似策略迭代 284

6.1.3  直接和间接近似 288

6.1.4  蒙特卡罗仿真 289

6.1.5  简化 295

6.2  直接策略评价——梯度法 298

6.3  策略评价的投影方程方法 302

6.3.1  投影贝尔曼方程 303

6.3.2  投影方程的矩阵形式 305

6.3.3  基于仿真的估计方法 308

6.3.4  LSTD、LSPE 和TD(0) 方法 310

6.3.5  乐观版本 312

6.3.6  多步基于仿真的方法 313

6.3.7  提要 320

6.4  策略迭代问题 322

6.4.1  基于几何采样的搜索增强 324

6.4.2  基于离线策略方法的搜索增强 332

6.4.3  策略振荡——震颤 334

6.5  聚集方法 339

6.5.1  基于聚集问题的费用近似 344

6.5.2  通过增广问题的费用近似 346

6.5.3  多步聚集 350

6.5.4  异步分布聚集 351

6.6  Q-学习 353

6.6.1  Q-学习：随机值迭代算法 353

6.6.2  Q-学习和策略迭代 355

6.6.3  Q-因子近似和投影方程 356

6.6.4  最优停止问题的Q-学习 358

6.6.5  Q-学习和聚集 362

6.6.6  有限阶段Q-学习 364

6.7  注释、资源和习题 365

习题 370

第7章  近似动态规划：无折扣模型及推广 380

7.1  随机最短路问题 380

7.2  平均费用问题 384

7.2.1  近似策略评价 384

7.2.2  近似策略迭代 391

7.2.3  平均费用问题的Q-学习 392

7.3  一般问题和蒙特卡罗线性代数 395

7.3.1  投影方程 401

7.3.2  矩阵逆合迭代方法 406

7.3.3  多步方法 412

7.3.4  最优停止的Q-学习的推广 418

7.3.5  方程误差方法 420

7.3.6  倾斜投影 424

7.3.7  推广聚集 426

7.3.8  奇异线性系统的确定性方法 428

7.3.9  奇异线性系统的随机方法 436

7.4  在策略空间的近似 445

7.4.1  梯度公式 445

7.4.2  通过仿真计算梯度 446

7.4.3  梯度评价的关键特征 448

7.4.4  策略和值空间的近似 450

7.5  注释、资源和习题 450

习题 453

附录A  动态规划中的测度论问题 460

A.1  两阶段例子 460

A.2  可测问题的解决方法 463

参考文献 470

??

??

??