基于多智能體強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)頻譜分配方法綜述

宋 波, 葉 偉, 孟祥輝

(1.航天工程大學(xué)電子與光學(xué)工程系, 北京 101416; 2.中國人民解放軍95801部隊(duì), 北京 100076)

0 引 言

近年來,5G移動(dòng)通信技術(shù)獲得迅速發(fā)展和應(yīng)用,該技術(shù)在物聯(lián)網(wǎng)、車聯(lián)網(wǎng)中具有非常廣泛的應(yīng)用前景,因此導(dǎo)致了無線電設(shè)備數(shù)量的快速增長和對頻譜需求的大幅增加。目前的頻譜管理方式仍然以靜態(tài)分配為主,將頻譜進(jìn)行劃分后分配給固定的授權(quán)用戶,這種已經(jīng)延續(xù)了上百年的頻譜管理體制已經(jīng)無法繼續(xù)滿足網(wǎng)絡(luò)容量的擴(kuò)增對頻譜的需求。

1998年Mitola等人提出了認(rèn)知無線電和認(rèn)知循環(huán)概念[1],引入了一種自動(dòng)感知外部無線環(huán)境,自主決策并機(jī)會(huì)式接入空閑頻譜的新型無線電技術(shù)。Haykin等人對認(rèn)知無線電的構(gòu)成、關(guān)鍵技術(shù)和應(yīng)用前景的進(jìn)一步研究,完善了認(rèn)知循環(huán)定義[2]。IEEE、FCC和ITU等機(jī)構(gòu)均對認(rèn)知無線電給予了充分重視,進(jìn)行了廣泛研究,給出了定義并制定了相關(guān)標(biāo)準(zhǔn),如IEEE 802.22無線地域網(wǎng)標(biāo)準(zhǔn)、IEEE 1900.7動(dòng)態(tài)頻譜接入網(wǎng)絡(luò)標(biāo)準(zhǔn)等。

動(dòng)態(tài)頻譜分配技術(shù)作為認(rèn)知無線電的關(guān)鍵技術(shù),可以大幅提高對頻譜資源的利用效率,改善目前的頻譜資源在開發(fā)利用中存在的不均衡的現(xiàn)象,因此在業(yè)界引起了廣泛關(guān)注與深入研究。目前來看,基于非智能技術(shù)的動(dòng)態(tài)頻譜分配算法的研究根據(jù)理論基礎(chǔ)可以分為以下3個(gè)方向:基于圖論、博弈論和交易理論的方法。其中基于圖論的動(dòng)態(tài)頻譜分配算法把問題抽象為圖論中的頂點(diǎn)著色問題,將各認(rèn)知無線電用戶及其可用信道作為圖中的頂點(diǎn),當(dāng)用戶間不能共用同一信道時(shí),以邊進(jìn)行連接,將頻譜分配過程抽象為對這種被稱為干擾圖的各頂點(diǎn)的逐一著色過程。

干擾圖的頂點(diǎn)著色是一個(gè)非確定多項(xiàng)式難題問題,難以得到最優(yōu)解,Peng等人提出了尋求次優(yōu)解的啟發(fā)式算法[3],該算法需要事先設(shè)定不同應(yīng)用環(huán)境以對不同節(jié)點(diǎn)設(shè)置優(yōu)先級,對優(yōu)先級高的節(jié)點(diǎn)優(yōu)先分配頻譜,當(dāng)信道較多時(shí)計(jì)算復(fù)雜度較高,收斂速度慢。廖楚林等人提出了一種分解復(fù)雜干擾圖為簡單圖的方法,將對節(jié)點(diǎn)的依次染色轉(zhuǎn)化為簡單圖的并行染色[4],改善了順序染色帶來的時(shí)間開銷大的問題。郝丹丹等人提出了一種基于信道回報(bào)的異構(gòu)頻譜分配算法,在首次分配時(shí)以貪婪方法分配信道減小算法迭代次數(shù)[5]。Wang等提出了一種列表著色算法,每一輪隨機(jī)分配信道后在列表中刪去該信道,提升了收斂速度[6]。劉鵬等提出了基于量子遺傳和圖著色方法的動(dòng)態(tài)頻譜分配算法[7],將小生境技術(shù)與量子遺傳算法相結(jié)合,可以解決算法陷入局部最優(yōu)問題,通過動(dòng)態(tài)調(diào)整旋轉(zhuǎn)門并提高染色體閾值,提高了整體收斂速度。何建強(qiáng)等人提出了一種基于顏色敏感圖著色的改進(jìn)方法,以最大化帶寬為目標(biāo)函數(shù),在二次分配時(shí)采取最大公平準(zhǔn)則,在性能上優(yōu)于單一顏色敏感圖著色算法和最大公平準(zhǔn)則算法[8]。

利用博弈論分析與解決多個(gè)認(rèn)知無線電用戶競爭頻譜獲得最大頻譜利用效率的動(dòng)態(tài)頻譜分配算法取得了很好的效果。Neel等人第一次分析了博弈論在認(rèn)知無線電系統(tǒng)中的應(yīng)用前景,推導(dǎo)并提出了在完全潛博弈模型下,動(dòng)態(tài)頻譜分配將最終收斂到納什均衡[9],之后分別分析了利用重復(fù)博弈、短視博弈、S-模博弈、潛博弈的認(rèn)知無線電模型的收斂性[10]。滕志軍等人提出了一種基于潛博弈的分布式算法,通過仿真驗(yàn)證了收斂性[11]。Cao等人提出了一種分布式局部議價(jià)算法,改進(jìn)了一般基于博弈論的頻譜分配納什均衡在環(huán)境拓?fù)浣Y(jié)構(gòu)發(fā)生改變時(shí)必須重新計(jì)算的不足,并根據(jù)Feed Poverty策略提升了算法的公平性[12],但假設(shè)了合作博弈的前提,而一般情況下,各用戶間是非合作關(guān)系。Etkin等人針對非合作博弈下難以收斂到納什均衡的問題,以重復(fù)博弈的方法證明了其長期有效性[13]。徐昌彪等人提出了一種改進(jìn)定價(jià)函數(shù)的博弈論動(dòng)態(tài)頻譜分配模型,并分別在靜態(tài)博弈與動(dòng)態(tài)博弈下進(jìn)行了驗(yàn)證[14]。

除了基于圖論和博弈論的方法外,基于頻譜市場理論和拍賣機(jī)制的動(dòng)態(tài)頻譜分配算法也發(fā)展出了不少成果?；谂馁u理論的動(dòng)態(tài)頻譜分配方法將活躍認(rèn)知用戶視作拍賣競標(biāo)者,將空閑頻譜認(rèn)知用戶視作拍賣出售者,基站作為拍賣交易方協(xié)調(diào)競標(biāo)與出售過程[15]。Chen等人提出了一種基于簡化VGG(Vickrey-Clark-Groves)模型的頻譜拍賣算法,根據(jù)累積參與與成功接入次數(shù)提出了一種基于首次定價(jià)封閉拍賣的新叫價(jià)方法,降低了頻譜切換時(shí)的通信中斷并提高了頻譜分配的公平性[16]。Zhou等人提出了一種可信雙頻譜拍賣模型,解決了頻譜重復(fù)利用和雙拍賣中的不可信問題[17]。Wang等人考慮以最大化頻譜利用率作為目標(biāo)函數(shù),引入近似誠信概念,兼顧頻譜利用率與誠信,可以最大化頻譜拍賣者利潤[18]。基于拍賣理論的方法整體上雖然能在限定主次用戶條件下收斂到最大化頻譜利用效率,但缺乏靈活性。

上述算法雖然可以解決動(dòng)態(tài)頻譜分配中的頻譜利用與用戶通信效能和網(wǎng)絡(luò)通信效能間的約束與優(yōu)化問題,但存在靈活性差,收斂速度慢和無法滿足分布式條件下需求的問題。這種中心化的分配方法對控制中心與用戶間的通信條件和頻譜感知的精確性要求比較高,在實(shí)際中實(shí)現(xiàn)難度大。

隨著近年來強(qiáng)化學(xué)習(xí)等機(jī)器學(xué)習(xí)研究領(lǐng)域的快速發(fā)展,基于機(jī)器學(xué)習(xí)算法的智能動(dòng)態(tài)頻譜分配方法逐漸吸引了越來越多研究者的注意。

