動態規劃 (dynamic programming)

考慮多階段決策的問題，例如下方的最短路徑問題，需要從起點 A、經過中間站的 BCDE、走到終點 F；A 到 B 的距離為 1，D 到 F 的距離為 100 等等。

現在的問題很小，可以使用窮舉法 (method of enumeration) 找出所有的可能。走 ABDF 總距離 102、ABEF 總距離 8、ACDF 總距離 106、ACEF 總距離 9，所以最短路徑為 ABEF。

如何解決一般化的問題？首先考慮短視的策略  (myopic policy)，站在 A 點時，在 B 和  C 兩條路中選擇 B (AB = 1 < 4 = AC)；站在 B 點時，選擇 D；站在 D 點時，只能選擇 F。總成本為 102，路徑為 ABDF。

接下來考慮最佳的 (optimal) 策略，根據的是動態規劃的最佳化原則 (principle of optimality)，詳見我的上課影片

動態規劃的方法是從終點開始、往回決定最佳策略；但是，實際的行走還是從 A 到 F。所以，站在 E 點時，只能選擇 F，路徑長度 2；站在 B 點時，可以選擇 BEF (長度 7) 或 BDF (長度 101)，所以選擇 BEF。站在 A 點時，可以考慮走 B，然後利用已知的最佳次路徑 BEF，得知走 ABEF，總距離 8；或者考慮走 C，然後利用已知的最佳次路徑 CEF，得知走 ACEF，總距離 9；所以二選一，最終的最佳路徑為 ABEF，長度 8，遠小於短視策略的 102。

基本上，動態規劃是一個聰明的窮舉法，省去重覆計算的部份。而且，因綜觀全局，中途走較遠的 BE，以便走較短的最終段 EF (註 1)。

上述問題屬於有限階段的 (finite stages)、離散的 (discrete) 和確定的 (deterministic)，可以擴充應用在時間是連續的 (continuous)、狀態是隨機的 (stochastic)、或無限長時間的問題上。

常見的參考書和其應用領域：

• Richard Bellman, Dynamic Programming, Dover Books on Computer Science, Reprint Edition, 2003. (作者是數學系教授，經典)
• Dimitri P. Bertsekas, Dynamic Programming and Optimal Control (2 Vol Set), Athena Scientific, 4th Edition, 2012. (作者是電機系教授，除了工業工程的例子外，有許多資工和工程的例子)
• Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley-Interscience, 1st Edition, 2005. (作者是作業研究教授)　
• Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, A Bradford Book, 1998. (作者們是資工教授)

當問題變複雜時，利用動態規劃求最佳解變得困難，必須求得近似解，是個熱門的研究領域。基本上，找一個近似函數 (approximate function)，以近似 cost-to-go (上述影片 7 分鐘處)；AlphaGo 是利用多層的類神經網路  (註 2)；這篇論文中，是利用線性規劃 (linear programming) 的對偶解 (dual solution)。常見的參考書和其應用領域：

• Dimitri P. Bertsekas and John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1 edition, 1996. (作者們是電機系教授)
• Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, Vol. II, 4th Edition: Approximate Dynamic Programming, Athena Scientific, 4th edition, 2012. (作者是電機系教授)
• Warren B. Powell, Approximate Dynamic Programming: Solving the Curses of Dimensionality, Wiley,  2 edition, 2011. (作者是作業研究教授)
• Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson, 3 edition, 2009. (作者們是資工教授)

2016年1月29日初稿 

(註 1) 在資工領域，也常使用強化性學習 (Reinforcement learning) 命名之。中途走較遠的 BE，稱為探索 (exploration)；以便走較短的最終段 EF，稱為利用 (exploitation)。

(註 2) AlphaGo 採用三大技術，分別是強化性學習  (reinforcement learning)、蒙地卡羅樹搜尋  (Monte Carlo tree search)、和深度學習 (deep learning)。因為 AlphaGo 的成功，更覺得基礎觀念的重要性。