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

曾柏森，鐘 勇，牛憲華

（1.中國科學院成都計算機應用研究所，成都 610041；2.中國科學院大學，北京 100049；3.成都工業學院網絡與通信工程學院，成都 611730；4.通信抗干擾技術國家級重點實驗室（電子科技大學），成都 611731；5.西華大學計算機與軟件工程學院，成都 610039）

0 引言

強化學習［1］是一種交互式機器學習方法，通過在環境中探索和試錯來學習獲取最大價值的最優策略，其中智能體的動作選擇稱為探索/利用策略。強化學習的大多數探索/利用策略都具有隨機選擇成分，這些方法不考慮隨機動作選擇的風險。然而，當強化學習應用于真實高風險環境時，在保證合理的系統性能同時確保智能體的探索不會造成損害或傷害尤其重要。因此，強化學習探索的安全性是亟須解決的問題［2］。

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

為了提高Q-learning 的探索安全性，本文提出了一種基于因子分解機（Factorization Machine，FM）的Q 表初始化方法。該方法引入已探索經驗Q 值作為先驗知識，通過FM 建立先驗知識中狀態與行動的交互作用模型，從而預測未知Q值，進一步引導智能體與環境交互。實驗結果表明，本文方法提高了傳統探索/利用策略在Q-learning 中的探索安全性，同時也加快了收斂。

1 相關基礎

1.1 探索安全性

強化學習的探索安全性沒有統一的定義［8］，目前主要有三種定義探索安全性的方式：

1）通過標簽定義安全。通過不同安全級別來標記狀態/行動，例如：安全、負面、臨界、致命［9］。這些標簽的數量和名稱因作者而異。

2）通過代價定義安全［10］。通過定義在狀態下執行動作的代價，并將生成策略的最壞情況的成本降至最低。但是，并非所有不安全的狀態都可以使用此類代價進行描述，此外設置正確的代價可能是一項艱巨的任務。

3）通過預期收益差異定義安全［10］。最小化損失和方差，是一種最小化代價（最壞情況或預期）的替代方案。根據這個標準的安全策略可以看作一個最小化不良動作數量的策略。

本文基于第3 種探索安全性定義，以期望減少Q-learning在探索過程中出現的不良動作次數。

1.2 Q-learning

Q-learning［11］是一種廣泛應用于離散狀態和動作空間的基于價值的無模型強化學習方法，采用時序差分方法優化一個可迭代計算的Q 值函數，定義如下：

其中：Q（s，a）表示智能體在狀態s下執行動作a獲得的累積價值（Q 值）；r表示執行動作a后得到環境反饋的收益；s′是執行動作a后環境的狀態；α為學習率，用來控制Q 值更新的快慢；γ為折扣率，決定時間的遠近對收益的影響程度。

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

1.3 因子分解機

FM［12］作為一種通用的矩陣分解模型，具有融合不同特征能力的強大的泛化性，被廣泛應用在推薦系統領域。FM結合了支持向量機和因子分解模型的優點，能夠在數據非常稀疏的情況下估算訓練出可靠的參數，取得較好的預測和推薦結果［13］。

一般具體的因子分解機模型的應用取二階交互，即特征的交互僅限兩兩交互模型。在理論上可以證明，隨著交互度的增加，因子分解機模型的時間復雜度呈線性增長趨勢。

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

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

2.1 問題描述

為了便于描述本文方法，將“狀態-動作-累積價值”Q 值三元組定義如下。

令S為m個狀態的集合，A表示n個動作的集合，Q表示m×n個Q 值的集合。

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

設Ω為Q 表中所有Q 值三元組集合，Δ為先驗Q 值三元組集合，則Λ=Ω-Δ是未知Q 值三元組集合。Λ中價值qi，j將由Δ中的先驗知識來預測。為更好地理解基于FM 預測未知Q 值的方法，一個簡化的示例如圖1 所示。

圖1 基于先驗Q值預測未知Q值Fig.1 Unknown Q-value prediction based on prior Q-values

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

2.2 算法模型

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

FM 可以通過分解參數利用二階乃至更高階的特征，在數據稀疏的情況下估算訓練出可靠的參數。本文的方法采用二階交互特征組合的FM 對先驗Q 值三元組中狀態和行動的交互作用進行建模：

