基于因子分解機(jī)用于安全探索的Q表初始化方法

曾柏森，鐘 勇，牛憲華

（1.中國(guó)科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所，成都 610041；2.中國(guó)科學(xué)院大學(xué)，北京 100049；3.成都工業(yè)學(xué)院網(wǎng)絡(luò)與通信工程學(xué)院，成都 611730；4.通信抗干擾技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室（電子科技大學(xué)），成都 611731；5.西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，成都 610039）

0 引言

強(qiáng)化學(xué)習(xí)［1］是一種交互式機(jī)器學(xué)習(xí)方法，通過在環(huán)境中探索和試錯(cuò)來(lái)學(xué)習(xí)獲取最大價(jià)值的最優(yōu)策略，其中智能體的動(dòng)作選擇稱為探索/利用策略。強(qiáng)化學(xué)習(xí)的大多數(shù)探索/利用策略都具有隨機(jī)選擇成分，這些方法不考慮隨機(jī)動(dòng)作選擇的風(fēng)險(xiǎn)。然而，當(dāng)強(qiáng)化學(xué)習(xí)應(yīng)用于真實(shí)高風(fēng)險(xiǎn)環(huán)境時(shí)，在保證合理的系統(tǒng)性能同時(shí)確保智能體的探索不會(huì)造成損害或傷害尤其重要。因此，強(qiáng)化學(xué)習(xí)探索的安全性是亟須解決的問題［2］。

Smart 等［3］提出了一種利用示例和訓(xùn)練作為先驗(yàn)知識(shí)，引導(dǎo)智能體減少隨機(jī)探索的時(shí)間從而更有效地學(xué)習(xí)的方法。Maire 等［4］提出了一種從人類現(xiàn)有演示中導(dǎo)出高質(zhì)量初始Q表的方法。Song 等［5］利用領(lǐng)域知識(shí)初始化Q 值改進(jìn)了Qlearning 算法性能，該算法可有效減少智能體移動(dòng)到障礙物中的時(shí)間。Turchetta 等［6］提出了一種基于模型的強(qiáng)化學(xué)習(xí)探索方法，該方法能夠在不違反先驗(yàn)未知安全約束的前提下安全探索決策空間。段建民等［7］利用環(huán)境的勢(shì)能值作為啟發(fā)信息對(duì)Q 表進(jìn)行初始化，從而在學(xué)習(xí)初期便能引導(dǎo)移動(dòng)機(jī)器人快速收斂。

為了提高Q-learning 的探索安全性，本文提出了一種基于因子分解機(jī)（Factorization Machine，F(xiàn)M）的Q 表初始化方法。該方法引入已探索經(jīng)驗(yàn)Q 值作為先驗(yàn)知識(shí)，通過FM 建立先驗(yàn)知識(shí)中狀態(tài)與行動(dòng)的交互作用模型，從而預(yù)測(cè)未知Q值，進(jìn)一步引導(dǎo)智能體與環(huán)境交互。實(shí)驗(yàn)結(jié)果表明，本文方法提高了傳統(tǒng)探索/利用策略在Q-learning 中的探索安全性，同時(shí)也加快了收斂。

1 相關(guān)基礎(chǔ)

1.1 探索安全性

強(qiáng)化學(xué)習(xí)的探索安全性沒有統(tǒng)一的定義［8］，目前主要有三種定義探索安全性的方式：

1）通過標(biāo)簽定義安全。通過不同安全級(jí)別來(lái)標(biāo)記狀態(tài)/行動(dòng)，例如：安全、負(fù)面、臨界、致命［9］。這些標(biāo)簽的數(shù)量和名稱因作者而異。

2）通過代價(jià)定義安全［10］。通過定義在狀態(tài)下執(zhí)行動(dòng)作的代價(jià)，并將生成策略的最壞情況的成本降至最低。但是，并非所有不安全的狀態(tài)都可以使用此類代價(jià)進(jìn)行描述，此外設(shè)置正確的代價(jià)可能是一項(xiàng)艱巨的任務(wù)。

