請問在強化學習的Qlearning中，如果狀態-動作很多的話，該如何處理？

01-30

Qlearning的目的我的理解是，得出一張記錄每個狀態對應最優的下一步動作的表，但是如果有很多狀態，每個狀態又對應很多動作的話，應該怎麼記錄呢？

狀態很多和動作很多是有細微差別的兩類問題，看到大家都提到了function approximation，這是用來處理狀態很多情況的好方法，但是動作很多則需要一些額外的方法支撐。

當狀態來自元素極多的離散集合（如下棋）時，或者根本就是個連續向量（如word embedding）時，用表格法存儲會遇到兩個大問題：1）這張表太大存不下來，2）樣本太過稀疏基於採樣的演算法不收斂（curse of dims）。此時，function approximation是常用的解決手段。用一族參數化的函數來表達未知函數，只要參數數量不是很多就可以在實際系統中用起來。與此同時，參數化函數表達如果使用得當（e.g. 避免了overfitting）還可以有泛化的功能，減少了所需樣本量。這一類方法在參數化函數的使用形式上很像regression問題。DeepMind提出的DQN ([1312.5602] Playing Atari with Deep Reinforcement Learning ) 就是上述方法的一個很現代的好例子，網上已經有way to many implementations，mine included (zaxliu/dqn4wirelesscontrol)，歡迎交流。

動作元素極多的情況更tricky，但是因為沒有大狀態空間問題普遍所以以往的討論較少。不普遍不代表不重要，例如自然語言序列到序列問題，就是狀態與動作空間雙高的例子，而實際世界的控制問題則大多是狀態動作雙連續的。

其實這裡面也有兩個問題：表示和搜索。大動作空間的表示與大狀態空間異曲同工。為解釋清楚，從David Silver課件里偷一張圖，如果採用下圖中間的action-in形式，那麼動作和狀態其實是等價的，e.g. 動作是圖片就用CNN，動作是序列就用RNN。如果採用下圖右側的action-out形式，那麼就需要採用相應的逆操作，比如圖片用反卷積，序列用RNN decoder。

大動作空間的搜索是個更難的問題。例如在Q learning演算法中，需要搜索當前狀態s下所有動作裡面Q值最大的那一個。當action space離散且很大的時候，基於遍歷求max的時間複雜度顯然是不能忍受的。此外，當action space是連續空間時，這個max是在非凸函數上求全局最大，難度可想而知。並且對於這個問題，我並不認為隨機策略梯度（stochastic policy gradient）是什麼良藥，因為依舊需要遍歷全部action space或者其中概率大於一定閾值的子集，因此使用起來往往需要搭配其他的方法。（例如Bahdanau的這篇文章 [1607.07086] An Actor-Critic Algorithm for Sequence Prediction 中就結合了beam search和策略梯度，還有AlphaGo中的蒙特卡洛樹搜）

雖然對於巨大離散的動作空間尚無良藥，但是在連續決策空間中這兩年DeepMind又貢獻了一些很有啟發意義的工作。其一是&http://www.jmlr.org/proceedings/papers/v32/silver14.pdf&>確定性策略梯度&（Deterministic Policy Gradient，DPG）。這個方法巧妙地用actor-critic架構求得一種新的策略梯度方向，可以很容易地和神經網路的BP梯度計演算法結合。另一篇是[1603.00748] Continuous Deep Q-Learning with Model-based Acceleration ，則通過對value function進行局部的二階正定近似假設，求得policy更新的閉式表達。遺憾的是連續決策空間中的工作均沒有較好的理論基礎（DPG那篇文章的推導至今沒找到...），也說明還有研究的空間。

對於簡單問題，比如小的迷宮尋路，可以構建 Q[s, a] 矩陣，量化任意狀態 s 時採取動作 a，對於最終勝利的貢獻。對於複雜環境，比如說英雄聯盟遊戲，每一時刻的遊戲畫面，都是不同的狀態，這個時候必須要把狀態空間進行壓縮。壓縮的方法可以參考Google DeepMind 的 Deep Q Learning，將每4幀的遊戲畫面作為輸入，使用卷積神經網路提取高層的抽象特徵，作為壓縮之後的狀態空間。卷積神經網路輸出層的神經元個數等於所有允許的動作數。卷積神經網路或者全連接神經網路都可以用來壓縮狀態空間，構造近似的Q函數，即Q(s, a)。Q函數對於分立的動作比較有用，如果動作空間是連續函數，比如自動駕駛時方向盤的轉動角度，那麼用策略梯度法 (Policy Gradient) 比較好。這個時候用深度神經網路來構造一個策略函數比較有用，策略函數與Q函數的區別在於策略函數輸入狀態，給出分立的動作，或者動作的幾率，或者連續動作的幅度，看你需要什麼。而Q函數的輸入同時包含狀態與動作，給出價值。

在演員-評審（Actor-Critic）框架中，一般會構造3個神經網路，Actor 神經網路得到近似的策略函數，對於給定狀態 s 抽樣動作 a, Critic 神經網路構造價值函數 Q(s, a), 評判 Actor 神經網路的策略好壞，另外還有 Target 神經網路，基本是 Actor 神經網路的拷貝，卻並不像 Actor 神經網路一樣每步都需要更新參數，這樣的做法是為了保持訓練的穩定。

這裡有幾篇推薦的文章和一本神書，可以讓你對強化學習的理解更上一層樓。

1. A Painless Q-Learning Tutorial 簡單的例子講清楚 Q Learning

2. Reinforcement learning 周莫煩，非常清晰的講解了各種強化學習的不同之處

3. songrotek/DRL-FlappyBird 實現Google DeepMind發表在nature paper 上的 Deep Q Leaning, 玩 FlappyBird （狀態空間巨大）

