楊宛璐，陳 瑋，黃浩暉，王廣濤

（廣東工業(yè)大學(xué) 自動化學(xué)院，廣東 廣州510006）

0 引 言

強化學(xué)習(xí)（reinforcement learning）［1］是解決智能體尋優(yōu)路徑的有效手段，通過與環(huán)境不斷交互來改進自身行為最終獲得最優(yōu)行為策略，在各個機器學(xué)習(xí)領(lǐng)域都有廣泛的應(yīng)用。強化學(xué)習(xí)分為兩種類型：折扣獎賞強化學(xué)習(xí)和平均獎賞強化學(xué)習(xí)。傳統(tǒng)的平均獎賞類型強化學(xué)習(xí)更多考慮當(dāng)前動作對未來的影響，適于解決不具有終結(jié)狀態(tài)或者具有循環(huán)特性的問題，但其研究還處于一個初級階段。早期，Schwarz提出了一種平均獎賞學(xué)習(xí)算法R－learning，采用值迭代的思想來獲得最優(yōu)策略，用于解決平均獎賞的MDP問題［2］；后來Tadepalli提出基于模型的H－learning［3］。這兩種算法都是基于值迭代，但是某個策略的平均獎賞和的逼近過程并不是很穩(wěn)定，并且其對參數(shù)環(huán)境的敏感也是一大弊端。隨后，高陽等人［4］將性能勢理論引入到強化學(xué)習(xí)技術(shù)中，得到一種新的平均獎賞強化學(xué)習(xí)算法G－learning。該算法主要針對的是單鏈馬爾科夫過程，對于多智能體這種非馬爾科夫環(huán)境，直接使用的效果并不好。文獻［5］提出了一種在多鏈馬爾科夫狀態(tài)下，求取平均代價的方法；文獻［6］結(jié)合敏感性分析方法（sensitivity－based approach）［7］和優(yōu)化幾何方差方法（geometric variance reduction）［8］提出了基于性能勢的預(yù)估平均獎賞方法。本文把改進的G－learning引入到多智能體系統(tǒng)中，考慮其它馬爾科夫鏈對agent所產(chǎn)生的影響。算法選擇最優(yōu)的參照系，旨在加快其收斂速度，并成功應(yīng)用在Keepaway平臺上，降低了狀態(tài)空間的大小，從而達到了預(yù)期學(xué)習(xí)效果，加快了學(xué)習(xí)過程。

1 強化學(xué)習(xí)

在人工智能領(lǐng)域中，強化學(xué)習(xí)是一種重要的解決學(xué)習(xí)問題的方法。在強化學(xué)習(xí)中，agent通過與環(huán)境的交互獲得知識，以此來改進自身的行為。試錯和回報是強化學(xué)習(xí)的兩個最顯著的特征，它主要是依靠環(huán)境對所采取行為的反饋信息來評價，并根據(jù)評價去指導(dǎo)以后的行為，使行為效果更佳，通過試探得到的較優(yōu)的行為策略來適應(yīng)環(huán)境。強化學(xué)習(xí)將環(huán)境映射到動作形成策略，最終目標(biāo)是獲得使得長期的積累的最大獎賞大的策略。在強化學(xué)習(xí)中，存在兩種評價獎賞值的標(biāo)準(zhǔn)，折扣累積獎賞值式（1）和平均累積獎賞值式（2）。近年，研究更多的是折扣累積獎賞值，它注重的是近期的回報，表示當(dāng)前動作對agent的影響，注重的是眼前的利益，符合大多數(shù)一般問題的求解。然而，對于不具終結(jié)狀態(tài)或者具有循環(huán)特點的問題，便顯得不適用。因此，對于注重長遠利益的問題，需要更多地考慮當(dāng)前動作的決策對未來環(huán)境的影響，平均獎賞強化學(xué)習(xí)方法更適于解決這類問題

1.1 平均獎賞強化學(xué)習(xí)

