人工智能之Q Learning算法

2018-06-18 00:57

人工智能機(jī)器學(xué)習(xí)有關(guān)算法內(nèi)容，請(qǐng)參見公眾號(hào)“科技優(yōu)化生活”之前相關(guān)文章。人工智能之機(jī)器學(xué)習(xí)主要有三大類：1）分類；2）回歸；3）聚類。今天我們重點(diǎn)探討一下Q Learning算法。＾＿＾

通過前一篇TD－Learning時(shí)序差分（請(qǐng)參見人工智能（48）算法介紹，我們知道，TD－Learning時(shí)序差分是結(jié)合了動(dòng)態(tài)規(guī)劃DP和蒙特卡洛MC（請(qǐng)參見人工智能（31））方法，并兼具兩種算法的優(yōu)點(diǎn)，是強(qiáng)化學(xué)習(xí)的中心。

TD－learning時(shí)序差分大概分了6類。其中，策略行動(dòng)價(jià)值qπ的off－policy時(shí)序差分學(xué)習(xí)方法： Q－Learning（單步），Double Q－Learning（單步）。今天重點(diǎn)介紹Q－Learning算法。

Q Learning算法是由Watkins于1989年在其博士論文中提出，是強(qiáng)化學(xué)習(xí)發(fā)展的里程碑，也是目前應(yīng)用最為廣泛的強(qiáng)化學(xué)習(xí)算法。

Q Learning算法概念：

Q Learning算法是一種off－policy的強(qiáng)化學(xué)習(xí)算法，一種典型的與模型無關(guān)的算法，即其Q表的更新不同于選取動(dòng)作時(shí)所遵循的策略，換句化說，Q表在更新的時(shí)候計(jì)算了下一個(gè)狀態(tài)的最大價(jià)值，但是取那個(gè)最大值的時(shí)候所對(duì)應(yīng)的行動(dòng)不依賴于當(dāng)前策略。

Q Learning始終是選擇最優(yōu)價(jià)值的行動(dòng)，在實(shí)際項(xiàng)目中，Q Learning充滿了冒險(xiǎn)性，傾向于大膽嘗試。

Q Learning算法下，目標(biāo)是達(dá)到目標(biāo)狀態(tài)（Goal State）并獲取最高收益，一旦到達(dá)目標(biāo)狀態(tài)，最終收益保持不變。因此，目標(biāo)狀態(tài)又稱之為吸收態(tài)。

Q Learning算法下的agent，不知道整體的環(huán)境，知道當(dāng)前狀態(tài)下可以選擇哪些動(dòng)作。通常，需要構(gòu)建一個(gè)即時(shí)獎(jiǎng)勵(lì)矩陣R，用于表示從狀態(tài)s到下一個(gè)狀態(tài)s’的動(dòng)作獎(jiǎng)勵(lì)值。由即時(shí)獎(jiǎng)勵(lì)矩陣R計(jì)算得出指導(dǎo)agent行動(dòng)的Q矩陣。

Q矩陣是agent的大腦。

Q Learning算法本質(zhì)：

QLearning屬于TD－Learning時(shí)序差分學(xué)習(xí)。同樣，該算法結(jié)合了動(dòng)態(tài)規(guī)劃和蒙特卡羅MC算法，模擬（或者經(jīng)歷）一個(gè)情節(jié)，每行動(dòng)一步（或多步）后，根據(jù)新狀態(tài)的價(jià)值，來估計(jì)執(zhí)行前的狀態(tài)價(jià)值。

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

Q Learning算法描述：

Q－learning是一個(gè)突破性的算法。

利用下面公式進(jìn)行off－policy學(xué)習(xí)，即用公式來表示Q－Learning中Q表的更新：

Q（St，At）←Q（St，At）＋α［Rt＋1＋γmax Q（St＋1，a）？Q（St，At）］

其中：

St：當(dāng)前狀態(tài)state

At：從當(dāng)前狀態(tài)下，采取的行動(dòng)action

St＋1：本次行動(dòng)所產(chǎn)生的新一輪state

At＋1：次回action

Rt：本次行動(dòng)的獎(jiǎng)勵(lì)reward