4. Using Keras and Deep Deterministic Policy Gradient to play TORCS 以自動駕駛為例講述連續動作控制（動作連續）

5. Sutton 的 Book ， Reinforcement Learning: An introduction 這是一本神書，除了上述內容，還有關於計劃（Planning）的思索。

剛開始看深度強化學習的時候，總有一種感覺，遊戲AI，俗稱代理人(Agent)，所學到的策略和價值函數，非常接近人和動物的本能反應，即遇到某種狀況時，Agent 知道應該這樣做，但不知道為什麼這樣做。人與 Agent 不同的地方在於，人可以從環境中學到物理定律，利用這些規律預測環境，做想像實驗並制定計劃，而Agent是在環境中死了無數次進化過來的。Sutton的書後面一部分講了Planning方面的內容，看之非常有啟發。

狀態很多的情況下，DeepMind的經典論文DQN ([1312.5602] Playing Atari with Deep Reinforcement Learning ) 已經解決了：用神經網路去表示和訓練。

但上述論文中，行為很少（不超過18），而且這些行為有個特點：具體到某遊戲中，在任意狀態s（t）下，都可以採用任意行為A(t)。由於這些行為任意可達的特點，所以epsilon-greedy演算法才成立。

現實應用場景下，行為沒這麼簡單。具體表現為：一、行為多，二、行為之間有複雜的邏輯依存關係，不是任意時刻都可以執行任意行為的。

行為很多，通常有兩種情形：

1）可執行的合法動作類型很多；

2) 行為不是離散的，是連續的。

行為之間複雜邏輯關係例子，以一個SLG遊戲為例：

玩家必須先造船塢(action1)，然後才能造戰艦(action2)。玩家在沒有船塢之前，是無法造戰艦的。
玩家基地為5級時，能升級基地到6級，不能升級到7級，也不能主動升級到4級。

這樣的場景，與Deepmind 玩Atari遊戲、飛FlappyBird的經典深度強化學習是存在區別的。起碼不能在任意時刻，以概率a選擇action1, 以概率1-a來選擇action2了。

目前對於這些巨大動作數量或邏輯依存動作的表示和搜索，是強化學習前沿，無論在理論上和實現上都處於探索中。 @劉景初的回答中提到了一些解決辦法，可以參考。

先區分狀態和動作是離散的還是連續的吧。連續的用function approximation. 大量離散的，做一些聚類操作，層次化操作。檢索一下相關的論文唄，如果沒有，自己組合一些經典聚類演算法試。試出來還可以出篇文章，多好。

這個表本質上就是一個函數嘛。

這個問題正好就是function approximation類強化學習所要解決的，推薦看一下Sutton那本經典教材Reinforcement Learning: An Introduction

@劉景初解釋的已經比較詳細了，我再補充一點。

個人認為這個問題的關鍵在於如何理解Q-learning中的最大化操作。可以從兩個方面理解。

對於Q-learning，演算法的核心在於迭代方程： $Q(S_t,A_t)leftarrow Q(S_t,A_t)+alpha[R_{t+1}+gammamax_aQ(S_{t+1},a)-Q(S_t,A_t)]$

其中，關鍵的操作在於：在探索並確定下一步狀態 $S_{t+1}$ 的情況下，從所有可能發生的的狀態-動作對 $(S_{t+1},a)$ 中尋找Q的最大值。這裡存在兩個問題：在什麼地方尋找、通過什麼方式尋找。

1、在什麼地方尋找。在充分探索的情況下，每一個狀態-動作對都會被訪問。狀態-動作對很多，包含狀態有很多，動作有很多，或者狀態、動作都很多。當然，在連續的情況下問題更為嚴重。狀態-動作對很多，意味著搜索空間很大。無論是從存儲開銷的角度，還是從計算開銷的角度，都需要我們有一種更好的方式進行壓縮表示，用較少的參數就能較為完整地表示整個搜索空間。一種方式就是函數近似function approximation，其中採用深度神經網路是一種可行的辦法。DQN等一系列演算法都在這個問題進行了改進。當然，壓縮或者近似，在獲得較小空間的同時也是有代價的。例如，與表方法不同，各狀態-動作對的Q值之間不再是完全獨立，改變一個狀態-動作對的 $Q(s_1,a_1)$ 會直接影響另一個的值 $Q(s_2,a_2)$ ，這個特點會直接影響演算法的收斂性。

2、通過什麼方式尋找。即使進行了壓縮表示，搜索空間一般仍然較大。尤其是對連續動作空間，壓縮之後仍然是連續的。迭代方程的最大化操作尋找的是全部集合中的最大值，也就是全局最大值。如果找不到全局最大，將影響Q值的估計，從而影響演算法收斂。如果沒有凸函數等特性保證，全局最大值的尋找一般需要遍歷整個搜索空間。這與策略梯度方法是不同的，策略梯度的每一步只要求最大化期望的累積回報，不要求全局最大，在局部利用一階近似的方法，只需沿著梯度方向逐漸上升即可。因此，要保證Q-learning在大動作空間的適用性，關鍵在於尋找特殊的方式來替代遍歷操作，快速尋找全局最大值。一種方式是通過巧妙的構造，增加凸函數等額外約束，使得利用數值優化演算法求解全局最大成為可能。[1603.00748] Continuous Deep Q-Learning with Model-based Acceleration 中，利用二次型構造了優勢函數advantage的凸性，再利用梯度下降演算法尋找最大值，能夠求出最大值對應的動作。

用一個神經網路之類的function approximator降維，但是需要注意Q Learning收斂條件的問題。

留個坑之後來噠

In reinforcement learning, how do you deal with a large possible action space?

可以用function approximation啊

神經網路不就是干這個用的嗎