增強學習（Reinforcement Learning）的幾點迷惑？

01-28

我現在了解增強學習已接近半年了，David Silver的課上過了，也跟著這門課看了Sutton的RL的書，有些疑惑，希望在這裡能得到大家的一些解答，主要有兩個問題：
1.收斂性的問題，現在DRL的很多應用，都採用非線性函數（神經網路）來逼近值函數或策略函數，可是RL書以及課上都講過，這種方法不能保證收斂，這是怎麼解決的。
2.方法選擇問題，增強學習主要分為兩類：value-based和policy-based（policy gradient descent），在應用的時候，如何進行選擇？例如，DQN和actor-critic方法的比較。

RL 本身是一個非常 general 的框架，然而很多 RL 演算法的收斂性都只在比較 restricted 的條件下才能得到證明，在實際應用中實際上經常忽略或者放鬆了這些條件。

Value-based 方法，比如 Q-learning，SARSA 這些，其實只有在 tabular setting 和 linear function approximator 條件下收斂才有保證，這篇論文里有詳細的闡述：An analysis of temporal-difference learning with function approximation.

Policy-based 方法，依賴於 policy gradient 的估計。如果我們可以得到 policy gradient 的一個 unbiased estimate，然後 learning rate 再滿足一定條件的話，那麼就可以保證收斂。早期的 REINFORCE 演算法，沒有使用任何形式的 value function，policy gradient 是通過 Monte Carlo Methods 來估計的，這個是 unbiased 的估計，所以是有收斂性的保證。但是這種方法的一個缺點是估計到的 policy gradient 具有非常大的 variance （貌似是 MC methods 的通病）。所以後來又提出了一系列的 actor-critic methods，主要就是為了儘可能減少估計 policy gradient 產生的 variance。Actor-critic methods 的理論依據主要是 Policy Gradient Theorem，是 Sutton 在 99年的一篇 NIPS 中提到的：Policy Gradient methods for reinforcement learning with function approximation。Policy Gradient Theorem 主要講了兩件事，第一個是把 policy gradient 和真實的 Q function 聯繫了起來，第二個是如果我們不知道真實的 Q function，那麼這個 Q function 可以由一組特殊的滿足一定條件的 function approximator 去估計，最終也能得到一個 unbiased 的 policy gradient。這組特殊的 function approximator 叫做 compatible function。這裡的條件非常苛刻，其實如果完全滿足的話，那麼演算法就等價於 REINFORCE 演算法了。實際中用的 actor-critic 其實也放鬆了一些條件，在這裡就不細講了。

最近的 deep reinforcement learning 方法都是在原有的 RL 框架下，發展一些 practical techniques，從而使得 RL 可以用在一些更實際的問題上，至於理論方面並沒有啥新的進展。

至於 policy-based 和 value-based 的選擇問題，個人覺得如果是 discrete action spaces，可能使用 value-based 效果更好也更容易 train。Deepmind 他們也搞了一個 asynchronous actor-critic （asynchronous methods for deep reinforcement learning）去打遊戲，policy network 最後面使用一個 softmax 就可以處理 discrete action spaces 了，但是好像 training 比起 DQN 來說，要更加不穩定。

第一個問題，理論方面，@Siyi LI回答得很好，包含了我所知的關於function approximation下收斂性的理論結果。對於神經網路這類複雜函數的逼近，我還沒有看到過任何理論結果。鑒於連supervised learning下deep neural network成功的原因都還沒理解清楚，個人感覺這方面的理論工作也不是深度強化學習community關心的主流方向。

實踐中，對於複雜問題而言總是需要用神經網路來作逼近，所以大家會儘力尋找各種辦法使得演算法穩定，robust，甚至達到更好的表現。除了 @Alex-zhai 提到的 experience replay, target network, gradient clipping 以外，演算法層面上與增加收斂性有關的工作還有一些。

1. Double Q-learning (Deep Reinforcement Learning with Double Q-learning). Idea 其實很簡單，把 max_a Q(s, a, theta) 換成了 Q(s, argmax_a Q(s, a ,theta), theta), 結合 target network 的思想可以部分克服 overoptimism 的數值現象。

2. Asynchronous Methods for Deep Reinforcement Learning. 簡而言之思想就是並行地同時訓練幾個agent來進行強化學習，然後非同步更新參數。它可以用在不同的深度強化學習演算法上，而且顯示出stabilizing effect. 其中asynchronous advantage actor- critic method (A3C) 曾經達到過一段時間的 state-of-the-art.

3. Trust Region Policy Optimization, 簡稱TRPO. 大部分深度強化學習的演算法在更新參數的時候都採用了sgd演算法，固定步長或自適應步長。 TRPO 的想法在於更新參數的時候希望新的policy和舊的policy "變化" 不是太大。這個變化用兩個 policy distribution 之間的 KL divergence 來刻畫。換言之，在一個trust region (由KL divergence 定義)中更新參數。實際演算法中，採用了conjugate gradient + line search 的辦法來實現，cost會比單純的sgd演算法大。TRPO是一個general的優化思想，可以用在不同的深度強化學習演算法中，而且從不少最近的工作來看效果很不錯。這裡有一篇比較不同演算法的工作: Benchmarking Deep Reinforcement Learning for Continuous Control。

第二個問題，我更喜歡把 value function 和policy function 當做看待 reinforcement learning 問題的兩個角度，在一定條件下，雙方其實都已經包含了對方的信息，可以通過計算相互轉化。在演算法層面上，value-based 和 policy-based 並不是那麼一分為二的，兩者的結合 actor-critic 本身就是很大的一類演算法。

具體來說，對於一些複雜的infinite time horizon的強化學習問題 (比如play video game), 單純只使用policy function難度比較大，因為只用monte carlo來計算return的方差實在太大，多多少少都需要一些bootstrap來利用value function的信息。所以剩下兩種選擇: value-based (Q-learning) 或者 actor-critic。前者演算法框架實現起來容易一些，但是只適用於有限且較小的action space。而後者對於有限 action 或者 continuous control 都適用。

謝邀。

問題1：主要通過三個技巧來解決神經網路逼近值函數時不能收斂的問題。

1. 使用experience reply機制。

2. 額外加入target network

3. 梯度縮減

詳細請參考論文：Human-level control through deep reinforcement learning

問題2：其實你說的很對，一些簡單的Atari遊戲的確是可以用policy-based的方法來做的。不過個人認為，只有離散動作空間較小的一些遊戲才可以既可以用value-based，又可用policy-based，比如breakout、pong等。對於一類動作空間較大，且明顯是具有連續動作空間的任務，（比如自動駕駛。動作包括剎車的幅度，方向盤的幅度，油門的幅度等），還是用policy-based的方法比較好吧。如果一定要將這兩種方法分開，可以說成是：value-based只是比較合適action space比較小的任務，而policy-based適用範圍就大的多（遊戲、機器人控制、自動駕駛等等）。個人觀點，歡迎大家修正。