動態規劃與最優控制：近似動態規劃(第Ⅱ卷)（簡體書）

德梅萃·P.博塞克斯Dimitri Bertsekas曾在希臘國立雅典技術大學學習機械與電機工程，之後從麻省理工學院獲得系統科學博士學位。曾先後在斯坦福大學工程與經濟系統系和伊利諾伊大學香檳分校的電機工程系任教。1979年以來，他一直在麻省理工學院電機工程與計算機科學系任教，現任麥卡菲工程教授。其研究涉及多個領域，包括優化、控制、大規模計算和數據通信網絡，並與其教學和著書工作聯繫緊密。他已撰寫14本著作以及眾多論文，其中數本著作在麻省理工學院被用作教材。他與動態規劃之緣始於博士論文的研究，並通過學術論文、多本教材和學術專著一直延續至今。
Bertsekas教授因其著作《神經元動態規劃》(與John Tsitsiklis合著）榮獲1997年INFORMS授予的運籌學與計算機科學交叉領域的傑出研究成果獎、2000年希臘運籌學國家獎、2001年美國控制會議John R.Ragazzini獎以及2009年INFORMS Expository寫作獎。2001年，他因為“基礎性研究、實踐並教育優化/控制理論，特別是在數據通信網絡中的應用”當選美國工程院院士。
Bertsekas博士近些年出版的書包括《概率導論》第二版(2008年與John Tsitsiklis合著）和《凸優化理論》(2009)，均由雅典娜科學出版社出版。

序言

這是第II卷的一次重要修訂，增加了大量新內容，並對原有內容進行了重新組織。與第三版相比，篇幅增加了逾60%，大部分原有內容被重新組織並/或修訂。第II卷現在超過700頁，在篇幅上超過了第I卷。這幾乎可以被視為一本新書！

近似動態規劃已成為第II卷的核心內容，佔據全書超過一半的內容（最後兩章的全部以及第1～3章的大部分內容）。所以，第II卷可被視作我1996年的《神經元動態規劃》一書（與JohnTsitsiklis合著）的續作。現在這本書著重關注1996年之後新的研究成果。另一方面，本書保留了作為教科書的體系，一些內容以形象的甚至是不嚴格的程度來解釋，並引用期刊論文或《神經元動態規劃》一書參考更數學化的處理。

在擴展與重新組織的過程中，本書的結構變得更加模塊化，更適合課堂教學的使用。可在一學期約三分之一至一半時間內講完的核心內容，包括第1章（除了1.3節、1.4節與特定應用對應的內容），第2章和第6章合在一起自成體系。這些內容集中在折扣問題，可通過第3章和7.1節的隨機最短路問題的內容進行補充。實際上，這構成了我在麻省理工學院的課堂上講授的內容的一半（剩下的一半來自第I卷，包括那一卷的第6章，討論有限階段近似動態規劃問題）。在第5章、7.2節、7.4節中的平均費用問題的內容，正和負動態規劃模型的高級內容（7.3節）是最後的內容，可由教師根據實際情況選用。

因為本書的重點發生了轉移，我將更多的重心放在新近的研究成果上，包括近似動態規劃和基於仿真的方法，還包括異步迭代方法，這一方法以仿真為中心視角，因為仿真是天然異步的。許多這些內容源自從前一版發行以來六年時間裡我自己以及合作的研究內容。其中一些重點，按照在文中出現的順序，如下：

(1) 一般的折扣動態規劃問題的計算方法（2.5節和2.6節），包括2.5節中近似涉及的誤差界，2.6.2節和2.6.3節中的異步樂觀策略迭代方法，以及在博弈與極小極大問題，約束策略迭代和Q-學習中的應用。

(2) 涉及不合適策略隨機最短路問題的策略迭代方法（包括異步樂觀的版本）（3.4節）。

(3) 在6.3節～6.6 節中的多種基於仿真的近似值迭代和近似策略迭代方法的大量新增內容。

(4) 樂觀策略迭代新的可靠的Q-學習算法（2.6.3節和6.6.2節）。

(5) 多步方法的新的仿真技術，比如幾何採樣和自由形式採樣（6.4.1節和7.3.3節）。

(6) 7.3節中蒙特卡羅線性代數的大量新增內容（主要是大規模線性方程的基於仿真和近似解），這部分內容擴展了近似策略評價的動態規劃方法。

(1)～(5) 中的許多研究內容基於我與Janey(Huizhen)Yu的工作，而(6)中的大部分研究是基於我與JaneyYu和MengdiWang的工作。我與Janey和Mengdi的合作對本書有重要影響，在此深表感謝。我們的一些工作只以總結形式涉及，並稍作修改以適應本書的體係與目的；自然地，其表述上的不足應由我承擔全部責任。請讀者參閱我們的合作以及各自的學術論文，那裡更全面地描述了我們的研究，包括本書不能涵蓋的內容。

我向在近似動態規劃的研究中合作的同事一併致謝，他們以不同形式為這本書做出了貢獻，特別是VivekBorkar、AngeliaNedic和BenVanRoy。特別感謝JohnTsitsiklis，我與他在動態規劃與異步算法上有著逾三十年的交流與合作。我還想感謝來自許多同事的有益的交流，包括VivekFarias、EugeneFeinberg、WarrenPowell、MartinPuterman、UrielRothblum和BrunoScherrer。最後，我想感謝近十年來我動態規劃課堂上的諸多學生，他們耐心地使用尚在建設中的教材，並通過涉及廣泛應用領域的研究課題貢獻了他們的想法和經驗。

 

Dimitri P. Bertsekas

2012 年春

第1章折扣問題——理論
1.1總費用最小化——介紹
1.1.1有限階段動態規划算法
1.1.2符號簡寫與單調性
1.1.3無窮階段結果的預覽
1.1.4隨機的和依賴歷史的策略
1.2折扣問題——各階段費用有界
1.3調度與多柄老虎機問題
1.3.1項目的指標
1.3.2項目逐個退出策略
1.4折扣連續時間問題
1.5壓縮映射的作用
1.5.1極大模壓縮
1.5.2折扣問題——單階段費用無界
1.6折扣動態規劃的一般形式
1.6.1壓縮與單調性的基本結論
1.6.2折扣動態博弈
1.7註釋、參考文獻及習題
習題
第2章折扣問題——計算方法
2.1馬爾可夫決策問題
2.2值迭代
2.2.1值迭代的單調誤差界
2.2.2值迭代的變形
2.2.3 Q-學習
2.3策略迭代
2.3.1針對費用的策略迭代
2.3.2 Q-因子的策略迭代
2.3.3樂觀策略迭代
2.3.4有限前瞻策略和滾動
2.4線性規劃方法
2.5一般折扣問題的方法
2.5.1採用近似的有限前瞻策略
2.5.2推廣的值迭代
2.5.3近似值迭代
2.5.4推廣的策略迭代
2.5.5推廣的樂觀策略迭代
2.5.6近似策略迭代
2.5.7數學規劃
2.6異步方法
2.6.1異步值迭代
2.6.2異步策略迭代
2.6.3具有均一不動點的策略迭代
2.7註釋、資源和習題
習題
第3章隨機最短路問題
3.1問題建模
3.2主要結論
3.3基本壓縮性質
3.4值迭代
3.4.1有限步終止的條件
3.4.2異步值迭代
3.5策略迭代
3.5.1樂觀策略迭代
3.5. 2近似策略迭代
3.5.3具有不合適策略的策略迭代
3.5.4具有均一不動點的異步策略迭代
3.6可數狀態問題
3.7註釋、資源和習題
習題
第4章無折扣問題
4.1每階段的費用無界
4.1.1主要結論
4.1.2值迭代
4.1.3其他計算方法
4.2線性系統和二次費用
4.3庫存控制
4.4最優停止
4.5最優博弈策略
4.6連續時間問題——排隊的控制
4.7非平穩和周期性問題
4.8註釋、資源和習題
習題
第5章每階段平均費用問題
5.1有限空間平均費用模型
5.1.1與折扣費用問題的關係
5.1.2 Blackwell最優策略
5.1.3最優性條件
5.2所有初始狀態的平均費用相等的條件
5.3值迭代
5.3.1單鏈值迭代
5.3.2多鏈值迭代
5.4策略迭代
5.4 .1單鏈策略迭代
5.4.2多鏈策略迭代
5.5線性規劃
5.6無窮空間平均費用模型
5.6.1最優性的充分條件
5.6.2有限狀態空間和無限控制空間
5.6.3可數狀態——消失的折扣方法
5.6.4可數狀態——壓縮方法
5.6.5具有二次費用的線性系統
5.7註釋、資源和習題
習題
第6章近似動態規劃：折扣模型
6.1基於仿真的費用近似的一般性問題
6.1.1近似結構
6.1.2基於仿真的近似策略迭代
6.1.3直接和間接近似
6.1. 4蒙特卡羅仿真
6.1.5簡化
6.2直接策略評價——梯度法
6.3策略評價的投影方程方法
6.3.1投影貝爾曼方程
6.3.2投影方程的矩陣形式
6.3.3基於仿真的估計方法
6.3.4 LSTD、LSPE和TD(0)方法
6.3.5樂觀版本
6.3.6多步基於仿真的方法
6.3.7提要
6.4策略迭代問題
6.4.1基於幾何採樣的搜索增強
6.4.2基於離線策略方法的搜索增強
6.4.3策略振盪——震顫
6.5聚集方法
6.5.1基於聚集問題的費用近似
6.5.2通過增廣問題的費用近似
6.5.3多步聚集
6.5.4異步分佈聚集
6.6 Q-學習
6.6.1 Q-學習：隨機值迭代算法
6.6 .2 Q-學習和策略迭代
6.6.3 Q-因子近似和投影方程
6.6.4最優停止問題的Q-學習
6.6.5 Q-學習和聚集
6.6.6有限階段Q-學習
6.7註釋、資源和習題
習題
第7章近似動態規劃：無折扣模型及推廣
7.1隨機最短路問題
7.2平均費用問題
7.2.1近似策略評價
7.2.2近似策略迭代
7.2.3平均費用問題的Q-學習
7.3一般問題和蒙特卡羅線性代數
7.3.1投影方程
7.3.2矩陣逆合迭代方法
7.3.3多步方法
7.3.4最優停止的Q-學習的推廣
7.3.5方程誤差方法
7.3.6傾斜投影
7.3.7推廣聚集
7.3.8奇異線性系統的確定性方法
7.3.9奇異線性系統的隨機方法
7.4在策略空間的近似
7.4.1梯度公式
7.4.2通過仿真計算梯度
7.4.3梯度評價的關鍵特徵
7.4.4策略和值空間的近似
7.5註釋、資源和習題
習題
附錄A動態規劃中的測度論問題
A.1兩階段例子
A.2可測問題