強(qiáng)化學(xué)習(xí)(reinforcement learning, RL)是為解決馬爾可夫決策過程(Markov decision process, MDP)策略優(yōu)化問題發(fā)展出的機(jī)器學(xué)習(xí)算法分支,用于解決具有馬爾可夫性的動(dòng)態(tài)環(huán)境序貫決策問題。

近年來,在多智能體系統(tǒng)問題中引入RL后獲得了很好的效果,多智能體強(qiáng)化學(xué)習(xí)(multi-agent reinforcement learning, MARL)方法逐漸成為機(jī)器學(xué)習(xí)與群體智能的研究熱點(diǎn),而多認(rèn)知用戶網(wǎng)絡(luò)在分布式?jīng)Q策模式下的動(dòng)態(tài)頻譜分配問題可以視為多個(gè)智能體的分布式馬爾可夫決策過程。這種分布式群體智能方法在動(dòng)態(tài)頻譜分配問題中的應(yīng)用前景十分廣闊。

下面首先對RL和MARL的相關(guān)理論基礎(chǔ)進(jìn)行簡要介紹并對發(fā)展現(xiàn)狀進(jìn)行梳理;對近年來基于MARL的動(dòng)態(tài)頻譜分配方法方面的相關(guān)工作進(jìn)行了歸納與分析;最后對當(dāng)前算法中存在的關(guān)鍵問題與解決思路進(jìn)行概括與展望。

1 強(qiáng)化學(xué)習(xí)

認(rèn)知環(huán)的感知與決策過程如圖1所示,基于圖論的頻譜分配模型如圖2所示。

圖1 認(rèn)知環(huán)的感知與決策過程

圖2 基于圖論的頻譜分配模型

RL是一種針對MDP長期收益最大化的機(jī)器學(xué)習(xí)算法。而MDP可以這樣描述:如果環(huán)境當(dāng)前狀態(tài)st,智能體觀測到該狀態(tài)后,根據(jù)策略π(at|st)選取動(dòng)作at,環(huán)境根據(jù)狀態(tài)轉(zhuǎn)移概率p(st+1|st,at)∈(0,1)進(jìn)入下一狀態(tài)st+1,智能體根據(jù)動(dòng)作好壞獲得環(huán)境給予的即時(shí)獎(jiǎng)勵(lì)rt,由于智能體做出決策只基于st,與之前的所有狀態(tài)s0,s1,…,st-1無關(guān),因此(s,a,r)具有馬爾可夫鏈性質(zhì),MDP如圖3所示。

圖3 MDP示意圖

根據(jù)貝爾曼方程,狀態(tài)st的價(jià)值函數(shù)v(st)為

(1)

式中:{at}表示t時(shí)刻所有動(dòng)作的集合；{st+1}表示t+1時(shí)刻所有狀態(tài)的集合；γ∈(0,1)為折扣因子,表示未來狀態(tài)下的獎(jiǎng)勵(lì)對當(dāng)前策略的影響程度。

為表征動(dòng)作a的好壞,定義動(dòng)作狀態(tài)價(jià)值函數(shù)(也稱為Q函數(shù))q(st,at)為

q(st,at)=

(2)

式中：{at+1}表示t+1時(shí)刻所有動(dòng)作的集合。

根據(jù)是否學(xué)習(xí)p(st+1|st,at)與rt,可以將強(qiáng)化學(xué)習(xí)方法分為基于模型的RL(model-based RL, MBRL)方法和與模型無關(guān)的RL(model-free RL, MFRL)方法兩類。其中,MFRL已成為當(dāng)前的主流方向。下面分別對基于值函數(shù)和策略梯度的MFRL算法與MBRL算法進(jìn)行介紹。

1.1 基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法

1.1.1 Q-學(xué)習(xí)方法

Q-學(xué)習(xí)是一種經(jīng)典的時(shí)序差分RL算法,Q-學(xué)習(xí)將當(dāng)前時(shí)刻的回報(bào)與下一時(shí)刻的狀態(tài)Q函數(shù)的最大值作為當(dāng)前狀態(tài)最優(yōu)策略的Q值估計(jì),以其與當(dāng)前狀態(tài)下Q函數(shù)的誤差對當(dāng)前狀態(tài)下的Q函數(shù)進(jìn)行更新:

(3)

式(3)的更新過程如圖4所示。

圖4 Q-學(xué)習(xí)更新過程

Q-學(xué)習(xí)的訓(xùn)練過程中需要建立并初始化一個(gè)|S|×|A|(S為環(huán)境狀態(tài)空間)的Q值表格,根據(jù)式(3)迭代更新該表格,待其收斂后,最佳策略π*(st|at)為

(4)

表格式Q-學(xué)習(xí)無法應(yīng)用于狀態(tài)空間和動(dòng)作空間都很大或者動(dòng)作空間連續(xù)或不存在終止?fàn)顟B(tài)的問題中,而深度Q-學(xué)習(xí)能有效解決這些問題。

1.1.2 深度Q-學(xué)習(xí)方法

2015年,一種結(jié)合了深度神經(jīng)網(wǎng)絡(luò)擬合能力的Q函數(shù)擬合方法——深度Q-學(xué)習(xí)(deep Q-learning, DQL)被Mnih等人提出[19],大幅提升了RL在復(fù)雜環(huán)境下的學(xué)習(xí)能力,引起了廣泛關(guān)注。

在文獻(xiàn)[19]中,作者提出的深度Q-網(wǎng)絡(luò)(deep Q-network, DQN)將Atari游戲畫面直接輸入卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行狀態(tài)特征提取,利用2層全連接層進(jìn)行Q函數(shù)的擬合，DQN結(jié)構(gòu)如圖5所示。同時(shí)提出了經(jīng)驗(yàn)回放、隨機(jī)采樣、批次訓(xùn)練等技術(shù)減小樣本間的相關(guān)以加快DQN訓(xùn)練速度,DQN是一種端到端學(xué)習(xí)的RL算法。

圖5 深度Q-網(wǎng)絡(luò)

由于在Q-學(xué)習(xí)和DQL中,Q值的估計(jì)直接利用下一狀態(tài)最優(yōu)Q值,造成了對Q值的過高估計(jì)。因此,Hasselt等人提出了一種雙Q-學(xué)習(xí)方法以改善對Q值的過高估計(jì)造成的訓(xùn)練波動(dòng)問題[20],并將其與DQN結(jié)合,提出了一種改進(jìn)后的深度雙Q網(wǎng)絡(luò)(double deep Q-network, DDQN)算法[21],在估計(jì)當(dāng)前Q值時(shí)用相同結(jié)構(gòu),但參數(shù)不同的另一個(gè)DQN(稱為目標(biāo)網(wǎng)絡(luò))代替,用行為網(wǎng)絡(luò)與環(huán)境交互,有效改善了DQN訓(xùn)練不穩(wěn)定的問題。Wang等人將Q函數(shù)分解為狀態(tài)價(jià)值函數(shù)V與各動(dòng)作的優(yōu)勢函數(shù)A(ai)的組合,提高了Q函數(shù)的表示能力,在Atari游戲環(huán)境中獲得了超過DQN的表現(xiàn)[22]。Fortunato等人為提高DQL算法的策略探索能力,提出了一種在DQN參數(shù)中加入隨機(jī)噪聲的Noisy Net算法[23],通過在神經(jīng)網(wǎng)絡(luò)超參數(shù)中隨機(jī)加噪的方法提高了DQN在價(jià)值函數(shù)表示的多樣性與隨機(jī)性。Hessel等人將上述改進(jìn)進(jìn)行了有效結(jié)合并全部集中在了所提出的Rainbow算法中[24],成為DQL的發(fā)展里程碑與集大成者。

DQL相比于表格式Q-學(xué)習(xí)方法解決了在連續(xù)狀態(tài)空間下的適用性,但仍無法有效解決連續(xù)動(dòng)作空間如機(jī)械手臂的連續(xù)控制問題。Gu等人提出的歸一化優(yōu)勢函數(shù)(normalized advantage functions, NAF)算法[25]第一次將Q-學(xué)習(xí)算法完整的拓展到了連續(xù)控制問題中。NAF采用了與競爭DQN[22]類似的思路,將Q函數(shù)分解為優(yōu)勢函數(shù)與狀態(tài)價(jià)值函數(shù)的組合,將狀態(tài)輸入神經(jīng)網(wǎng)絡(luò)中輸出動(dòng)作并作為Q-學(xué)習(xí)方法中的最大價(jià)值動(dòng)作,以被評估動(dòng)作與Q函數(shù)最優(yōu)值的差構(gòu)建一個(gè)二次型作為優(yōu)勢函數(shù),利用經(jīng)驗(yàn)回放、隨機(jī)采樣與批次訓(xùn)練等DQN的經(jīng)典技巧進(jìn)行訓(xùn)練。NAF算法的提出擴(kuò)展了DQN的應(yīng)用范圍。

