基于參數(shù)逼近的多智能體強(qiáng)化學(xué)習(xí)算法

趙高長，劉 豪，蘇 軍

(西安科技大學(xué) 理學(xué)院，陜西 西安 710054)

0 引 言

機(jī)器學(xué)習(xí)是人工智能的核心，也是使計算機(jī)具備智能的根本途徑，根據(jù)學(xué)習(xí)方法的不同，可分為非監(jiān)督學(xué)習(xí)、監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)。強(qiáng)化學(xué)習(xí)通過利用自己產(chǎn)生的數(shù)據(jù)與環(huán)境交互，不斷改善自身的行為，最終獲得最優(yōu)的行為策略，由于其試錯和利用困境以及在線學(xué)習(xí)的特點(diǎn)，使其成為解決智能體策略尋優(yōu)問題的最有效工具，在科學(xué)技術(shù)中得到了大量的應(yīng)用[1,2]。而在一個環(huán)境中多個智能體組成的交互式系統(tǒng)通常需要在線學(xué)習(xí)提高智能體的性能，由于實際原因不可能對系統(tǒng)進(jìn)行預(yù)編程，因而需要學(xué)習(xí)和適應(yīng)[3]，同時也是為了使智能體和環(huán)境的動態(tài)性能夠隨著時間而變化[4]。近年來，單智能體強(qiáng)化學(xué)習(xí)方法快速發(fā)展，其算法思想通常用來描述一般MARL(multi-agent reinforcement learning)算法[5,6]。然而在現(xiàn)有的多智能體強(qiáng)化學(xué)習(xí)算法中，普遍缺乏相當(dāng)?shù)倪m應(yīng)性，條件較多，且算法運(yùn)算較為復(fù)雜，收斂較慢，性能不好。本文基于智能體在自身情況下的納什Q學(xué)習(xí)算法，提出一種利用參數(shù)近似的控制狀態(tài)-行為值函數(shù)的多智能體強(qiáng)化學(xué)習(xí)方法，用一組參數(shù)的更新替代Q值函數(shù)的更新，通過仿真驗證了算法的有效性，該算法不僅簡化了算法復(fù)雜性，擁有良好的性能，且能夠盡快收斂。

1 多智能體納什Q學(xué)習(xí)

Q學(xué)習(xí)應(yīng)用在單智能體情形中是一種行之有效的強(qiáng)化學(xué)習(xí)方法，Q學(xué)習(xí)算法擁有很好的收斂性，其更新方程為

(1)

其中，αt表示當(dāng)前狀態(tài)的學(xué)習(xí)率，γ∈[0,1] 表示折扣因子，rt為狀態(tài)st時智能體選擇行動at轉(zhuǎn)移到下一狀態(tài)st+1得到的回報。

將單智能體Q學(xué)習(xí)算法直接應(yīng)用到多智能體強(qiáng)化學(xué)習(xí)上會受到幾個方面的影響：環(huán)境不再是固定的，常用的保證條件不再成立，假設(shè)合理的其它智能體處于非穩(wěn)定的環(huán)境。馬爾科夫決策過程可以用來描述一個智能體、多個狀態(tài)，卻不能用來描述多智能體強(qiáng)化學(xué)習(xí)。多個智能體在多個狀態(tài)之間相互交互的問題，可定義為馬爾科夫博弈或者隨機(jī)博弈。馬爾科夫博弈描述多智能體強(qiáng)化學(xué)習(xí)系統(tǒng)，用一個元組表示為 (n,S,A1,…,An,T,γ,R1,…,Rn)， 其中，n表示智能體個數(shù)，T:S×A1×…×An×S→[0,1] 表示轉(zhuǎn)移函數(shù)，即給定智能體當(dāng)前的狀態(tài)和聯(lián)合行為時下一個狀態(tài)的概率分布，Ai(i=1,…n) 表示智能體i的行動集，γ∈[0,1] 表示折扣因子，Ri:S×A1×…×An×S→R表示智能體i的回報函數(shù)，即智能體i在一個狀態(tài)采用聯(lián)合行為到達(dá)下一個狀態(tài)得到的回報。

