Reinforcement learning 強化學習

Reinforcement learning 是機器學習裡面的一個分支，特別善於控制一隻能夠在某個環境 自主行動的個體 (autonomous agent)，透過和環境之間的互動，例如 sensory perception 和 rewards，而不斷改進它的行為。

pacman game

對「環境」(environment) 這概念，可由這經典遊戲的迷宮表示。agent是裡面的小精靈。包括有追捕你的怪物、和吃了會加分的食物 （這些代表負值和正值的 rewards）。 當然，實際應用的「環境」和「獎勵」可以是抽象的，這遊戲是一個很具體的例子。

  • 人類玩遊戲的流程如下：
    • 首先，遊戲開始，停留在初始時刻。然後，遊戲場景開始變換，玩家眼睛捕捉到畫面的變化，將視覺信號傳遞回腦皮層進行處理。
    • 之後，腦皮層將視覺信號轉換為遊戲的語義資訊，通過經驗指導，將語義資訊與應該進行的操作做映射，之後是將映射後得到的操作信號傳遞到身體，如手指動作。操作結束後，遊戲場景進入下一幀，玩家得到一定的回報，如越過關隘，或者吃到金幣。如此迴圈，直到遊戲結束。

  • 仔細想想這個過程，發生在遊戲內部的那些事情是玩家所不用考慮的，玩家能夠覆蓋的只是上述遊戲迴圈的右半段。即輸入視覺信號，輸出手指動作。而手指動作到下一幀場景，以及玩家得到回報是遊戲內部的過程。

  • 既然瞭解了人類玩家的操作過程，並分解出實際需要玩家的部分內容，下一步就是讓機器替代人類玩家了。為了區分，通常稱機器玩家為agent。與人類玩家的操作類似，agent需要負責：

    • 由上一幀回報信號學習到玩遊戲的知識，即經驗（什麼場景下需要什麼操作）
    • 視覺信號的處理與理解（降維，高層特徵抽取）
    • 根據經驗以及高層的視覺特徵，選擇合理的經驗（動作）
    • 動作回饋到遊戲，即玩家手動的部分

reinforcement learning

  • RL其實就是一個連續決策的過程。
    • 傳統的機器學習中的supervised learning就是給定一些已知類別(答案)的資料，這些類別作為supervisor。
    • 學習一個好的函數，來對未知數據作出很好的決策。但是有時候你不知道答案是什麼，即一開始不知道什麼是好的結果，所以RL不是給定答案，而是給一個回報函數，這個回報函數決定當前狀態得到什麼樣的結果（“好”還是“壞”）。
    • 其數學本質是一個Markov決策過程。最終的目的是決策過程中整體的回報函數期望最優。

  • 首先，RL的過程是一種隨機過程，意即整個決策的過程都是有概率特性的，每一步的選擇都不是確定的，而是在一個概率分佈中採樣出來的結果。因此，整個回報函數是一種沿時間軸進行的時序/路徑積分。

    • 依據Bayes定理，開局時刻不確定性是最大的，開局基本靠猜，或者一些現有的先驗知識。隨著遊戲的不斷進行接近終點，局勢會逐漸晴朗，預測的準確性也會增高。
    • 深藍對戰國際象棋大師卡斯帕羅夫的時候，開局就是一些經典的開局場景，中局不斷預測，多考慮戰略優勢，局勢逐漸明朗，因此這時候一般會出現未結束就認輸的情況。
    • 終局通常就是一些戰術上的考量，如何更快的將軍等。類似地，在RL中，回報函數的時序/路徑積分中，每一步的回報都會乘上一個decay量，即回報隨著遊戲的進行逐漸衰減。此舉也有另一些意味：如何最快的找到好的結果，例如在無人直升機中，花費最小的時間找到最優的控制策略，剩下的就是微調。

  • 接下來，當這一切都確定了，剩下的事情就是尋找一種最優策略（policy）。所謂策略，就是狀態到動作的映射。我們的目的是，找到一種最優策略，使得遵循這種策略進行的決策過程，得到的全域回報最大。所以，RL的本質就是在這些信號下找到這個最佳策略。

  • 動態規劃，其中一條理論基石就來自Bellman公式。Bellman公式告訴我們，在一種序列求解的過程中，如果一個解的路徑是最優路徑，那麼其中的每個分片都是當前的最佳路徑，即子問題的最優解合起來就是全域最優解。回報函數的最大化就服從Bellman公式，這是非常棒的性質，表示著我們可以不斷反覆運算求解問題。TSP問題就不服從Bellman公式，因此它是NP-hard問題。