下面對MFRL的另一條發(fā)展路徑——基于策略梯度的RL方法進(jìn)行簡要介紹。

1.2 基于策略梯度的強(qiáng)化學(xué)習(xí)方法

1.2.1 隨機(jī)策略梯度算法

相比于值函數(shù)方法通過搜索Q值最大的動(dòng)作獲得最優(yōu)策略,策略梯度方法直接通過訓(xùn)練優(yōu)化策略函數(shù)π(a|s),同時(shí)由于策略函數(shù)是動(dòng)作的概率分布,天然地保留了一定的探索性,也有避免陷入局部最優(yōu)的優(yōu)勢。

如果智能體在參數(shù)為ω的策略函數(shù)πω(a|s)下對環(huán)境進(jìn)行探索與采樣,軌跡為T,在使得T的累積獎(jiǎng)勵(lì)最大的優(yōu)化目標(biāo)下,可以得到目標(biāo)函數(shù)ytarget(ω)為

(5)

式中:r(T)為軌跡T下的獎(jiǎng)勵(lì)函數(shù)。

可利用梯度上升法求上述目標(biāo)函數(shù)的最大值,對式(5)求導(dǎo)可得

(6)

式(5)被稱為策略梯度(policy gradient, PG),在離散動(dòng)作空間問題中,將式(6)中求數(shù)學(xué)期望的形式變換一下,可得

(7)

同時(shí)可以利用優(yōu)勢函數(shù)Aπ,γ:

Aπ,γ=r+γ·v(st+1)-v(st)

(8)

代替式(7)中的累積獎(jiǎng)勵(lì),可以顯著改善訓(xùn)練中策略梯度的波動(dòng)。

Konda等人提出的行動(dòng)器—評判器(actor-critic, AC)算法[26]中利用線性擬合算法擬合πω(a|s)、價(jià)值函數(shù)v(s)與優(yōu)勢函數(shù)Aπ,γ,以優(yōu)勢函數(shù)Aπ,γ作為損失函數(shù)進(jìn)行訓(xùn)練;Mnih等人提出了一種用深度神經(jīng)網(wǎng)絡(luò)分別擬合πω(a|s)與v(s),并利用多線程采樣交互進(jìn)行訓(xùn)練的異步優(yōu)勢AC(asynchronous advantage AC, A3C)算法[27],有效提升了訓(xùn)練速度。

這些基于策略梯度的AC算法對策略的訓(xùn)練需要基于當(dāng)前策略與環(huán)境的交互數(shù)據(jù)支撐,這種同策略方法存在策略函數(shù)方差大、訓(xùn)練不夠穩(wěn)定的問題。因此,Schulman等從策略更新約束的角度提出了改進(jìn)方法:利用更新前后的策略分布KL散度作為約束項(xiàng)以提高收斂穩(wěn)定性,稱為置信域策略優(yōu)化(trust region policy optimization, TRPO)算法[28],但該算法每次更新需要計(jì)算費(fèi)舍爾信息矩陣的逆,計(jì)算復(fù)雜度比較高,后Wu等人提出用Kronecker分解來降低費(fèi)舍爾信息矩陣求逆運(yùn)算的復(fù)雜度[29];Schulman等人后來又提出一種TRPO算法的改進(jìn)算法:近端策略優(yōu)化(proximal policy optimization, PPO)算法,PPO算法通過限制更新前后策略分布比率的范圍代替TRPO的復(fù)雜優(yōu)化方法,使得計(jì)算復(fù)雜度大幅降低,但實(shí)際效果不低于TRPO算法[30]。

為改善隨機(jī)策略梯度方法基于同策略更新,無法充分利用歷史交互數(shù)據(jù)的缺陷,Wang等人提出了一種異策略更新的AC算法——經(jīng)驗(yàn)回放AC算法(actor-critic experience replay, ACER)[31],利用了Munos等人提出的Retrace算法[32]使用異策略經(jīng)驗(yàn)緩存更新當(dāng)前策略的Q函數(shù),利用重要性采樣方法進(jìn)行策略梯度的更新;同時(shí),為解決策略梯度波動(dòng)的問題,提出了一種類似于TRPO算法的KL散度約束以降低策略梯度方差,但由于只用了KL散度的一階導(dǎo),計(jì)算復(fù)雜度上比TRPO算法低。

由于A3C、TRPO、PPO等隨機(jī)策略梯度算法不能利用歷史數(shù)據(jù)進(jìn)行學(xué)習(xí),而ACER算法雖然利用了重要性采樣等手段具備了異策略更新的能力,但DQN中的隨機(jī)采樣、批次訓(xùn)練等可以提高訓(xùn)練效率的手段難以應(yīng)用到Critic的更新上。確定策略梯度算法可以很好地解決這個(gè)問題。

1.2.2 確定策略梯度算法

Silver等人提出一種使得AC算法中策略梯度更新與價(jià)值函數(shù)更新解耦,從而可以利用隨機(jī)采樣和批次訓(xùn)練加快價(jià)值函數(shù)訓(xùn)練的深度確定性策略梯度(deep deterministic policy gradient, DDPG)方法,有效提升了AC算法的收斂性[33]。隨機(jī)策略梯度算法中策略網(wǎng)絡(luò)輸出動(dòng)作空間的概率分布,根據(jù)分布采樣得到具體動(dòng)作,DDPG算法則直接輸出確定動(dòng)作,如果以參數(shù)為β的深度神經(jīng)網(wǎng)絡(luò)μβ(s)擬合該函數(shù),以參數(shù)為θ的深度神經(jīng)網(wǎng)絡(luò)Qθ(s,a)擬合價(jià)值函數(shù),則目標(biāo)函數(shù)可以這樣定義:

(9)

(10)

式中:ytarget(θ)為值函數(shù)網(wǎng)絡(luò)更新的目標(biāo)函數(shù);ytarget(β)為策略網(wǎng)絡(luò)更新的目標(biāo)函數(shù)。

作者證明了Qθ(s,a)不必遵從固定策略,這意味著可以通過經(jīng)驗(yàn)緩存機(jī)制更有效率的訓(xùn)練價(jià)值函數(shù),但基于TD-error的更新容易過高估計(jì)Q函數(shù)。

為解決DDPG過高估計(jì)Q函數(shù)的問題,Fujimoto等人提出的雙延遲深度確定性策略梯度算法(twin delayed deep deterministic poli-cy gradient algorithm, TD3)[34]進(jìn)行了如下改進(jìn):① 同時(shí)訓(xùn)練兩個(gè)Q函數(shù),選擇輸出較小的值;② 延遲更新策略網(wǎng)絡(luò),減小策略更新的波動(dòng);③ 在策略網(wǎng)絡(luò)輸出中加噪聲,以平滑Q函數(shù)的估計(jì)誤差。

DDPG與TD3雖然實(shí)現(xiàn)了連續(xù)動(dòng)作問題的異策略學(xué)習(xí),但由于其采用了確定性的動(dòng)作策略網(wǎng)絡(luò),訓(xùn)練過程對超參數(shù)(如學(xué)習(xí)率α等)的調(diào)整比較敏感,而且確定性策略輸出帶來了對環(huán)境探索性不足的問題。因此,Haarnoja等人提出通過在Critic部分的Q函數(shù)中加入熵約束的軟AC(soft AC, SAC)算法,學(xué)習(xí)過程中不但要最大化Q函數(shù),同時(shí)要最大化動(dòng)作的熵,以增強(qiáng)動(dòng)作的探索性[35]。

1.3 基于模型的強(qiáng)化學(xué)習(xí)方法

RL的經(jīng)典算法動(dòng)態(tài)規(guī)劃(dynamic programming, DP)以當(dāng)前狀態(tài)為根節(jié)點(diǎn),根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)與策略函數(shù)建立未來狀態(tài)作為葉子節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移樹型結(jié)構(gòu),根據(jù)樹型結(jié)構(gòu)計(jì)算每個(gè)狀態(tài)下的葉子節(jié)點(diǎn)(后續(xù)狀態(tài))的期望累積回報(bào),這是一種典型的MBRL方法。但這種方法在計(jì)算狀態(tài)的價(jià)值時(shí)需要遍歷所有以該狀態(tài)為根節(jié)點(diǎn)的所有葉子節(jié)點(diǎn)狀態(tài),在狀態(tài)空間很大的問題上實(shí)現(xiàn)起來復(fù)雜度過高。