γ為折扣因子，0＜＝ γ＜1，γ＝0表示立即回報(bào)，γ趨于1表示將來回報(bào)，γ決定時(shí)間的遠(yuǎn)近對(duì)回報(bào)的影響程度，表示犧牲當(dāng)前收益，換取長(zhǎng)遠(yuǎn)收益的程度。將累計(jì)回報(bào)作為評(píng)價(jià)策略優(yōu)劣的評(píng)估函數(shù)。當(dāng)前的回報(bào)值以及以前的回報(bào)值都可以得到，但是后續(xù)狀態(tài)的回報(bào)很難得到，因此累計(jì)回報(bào)就難以計(jì)算。而Q－learning用Q函數(shù)來代替累計(jì)回報(bào)作為評(píng)估函數(shù)，正好解決這個(gè)問題。

α為控制收斂的學(xué)習(xí)率，0＜ α＜1。通過不斷的嘗試搜索空間，Q值會(huì)逐步趨近最佳值Q＊。

1）Q－learning單步時(shí)序差分學(xué)習(xí)方法算法描述

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

每個(gè)episode是一個(gè)training session，且每一輪訓(xùn)練意義就是加強(qiáng)大腦，表現(xiàn)形式是agent的Q矩陣元素更新。當(dāng)Q習(xí)得后，可以用Q矩陣來指引agent的行動(dòng)。

Q－learning使用了max，會(huì)引起一個(gè)最大化偏差（Maximization Bias）問題。
可以使用Double Q－learning可以消除這個(gè)問題。

2）Double Q－learning單步時(shí)序差分學(xué)習(xí)方法算法描述

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算法本質(zhì)上是將計(jì)算Q函數(shù)進(jìn)行延遲，并不是得到一條樣本就可以更新價(jià)值函數(shù)，而是一定的概率才可以更新。由原來的1條樣本做到影響決策變?yōu)槎鄺l（至少兩條）樣本影響決策。

Q Learning理論基礎(chǔ)：

QLearning理論基礎(chǔ)如下：

1）蒙特卡羅方法

2）動(dòng)態(tài)規(guī)劃

3）信號(hào)系統(tǒng)

4）隨機(jī)逼近

5）優(yōu)化控制

Q Learning算法優(yōu)點(diǎn)：

1）所需的參數(shù)少；

2）不需要環(huán)境的模型；

3）不局限于episode task；

4）可以采用離線的實(shí)現(xiàn)方式；

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

Q Learning算法缺點(diǎn)：

1） Q－learning使用了max，會(huì)引起一個(gè)最大化偏差問題；

2）可能會(huì)出現(xiàn)更新速度慢；

3）可能會(huì)出現(xiàn)預(yù)見能力不強(qiáng)。

注：使用Double Q－learning可以消除問題1）；使用多步Q －learning可以消除問題2）和3）。

Q Learning算法應(yīng)用：

從應(yīng)用角度看，Q Learning應(yīng)用領(lǐng)域與應(yīng)用前景都是非常廣闊的，目前主要應(yīng)用于動(dòng)態(tài)系統(tǒng)、機(jī)器人控制、工廠中學(xué)習(xí)最優(yōu)操作工序以及學(xué)習(xí)棋類對(duì)弈等領(lǐng)域。

結(jié)語：

Q Learning是一種典型的與模型無關(guān)的算法，它是由Watkins于1989年在其博士論文中提出，是強(qiáng)化學(xué)習(xí)發(fā)展的里程碑，也是目前應(yīng)用最為廣泛的強(qiáng)化學(xué)習(xí)算法。Q Learning始終是選擇最優(yōu)價(jià)值的行動(dòng)，在實(shí)際項(xiàng)目中，Q Learning充滿了冒險(xiǎn)性，傾向于大膽嘗試，屬于TD－Learning時(shí)序差分學(xué)習(xí)。Q Learning算法已經(jīng)被廣泛應(yīng)用于動(dòng)態(tài)系統(tǒng)、機(jī)器人控制、工廠中學(xué)習(xí)最優(yōu)操作工序以及學(xué)習(xí)棋類對(duì)弈等領(lǐng)域。