3）通過預(yù)期收益差異定義安全［10］。最小化損失和方差，是一種最小化代價(jià)（最壞情況或預(yù)期）的替代方案。根據(jù)這個(gè)標(biāo)準(zhǔn)的安全策略可以看作一個(gè)最小化不良動(dòng)作數(shù)量的策略。

本文基于第3 種探索安全性定義，以期望減少Q(mào)-learning在探索過程中出現(xiàn)的不良動(dòng)作次數(shù)。

1.2 Q-learning

Q-learning［11］是一種廣泛應(yīng)用于離散狀態(tài)和動(dòng)作空間的基于價(jià)值的無(wú)模型強(qiáng)化學(xué)習(xí)方法，采用時(shí)序差分方法優(yōu)化一個(gè)可迭代計(jì)算的Q 值函數(shù)，定義如下：

其中：Q（s，a）表示智能體在狀態(tài)s下執(zhí)行動(dòng)作a獲得的累積價(jià)值（Q 值）；r表示執(zhí)行動(dòng)作a后得到環(huán)境反饋的收益；s′是執(zhí)行動(dòng)作a后環(huán)境的狀態(tài)；α為學(xué)習(xí)率，用來(lái)控制Q 值更新的快慢；γ為折扣率，決定時(shí)間的遠(yuǎn)近對(duì)收益的影響程度。

Q-learning 主要由四部分組成。1）Q 表：所有“狀態(tài)-動(dòng)作-累積價(jià)值”Q 值三元組的集合；2）探索/利用策略：智能體選擇動(dòng)作的方法，根據(jù)所處狀態(tài)s決定采取哪種動(dòng)作a；3）環(huán)境交互：智能體執(zhí)行動(dòng)作，并收集環(huán)境反饋的收益r；4）Q 表更新：利用執(zhí)行的動(dòng)作a、得到的收益r和環(huán)境新的狀態(tài)s′按照式（1）更新Q 表。當(dāng)所有Q 值三元組可以持續(xù)更新，整個(gè)學(xué)習(xí)過程就能夠收斂。

1.3 因子分解機(jī)

FM［12］作為一種通用的矩陣分解模型，具有融合不同特征能力的強(qiáng)大的泛化性，被廣泛應(yīng)用在推薦系統(tǒng)領(lǐng)域。FM結(jié)合了支持向量機(jī)和因子分解模型的優(yōu)點(diǎn)，能夠在數(shù)據(jù)非常稀疏的情況下估算訓(xùn)練出可靠的參數(shù)，取得較好的預(yù)測(cè)和推薦結(jié)果［13］。

一般具體的因子分解機(jī)模型的應(yīng)用取二階交互，即特征的交互僅限兩兩交互模型。在理論上可以證明，隨著交互度的增加，因子分解機(jī)模型的時(shí)間復(fù)雜度呈線性增長(zhǎng)趨勢(shì)。

2 基于因子分解機(jī)的Q表初始化方法

先驗(yàn)知識(shí)對(duì)于提高探索/利用策略的探索安全性起著至關(guān)重要的作用［14］。本文采用已探索的有限的Q 值三元組作為先驗(yàn)知識(shí)，基于FM 預(yù)測(cè)未知Q 值，提出了一種Q 表初始化方法。基于該初始化Q 表，智能體繼續(xù)采用探索/利用策略與環(huán)境交互用，可提高Q-learning 的探索安全性。

2.1 問題描述

為了便于描述本文方法，將“狀態(tài)-動(dòng)作-累積價(jià)值”Q 值三元組定義如下。

令S為m個(gè)狀態(tài)的集合，A表示n個(gè)動(dòng)作的集合，Q表示m×n個(gè)Q 值的集合。

其中：si表示第i種狀態(tài)；aj表示第j種行為；qi，j表示Q 值，即在狀態(tài)si下執(zhí)行動(dòng)作aj獲得的累積價(jià)值；?表示未知Q 值。Q值三元組由（si，aj，qi，j）表示。

設(shè)Ω為Q 表中所有Q 值三元組集合，Δ為先驗(yàn)Q 值三元組集合，則Λ=Ω-Δ是未知Q 值三元組集合。Λ中價(jià)值qi，j將由Δ中的先驗(yàn)知識(shí)來(lái)預(yù)測(cè)。為更好地理解基于FM 預(yù)測(cè)未知Q 值的方法，一個(gè)簡(jiǎn)化的示例如圖1 所示。

