---
# System prepended metadata

title: 'Reinforcement Learning: An Introduction_Chapter Part II: Approximate Solution Methods'
tags: [Reinforcement Learning, Second Edition]

---

# Reinforcement Learning: An Introduction_Chapter Part II: Approximate Solution Methods
###### tags: `Reinforcement Learning` `Second Edition`

[相關連結_Sutton_2nd](http://incompleteideas.net/book/the-book-2nd.html)
[David Silver_bilibili_簡中字幕](https://www.bilibili.com/video/BV1kb411i7KG/)
[程式碼參考_ShangtongZhang](https://github.com/ShangtongZhang/reinforcement-learning-an-introduction)
[程式碼參考_dennybritz](https://github.com/dennybritz/reinforcement-learning)
[程式碼參考_弱弱的我](https://github.com/shaoeChen/Reinforcement-Learning-An-Introduction-Record)
[LyWangPX/Reinforcement-Learning-2nd-Edition-by-Sutton-Exercise-Solutions](https://github.com/LyWangPX/Reinforcement-Learning-2nd-Edition-by-Sutton-Exercise-Solutions)

第二部份的內容，我們會把第一部份中介紹的tabular methods擴展至適用於任意大小的狀態空間(state space)。在很多我們希望應用強化學習的任務中，有很多的state space是組合的而且又很大；舉例來說，可能的照相機拍出來的照片的數量就可能遠遠大於宇宙中的原子(atom)數量。這種情況下，即使給你擁有無限的時間與資料，我們還是沒有辦法期待可以找到一個optimal policy或是optimal value function；我們的目標就只好變成用有限的計算資源去找到一個好的近似解(approximate solution)。所以這邊我們就要來探討這種求近似解的方法。

這種擁有非常大的state spaces的問題不單單在於記錄用的table所需要的記憶體需求，還要能夠準確的填入這些table所需的時間與資料。在很多目標任務中，幾乎每一個遇到的state都會是前所未見的。因此，為了能夠在這樣子的狀態(states)下有好的決策，我們就需要從先前遇過在某種意義上與當下的狀態(current state)有一點點相似的不同狀態(states)來做泛化。換句話說，關鍵點就在於泛化。如何從一個state space有限的子集中的經驗泛化，然後在較大的子集中產生出一個好的近似？

幸運的是，從樣本中的泛化這種問題已經被擴泛的研究，所以我們不需要悶著頭重新來過。某種程度來說，我們只需要把強化學習跟已經有的泛化方式相結合就可以了。我們需要的這種泛化型式通常稱為[函數逼近](http://terms.naer.edu.tw/detail/2123125/)(function approximation)，因為它會從期望函數(desired function，像是value function)中取範本，然後試著從取得的範本中泛化，以此建構出整個函數的近似。function approximation是一種監督式學習的實例，它本身就是機器學習、人工神經網路、模式識別(pattern recognition)與統計[曲線擬合](http://terms.naer.edu.tw/detail/2114073/)的首要話題。理論上，這些領域中的任一個方法都可以用來做為強化學習演算法的函數逼近器(function approximator)的這個角色，儘管實務上還有其它方法更容易扮演這個角色。

使用函數逼近的強化學習涉及很多傳統監督式學習通常不會出現的問題，像是非平穩性、自舉(bootstrapping)與延遲目標(delayed targets)。這一部份(第二部份)的這五章，我們就會依序的來介紹這些問題跟其它問題。一開始我們會先關注on-policy training，在Chapter 9處理預測狀況，這邊會給出policy，然後僅對其value function做近似的計算，然後在Chapter 10會聊聊控制(control)狀況，會在這邊找到optimal policy的近似。那，對於off-policy learning使用function approximation這個深具挑戰性的問題就在Chapter 11處理。9、10、11這三章都逼得我們不得不回頭看看首要原則，然後重新審視學習的目標(將function approximation考慮進去)。Chapter 12介紹並分析eligibility traces的算法機制，這大大的改進了multi-step reinforcement learning的計算特性。Chapter 13，也就是第二部份的最後一章，探討了一個不同的控制方法，也就是policy-gradient methods(策略梯度)，它直接的近似最佳策略(optimal policy)，而且不需要構造一個approximate value function。