基于模型的Dyna算法框架首先由Sutton等人提出[36],是一種結(jié)合了MBRL和MFRL的算法。該算法中,首先初始化一個(gè)狀態(tài)轉(zhuǎn)移模型,根據(jù)當(dāng)前狀態(tài)和動(dòng)作輸出下一狀態(tài)和當(dāng)前(s,a)下的獎(jiǎng)勵(lì);初始化Q函數(shù)。在與環(huán)境交互過程中,根據(jù)Q函數(shù)結(jié)合貪婪策略進(jìn)行軌跡的更新,根據(jù)交互軌跡對Q函數(shù)和模型分別進(jìn)行更新;同時(shí)隨機(jī)產(chǎn)生狀態(tài)與動(dòng)作輸入模型后,利用模型輸出的下一狀態(tài)與獎(jiǎng)勵(lì)對Q函數(shù)進(jìn)行n次更新。Silver等人提出的Dyna-2算法[37]對Dyna算法進(jìn)行了改進(jìn):該算法在每輪的更新中需要重新建立一個(gè)稱為瞬時(shí)記憶的Q′函數(shù),利用Q′進(jìn)行策略的選擇以產(chǎn)生交互軌跡,對模型與被稱為長期記憶的Q函數(shù)進(jìn)行更新。

相比于Dyna算法每一次更新需要對環(huán)境進(jìn)行完整的蒙特卡羅探索,蒙特卡羅樹搜索(Monte-Carlo tree search, MCTS)算法[38]首先通過隨機(jī)采樣動(dòng)作后得到當(dāng)前狀態(tài)為根節(jié)點(diǎn)的子節(jié)點(diǎn),如果該子節(jié)點(diǎn)尚未被探索就將其加入蒙特卡羅樹中,之后在該節(jié)點(diǎn)后用模擬交互的方法直到得到終止?fàn)顟B(tài),根據(jù)模擬交互得到的終止?fàn)顟B(tài)獲得的獎(jiǎng)勵(lì)對該子節(jié)點(diǎn)處的總探索數(shù)及勝利數(shù)(以圍棋為例)信息進(jìn)行更新,在之后對該節(jié)點(diǎn)的探索中以置信度上界(upper confidence bound, UCB)方法在此信息的基礎(chǔ)上增加隨機(jī)性并作為采樣的依據(jù)。

MBRL在AlphaGo[39]算法中大獲成功,在2016年AlphaGo以5∶0擊敗了歐洲圍棋冠軍樊麾,2017年以3∶0擊敗了專業(yè)9段棋手柯潔,在人工智能的研究中具有里程碑式的意義。該算法結(jié)合了MCTS與AC算法的優(yōu)勢,首先利用人類專業(yè)棋手的對決棋譜和監(jiān)督學(xué)習(xí)方法對策略網(wǎng)絡(luò)進(jìn)行訓(xùn)練,并開創(chuàng)性地采用了一種自博弈方法進(jìn)一步對策略網(wǎng)絡(luò)進(jìn)行提升,在MCTS的初始搜索中利用訓(xùn)練好的策略網(wǎng)絡(luò)指導(dǎo)探索行為,避免了從零開始學(xué)習(xí)。

在其后續(xù)的改進(jìn)版本AlphaZero中[40],進(jìn)一步強(qiáng)化了自博弈方法的重要性,DeepMind團(tuán)隊(duì)利用與AlphaGo的自博弈代替人類專業(yè)棋手的棋譜來監(jiān)督訓(xùn)練的方法大幅度提高了AlphaZero算法的訓(xùn)練速度與效果,同樣利用MCTS方法進(jìn)行策略搜索與狀態(tài)轉(zhuǎn)移模型的學(xué)習(xí)。

AlphaGo與AlphaZero算法的成功大大刺激了基于模型算法的研究熱度,但這種專門針對圍棋和象棋等棋類游戲的強(qiáng)化學(xué)習(xí)算法如何泛化在其他領(lǐng)域的問題中也被人們經(jīng)常討論和質(zhì)疑。而MuZero算法的提出[41]為這個(gè)問題的解決提出了一種前景非常廣闊的思路:通過環(huán)境轉(zhuǎn)移模型在建模時(shí)以隱藏狀態(tài)的形式進(jìn)行表示與學(xué)習(xí),在減小狀態(tài)空間復(fù)雜度的同時(shí)不以精確表示真實(shí)的環(huán)境狀態(tài)轉(zhuǎn)移為目的,而是以對策略提升的貢獻(xiàn)為評價(jià)指標(biāo),同時(shí)利用了MCTS方法以解決狀態(tài)空間過大的問題。該算法的提出把AlphaGo及后續(xù)改進(jìn)的算法拓展到雅達(dá)利游戲測試環(huán)境中,在同MFRL和其他MBRL基線算法的對比中取得了最好的結(jié)果。

近年來,人們開始考慮利用離線采樣交互的軌跡代替智能體與環(huán)境交互利用試錯(cuò)的方法進(jìn)行強(qiáng)化學(xué)習(xí),如模仿學(xué)習(xí)與結(jié)合了生成式對抗網(wǎng)絡(luò)(generative adversarial network, GAN)[42]思想的生成式對抗模仿學(xué)習(xí)(generative adversarial imitation learning, GAIL)[43]以及離線學(xué)習(xí)(offline reinforcement learning, ORL)[44]。這些方法立足于改善現(xiàn)存的強(qiáng)化學(xué)習(xí)算法在訓(xùn)練過程中必須不斷重新與環(huán)境交互的過程,致力于解決利用離線的采樣數(shù)據(jù)進(jìn)行強(qiáng)化學(xué)習(xí)訓(xùn)練過程中存在的問題,也同樣是強(qiáng)化學(xué)習(xí)的熱點(diǎn)方向之一。

當(dāng)強(qiáng)化學(xué)習(xí)應(yīng)用在實(shí)際問題的解決中不可避免的遇到了在部分復(fù)雜控制問題中所遇到的維度災(zāi)難問題,特別是在下文中提到的集中式MARL問題中隨著智能體個(gè)數(shù)的增加而出現(xiàn)的維度指數(shù)性增長。而分層強(qiáng)化學(xué)習(xí)在近年來由于其具有的分解復(fù)雜任務(wù)空間為子空間的特性,在解決狀態(tài)空間非常大的問題時(shí)相比于其他強(qiáng)化學(xué)習(xí)方法具有明顯的優(yōu)勢,受到了研究者們的廣泛關(guān)注。分層強(qiáng)化學(xué)習(xí)中基于選項(xiàng)、基于分層抽象以及基于值函數(shù)分解[45]的思想已經(jīng)部分應(yīng)用于多智能體問題的解決中,特別是利用基于值函數(shù)分解的方法解決MARL方面已經(jīng)涌現(xiàn)出了不少成果,是最近受到廣泛關(guān)注的熱點(diǎn)方向。

2 多智能體強(qiáng)化學(xué)習(xí)

MARL與單智能體RL所不同之處在于其要解決的是分布式部分可觀測MDP(decentralized partially observable MDP, Dec-POMDP)。Dec-POMDP可用一個(gè)元組〈N,S,A,R,T,γ,O〉來表示,其中N表示智能體集合;S表示環(huán)境全局狀態(tài)空間;A表示智能體聯(lián)合動(dòng)作空間,動(dòng)作向量a=[a1,a2,…,ai,…]∈A,其中ai代表智能體i的獨(dú)立動(dòng)作;R表示當(dāng)前狀態(tài)-動(dòng)作對(s,a1,a2,…,ai,…)下的全局獎(jiǎng)勵(lì)函數(shù);T代表環(huán)境的狀態(tài)轉(zhuǎn)移函數(shù)T(s′|s,A)∈(0,1);γ為折扣因子;O為各時(shí)刻智能體部分觀測狀態(tài)向量[o1,o2,…,oi,…]。Dec-POMDP如圖6所示。

圖6 部分可觀測MDP

對于多智能體在環(huán)境中的學(xué)習(xí)過程,當(dāng)采用中心化訓(xùn)練時(shí),以完全合作博弈來描述;當(dāng)采用無中心化的完全競爭模式進(jìn)行訓(xùn)練時(shí),以完全競爭博弈來描述;當(dāng)采用無中心化的混合策略進(jìn)行訓(xùn)練時(shí),即智能體間既競爭又合作時(shí),以隨機(jī)博弈來描述[46]。

