人工智能之Q Learning算法

　　人工智能機器學習有關算法內容，請參見公眾號“科技優化生活”之前相關文章。人工智能之機器學習主要有三大類：1)分類;2)回歸;3)聚類。今天我們重點探討一下Q Learning算法。 ^_^

　　通過前一篇TD-Learning時序差分(請參見人工智能(48)算法介紹，我們知道，TD-Learning時序差分是結合了動態規劃DP和蒙特卡洛MC(請參見人工智能(31))方法，并兼具兩種算法的優點，是強化學習的中心。

　　TD-learning時序差分大概分了6類。其中，策略行動價值qπ的off-policy時序差分學習方法： Q-Learning(單步)，Double Q-Learning(單步)。今天重點介紹Q-Learning算法。

　　Q Learning算法是由Watkins于1989年在其博士論文中提出，是強化學習發展的里程碑，也是目前應用最為廣泛的強化學習算法。

　　Q Learning算法概念：

　　Q Learning算法是一種off-policy的強化學習算法，一種典型的與模型無關的算法，即其Q表的更新不同于選取動作時所遵循的策略，換句化說，Q表在更新的時候計算了下一個狀態的最大價值，但是取那個最大值的時候所對應的行動不依賴于當前策略。

　　Q Learning始終是選擇最優價值的行動，在實際項目中，Q Learning充滿了冒險性，傾向于大膽嘗試。

　　Q Learning算法下，目標是達到目標狀態(Goal State)并獲取最高收益，一旦到達目標狀態，最終收益保持不變。因此，目標狀態又稱之為吸收態。

　　Q Learning算法下的agent，不知道整體的環境，知道當前狀態下可以選擇哪些動作。通常，需要構建一個即時獎勵矩陣R，用于表示從狀態s到下一個狀態s’的動作獎勵值。由即時獎勵矩陣R計算得出指導agent行動的Q矩陣。

　　Q矩陣是agent的大腦。

　　Q Learning算法本質：

　　QLearning屬于TD-Learning時序差分學習。同樣，該算法結合了動態規劃和蒙特卡羅MC算法，模擬(或者經歷)一個情節，每行動一步(或多步)后，根據新狀態的價值，來估計執行前的狀態價值。

　　下面提到的Q-Learning是單步更新算法。

　　Q Learning算法描述：

　　Q-learning是一個突破性的算法。

　　利用下面公式進行off-policy學習，即用公式來表示Q-Learning中Q表的更新：

　　Q(St，At)←Q(St，At)+α[Rt+1+γmax Q(St+1，a)?Q(St，At)]

　　其中：

　　St： 當前狀態state

　　At： 從當前狀態下，采取的行動action

　　St+1：本次行動所產生的新一輪state

　　At+1： 次回action

　　Rt： 本次行動的獎勵reward

　　γ為折扣因子，0<= γ<1，γ=0表示立即回報，γ趨于1表示將來回報，γ決定時間的遠近對回報的影響程度，表示犧牲當前收益，換取長遠收益的程度。將累計回報作為評價策略優劣的評估函數。當前的回報值以及以前的回報值都可以得到，但是后續狀態的回報很難得到，因此累計回報就難以計算。而Q-learning用Q函數來代替累計回報作為評估函數，正好解決這個問題。

　　α為控制收斂的學習率，0< α<1。通過不斷的嘗試搜索空間，Q值會逐步趨近最佳值Q*。

　　1)Q-learning單步時序差分學習方法算法描述

　　Initialize Q(s，a)，?s∈S，a∈A(s) arbitrarily， and Q(terminal， ˙)=0

　　Repeat (for each episode)：

　　? Initialize S

　　? Choose A from S using policy derived from Q (e.g. ??greedy)

　　? Repeat (for each step of episode)：

　　?? Take action A， observe R，S′

　　?? Q(S，A)←Q(S，A)+α[R+γmaxa Q(S‘，a)?Q(S，A)]

　　?? S←S′;

　　? Until S is terminal

　　每個episode是一個training session，且每一輪訓練意義就是加強大腦，表現形式是agent的Q矩陣元素更新。當Q習得后，可以用Q矩陣來指引agent的行動。

　　Q-learning使用了max，會引起一個最大化偏差(Maximization Bias)問題。

　　可以使用Double Q-learning可以消除這個問題。

　　2)Double Q-learning單步時序差分學習方法算法描述

　　Initialize Q1(s，a) and Q2(s，a)，?s∈S，a∈A(s) arbitrarily

　　Initialize Q1(terminal， ˙)=Q2(terminal， ˙)=0

　　Repeat (for each episode)：

　　? Initialize S

　　? Repeat (for each step of episode)：

　　?? Choose A from S using policy derived from Q1 and Q2 (e.g. ??greedy)

　　?? Take action A， observe R，S′

　　?? With 0.5 probability：

　　??? Q1(S，A)←Q1(S，A)+α[R+γQ2(S′，argmax Q1(S′，a))?Q1(S，A)]

　　?? Else：

　　??? Q2(S，A)←Q2(S，A)+α[R+γQ1(S′，argmax Q2(S′，a))?Q2(S，A)]

　　?? S←S′;

　　? Until S is terminal

　　Double Q Learning算法本質上是將計算Q函數進行延遲，并不是得到一條樣本就可以更新價值函數，而是一定的概率才可以更新。由原來的1條樣本做到影響決策變為多條(至少兩條)樣本影響決策。

　　Q Learning理論基礎：

　　QLearning理論基礎如下：

　　1)蒙特卡羅方法

　　2)動態規劃

　　3)信號系統

　　4)隨機逼近

　　5)優化控制

　　Q Learning算法優點：

　　1)所需的參數少;

　　2)不需要環境的模型;

　　3)不局限于episode task;

　　4)可以采用離線的實現方式;

　　5)可以保證收斂到 qπ。

　　Q Learning算法缺點：

　　1) Q-learning使用了max，會引起一個最大化偏差問題;

　　2) 可能會出現更新速度慢;

　　3) 可能會出現預見能力不強。

　　注：使用Double Q-learning可以消除問題1);使用多步Q -learning可以消除問題2)和3)。

　　Q Learning算法應用：

　　從應用角度看，Q Learning應用領域與應用前景都是非常廣闊的，目前主要應用于動態系統、機器人控制、工廠中學習最優操作工序以及學習棋類對弈等領域。

　　結語：

　　Q Learning是一種典型的與模型無關的算法，它是由Watkins于1989年在其博士論文中提出，是強化學習發展的里程碑，也是目前應用最為廣泛的強化學習算法。Q Learning始終是選擇最優價值的行動，在實際項目中，Q Learning充滿了冒險性，傾向于大膽嘗試，屬于TD-Learning時序差分學習。Q Learning算法已經被廣泛應用于動態系統、機器人控制、工廠中學習最優操作工序以及學習棋類對弈等領域。