RL兩大類演算法的本質區別？（Policy Gradient 和 Q-Learning)

11-24

方法1. 這兩種方法的本質上是否是一樣的（解空間是否相等）？比如說如果可以收斂到最優解，那麼對於同一個問題它們一定會收斂到一樣的情況？

2. 在Karpathy的blog中提到說更多的人更傾向於Policy Gradient，那麼它們兩種方法之間一些更細節的區別是什麼呢？

（3. 有人願意再對比一下action-critic就更好了(:

我想這張圖大概就是樓主想要的吧：

---
Q Learning 和 Policy Gradient分屬RL的兩大分支：Dynamic Programming 和 Policy Optimization。我主要講下Policy Optimization，因為Q Learning相對好懂，不就是個貝爾曼公式么。

至於Policy Optimization的優缺點，David Silver是這麼總結的：

意思是演算法收斂性好，能解決q learning再高緯度和連續action space時遇到的問題，而且相對於q learning的deterministic policy，我們可以學習一個stochastic policy。

Policy Optimization的核心思想在於，通過調整control policy的參數，使得control policy的expected reward最大化。也就是:
$max_ heta{E[sum_{t=0}^{H}R(s_t)|pi_{ heta}]}$

而Dynamic Programming 的核心思想在於，將一個problem分解為同一範式的subproblem，以此類推，說白了就是recursion。具體到q learning，貝爾曼公式就是recursive decomposition的很好體現:

---
較為簡單且經典的Policy Optimization 演算法就是 Cross Entropy Method了。
簡單到不行，而且某些簡單場景效果拔群，參見文章（Tetris是俄羅斯方塊）
Learning Tetris with the Noisy Cross-Entropy Method
http://nipg.inf.elte.hu/publications/szita06learning.pdf

Code也非常簡單：
https://gist.github.com/domluna/022e73fd5128b05bdd96d118b5131631
演算法：

意思就是，根據episodic的rewards排序，選top p%的policy parameters稱之為elite set, 做gaussian distribution fitting，得到elite set的policy parameter的mean和variance。據此mean 和 variance產生新的一組policy parameter, 再做評估，選出top p%，以此類推。
採用evolution的思想，淘汰表現不好的策略，讓表現好的策略繁衍出更好的策略，再做淘汰，以此類推，這就是CEM。

--
再看Policy Gradient:

最大化目標函數，自然想到對其求導，最後能得出：

上式的意思是：
我們調整的梯度，會增加positive reward的 trajectory (state-action sequence) 的概率，而減小negative reward的trajectory的概率。

那萬一我們的reward全為positive呢？結果是好的壞的trajectory的概率都一起增加了，它這個樣子是不行的。所以我們可以給梯度調整加個baseline b:

reward超過b的trajectory 增加概率，小於b的減小概率。
由於這個gradient是目標函數的一階導數，所以會考慮到step size的問題，萬一步子太大，會扯著蛋，那更新出來的策略表現一下子就下降很多，新的策略採集到的trajectory就不好，你再根據這些不好的trajectory更新策略，你等於，你也變差了吧。這樣策略的variance就會很大。
為了解決這個步長問難呢，有些人就搞了個Trust Region Policy Optimization (TRPO)，意思就是說啊：
First-order approximation from gradient is only a good approximation within 「trust region」
這個數學有點複雜具體不表。可看原文：
https://arxiv.org/pdf/1502.05477.pdf
---
Actor Critic method

還有人就認為policy optimization中的baseline b選的也不好。他認為應該是這樣子：

也就是說，最好的baseline應該是該狀態下所有路徑的未來獎勵期望的平均值，也就是當前的state value。注意reward從k=t開始算，因為past reward不影響我們的future action。那reward這項不就是state-action value function么。那最後的括弧里就是advantage function了。如果不減baseline，那最後一項就只是state-action value function了。所以根據括弧裡面的內容不同，就出現了很多actor critic的變種：

以 Q Actor-Critic 為例，q value based on parameter w:

那麼actor-critic algorithm 主要調整兩組參數：
critic 更新 action-value function (Q value function) 的參數 w （可以依據bellman公式）
actor 更新 control policy 的參數 θ實例演算法：

Q-learning 是一種基於值函數估計的強化學習方法，Policy Gradient是一種策略搜索強化學習方法。兩者是求解強化學習問題的不同方法，如果熟悉監督學習，前者可類比Naive Bayes——通過估計後驗概率來得到預測，後者可類比SVM——不估計後驗概率而直接優化學習目標。

回答問題：

1. 這兩種方法的本質上是否是一樣的（解空間是否相等）？比如說如果可以收斂到最優解，那麼對於同一個問題它們一定會收斂到一樣的情況？

兩者是不同的求解方法，而解空間（策略空間）不是由求解方法確定的，而是由策略模型確定的。兩者可以使用相同的模型，例如相同大小的神經網路，這時它們的解空間是一樣的。
Q-learning在離散狀態空間中理論上可以收斂到最優策略，但收斂速度可能極慢。在使用函數逼近後（例如使用神經網路策略模型）則不一定。Policy Gradient由於使用梯度方法求解非凸目標，只能收斂到不動點，不能證明收斂到最優策略。

2. 在Karpathy的blog中提到說更多的人更傾向於Policy Gradient，那麼它們兩種方法之間一些更細節的區別是什麼呢？

基於值函數的方法（Q-learning, SARSA等等經典強化學習研究的大部分演算法）存在策略退化問題，即值函數估計已經很準確了，但通過值函數得到的策略仍然不是最優。這一現象類似於監督學習中通過後驗概率來分類，後驗概率估計的精度很高，但得到的分類仍然可能是錯的，例如真實正類後驗概率為 0.501，如果估計為0.9，雖然差別有0.3，如果估計為0.499，雖然差別只有0.002，但分類確是錯的。
尤其是當強化學習使用值函數近似時，策略退化現象非常常見。可見 Tutorial on Reinforcement Learning slides中的例子。
Policy Gradient不會出現策略退化現象，其目標表達更直接，求解方法更現代，還能夠直接求解stochastic policy等等優點更加實用。

（3. 有人願意再對比一下action-critic就更好了(:

Actor-Critic 就是在求解策略的同時用值函數進行輔助，用估計的值函數替代採樣的reward，提高樣本利用率。

按我的理解，兩者從本質上就是不一樣的。和MDP裡面的value iteration與policy iteration不同(MDP馬爾可夫決策過程中的值迭代和策略迭代感覺並沒有本質區別？ - nia nia 的回答)，Q Learning和Policy Gradient是在解決不同的問題，而不是同一問題的兩種不同的數值方法。

首先，在modeling上，Q Learning假設policy是deterministic的，而且它的求解空間是函數空間，一個 (state, action) -&> R 的函數。其次，在一些很弱的假設下(一般都成立)，Q Learning演算法本身定義的迭代運算元是一個contraction operator，所以在 t -&> infinity 保證收斂到全局最優解 (最優解不一定對應唯一的policy)。

當然，和Machine Learning中要學習一個分布一樣，實際操作中往往是parametrize Q函數，假設Q函數是由有限維參數 $heta$ 決定，然後求解最優的函數 $heta$ 。這個時候收斂性就不好說了，比如像DQN用神經網路來描述 $heta$ ，用隨機梯度下降來求解，當t -&> infinity，replay buffer size -&> infinity的情況下能保證收斂到最優的 $heta$ 嗎？我覺得答案是否定的。

在modeling上，Policy Gradient假設policy是stochastic的，而且是服從一個parametrized的policy分布。得到這個最優的參數就得到了在這個分布假設下最優的Policy。求解演算法就是通過梯度下降，每一步迭代的梯度也是stochastic的，沒有全局收斂性的保障。如果learning rate逐漸下降能收斂到一個局部最優。

Actor-critic可被視作Policy Gradient，唯一的區別是進一步通過Q function來降低Policy Gradient每一步stochastic梯度的variance。Q function也是用同樣的sample，通過Q Learning來學習的，可以說是充分利用了agent每一步探索得到的寶貴信息吧。

看了下，樓主的分類不對。@宋假名的分類也不對。

正確的分類應該是：強化學習問題分為無模型問題和有模型的問題。而對於強化學習問題的求解，主要分為動態規劃演算法（DP）以及策略優化（PO）。而樓主所說的 PG的演算法屬於PO，Q學習演算法屬於DP。具體空的時候詳細寫寫。

這兩種方法應該都不算大類吧；真正的大類應該是model-free RL和model-based RL。PG和QL都屬於model-free RL。

- QL屬於off-policy model-free control，其目的是求出Q*(s, a)。
- PG屬於policy optimization，其目的是優化expected reward，並不關心Q*(s, a).
- Actor-critic是兩者的結合，目標是policy optimization (類比為actor)，但是引入了對Q(s, a)的估計 (類比為critic)，使得求PG時的梯度估計方差降低。但是很顯然，由於critic的估計並不一定準確，可能會帶來bias - 這是典型的bias-variance trade-off.

PS.
1) 減小unbiased estimate的variance有很多解決方法，例如baseline, 例如reparameterization trick，在VAE和RL中都很常用到。
2) 感覺David Silver的RL課的slides將這些方法的區別講得非常清楚。傳送門：http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html
3) 感覺QL和PG之間的關係，就好像Bayesian ML和Non-Bayesian ML之間的關係，前者描述更多uncertainty，後者優化得更直接。QL的一個弱點在於如果s, a都是非常高維度的，那麼即使是從Q*(s, a)得到一個sample都變得非常難，PG就沒有這個問題，如果episodes很多（數據很多），數據維度很大，PG就更有優勢。
4) 誰來拯救一下model-based RL啊