MARL的優(yōu)化目標(biāo)可以用一個(gè)納什均衡來表示:

(11)

MARL相比于單智能體強(qiáng)化學(xué)習(xí)的難點(diǎn)在于對每個(gè)智能體來說,其他智能體的策略優(yōu)化過程構(gòu)成了環(huán)境的一部分,因此對每個(gè)智能體來說,環(huán)境的狀態(tài)轉(zhuǎn)移概率是非平穩(wěn)的,這就意味著如果不加限制地利用單智能體強(qiáng)化學(xué)習(xí)方法解決多智能體問題,會(huì)存在收斂困難的問題。

隨著近年來DQN、DDPG等深度強(qiáng)化學(xué)習(xí)算法的提出,吸收了這些算法優(yōu)點(diǎn)的多智能體深度強(qiáng)化學(xué)習(xí)算法逐漸發(fā)展起來并取得了一系列成果。

按照MARL算法的訓(xùn)練與決策方式,可以分為3種類型,即集中訓(xùn)練集中執(zhí)行、集中訓(xùn)練分布執(zhí)行與分布訓(xùn)練分布執(zhí)行模式[52]。

集中訓(xùn)練集中執(zhí)行模式下,通過一個(gè)中心訓(xùn)練并控制所有智能體的行為。Sukhbaatar等人提出了一種CommNet算法和隱層信息池化共享的思想,利用深度神經(jīng)網(wǎng)絡(luò)(deep neural network, DNN)的全連接性進(jìn)行隱式的信息共享,同時(shí)利用平均池化方法可以適用于智能體數(shù)量變化的場景[53]。Peng等提出了一種BicNet算法,利用循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network, RNN)的記憶功能,依靠隱藏狀態(tài)hi在各智能體間共享信息[54]。

此類方法存在的問題主要是:隨著智能體數(shù)量的增加,聯(lián)合動(dòng)作空間呈指數(shù)增長,導(dǎo)致了計(jì)算復(fù)雜度增加,訓(xùn)練難度加大;同時(shí)也無法解決智能體信用分配避免“懶惰智能體”問題。

在分布訓(xùn)練分布執(zhí)行模式下,可分為基于獨(dú)立值函數(shù)的學(xué)習(xí)——獨(dú)立Q-學(xué)習(xí)(independent Q-learning, IQL)與基于AC結(jié)構(gòu)的算法兩種。其中,Tan等人最早提出IQL方法[55],在同構(gòu)智能體前提下,作者證明了IQL能收斂到團(tuán)隊(duì)最優(yōu)均衡策略;Littman等人提出的Team-Q算法能在確定環(huán)境條件下收斂,但如果環(huán)境是非平穩(wěn)的則難以收斂[47];Matignon等人提出了一種滯后Q-學(xué)習(xí)算法[56],通過設(shè)置兩個(gè)不同的學(xué)習(xí)率因子調(diào)整價(jià)值函數(shù)的更新;基于此,Omidshafiei等人采用基于RNN的DQN代替了之前的表格學(xué)習(xí)[57],加入RNN結(jié)構(gòu)的DQN具有記憶能力,能在一定程度上克服環(huán)境的非平穩(wěn)性造成的難以訓(xùn)練的問題。

基于AC結(jié)構(gòu)的獨(dú)立學(xué)習(xí)算法有Perolat等人提出的虛構(gòu)AC算法[58],該算法通過對行動(dòng)器與評判器設(shè)置不同的更新延遲,以增加策略更新的穩(wěn)定性。

分布訓(xùn)練分布執(zhí)行模式算法在無相互協(xié)作和全局信息的條件下進(jìn)行獨(dú)立訓(xùn)練存在的主要問題是訓(xùn)練難度大,隨著智能體數(shù)量增加,收斂變得非常困難。

集中訓(xùn)練分布執(zhí)行結(jié)構(gòu)下智能體間可以建立通信從而傳遞信息進(jìn)行協(xié)調(diào),由于深度強(qiáng)化學(xué)習(xí)的興起,智能體間可以利用DNN中的全連接層進(jìn)行信息傳遞與融合,這方面具有代表性的算法有:Foerster等人提出的增強(qiáng)型智能體間學(xué)習(xí)(reinforced inter-agent learning, RIAL)與微分型智能體間學(xué)習(xí)(differential inter-agent learning, DIAL)[59],代表各智能體的DQN均以RNN構(gòu)建并相互串聯(lián),將并行決策架構(gòu)改為串行決策架構(gòu),利用RNN的記憶功能對智能體間的動(dòng)作進(jìn)行學(xué)習(xí)與協(xié)調(diào);Mao等人提出了一種基于AC架構(gòu)的多智能體協(xié)作學(xué)習(xí)方法AC-CNet與A-CCNet[60],其中AC-CNet在行動(dòng)器端建立通信網(wǎng)絡(luò)進(jìn)行信息編碼與交換,A-CCNet則在評判器端進(jìn)行信息編碼與共享;Lowe等人則提出了一種多智能體深度確定性策略梯度(multi-agent deep deterministic policy gradient, MADDPG)算法[61],在集中訓(xùn)練下,利用全局狀態(tài)信息分別訓(xùn)練各個(gè)智能體的值函數(shù)網(wǎng)絡(luò),促進(jìn)各智能體的策略網(wǎng)絡(luò)進(jìn)行更新。

針對集中訓(xùn)練的MARL算法無法有效解決智能體信用分配問題從而容易導(dǎo)致出現(xiàn)“懶惰智能體”現(xiàn)象的問題,Foerster等提出了一種反事實(shí)基線MARL(counterfactual baseline of MARL, COMA)算法[62],以非納什均衡策略下聯(lián)合Q函數(shù)的期望與納什均衡策略聯(lián)合Q函數(shù)得到反事實(shí)基線,依此評估單個(gè)智能體對總體收益所做貢獻(xiàn);而Sunehag等人則結(jié)合分層強(qiáng)化學(xué)習(xí)中的值函數(shù)分解方法,將其應(yīng)用在MARL的智能體信用評價(jià)上[63],論文中提出的分解方法建立了兩個(gè)強(qiáng)假設(shè):① 聯(lián)合價(jià)值函數(shù)對獨(dú)立價(jià)值函數(shù)是單調(diào)的;② 聯(lián)合價(jià)值函數(shù)與獨(dú)立價(jià)值函數(shù)符合線性擬合的關(guān)系。這兩點(diǎn)假設(shè)在實(shí)際情況下均不容易滿足。因此,Rashid等人提出了一種改進(jìn)的值函數(shù)分解方法——QMIX[64],該算法利用全連接層對聯(lián)合值函數(shù)與獨(dú)立值函數(shù)的關(guān)系進(jìn)行非線性擬合,提升了分解的多樣化,增強(qiáng)了獨(dú)立值函數(shù)的表示能力。隨著多頭注意力機(jī)制[65]在深度學(xué)習(xí)研究中獲得越來越廣泛的關(guān)注,Yang等人提出了一種利用泰勒展開對聯(lián)合值函數(shù)進(jìn)行非線性分解的Qatten算法,并利用多頭注意力機(jī)制網(wǎng)絡(luò)實(shí)現(xiàn)了不同階數(shù)系數(shù)的訓(xùn)練,在多智能體實(shí)驗(yàn)環(huán)境星際爭霸多智能體挑戰(zhàn)賽(starcraft multi-agent challenge, SMAC)中取得了很好的效果[66]。

MARL方法近年來獲得了迅速發(fā)展,雖然還存在理論支撐較少、算法的泛化性不足等問題,但在應(yīng)用并解決自動(dòng)駕駛[67]、集群規(guī)劃[68]、資源調(diào)度[69]等問題中已經(jīng)顯示出較好的前景,在認(rèn)知無線電與動(dòng)態(tài)頻譜分配的研究者中也有越來越多的人將目光投入這一生機(jī)勃勃且前景廣闊的研究領(lǐng)域中,涌現(xiàn)出了一些開創(chuàng)性的工作,下面將進(jìn)行簡要介紹。

3 基于多智能體強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)頻譜分配方法

基于傳統(tǒng)算法如圖染色法、博弈論與交易理論的方法需要利用中心控制實(shí)體對頻譜資源進(jìn)行分配。這些方法存在的共性問題主要是頻譜分配控制中心與用戶間的通信需要占用大量資源,并且這些算法魯棒性差,環(huán)境發(fā)生變化時(shí)必須重新進(jìn)行分配,因此時(shí)間開銷比較大,達(dá)不到實(shí)際應(yīng)用中動(dòng)態(tài)頻譜分配的實(shí)時(shí)性要求。