圖1 基于先驗(yàn)Q值預(yù)測(cè)未知Q值Fig.1 Unknown Q-value prediction based on prior Q-values

假設(shè)Q 表包含5 種狀態(tài)（s1，s2，s3，s4，s5）和4 種動(dòng)作（a1，a2，a3，a4），共20 組Q 值三元組，如圖1（a）為已獲得的12 組先驗(yàn)Q 值三元組。基于已知的12 組先驗(yàn)Q 值三元組，對(duì)未知的Q值?使用FM 方法進(jìn)行預(yù)測(cè)，預(yù)測(cè)后的Q 表如圖1（b）所示。預(yù)測(cè)后的Q 表可以引導(dǎo)智能體安全地探索未知的Q 值，減少其在探索過程中選擇不良動(dòng)作的次數(shù)。

2.2 算法模型

本文提出的基于FM 的Q 表初始化方法的核心思想是：利用FM 方法建立先驗(yàn)Q 值三元組中狀態(tài)和動(dòng)作之間潛在的交互作用模型來(lái)預(yù)測(cè)未知Q 值，以減少智能體在探索過程中選擇不良動(dòng)作的次數(shù)。

FM 可以通過分解參數(shù)利用二階乃至更高階的特征，在數(shù)據(jù)稀疏的情況下估算訓(xùn)練出可靠的參數(shù)。本文的方法采用二階交互特征組合的FM 對(duì)先驗(yàn)Q 值三元組中狀態(tài)和行動(dòng)的交互作用進(jìn)行建模：

模型輸入的訓(xùn)練數(shù)據(jù)如圖2 所示，圖中每一行表示一個(gè)特征向量和其對(duì)應(yīng)的目標(biāo)，圖中特征x由先驗(yàn)Q 值三元組中狀態(tài)和行動(dòng)的獨(dú)熱碼組成。本文方法本質(zhì)上是回歸問題，因此選擇均方誤差作為損失函數(shù)評(píng)估模型的質(zhì)量。本文方法的優(yōu)化函數(shù)是最小化預(yù)測(cè)值與真實(shí)值的均方差函數(shù)，定義如下：

圖2 輸入數(shù)據(jù)示例Fig.2 Example of input data

其中：L(·)為損失函數(shù)；Ii，j用來(lái)標(biāo)識(shí)qi，j是否為先驗(yàn)Q 值，若是則Ii，j=1，否則Ii，j=0。隨后，采用隨機(jī)梯度下降（Stochastic Gradient Descent，SGD）求解優(yōu)化函數(shù)（7），估計(jì)模型參數(shù)θ：

將已估計(jì)的模型參數(shù)θ代入式（5）中，便可以得到所有特征向量x的預(yù)測(cè)Q 值。

2.3 算法流程

本文方法偽代碼如算法1。首先對(duì)Q 表中的狀態(tài)和動(dòng)作分別進(jìn)行獨(dú)熱編碼（第1）行）。由先驗(yàn)Q 值三元組中狀態(tài)和動(dòng)作的獨(dú)熱碼構(gòu)建特征向量x，對(duì)應(yīng)Q 值作為算法目標(biāo)q（第2）行）。然后利用式（8）、（9）求解優(yōu)化函數(shù)（7）估計(jì)模型參數(shù)（第3）行）。再利用式（5）預(yù)測(cè)未知Q 值（第4）行）。最后將預(yù)測(cè)Q 值三元組與先驗(yàn)Q 值三元組合并為初始Q 表（第5）行）。

算法1 基于FM 的Q 表初始化。

輸入 先驗(yàn)Q 值三元組（si，aj，qi，j），因子分解維度k；

輸出 初始Q 表。

1）將S和A進(jìn)行獨(dú)熱編碼；

2）每個(gè)先驗(yàn)Q 值三元組，將si和aj的獨(dú)熱碼作為特征矩陣，qi，j作為目標(biāo)；