多智能體強(qiáng)化學(xué)習(xí)相比單智能體，區(qū)別在于多智能體的狀態(tài)和回報都是建立在多個智能體的聯(lián)合行動下，其狀態(tài)、回報也取決于聯(lián)合行動，尋找最優(yōu)的聯(lián)合行為，即是在一般和博弈中求解納什均衡。在Q學(xué)習(xí)的框架下的納什均衡稱為納什Q值，如圖1所示，多智能體在聯(lián)合行為下狀態(tài)才能轉(zhuǎn)移。

圖1 多智能體強(qiáng)化學(xué)習(xí)系統(tǒng)

根據(jù)Bellman方程，智能體i的納什Q函數(shù)定義為對于狀態(tài)s處的聯(lián)合動作 (a1,…,an)， 當(dāng)所有的智能體都是執(zhí)行聯(lián)合納什均衡策略時，智能體i的當(dāng)前回報與未來回報之和為

(2)

其中， (π1,…,πn) 為聯(lián)合納什策略，ri(s,a1,…,an) 為當(dāng)智能體i在狀態(tài)s處和聯(lián)合行為 (a1,…,an) 下的回報，vi(s′,π1,…,πn) 為所有的其它智能體執(zhí)行各自的納什均衡策略時在當(dāng)時狀態(tài)下的總的折扣回報。

根據(jù)上述定義，可以直接通過采取使得回報最大的納什均衡策略進(jìn)行迭代逼近。更新方程為

(3)

2 算法改進(jìn)

2.1 基于參數(shù)逼近

根據(jù)以上的理論分析，納什Q學(xué)習(xí)算法的條件十分苛刻，需要計算出所有的Q值函數(shù)，策略需要大量空間來記憶策略價值，計算過程十分復(fù)雜，也會導(dǎo)致收斂較慢，性能不好。此外，在不穩(wěn)定環(huán)境下，過去的經(jīng)驗也不能完全適應(yīng)于未來的情況，需要一種通用的方法更新策略價值，尋求一個通用的值來替代狀態(tài)-行為值函數(shù)，通用的值更新即是值函數(shù)的更新，不需要大量的策略空間記錄值函數(shù)，從而提高算法優(yōu)化策略的程度，提高算法性能，簡化算法的運(yùn)算量，加快算法收斂[7]。

(4)

定義特征函數(shù)

φ=(φ1(s),φ2(s),…,φn(s))T

則有

(5)

(6)

根據(jù)狀態(tài)-行為值函數(shù)的貝爾曼最優(yōu)方程以及隨機(jī)梯度遞減法，通過誤差逼近最優(yōu)值

(7)

采用忽略參數(shù)θ對未知納什Q值得半梯度法，智能體i的狀態(tài)-行為值函數(shù)關(guān)于θ的迭代方程為

(8)

上式即為提出的基于參數(shù)逼近的多智能體強(qiáng)化學(xué)習(xí)算法的更新方程，傳統(tǒng)的納什Q學(xué)習(xí)算法求值函數(shù)表，改進(jìn)的算法只需要求出更新的θ值，即用參數(shù)的更新代替值函數(shù)的更新。在多智能體環(huán)境下，智能體將通過式(8)學(xué)習(xí)。

2.2 算法描述

基于參數(shù)逼近的多智能體強(qiáng)化學(xué)習(xí)算法的實施步驟如下：

步驟1 初始化逼近狀態(tài)-行為值函數(shù)的參數(shù)θ；

步驟2 根據(jù)搜索方法選擇策略，智能體i從當(dāng)前狀態(tài)s采取行為at；

步驟3 在下一狀態(tài)s′， 智能體i觀測所有智能體所獲的回報，以及在先前狀態(tài)s下所有智能體采取的行動；

步驟6 采用二次規(guī)劃來更新狀態(tài)s的納什Q值和策略；

步驟7 轉(zhuǎn)入下一次迭代。

2.3 算法的收斂性和可行性分析