而利用MARL方法恰好能解決這樣的問題,各智能體可以根據(jù)對信道環(huán)境的部分觀測信息,根據(jù)訓(xùn)練所得的經(jīng)驗(yàn)進(jìn)行分布式?jīng)Q策并收斂到最優(yōu)。當(dāng)外部環(huán)境變化時(shí),各個(gè)用戶(智能體)可以根據(jù)訓(xùn)練好的策略迅速進(jìn)行響應(yīng),并快速收斂。這種智能化的動(dòng)態(tài)頻譜分配方法在對動(dòng)態(tài)環(huán)境的適應(yīng)性和重新分配頻譜的實(shí)時(shí)性上相比傳統(tǒng)的算法具有巨大的優(yōu)勢。

3.1 基于Dec-POMDP的動(dòng)態(tài)頻譜分配模型分析

動(dòng)態(tài)頻譜分配模型的研究是研究動(dòng)態(tài)分配算法的基礎(chǔ),也是認(rèn)知無線電理論研究的重要方面,Zhao等人[70]總結(jié)了動(dòng)態(tài)頻譜分配的研究成果,將動(dòng)態(tài)頻譜分配模型總結(jié)為專用模型、開放共享模型和分層接入模型3種,其中專用模型分為頻譜產(chǎn)權(quán)模型與動(dòng)態(tài)專有模型;分層接入模型分為頻譜下墊接入模型與機(jī)會(huì)式頻譜接入模型兩種。動(dòng)態(tài)頻譜分配模型分類如圖7所示。

圖7 動(dòng)態(tài)頻譜分配模型

其中頻譜產(chǎn)權(quán)模型下各用戶把擁有的頻譜作為可自由支配的財(cái)產(chǎn),可以互相租賃、出售,無需監(jiān)管部門介入;動(dòng)態(tài)專有模型下根據(jù)各用戶的頻譜需求在空域與頻譜對頻譜資源進(jìn)行快速分配;開放共享模型中無主次用戶的區(qū)別,可以采取合作(或中心化)和競爭(或去中心化)的頻譜分配方式,在工業(yè)、科學(xué)、醫(yī)療頻段這些無授權(quán)用戶的頻段中可以采用這樣的接入方式;頻譜下墊接入模型中認(rèn)知用戶通過微功率技術(shù)(如超寬帶技術(shù))接入頻譜,需要滿足主用戶接收端的干擾溫度約束[71];機(jī)會(huì)式頻譜接入模型既是Mitola在關(guān)于認(rèn)知無線電的定義中建議的一種模型,也是最能夠兼容當(dāng)前的頻譜管理政策與無線電系統(tǒng)的模型,因此成為了當(dāng)前認(rèn)知無線電研究領(lǐng)域的主流[70]。

南京郵電大學(xué)的夏婷婷等人針對多認(rèn)知用戶下的機(jī)會(huì)式頻譜接入問題,提出了一種基于Dec-POMDP的模型[73],以各信道的可用性作為狀態(tài)向量s(t)=[s1,s2,…,sN],sn∈{0(空閑),1(占用)},1≤n≤N,以各認(rèn)知用戶的頻譜接入行為作為動(dòng)作向量a(t)=[a1(t),a2(t),…,aN(t)],其中an(t)表示各用戶在時(shí)隙t的頻譜接入動(dòng)作(選擇哪個(gè)信道接入)。以認(rèn)知用戶在時(shí)隙t的吞吐量作為獎(jiǎng)勵(lì)函數(shù),通過作者提出的發(fā)送前請求(request to send, RTS)和發(fā)送前確認(rèn)(confirm to send, CTS)以及在觀測到可用信道時(shí)采取的隨機(jī)等待時(shí)間等機(jī)制進(jìn)行信道的準(zhǔn)入,以本地對s(t)的觀測和是否準(zhǔn)入發(fā)射信道作為觀測值o(t)。

電子科技大學(xué)的郭冰潔提出的Dec-POMDP動(dòng)態(tài)頻譜分配模型中各用戶的時(shí)隙中加入確認(rèn)字符(acknowledge character, ACK)狀態(tài)字,將觀測信道狀態(tài)增加為4種:空閑、繁忙、成功、失敗。除此之外,還在觀測信息種加入了繁忙率指標(biāo)來表示截至當(dāng)前觀測時(shí)隙觀測信道為繁忙的次數(shù)與對該信道的總觀測次數(shù)的比率[74],通過加入該統(tǒng)計(jì)量表征各信道的繁忙程度。但該模型在獎(jiǎng)勵(lì)函數(shù)的設(shè)計(jì)中沒有考慮用戶業(yè)務(wù)的服務(wù)質(zhì)量(quality of service, QoS),僅簡單地以接入信道成功與否作為獎(jiǎng)勵(lì)的依據(jù),在實(shí)際動(dòng)態(tài)頻譜分配中,不僅要考慮到用戶能否接入頻譜,還必須考慮接入同一信道后造成的干擾(尤其是對主用戶)對QoS造成的影響,在此約束條件下進(jìn)行權(quán)衡。

電子科技大學(xué)的何浩考慮了在能效約束下優(yōu)化認(rèn)知用戶的總吞吐率的問題,在文獻(xiàn)[75]中,他在將信道狀態(tài)建模為有限狀態(tài)馬爾可夫信道(finite state Markov channel, FSMC),在考慮了不同信道狀態(tài)(信道增益)下基于M元正交振幅調(diào)制下滿足誤碼率門限下的最小功率約束條件下,將所有信道的信道狀態(tài)與頻譜感知結(jié)果作為狀態(tài)向量s,將各用戶的信道選擇與速率選擇(調(diào)制信息)作為動(dòng)作向量a,目標(biāo)函數(shù)為在平均功率耗費(fèi)門限約束下最大化各用戶的總吞吐量,由于認(rèn)知用戶對狀態(tài)信息的觀測由認(rèn)知用戶發(fā)送導(dǎo)頻到基站，由基站估計(jì)后回傳得到,因此也是部分觀測狀態(tài),本文在這種Dec-POMDP模型下提出其最優(yōu)策略滿足納什均衡。

上面所提的這些模型中都沒有將發(fā)射功率控制及其對網(wǎng)絡(luò)效用造成的影響進(jìn)行考慮,廣東工業(yè)大學(xué)的葉梓峰提出頻譜下墊接入模型中[76],通過微基站作為感知節(jié)點(diǎn)輔助次用戶進(jìn)行頻譜接入決策。將認(rèn)知無線電網(wǎng)絡(luò)中的微基站接收到的主用戶、次用戶信號與噪聲功率的和作為狀態(tài)向量,以離散化的功率水平控制作為動(dòng)作向量,在主用戶QoS滿足門限要求時(shí),其獎(jiǎng)勵(lì)函數(shù)為次用戶的信噪比和;當(dāng)主用戶QoS在次用戶接入后不滿足門限要求,則獎(jiǎng)勵(lì)函數(shù)為次用戶信噪比和的負(fù)值。目標(biāo)函數(shù)為最大化網(wǎng)絡(luò)的總吞吐率。

綜上所述,把動(dòng)態(tài)頻譜分配問題映射到Dec-POMDP模型中,其狀態(tài)空間S主要表示當(dāng)前頻譜分配的狀態(tài)、信道狀態(tài)(信道增益)以及主用戶接收端的信號與干擾加噪聲功率比(signal to interference plus noise ratio, SINR);決策(動(dòng)作)空間A主要可以分為兩個(gè)方面,一是頻譜的分配,二是認(rèn)知用戶的功率控制(功率水平的選擇);而獎(jiǎng)勵(lì)函數(shù)R是MARL的關(guān)鍵,一般是在頻譜分配約束(一個(gè)信道同時(shí)最多只能分配給一個(gè)次用戶)下的總頻譜利用率與主用戶干擾溫度約束下的認(rèn)知無線電網(wǎng)絡(luò)的總吞吐率以及主用戶QoS的變化。

Dec-POMDP與動(dòng)態(tài)頻譜分配過程之間的映射關(guān)系如圖8所示。

圖8 基于Dec-POMDP的動(dòng)態(tài)頻譜分配建模

3.2 基于Dec-POMDP模型的動(dòng)態(tài)頻譜分配方法