R－learning是一種典型的無模型的平均獎賞強化學(xué)習(xí)算法，它在學(xué)習(xí)的過程中環(huán)境模型是不可知的。R－learning由4個關(guān)鍵部分組成：策略函數(shù)、回報函數(shù)、值函數(shù)、環(huán)境模型。策略函數(shù)被定義成從觀察到的狀態(tài)到選擇的動作的映射；回報函數(shù)可以看作是強化學(xué)習(xí)的目標(biāo)，在每一步學(xué)習(xí)過程中，回報函數(shù)估計智能體與環(huán)境之間的相互作用的效果，智能體的學(xué)習(xí)目標(biāo)是使的長期積累獎賞值最大化，換句話說，回報的狀態(tài)到選擇的動作的映射；回報函數(shù)可以看作是強化學(xué)習(xí)的目標(biāo)，在每一步學(xué)習(xí)過程中，回報函數(shù)估計智能體與環(huán)境之間的相互作用的效果，智能體的學(xué)習(xí)目標(biāo)是使的長期積累獎賞值最大化，換句話說，回報函數(shù)可以確定哪些動作會更適于現(xiàn)在的環(huán)境，哪些動作被忽略掉；值函數(shù)用來估計這些被選擇動作的獎賞值；而環(huán)境模型是用來模擬智能體的學(xué)習(xí)環(huán)境。

但是在目前已有的一些平均獎賞強化學(xué)習(xí)方法中，都采用采樣的方式逼近某個策略的平均獎賞和，由于在逼近過程中并不穩(wěn)定，則導(dǎo)致已有學(xué)習(xí)算法不穩(wěn)定。高陽等人將性能勢理論應(yīng)用到強化學(xué)習(xí)算法中，用相對參考狀態(tài)來替代平均獎賞和，獲得一種新的平均獎賞強化學(xué)習(xí)算法——G－learning學(xué)習(xí)算法。

1.2 性能勢以及基于性能勢的無折扣強化學(xué)習(xí)算法

假定有一個可重復(fù)且各態(tài)歷經(jīng)的Markov 鏈X ＝｛Xn：n≥0｝ 在有限狀態(tài)空間S＝1，2，…，M，其狀態(tài)轉(zhuǎn)移概率矩陣為P＝［p（i，j）］∈［0，1］（M×M），π＝π（1），…，π（M）表示狀態(tài)穩(wěn)定概率，f＝（f（1），f（2），…f（M））T表示各個狀態(tài)的獎賞值，是一個M 維的全1矩陣。而π＝πp。平均性能可定義為式（6）

g＝（g1，g2，…，gn）T表示系統(tǒng)的性能勢，令g＝（Ip＋eπ）－1f，其中矩陣（I－p＋eπ）－1被定義為基礎(chǔ)矩陣。I表示單位矩陣，e＝（1，1，…，1）T，根據(jù)泰勒公式展開成式（7）［9］

將性能勢和值迭代方法相結(jié)合，得到一種新的強化學(xué)習(xí)算法－G 學(xué)習(xí)，該算法選擇任意一個狀態(tài)作為參考狀態(tài)，采用值迭代的方法更新狀態(tài)的性能勢，且算法的運行只需要設(shè)定一個學(xué)習(xí)參數(shù)［10］。

根據(jù)性能勢的定義，選擇任意一個狀態(tài)作為其它狀態(tài)性能勢的參考標(biāo)準(zhǔn)。假定選擇狀態(tài)S0作為參考狀態(tài)，則sn狀態(tài)下的性能勢可表示為下式

定義在策略π下，狀態(tài)s相對參考狀態(tài)sk的性能勢

式（6）對于任意s∈S，a∈A 均成立。

性能勢的無折扣強化學(xué)習(xí)算法是一種在策略的G－學(xué)習(xí)算法，其算法描述如下所示：

算法1：在策略的G－學(xué)習(xí)算法

2 基于改進的G－learning在RoboCup中的應(yīng)用

2.1 改進的G－learning算法

在傳統(tǒng)的G－learning中，算法強調(diào)的是單個智能體在復(fù)雜環(huán)境中的學(xué)習(xí)過程，該算法并不能直接將G－learning應(yīng)用到多智能體系統(tǒng)中，所以有必要對原有的算法進行改進。改進的思想是把算法應(yīng)用到多智能體環(huán)境中，考慮到其它智能體的勢函數(shù)對當(dāng)前智能體的影響；改進的目的是當(dāng)智能體在選擇動作的時候，能夠考慮到其它智能體的行為對其決策的影響。智能體在策略π下進行學(xué)習(xí)，參照相對參考狀態(tài)g （s0）不斷改變G （s， a） 。設(shè)智能體共有k個，則γ＝［γ1，γ2，…γk］T表示k 個智能體學(xué)習(xí)的權(quán)值。則G可表示為式（10）

根據(jù)bellman最優(yōu)化定理，結(jié)合式（7）和式（8）的最優(yōu)策略為

由式（9）來確定智能體應(yīng)當(dāng)采取的下一個動作，其中τ（s， a，s′） 為兩次狀態(tài)的停留時間。