輸入/輸出

  • reinforcement learning 的輸入是：

    • 狀態 (States): 環境，例如迷宮的每一格是一個 state，或是游戲中某一個時間點所採集到的視覺訊號。
    • 動作 (Actions): 在每個狀態下，所允許的合法操作。
    • 獎勵 (Rewards): 進入每個狀態時，能帶來正面或負面的價值(效用) (utility)。需要注意的是，這裡的回報不一定是即時回報，如棋牌遊戲中，棋子移動一次可能會立刻吃掉對方的棋子，也可能在好多步之後才產生作用。

  • 而輸出就是方案(Policy): 在每個狀態下，應該選擇哪個行動？

  • 於是這4個元素的tuple（S,A,R,P）就構成了一個強化學習的系統。在抽象代數中我們常常用這 tuple 的方法去定義系統或結構。
    • 再詳細一點的例子就是：
    • states S: 迷宮中每一格的位置，可以用一對座標表示，例如(1,3)
    • actions A: 在迷宮中每一格，你可以行走的方向，例如：｛上，下，左，右｝
    • rewards R: 當前的狀態 (current state) 之下，迷宮中的那格可能有食物 (+1) 、也可能有怪獸 (-100)
    • policy P: 一個由 狀態至行動 的 函數，意即：這函數對給定的每一個狀態，都會給出一個行動。 -（S,A,R)是使用者設定的，P是演算法自動計算出來的。

第一個遇到的問題是：為什麼不用這個方法打造人工智慧？現時的強化學習演算法，只對比較細小和簡單的環境適用，對於大的複雜的世界，例如圍棋的 103611 0^{361} 狀態空間，仍是 intractable 的，必須用抽樣的方式處理。關鍵就是，高等智慧生物會在腦中建立世界的模型 (world model) 或知識 (knowledge)， 而強化學習只是關心簡單的「狀態-行動」配對。

強化學習的領導研究者 Richard Sutton 認為，只有這種學習法才考慮到 自主個體、環境、獎勵 等因素，所以它是人工智慧中最 top-level 的 architecture，而其他人工智慧的子系統，例如 logic 或 pattern recognition，都應該在它的控制之下。所以要製造 strong AI，一個可能的方案就是結合強化學習和某種處理複雜 world model 的能力：

Strong AI

程式：貓追老鼠

作者是 Travis DeWolf：程式只要 Python 便可運行，但需要 install PyGame。

貓的行動是簡單地朝著老鼠追（沒有智慧），老鼠的行動是學習出來的。注意，在 main program 和 cellular.py 這兩部分，純粹是定義了迷宮世界如何運作，基本上是一個 game，裡面完全沒有智慧，你可以用｛上、下、左、右｝ 控制各 agent 的活動，如此而已。強化學習的程式在 qlearn.py，很短，而真正學習的程式如下：

def learnQ(self, state, action, reward, value):
    oldv = self.q.get((state, action), None)
    if oldv is None:
        self.q[(state, action)] = reward
    else:
       self.q[(state, action)] = oldv + self.alpha * (value - oldv)

強化學習的原理

Utility (價值，效用)

U 是一連串列動的 rewards 的總和。例如說，走一步棋的效用，不單是那步棋當前的利益，還包括走那步棋之後帶來的後果。 例如，當下貪吃一隻卒，但 10 步後可能被將死。又或者，眼前有美味的食物，但有些人選擇不吃，因為怕吃了會變肥。

一個 state 的效用 U 就是：假設方案(policy)固定，考慮到未來所有可能的 transitions，從這個 state 開始的平均期望的 total reward 是多少 : U(S0)=E(∑t=0∞γtR(st)) U(S_0) = E(\sum_{t=0}^{\infty} \gamma^t R(s_t) ) . 其中 γ \gamma 是discount factor.

Bellman condition

Richard Bellman 在 1953 年提出這個方程，當時他在 RAND 公司工作，處理的是運籌學的問題。 他也首先使用了curse of dimensionality這個術語，形容動態規劃的主要障礙。