目前基于Dec-POMDP模型和MARL的動(dòng)態(tài)頻譜分配算法分為:基于獨(dú)立Q-學(xué)習(xí)(independent Q-learning, IQL)的方法、基于合作Q-學(xué)習(xí)(cooperative Q-learning, CQL)的方法、基于聯(lián)合Q-學(xué)習(xí)(joint Q-learning, JQL)的方法以及基于多智能體AC算法(multi-agent AC，MAAC)的集中訓(xùn)練分布執(zhí)行方法。

3.2.1 基于IQL的動(dòng)態(tài)頻譜分配方法

基于獨(dú)立Q-學(xué)習(xí)的方法使每個(gè)智能體(用戶)根據(jù)獨(dú)立觀測的信息利用式(3)和式(4)進(jìn)行狀態(tài)價(jià)值估計(jì)與策略的優(yōu)化,通過大量訓(xùn)練收斂到穩(wěn)定點(diǎn)。

Li等人分析了兩認(rèn)知用戶下無協(xié)同的基于IQL的動(dòng)態(tài)頻譜分配過程,證明并驗(yàn)證了認(rèn)知用戶無論在僅獲得部分觀測信息或完整觀測時(shí)均可收斂到穩(wěn)定點(diǎn)(納什均衡點(diǎn))[77];Teng等提出了一種基于IQL的競價(jià)拍賣機(jī)制進(jìn)行動(dòng)態(tài)頻譜分配[78],次用戶通過IQL算法學(xué)習(xí)最優(yōu)的競價(jià)策略,主用戶則根據(jù)次用戶的策略產(chǎn)生可接受價(jià)格向量確保自身利益,該算法有效提升了競價(jià)效率;Wu等根據(jù)認(rèn)知網(wǎng)絡(luò)中用戶間由于頻譜接入行為造成的相互干擾構(gòu)建了IQL的獎(jiǎng)勵(lì)函數(shù)[79];伍春等將無監(jiān)督機(jī)器學(xué)習(xí)方法k-means與IQL算法結(jié)合,用戶進(jìn)行聚類減小智能體數(shù)量后,用可變學(xué)習(xí)率IQL方法進(jìn)行策略優(yōu)化[80];除此之外,Zia等人討論了在多層異構(gòu)網(wǎng)絡(luò)下,D2D通信用戶與蜂窩用戶間的動(dòng)態(tài)頻譜共享問題,利用IQL算法進(jìn)行優(yōu)化并與兩種理想狀態(tài)方法進(jìn)行了對比[81]; Asheralieva等人利用IQL算法優(yōu)化一個(gè)基站內(nèi)的D2D通信用戶動(dòng)態(tài)頻譜分配問題,并提出了一種利用當(dāng)前狀態(tài)下Q函數(shù)的的玻爾茲曼分布作為策略函數(shù),增加策略的隨機(jī)性與探索性,與貪婪Q-學(xué)習(xí)、其他兩種理想狀態(tài)下的傳統(tǒng)算法進(jìn)行了對比,證明了基于MARL方法相較于傳統(tǒng)方法在性能上的優(yōu)越性[82]。

上述方法均采用了表格學(xué)習(xí)對各用戶的獨(dú)立Q函數(shù)進(jìn)行更新,而這種方法隨著智能體數(shù)量、觀測狀態(tài)空間的增加,Q表的更新和收斂速度會(huì)受到很大的影響,因此Naparstek等人結(jié)合DQL領(lǐng)域的進(jìn)展,提出利用DQN擬合各用戶的Q函數(shù),并加入循環(huán)神經(jīng)網(wǎng)絡(luò)層如長短期記憶(long short-term memory, LSTM)網(wǎng)絡(luò)或門控循環(huán)單元(gated recurrent unit, GRU)網(wǎng)絡(luò),利用構(gòu)造的DQN的記憶能力和認(rèn)知用戶的同構(gòu)性,僅訓(xùn)練一個(gè)DQN網(wǎng)絡(luò)將其在用戶間共享,利用RNN的記憶性在用戶間建立協(xié)調(diào)關(guān)系,利用經(jīng)驗(yàn)回放和隨機(jī)采樣等DQN中的技巧加快了訓(xùn)練速度[83]。Zhao等人提出的MADQN算法是一種結(jié)合了DQN的IQL方法,在仿真實(shí)驗(yàn)中用戶數(shù)較少的環(huán)境下,與基于比例公平權(quán)重的信道選擇算法和隨機(jī)分配算法進(jìn)行對比,在單用戶吞吐率、系統(tǒng)總吞吐率、單用戶的成功發(fā)送概率等性能指標(biāo)上優(yōu)于兩類傳統(tǒng)方法[84]。Nasir等人對基于DQN與IQL的認(rèn)知無線電網(wǎng)絡(luò)中的功率分配算法進(jìn)行了研究,與傳統(tǒng)算法進(jìn)行對比后,結(jié)果表明該算法不僅在頻譜效率和系統(tǒng)總吞吐率上取得比傳統(tǒng)算法更好的表現(xiàn),在收斂速度上也有不低于傳統(tǒng)算法的表現(xiàn)[85]。

基于IQL算法的動(dòng)態(tài)頻譜分配方法忽略了對于單個(gè)用戶而言外部環(huán)境變化具有的非馬爾可夫鏈的性質(zhì),其狀態(tài)轉(zhuǎn)移模型并不是平穩(wěn)的,加之在值函數(shù)的優(yōu)化上沒有考慮用戶間協(xié)作產(chǎn)生均衡策略的約束,因此適用的用戶數(shù)量較少,訓(xùn)練時(shí)收斂速度慢,且不一定能收斂到最優(yōu)策略,往往得到的是次優(yōu)策略。

3.2.2 基于CQL的動(dòng)態(tài)頻譜分配方法

基于合作Q-學(xué)習(xí)的方法中單個(gè)用戶Q函數(shù)中不僅考慮當(dāng)前狀態(tài)下自身動(dòng)作,還包含了其他用戶動(dòng)作的因素,通過考慮其他智能體的策略優(yōu)化趨勢,使得單獨(dú)用戶的Q函數(shù)可以更快收斂到穩(wěn)定點(diǎn)(或納什均衡點(diǎn))。

CQL算法在更新獨(dú)立Q函數(shù)過程中需要得到其他所有智能體的動(dòng)作與Q函數(shù)以及環(huán)境的聯(lián)合狀態(tài)信息,在分布式?jīng)Q策條件下,全局狀態(tài)實(shí)際上不容易得到;這種完備的信息交互在實(shí)際的通信網(wǎng)絡(luò)中將造成很大的通信開銷,難以實(shí)現(xiàn)。

3.2.3 基于JQL的動(dòng)態(tài)頻譜分配方法

基于JQL的方法是一種集中訓(xùn)練集中執(zhí)行的方法,該方法將所有用戶的動(dòng)作視為在全局環(huán)境狀態(tài)下的統(tǒng)一動(dòng)作,因此將分布執(zhí)行下智能體決策的部分可觀測馬爾可夫決策問題簡化為一般的馬爾可夫決策問題,從而可以直接應(yīng)用單智能體強(qiáng)化學(xué)習(xí)。

Wang等人將DQN作為集中訓(xùn)練集中執(zhí)行算法,在實(shí)驗(yàn)環(huán)境中驗(yàn)證了算法的收斂性,與Whittle索引啟發(fā)式算法和信道正相關(guān)條件下的最優(yōu)短視算法進(jìn)行對比,結(jié)果表明DQN能收斂到與最優(yōu)算法相近的結(jié)果[88]。

但這種JQL算法首先需要進(jìn)行集中決策,在每個(gè)狀態(tài)下都必須確保中心對用戶的完全控制,因此存在通信開銷大的缺點(diǎn);其次是該算法要求得到對環(huán)境的完整感知信息,由于多徑、陰影衰落和路徑損耗,這種對環(huán)境的完整感知在實(shí)際中難以做到;加之該方法隨著用戶數(shù)量增加,其評估與決策的動(dòng)作空間維度呈指數(shù)級增長,容易造成值函數(shù)表示困難、難以訓(xùn)練等問題。所以其適合解決用戶數(shù)量較少的問題,不適合解決用戶數(shù)量龐大如超密集網(wǎng)絡(luò)的動(dòng)態(tài)頻譜分配問題。

3.2.4 基于MAAC的動(dòng)態(tài)頻譜分配方法