2.2 仿真實驗

機器人足球已經(jīng)被成功地作為國際化競技的基礎(chǔ)和研究的一項挑戰(zhàn)，它是一個完全分布式的多主體域。但這里有隱藏狀態(tài)，每個智能體在任意給定的時刻里只能擁有部分世界觀。智能體還有噪音傳感器和執(zhí)行器，他們不能準(zhǔn)確的感知世界，同樣他們也不能完全影響世界。溝通的機會也是有限的，因此智能體必須實時地做出決定。這些特性決定了模擬機器人足球是一個現(xiàn)實的富有挑戰(zhàn)性的領(lǐng)域。

本文利用Keepaway－機器人足球的一個子任務(wù)進行仿真實驗，該平臺用于比較不同的機器學(xué)習(xí)方法。在Keepaway平臺中，其中一個球隊的keepers試圖保證控球在一個有限的區(qū)域內(nèi)，而另一個球隊的takers試圖從keepers中搶奪控球權(quán)，只有當(dāng)takers從keepers那搶奪到控球權(quán)或離開了限定的區(qū)域，這個周期結(jié)束，下一個周期隨之開始。

在RoboCup2D 仿真平臺中，每位agent都擁有各自的原子動作，如kick，dash，turn等。而由于2D 仿真平臺要求的實時性比較高，在每個決策周期內(nèi)必須根據(jù)當(dāng)前狀態(tài)環(huán)境做出決策，因此假如每個學(xué)習(xí)步驟都以原子動作作為學(xué)習(xí)對象，必然影響決策時間，因此本文引入SMDP概念，首先根據(jù)原子動作建立宏動作指令［11］：

HoldBall（）：保持持球，盡可能在距離對手較遠的未知保持控球；

PassBall－：傳球，將球直接傳給keeper（k）；

GetOpen（）：跑位，移動到距離對手有一定空間的未知，并根據(jù)當(dāng)前球的位置創(chuàng)造傳球的機會；

GoToBall（）：截取一個運動著的球或移動到靜止的球；

BlockPass（k）：移動到持球keeper和keeper（k）之間；

Shoot（）：在適當(dāng)?shù)那闆r下射門。

在學(xué)習(xí)過程中，場上的狀態(tài)描述我們主要考慮一下幾個方面：

ball＿pos（）：球的位置；

ball＿distto＿goal（）：球離球門的距離；

mate＿pos（）：該變量為一隊列，存儲隊友的位置信息；

opp＿pos（）：該變量為一隊列，存儲對方球員的位置信息；

球員的Keepaway的技能對于整個足球機器人比賽問題的求解也是非常有用的。Keepaway可看成一個MDP過程，每個隊員只負責(zé)整個決策過程的一部分。每個隊員都是獨立地同時進行學(xué)習(xí)。在本文的仿真實驗中，選擇了如圖1所示的3個典型的前場進攻場景，場景中防守方為agent2d底層，以這些場景開始，直到出現(xiàn)進球、球離開限定區(qū)域或者場景執(zhí)行時間超時，終止當(dāng)前場景訓(xùn)練，選取新的場景并分別以3 個不同點（52.5，0.0）、（47.5，0.0）、（35.0，0.0）作為參考狀態(tài)對象分別運用傳統(tǒng)R－learning和改進的G－learning 進行訓(xùn)練。在學(xué)習(xí)過程中，初始學(xué)習(xí)率默認值為1，并按照進行更新。每個場景限定執(zhí)行1500個仿真周期，按照服務(wù)器規(guī)定每個周期為100ms，每50個場景統(tǒng)計一次進球數(shù)，進球變化情況如圖2所示。

圖1 訓(xùn)練場景

從圖2可以看出，本文所采用的G－learning算法的訓(xùn)練效果明顯優(yōu)于R－learning。算法在學(xué)習(xí)過程中采用不同的參考狀態(tài)，發(fā)生頻率高的狀態(tài)（47.5，0.0）在650 個訓(xùn)練場景后開始收斂，而R－learning則是在接近1000個訓(xùn)練場景后才開始收斂。從進球數(shù)看，應(yīng)用R－learning算法的整體進球數(shù)低于G－learning算法的球隊進球數(shù)，并且在收斂的初期仍有震蕩，從側(cè)面說明了R－learning的敏感性。本文的算法收斂速度比R－learning快，整體算法穩(wěn)定。從訓(xùn)練結(jié)果看，本文的算法在收斂速度和收斂的穩(wěn)定性上均優(yōu)于傳統(tǒng)的R－learning。