3）按照式（8）和式（9）估計(jì)參數(shù)θ={w0，w，V}；

4）按照式（5）預(yù)測(cè)未知Q 值；

5）合并先驗(yàn)Q 值三元組和預(yù)測(cè)Q 值三元組為初始Q 表。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)采用OpenAI Gym［15］中經(jīng)典的網(wǎng)格強(qiáng)化學(xué)習(xí)環(huán)境Cliffwalk。該網(wǎng)格環(huán)境如圖3 所示，共有48 種狀態(tài)（每個(gè)網(wǎng)格一種狀態(tài)），智能體有4 種行為（上、下、左、右）。強(qiáng)化學(xué)習(xí)的任務(wù)從起點(diǎn)（狀態(tài)37）出發(fā)找到一條走到終點(diǎn)（狀態(tài)48）的最優(yōu)路徑（累積收益最大）。在學(xué)習(xí)過程中，智能體每走一步能得到環(huán)境反饋的收益：若走到終點(diǎn)，無(wú)收益，游戲結(jié)束；走進(jìn)灰色懸崖區(qū)域（狀態(tài)38～47）將獲得-100 的收益并回到起點(diǎn)；走到其他區(qū)域得到-1 的收益。

圖3 Cliffwalk環(huán)境Fig.3 Cliffwalk environment

3.2 實(shí)驗(yàn)設(shè)計(jì)

從已收斂策略的Q 值三元組中隨機(jī)采樣作為先驗(yàn)知識(shí)，再采用不同探索/利用策略進(jìn)行A/B 測(cè)試。一組為對(duì)照組，初始Q 表中除已采樣先驗(yàn)Q 值外，其余均為默認(rèn)值；另一組為實(shí)驗(yàn)組，基于先驗(yàn)Q 值使用本文方法對(duì)Q 表進(jìn)行初始化。實(shí)驗(yàn)后，對(duì)比兩組的探索安全性和收斂速度。

3.2.1 探索/利用策略

實(shí)驗(yàn)中采用三種常見的強(qiáng)化學(xué)習(xí)探索/利用策略進(jìn)行智能體動(dòng)作選擇：

1）ε-greedy 策略。該策略在選取動(dòng)作時(shí)有1-ε的概率選擇當(dāng)前策略評(píng)估下收益最大的動(dòng)作（利用），而ε的概率隨機(jī)選擇動(dòng)作（探索）。動(dòng)作選擇方式如下：

2）Boltzmann 策略［16］。該策略基于Q 值計(jì)算所有動(dòng)作的概率分布，再依據(jù)概率分布來(lái)采樣動(dòng)作。該方法充分考慮不同動(dòng)作a之間的優(yōu)劣，讓Q 值更高的動(dòng)作a更容易被選中。概率分布計(jì)算式如下：

3）置信區(qū)間上界（Upper Confidence Bound，UCB）策略［17］。該策略的基本思想是樂觀地面對(duì)不確定性，基于當(dāng)前收益及探索次數(shù)為標(biāo)準(zhǔn)選擇當(dāng)前最優(yōu)的動(dòng)作來(lái)最大化置信區(qū)間上界。動(dòng)作選擇方式如下：

其中：n是已執(zhí)行動(dòng)作的總次數(shù)，N（a）是已執(zhí)行動(dòng)作a的次數(shù)。當(dāng)幕數(shù)趨于無(wú)窮時(shí)，置信區(qū)間寬度趨近于0，Q 值預(yù)測(cè)會(huì)越來(lái)越準(zhǔn)確。

3.2.2 實(shí)驗(yàn)參數(shù)

根據(jù)3.1 節(jié)可知，Cliffwalk 環(huán)境中Q 表共有192 組Q 值三元組，實(shí)驗(yàn)分別隨機(jī)采樣不同數(shù)量的Q 值三元組作為先驗(yàn)知識(shí)。每次隨機(jī)采樣后，對(duì)照組和實(shí)驗(yàn)組分別獨(dú)立進(jìn)行10 次實(shí)驗(yàn)，每次實(shí)驗(yàn)?zāi)粩?shù)為500 幕。實(shí)驗(yàn)中涉及的具體參數(shù)如表1。本文使用開源項(xiàng)目TuriCreate［18］對(duì)該問題進(jìn)行建模。