2.3.1 算法的收斂性

下面驗證梯度遞減方法在該算法中的有效性。在一個智能體更新的狀態(tài)-行為值函數(shù)表中，隨機(jī)地選取k∈{1,2,…,N}， 令

(9)

對于一系列逐漸遞減的學(xué)習(xí)率αt， 迭代方程為

(10)

將迭代過程中誤差記為et，根據(jù)上式

(11)

(12)

再由式(11)

根據(jù)式(12)，學(xué)習(xí)率足夠小時，對et求期望

(13)

該不等式表明，當(dāng)學(xué)習(xí)率αt足夠小，f(θt+1) 的期望小于f(θt)， 如果θt不是最小值，則θt將會沿著目標(biāo)函數(shù)最小的方向減小到最小，即隨機(jī)梯度遞減方法能夠找出滿足算法損失函數(shù)最小的θt。 智能體通過參數(shù)近似的控制狀態(tài)-行為值函數(shù)，根據(jù)納什Q算法收斂性的驗證，算法將會通過θ值的更新逼近納什均衡點(diǎn)。因此該算法是具有收斂性的[10]。

2.3.2 算法的可行性

傳統(tǒng)的納什Q算法得到的Q值是智能體每個狀態(tài)下實際的狀態(tài)-行為值函數(shù)。改進(jìn)的算法則存在潛在的誤差m

(14)

根據(jù)式(13)，當(dāng)學(xué)習(xí)的次數(shù)多到一定程度，隨機(jī)梯度遞減能夠得到使得損失函數(shù)最小的參數(shù)值，因此，改進(jìn)的算法存在的誤差實際上取決于隨機(jī)梯度遞減法，即最優(yōu)的參數(shù)值能夠使誤差最小。

此外，傳統(tǒng)的納什Q算法，是十分復(fù)雜的，需要維護(hù)多個Q表，常常會面臨維數(shù)災(zāi)難，學(xué)習(xí)效率會減弱[11]。式(8)能夠有效避免這些問題，尋求一個參數(shù)替代Q值，將復(fù)雜的運(yùn)算分為兩個過程，兩個學(xué)習(xí)過程中不是每個智能體的狀態(tài)-行為值函數(shù)的更新，而一直是參數(shù)θ的更新，這不僅簡化了復(fù)雜的運(yùn)算，也能夠有效地避免上述問題。因此算法是可行的，且性能足夠好。

3 實驗與結(jié)果分析

在網(wǎng)格博弈游戲上驗證算法，在上、下、左、右4個方向上，兩個智能體可以自由移動。如果這兩個智能體移動到除了目標(biāo)單元格以外的任意的同一個單元格，兩個智能體都會返回到原來的位置，即兩個智能體不能在目標(biāo)單元格以外的單元格相遇。當(dāng)其中一個能夠達(dá)到目標(biāo)位置時，博弈游戲立即結(jié)束。相反，如果是能夠同時到達(dá)，兩個智能體分別可獲得正回報。智能體最初不知道各自回報或目標(biāo)，智能體同時選擇行為。網(wǎng)格單元定義為從左下角的單元狀態(tài)0開始，從左向右逐步增加，直到右上角為單元狀態(tài)8。每個智能體能夠選擇的行動是上、下、左、右。兩個智能體的狀態(tài)位置可分別用 (s1,s2)。 如果一個智能體達(dá)到目標(biāo)單元格，可獲得回報100，如果兩個智能體沖突，則都返回最初位置，并得到懲罰-1，到達(dá)空的單元格獲得回報0。網(wǎng)格博弈游戲如圖2所示菱形1、2分別代表兩個智能體，圓圈1、2表示目標(biāo)單元格。

圖2 網(wǎng)格游戲

表1是計算出的智能體1、2在網(wǎng)格博弈(1,3)狀態(tài)下的納什均衡值。兩個智能體根據(jù)此狀態(tài)下的納什均衡值進(jìn)行迭代更新。