圖2 運行場景目數(shù)與進球的關(guān)系

通過學(xué)習(xí)，把R－Learning與改進后的G－Learning代碼應(yīng)用到廣東工業(yè)大學(xué)的仿真2D 球隊GDUT＿TiJi中，并分別與RoboCup2012世界賽的冠軍Helios、亞軍WrightEagle和agent2d底層進行了100場比賽，結(jié)果見表1。

表1 仿真比賽統(tǒng)計結(jié)果（勝率）

3 結(jié)束語

針對在非確定性SMDP中的多智能體系統(tǒng)里，本文基于傳統(tǒng)的性勢能理論和平均強化學(xué)習(xí)提出了基于多智能系統(tǒng)的G－learning算法。該算法使用參考狀態(tài)的性勢能函數(shù)代替了R－learning中的平均獎賞值，同時還考慮團隊決策對智能體決策的影響，使智能體做出最有利于團隊的決策。仿真實驗表明，通過大量情景的學(xué)習(xí)，驗證了改進后Glearning算法的比傳統(tǒng)的R－learning效果更好，而且不同的參考狀態(tài)對G－learning的算法性能也會產(chǎn)生影響。從實驗可以看出，選擇發(fā)生頻率高的狀態(tài)作為參考狀態(tài)，算法的收斂速度將會得到提高。運用改進后的G－learning后，廣東工業(yè)大學(xué)的仿真2D 球隊GDUT＿TiJi在比賽中的效果也得到了提高。從實驗仿真結(jié)果上可以看出，該算法存在收斂時間長、學(xué)習(xí)量大問題，是進一步研究的重點。

［1］Szepesvari C.Algorithms for reinforcement learning：Synthesis lectures on artificial intelligence and machine learning ［M］.San Rafael：Morgan＆Claypool Pulishers，2009：2－3.

［2］Chatterjee K，Majumadar R，Henzinge A T.Stochastic limitaverage games are in exptime［J］.International Journal in Game Theory，2007，37 （2）：219－234.

［3］Tadepalli P，D OK.Model－based average reward reinforcement learning ［J］.Artificial Intelligence，1998，100 （1－2）：177－224.

［4］GAO Yang，ZHOU Ruyi，WANG Hao，et al.Research on the average reward reinforcement learning ［J］.Chinese Journal of Computers，2007，30 （8）：1372－1378 （in Chinese）. ［高陽，周如益，王皓，等.平均獎賞強化學(xué)習(xí)算法研究 ［J］.計算機學(xué)報，2007，30 （8）：1372－1378.］

［5］Sun T，Zhao Q，Luh P B.A rollout algorithm for multi chain Markov decision processes with average cost［J］.Positive Systems，2009，389：151－162.

［6］Yanjie L.An average reward performance potential estimation with geometric variance reduction ［C］／／31st Chinese Control Conference.IEEE，2012：2061－2065.

［7］Cao X R.Stochastic learning and optimization：A sensitivitybased approach ［J］.Annual Reviews in Control，2009，33（1）：11－24.

［8］Munos R.Geometric variance reduction in Markov chains：Application to value function and gradient estimation ［J］.Journal of Machine Learning Research，2006：413－427.

［9］CHEN Xuesong，YANG Yimin.Research on the reinforcement learning ［J］.Application Research of Computers，2010，27 （8）：2834－2838 （in Chinese）.［陳學(xué)松，楊宜民.強化學(xué)習(xí)研究綜述 ［J］.計算機應(yīng)用研究，2010，27 （8）：2834－2838.］

［10］ZHOU Ruyi，GAO Yang.A undiscounted reinforcement learning base on the performance potentials ［J］.Guangxi Normal University （Natural Science），2006，24 （4）：58－61（in Chinese）.［周如益，高陽.一種基于性能勢的無折扣強化學(xué)習(xí)算法 ［J］.廣西師范大學(xué)學(xué)報 （自然科學(xué)版），2006，24 （4）：58－61.］

［11］ZUO Guoyu，ZHANG Hongwei，HAN Guangsheng.A reward function based on reinforcement learning of multi－agent［J］.Control Engineering，2009，16 （2）：239－242 （in Chinese）.［左國玉，張紅衛(wèi)，韓光勝.基于多智能體強化學(xué)習(xí)的新強化函數(shù)設(shè)計 ［J］.控制工程，2009，16 （2）：239－242.］