考慮的問題是： 要做一連串的 sequential decisions。Bellman equation 說的是： 「如果從最佳選擇的路徑的末端截除一小部分，餘下的路徑仍然是最佳路徑。」。換句話說，如果一系列的選擇 A B C D E 是...最優的，那麼這系列除去開始的 A，那 B C D E …… 系列應用在後繼的狀態上也是最優的。

  • U∗(S)=maxa{R(a)+U∗(S′} U^{*}(S) = \max_{a} \{ R(a) + U^{*}(S^{'} \} .
    • U∗(S) U^{*}(S) : 全部路徑的最佳解．
    • R(a) R(a) : 在當前狀態選擇a的報酬
    • U∗(S′) U^{*}(S^{'}) : 未選a時的最佳解
    • ∗表示「最優 (optimal)」。 這條看似簡單的式子是動態規劃的全部內容； 它的意義是： 我們想獲得最佳效益的路徑，所以將路徑切短一些，於是問題化解成一個較小的問題；換句話說它是一個 recursive relation。

Delta rule

  • Delta rule是在機器學習中經常使用的方法。假設我們有一個理想目標，我們要逐步調教當前的狀態，令它慢慢趨近這個目標。方法是：
    • current state= previous state +α(goal−previousstate) \text{current state} = \text{ previous state } + \alpha(goal - previous state) .
    • α \alpha 稱學習速率 (learning rate)，後面的差值為理想與現實的差距。
    • 很明顯，只要反覆執行上式，狀態就會逐漸逼近理想值。

Temporal difference (TD) learning

將 delta rule 應用到 Bellman condition 上，去尋找最優路徑，這就是 temporal difference learning。我們還是從簡單情況開始：假設方案固定，目標是學習每個 state 的 utility。

  • 理想的U(S)值，是要從 state S 開始，試驗所有可能的 transitions，再計算這些路徑的 total rewards 的平均值。

  • 但實際上，agent 只能夠每次體驗一個行動之後的 state transition。

  • 所以要應用 Bellman condition： 一個 state S 的 U 值，是它自身的 reward，加上所有可能的後繼 states 的 U 值，取其機率平均，再乘以 discount factor：

    • U(S)=R(S)+γ∑S′P(S→S′)U(S′) U(S) = R(S) + \gamma \sum_{S^{'}}P(S \rightarrow S^{'})U(S^{'})
    • P是狀態轉移的機率
    • S'是後繼的狀態
    • ∑ \sum 是所有後繼狀態的總和
    • 換句話說，這是理想的 U(S) 和 U(S 的後繼) 之間的關係，是一個 recursive relation。

  • TD learning 的思想是：假設其他 U(S') 的值正確，利用 Bellman optimality 來調整當下 state 的 U(S)。 當嘗試的次數多了，所有 U 值都會趨向理想。Agent 只需要用這條 update rule：

    • U(S)+=α[R(S)+γU(S′)−U(S)] U(S) += \alpha [R(S) + \gamma U(S^{'}) - U(S)]

  • 在上面理想約束的公式裡，有對於機率 P 的求和，但在 update formula 中 P 不見了。 那是因為 agent 在環境中的行動，暗含了對於 state transition 機率的 sampling (隨機地取樣本)。 換句話說，那機率求和是由 agent 本身體現的。

  • P 是 state transitions 的機率，換句話是關於世界的一個 model。 TD learning 不需要學習 P，所以叫 model-free learning。 但正如開篇時說過，model-free 並不一定是好事，人的智慧就是基於我們對外在世界有一些很好的 models。

Q value

  • Q 值只是 U 值的一個變種 ; U 是對每個 state 而言的，Q 把 U 值分拆成每個 state 中的每個 action 的份量。 換句話說，Q 就是在 state S 做 action A 的 utility。

    • U(S)=maxAQ(A,S) U(S) = \max_{A} Q(A,S) .
    • Q value 配合 TD learning，可以在 active learning 中也消除 P，達到 model-free 的效果。

  • update rule 只要用這個關係改寫就行

    • U(S)+=α[R(S)+γmaxA′Q(A′,S′)−Q(A,S)] U(S) += \alpha[R(S) + \gamma \max_{A^{'}} Q(A^{'}, S^{'}) - Q(A,S)] .

Active learning

  • 在 passive learning 中，方案不變，我們已經能夠計算每個 state S 的效用 U(S)，或者每個 state S 之下行動 A 的效用 Q(S, A)。

    • 如果方案是可以改變的，我們只需計算不同方案的 Q 值，然後在每個 state S 選取相應於最大 Q 值的行動 A，那就是最佳方案，不是嗎？
    • 實際上執行的結果，卻發現這些 agent 的方案很差！ 原因是，學習過程中的 Q 值是 estimate，不是理想的 Q 值，而如果根據這樣的 Q 行動，agent 變得很短視，不會找到 optimal policy。 （例如，某人經常吃同一間餐館，但循另一路徑走，可以發現更好的餐館。）

  • Agent 需要嘗試一些未知的狀態／行動，才會學到 optimal policy； 這就是所謂的 exploration vs exploitation （好奇心 vs 短暫貪婪）之間的平衡。

  • 解決方法是，人工地將未知狀態的價值增加一點：

    • U(S)=R(S)+γmaxAF[∑S′P(S→S′)U(S′),N(A,S)] U(S) = R(S) + \gamma max_{A} F[\sum_{S^{'}} P(S \rightarrow S^{'}) U(S^{'}), N(A,S)] .
    • 其中 N(A, S) 是狀態 S 和行動 A 這對組合出現過（被經歷過）的次數，F 是 exploration 函數，它平時回覆正常的 U 的估計值，但當 N 很小時（亦即我們對 S，A 的經驗少），它會回覆一個比較大的估值，那代表「好奇心」的效用。

參考資料

results matching ""

    No results matching ""