在MATLAB(R2017a)環(huán)境下，在相同的參數(shù)基礎(chǔ)上驗證原始算法與改進(jìn)算法，同時分別按照兩個智能體都是探索-開發(fā)智能體，都是探索智能體，都是開發(fā)智能體，即智能體使用探索-開發(fā)方法，探索方法，開發(fā)方法驗證兩種算法。在游戲中，(1,3)狀態(tài)下的智能體都是納什均衡值的學(xué)習(xí)者，不改變實驗參數(shù)的情況下，在同等條件下比較改進(jìn)算法與原始算法，對每次算法測試20次，兩種算法中智能體都會100%地得到納什均衡策略。性能曲線是通過智能體累積每一時間步的平均回報來計算的，不僅能夠反映出算法優(yōu)化策略的程度，也能得到算法的收斂性[12]。圖3～圖5是當(dāng)智能體都是探索-開發(fā)智能體、探索智能體、開發(fā)智能體時，在(1,3)狀態(tài)下，得到納什均衡，通過計算智能體1的性能曲線，為確保這些值不是僅反映一次博弈的結(jié)果，取5次博弈的平均值得到的納什Q算法和本文改進(jìn)算法智能體性能關(guān)于時間步的平滑曲線。

表1 (1,3)狀態(tài)下的納什Q值

圖3 探索-開發(fā)智能體納什均衡學(xué)習(xí)

圖4 探索智能體納什均衡學(xué)習(xí)

圖5 開發(fā)智能體納什均衡學(xué)習(xí)

根據(jù)智能體1的性能曲線，可以得到以下結(jié)論：探索-開發(fā)方法在原始算法和改進(jìn)算法中都是尋找最優(yōu)策略表現(xiàn)最佳的方法；采用本文算法參數(shù)近似控制，改進(jìn)算法平均回報比原始算法高，優(yōu)化策略比原始算法好，即改進(jìn)的算法性能值較高；改進(jìn)算法相比原始算法能夠盡快收斂；表明本文改進(jìn)的算法擁有良好的適用性，且能夠簡化算法運(yùn)算量，改進(jìn)算法相比原始算法能夠較快收斂。

探索-開發(fā)方法在游戲中表現(xiàn)最佳，算法是隨機(jī)選擇動作的，因此探索和探索-開發(fā)的結(jié)果較為接近，探索-開發(fā)方法的優(yōu)勢在于通過貪婪策略增加了總的收益，開發(fā)的方法允許在搜索策略時增加一些探索，否則開發(fā)智能體會陷入相同動作的困境中，無休止的游戲下去[13]；兩種算法平均回報之間存在結(jié)果差異，平均回報可以反應(yīng)性能，改進(jìn)的算法通過近似值逼近值函數(shù)，不需要更新維護(hù)Q值表，能夠更好地優(yōu)化策略，獲得較高的平均回報，提高算法的性能；改進(jìn)的算法能夠較快收斂，理論分析改進(jìn)的算法具備收斂性，主要簡化了傳統(tǒng)納什 Q 學(xué)習(xí)算法的復(fù)雜性，使用通用的方法更新策略，提高了算法的學(xué)習(xí)效率，這樣可以保證算法盡快收斂。

4 結(jié)束語

針對多智能體馬爾科夫博弈，本文提出了一種基于參數(shù)改進(jìn)的多智能體強(qiáng)化學(xué)習(xí)算法。該算法通過參數(shù)逼近的方法近似控制Q值函數(shù)，找出通用的方法更新策略空間，簡化了納什Q算法的復(fù)雜性，提高了算法的性能，并在理論上分析討論了算法的收斂性以及可行性，同時也從仿真上說明了算法的有效性。由于在一般情況下，多智能體學(xué)習(xí)是一個動態(tài)目標(biāo)問題，以及用參數(shù)代替時與真實Q值存在誤差，進(jìn)一步的研究包括：提高處于理論前沿的參數(shù)逼近方法在馬爾科夫博弈上的適用性，以及加快算法學(xué)習(xí)過程中的收斂性，使MARL算法更適應(yīng)在線學(xué)習(xí)的情況等。