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

趙高長(zhǎng)，劉 豪，蘇 軍

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

0 引 言

機(jī)器學(xué)習(xí)是人工智能的核心，也是使計(jì)算機(jī)具備智能的根本途徑，根據(jù)學(xué)習(xí)方法的不同，可分為非監(jiān)督學(xué)習(xí)、監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)。強(qiáng)化學(xué)習(xí)通過(guò)利用自己產(chǎn)生的數(shù)據(jù)與環(huán)境交互，不斷改善自身的行為，最終獲得最優(yōu)的行為策略，由于其試錯(cuò)和利用困境以及在線學(xué)習(xí)的特點(diǎn)，使其成為解決智能體策略尋優(yōu)問(wèn)題的最有效工具，在科學(xué)技術(shù)中得到了大量的應(yīng)用[1,2]。而在一個(gè)環(huán)境中多個(gè)智能體組成的交互式系統(tǒng)通常需要在線學(xué)習(xí)提高智能體的性能，由于實(shí)際原因不可能對(duì)系統(tǒng)進(jìn)行預(yù)編程，因而需要學(xué)習(xí)和適應(yīng)[3]，同時(shí)也是為了使智能體和環(huán)境的動(dòng)態(tài)性能夠隨著時(shí)間而變化[4]。近年來(lái)，單智能體強(qiáng)化學(xué)習(xí)方法快速發(fā)展，其算法思想通常用來(lái)描述一般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ù)的更新，通過(guò)仿真驗(yàn)證了算法的有效性，該算法不僅簡(jiǎn)化了算法復(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時(shí)智能體選擇行動(dòng)at轉(zhuǎn)移到下一狀態(tài)st+1得到的回報(bào)。

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

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

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

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

(2)

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

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

(3)

2 算法改進(jìn)

2.1 基于參數(shù)逼近

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

(4)

定義特征函數(shù)

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

則有

(5)

(6)

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

(7)

采用忽略參數(shù)θ對(duì)未知納什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)境下，智能體將通過(guò)式(8)學(xué)習(xí)。

2.2 算法描述

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

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

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

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

步驟6 采用二次規(guī)劃來(lái)更新?tīng)顟B(tài)s的納什Q值和策略；

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

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

2.3.1 算法的收斂性

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

(9)

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

(10)

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

(11)

(12)

再由式(11)

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

(13)

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

2.3.2 算法的可行性

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

(14)

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

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

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

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

圖2 網(wǎng)格游戲

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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