模型輸入的訓練數據如圖2 所示，圖中每一行表示一個特征向量和其對應的目標，圖中特征x由先驗Q 值三元組中狀態和行動的獨熱碼組成。本文方法本質上是回歸問題，因此選擇均方誤差作為損失函數評估模型的質量。本文方法的優化函數是最小化預測值與真實值的均方差函數，定義如下：

圖2 輸入數據示例Fig.2 Example of input data

其中：L(·)為損失函數；Ii，j用來標識qi，j是否為先驗Q 值，若是則Ii，j=1，否則Ii，j=0。隨后，采用隨機梯度下降（Stochastic Gradient Descent，SGD）求解優化函數（7），估計模型參數θ：

將已估計的模型參數θ代入式（5）中，便可以得到所有特征向量x的預測Q 值。

2.3 算法流程

本文方法偽代碼如算法1。首先對Q 表中的狀態和動作分別進行獨熱編碼（第1）行）。由先驗Q 值三元組中狀態和動作的獨熱碼構建特征向量x，對應Q 值作為算法目標q（第2）行）。然后利用式（8）、（9）求解優化函數（7）估計模型參數（第3）行）。再利用式（5）預測未知Q 值（第4）行）。最后將預測Q 值三元組與先驗Q 值三元組合并為初始Q 表（第5）行）。

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

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

輸出 初始Q 表。

1）將S和A進行獨熱編碼；

2）每個先驗Q 值三元組，將si和aj的獨熱碼作為特征矩陣，qi，j作為目標；

3）按照式（8）和式（9）估計參數θ={w0，w，V}；

4）按照式（5）預測未知Q 值；

5）合并先驗Q 值三元組和預測Q 值三元組為初始Q 表。

3 實驗及結果分析

3.1 實驗環境

實驗采用OpenAI Gym［15］中經典的網格強化學習環境Cliffwalk。該網格環境如圖3 所示，共有48 種狀態（每個網格一種狀態），智能體有4 種行為（上、下、左、右）。強化學習的任務從起點（狀態37）出發找到一條走到終點（狀態48）的最優路徑（累積收益最大）。在學習過程中，智能體每走一步能得到環境反饋的收益：若走到終點，無收益，游戲結束；走進灰色懸崖區域（狀態38～47）將獲得-100 的收益并回到起點；走到其他區域得到-1 的收益。

圖3 Cliffwalk環境Fig.3 Cliffwalk environment

3.2 實驗設計

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

3.2.1 探索/利用策略

實驗中采用三種常見的強化學習探索/利用策略進行智能體動作選擇：

1）ε-greedy 策略。該策略在選取動作時有1-ε的概率選擇當前策略評估下收益最大的動作（利用），而ε的概率隨機選擇動作（探索）。動作選擇方式如下：

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

3）置信區間上界（Upper Confidence Bound，UCB）策略［17］。該策略的基本思想是樂觀地面對不確定性，基于當前收益及探索次數為標準選擇當前最優的動作來最大化置信區間上界。動作選擇方式如下：

其中：n是已執行動作的總次數，N（a）是已執行動作a的次數。當幕數趨于無窮時，置信區間寬度趨近于0，Q 值預測會越來越準確。

3.2.2 實驗參數

根據3.1 節可知，Cliffwalk 環境中Q 表共有192 組Q 值三元組，實驗分別隨機采樣不同數量的Q 值三元組作為先驗知識。每次隨機采樣后，對照組和實驗組分別獨立進行10 次實驗，每次實驗幕數為500 幕。實驗中涉及的具體參數如表1。本文使用開源項目TuriCreate［18］對該問題進行建模。

表1 實驗參數Tab.1 Experimental parameters

3.2.3 評價指標

通過計算每一幕中動作平均收益來衡量該幕中的探索安全性。每一幕中的動作平均收益=總收益/行動總次數。

根據Cliffwalk 環境，若某一幕的動作平均收益小于-1，表明在探索過程中曾掉進過懸崖（訪問狀態38～47 之一），則認為該幕中的探索是不安全的即為一次不良探索，反之若動作平均收益等于-1，則認為探索是安全的。

3.3 結果分析

3.3.1 探索安全性

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

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

3.3.2 收斂速度

圖5～7 是在不同先驗Q 值三元組數量下不同探索/利用策略每幕平均收益的結果。

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

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

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

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

4 結語

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