由于多智能體環(huán)境中單個(gè)智能體的環(huán)境非平穩(wěn)性,給基于Q-學(xué)習(xí)的算法帶來了很大的挑戰(zhàn),雖然可以利用合作學(xué)習(xí)或集中學(xué)習(xí)的方法減緩因此造成的影響,但收斂速度慢、容易陷入局部最優(yōu)或某一固定點(diǎn)以及協(xié)同、控制中對通信需求較大等缺點(diǎn)仍然難以有效解決。

因此,隨著近年來集中訓(xùn)練分布執(zhí)行的MARL算法取得了很多突破與進(jìn)展,利用該類型的MARL算法解決多用戶動(dòng)態(tài)頻譜分配策略的訓(xùn)練就顯的非常具有研究意義與前景。

Li等人提出了一種利用MAAC算法解決車聯(lián)網(wǎng)環(huán)境中D2D用戶與蜂窩用戶間的動(dòng)態(tài)頻譜分配問題的方法。并在MAAC算法的基礎(chǔ)上,提出了一種基于距離降低訓(xùn)練樣本需求的NAAC算法可以進(jìn)一步加快訓(xùn)練的速度,降低計(jì)算復(fù)雜度。在實(shí)驗(yàn)中將MAAC和NAAC算法與DQN、IQL以及基于主從博弈的隨機(jī)學(xué)習(xí)算法(stochastic learning algorithm, SLA)進(jìn)行了對比,無論在用戶的中斷率還是收斂后的網(wǎng)絡(luò)整體效用上均大大超過了DQN、IQL和SLA算法[89]。

表1中對比了4種基于多智能體強(qiáng)化學(xué)習(xí)方法的動(dòng)態(tài)頻譜方法的特點(diǎn)。

表1 4種方法特性對比

4 基于多智能體強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)頻譜分配方法關(guān)鍵問題

通過總結(jié)歸納上述文獻(xiàn)可以發(fā)現(xiàn),現(xiàn)有的文獻(xiàn)中在建立基于Dec-POMDP模型的MARL動(dòng)態(tài)頻譜分配算法中往往將SUA與OSA模型分開考慮,即利用功率控制算法解決SUA問題,利用頻譜選擇接入算法解決OSA問題。而在實(shí)際的動(dòng)態(tài)頻譜分配問題中,頻譜分配與功率控制需要同時(shí)考慮;在集中訓(xùn)練分布執(zhí)行的MARL算法中,集中訓(xùn)練過程需要對環(huán)境具有完整的觀測或估計(jì),如何由認(rèn)知用戶的部分觀測信息推斷出頻譜分配的完整信息是一個(gè)重要的問題;當(dāng)前的MARL算法多數(shù)應(yīng)用在智能體數(shù)量固定的環(huán)境中,而認(rèn)知無線電網(wǎng)絡(luò)中用戶數(shù)量可能是動(dòng)態(tài)變化的。

通過以上分析可以進(jìn)一步梳理出如下3種基于MARL的動(dòng)態(tài)頻譜分配方法的關(guān)鍵問題。

(1)基于Dec-POMDP建立更合理的動(dòng)態(tài)頻譜分配模型

在基于OSA的模型中,往往只考慮了頻譜的選擇,次用戶在頻譜感知后只要檢測到主用戶信號的存在,就要立即從該信道中退出,這種接入方式既增加了次用戶的中斷率,容易增加次用戶的通信時(shí)延,又使得次用戶的頻譜利用率降低;而基于SUA的模型中,基于超寬帶等技術(shù)的認(rèn)知用戶受限于在所有頻段上的發(fā)射功率都處于較低水平,為保證主用戶的干擾溫度約束,信道容量容易受限,在主用戶未占用的頻帶內(nèi),功率不能靈活調(diào)整以提高QoS。因此,可以考慮結(jié)合頻譜下墊接入與機(jī)會(huì)式頻譜接入模型,在主用戶占用的頻帶內(nèi),在主用戶干擾溫度約束下以SUA接入,而在主用戶尚未占用的頻帶內(nèi)以O(shè)SA接入,以進(jìn)一步提高頻譜利用率與次用戶QoS。

基于MARL的動(dòng)態(tài)頻譜分配方法中,獎(jiǎng)勵(lì)函數(shù)以及產(chǎn)生的即時(shí)獎(jiǎng)勵(lì)是促進(jìn)算法優(yōu)化的激勵(lì)信號,如何合理設(shè)置獎(jiǎng)勵(lì)函數(shù)是算法能否快速收斂的關(guān)鍵因素,尤其是獎(jiǎng)勵(lì)函數(shù)中體現(xiàn)對主用戶QoS的保護(hù)以及提高頻譜利用率的約束條件是算法合理性的關(guān)鍵條件,需要進(jìn)行進(jìn)一步深入研究。

(2)基于分層抽象建立部分觀測到狀態(tài)的映射

傳統(tǒng)的POMDP問題的解決方法中加入了信念向量的輔助,信念向量由歷史觀測值{ot,at,ot-1,at-1,…,o0,a0}組成的觀測向量由狀態(tài)轉(zhuǎn)移函數(shù)進(jìn)行變換后得到一個(gè)關(guān)于真實(shí)狀態(tài)轉(zhuǎn)移的概率分布。但實(shí)際上狀態(tài)轉(zhuǎn)移函數(shù)是未知的,而利用分層強(qiáng)化學(xué)習(xí)可以解決這個(gè)問題,在不需要信念向量的條件下,通過設(shè)置選項(xiàng)、分層抽象等方法，從觀測信息中對真實(shí)的環(huán)境全局狀態(tài)進(jìn)行學(xué)習(xí),映射到動(dòng)態(tài)頻譜分配問題中,也就是利用認(rèn)知用戶的不完全頻譜感知信息在集中訓(xùn)練架構(gòu)下通過分層強(qiáng)化學(xué)習(xí)的方法估計(jì)真實(shí)的頻譜分配狀態(tài),這也將解決集中訓(xùn)練方法中真實(shí)狀態(tài)不可知條件下全局Q函數(shù)的學(xué)習(xí)問題。

(3)認(rèn)知無線電網(wǎng)絡(luò)的動(dòng)態(tài)拓展

目前基于MARL的動(dòng)態(tài)頻譜分配算法存在的主要問題之一是如何應(yīng)用在用戶數(shù)量變化的認(rèn)知無線電網(wǎng)絡(luò)中,換言之,也就是如何解決智能體策略的泛化性。利用集中訓(xùn)練分布執(zhí)行的模式有效解決了多智能體間環(huán)境的非平穩(wěn)性導(dǎo)致的訓(xùn)練收斂性問題,但集中訓(xùn)練的前提是多智能體整體所處外部環(huán)境是平穩(wěn)的,一旦加入新的用戶,即智能體后,多智能體整體的外部環(huán)境也變得非平穩(wěn),這就導(dǎo)致一旦網(wǎng)絡(luò)內(nèi)用戶數(shù)量發(fā)生變化,網(wǎng)絡(luò)內(nèi)的所有用戶的策略都需要重新進(jìn)行訓(xùn)練。

隨著離線強(qiáng)化學(xué)習(xí)的提出,這種利用其他智能體與環(huán)境的交互軌跡對新的智能體策略進(jìn)行訓(xùn)練的方式為解決智能體策略的泛化性或者認(rèn)知無線電網(wǎng)絡(luò)用戶的可擴(kuò)展性提供了新的思路。

5 結(jié)束語

基于傳統(tǒng)理論的動(dòng)態(tài)頻譜分配算法存在分配時(shí)間長,計(jì)算復(fù)雜度高,不適應(yīng)動(dòng)態(tài)變化的無線通信環(huán)境且不適合分布式?jīng)Q策的缺點(diǎn),而隨著MARL為代表的群體智能技術(shù)的興起和發(fā)展,基于這種群體智能技術(shù)的動(dòng)態(tài)頻譜分配方法相比于傳統(tǒng)方法來說具有智能化、實(shí)時(shí)化和分布化的諸多優(yōu)勢。本文對現(xiàn)有的基于MARL的動(dòng)態(tài)頻譜分配方法的研究現(xiàn)狀進(jìn)行了梳理與總結(jié),根據(jù)應(yīng)用算法框架將這些研究成果分為4種類型,比較了4種類型方法的優(yōu)劣,結(jié)合RL、MARL及其在動(dòng)態(tài)頻譜分配問題中的應(yīng)用,提出了模型建立、從部分觀測信息中分層學(xué)習(xí)以及認(rèn)知無線電網(wǎng)絡(luò)用戶的拓展性中存在的關(guān)鍵問題,并分析了解決思路。