表1 實(shí)驗(yàn)參數(shù)Tab.1 Experimental parameters

3.2.3 評(píng)價(jià)指標(biāo)

通過計(jì)算每一幕中動(dòng)作平均收益來(lái)衡量該幕中的探索安全性。每一幕中的動(dòng)作平均收益=總收益/行動(dòng)總次數(shù)。

根據(jù)Cliffwalk 環(huán)境，若某一幕的動(dòng)作平均收益小于-1，表明在探索過程中曾掉進(jìn)過懸崖（訪問狀態(tài)38～47 之一），則認(rèn)為該幕中的探索是不安全的即為一次不良探索，反之若動(dòng)作平均收益等于-1，則認(rèn)為探索是安全的。

3.3 結(jié)果分析

3.3.1 探索安全性

實(shí)驗(yàn)完成后，按照先驗(yàn)知識(shí)隨機(jī)采樣數(shù)量，分別統(tǒng)計(jì)對(duì)照組和實(shí)驗(yàn)組10 次實(shí)驗(yàn)中出現(xiàn)的不良探索幕數(shù)，結(jié)果如圖4所示。從圖4 中可以看出，使用本文方法的實(shí)驗(yàn)組相較對(duì)照組，不良探索幕數(shù)均有不同程度的減少，其中Boltzmann 和UCB 策略的不良探索幕數(shù)分別下降了68.12%和89.98%，分別如圖4（a）和圖4（b）所示，表明本文方法能有效利用先驗(yàn)知識(shí)提高智能體的探索安全性。由于ε-greedy 策略僅是盲目的、隨機(jī)的選擇動(dòng)作，實(shí)驗(yàn)組相較對(duì)照組的改善不明顯，且這兩組總體不良探索幕數(shù)均明顯高于其他兩種策略，如圖4（c）所示。

圖4 不同策略探索安全性對(duì)比Fig.4 Exploration safety comparison of different strategies

3.3.2 收斂速度

圖5～7 是在不同先驗(yàn)Q 值三元組數(shù)量下不同探索/利用策略每幕平均收益的結(jié)果。

實(shí)驗(yàn)組在三種探索/利用策略中均能快速收斂，尤其是在Boltzmann 策略和UCB 策略中，實(shí)驗(yàn)組比對(duì)照組的收斂速度更快，分別如圖5 和圖6。因ε-greedy 策略隨機(jī)選擇動(dòng)作的特性，實(shí)驗(yàn)組和對(duì)照組收斂情況類似，在學(xué)習(xí)初期的平均收益要明顯低于另兩種策略，如圖7。

圖5 Boltzmann策略收斂速度對(duì)比Fig.5 Comparison of convergence speed of Boltzmann strategy

圖6 UCB策略收斂速度對(duì)比Fig.6 Comparison of convergence speed of UCB strategy

圖7 ε-greedy策略收斂速度對(duì)比Fig.7 Comparison of convergence speed of ε-greedy strategy

4 結(jié)語(yǔ)

本文提出了一種用于Q-learning 安全探索的Q 表初始化方法。該方法利用FM 模型，構(gòu)建先驗(yàn)Q 值三元組中狀態(tài)與動(dòng)作的交互作用模型，并通過該模型預(yù)測(cè)未知Q 值，進(jìn)一步引導(dǎo)智能體探索。在OpenAI Gym 的強(qiáng)化學(xué)習(xí)環(huán)境Cliffwalk中進(jìn)行A/B 測(cè)試，基于本文方法的Boltzmann 和UCB 探索/利用策略的不良探索幕數(shù)分別下降了68.12%和89.98%。實(shí)驗(yàn)結(jié)果表明，本文方法提高了傳統(tǒng)探索/利用策略的探索安全性，同時(shí)提高了收斂速度。未來(lái)的工作將重點(diǎn)研究如何利用本文提出的方法提高深度強(qiáng)化學(xué)習(xí)DQN（Deep Q- Network）在連續(xù)空間的探索安全性。