長話短說：

1.ql和pg都是為了求解最好的RL決策鏈

2.ql一般針對離散空間，採用值迭代方法。以value推policy

3.pg針對連續場景，直接在策略空間求解，泛化更好，直推policy

4.actor-critic可以看作是一個共軛，互相作用，策略也更穩定

我就先針對連續空間說兩句。1. 基於PG的SVG、DPG、GAE用的都是actor-critic的方法並且可以用於解決連續action空間的問題 2. Q-learning是off-policy，本身有個Max值，在無限action下是不合理的 3. RDPG裡面有談到Normalized Advantage Function，把一個policy轉換成advantage function，本身也好像是actor-critic，但是actor和critic共用一個網路。

見我的知乎文章：增強學習 | 多臂賭博機模型 - 知乎專欄和增強學習 | Q-Learning - 知乎專欄從概念原理和代碼實現角度的分析。

知乎專欄覺得這裡的回答更好
這裡要提一下概率輸出的問題。對於DQN來說，本質上是一個接近於確定性輸出的演算法。至多就是採用 $epsilon-greedy$ 進行探索。但是有很多時候，在某一個特定狀態下，很多動作的選擇可能都是可以的。比如說我有20塊錢去買飯。那麼不管我買的是蛋炒飯還是土豆肉片蓋碼飯，結果都是一樣的填飽肚子。因此，採用輸出概率會更通用一些。而DQN並不能輸出動作的概率，所以採用Policy Network是一個更好的辦法。

作者：Flood Sung
鏈接：知乎專欄
來源：知乎
著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。