雷 瑩，許道云

(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025)

1 概 述

在機(jī)器學(xué)習(xí)中，依據(jù)學(xué)習(xí)方式不同可以分為三大類[1]：監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)。其中，強(qiáng)化學(xué)習(xí)[2-4](又稱為增強(qiáng)學(xué)習(xí))是一個(gè)重要的研究領(lǐng)域，其目的是學(xué)習(xí)環(huán)境狀態(tài)到行動的映射，本質(zhì)是自主學(xué)習(xí)并解決負(fù)責(zé)的決策問題。通過強(qiáng)化學(xué)習(xí)的方式，智能體[5]能夠在探索和開發(fā)之間進(jìn)行折中處理，進(jìn)而尋找最優(yōu)策略[6-7]并獲得最大回報(bào)。Asmuth等人[8]將尋找最優(yōu)策略的方法歸納為三類，第一類是基于貝葉斯的方法，第二類是間接選擇的方法，第三類是近似效用的方法，其中第一類方法的設(shè)計(jì)理論較為完善，可用來解決隨機(jī)決策問題。

在強(qiáng)化學(xué)習(xí)中，Markov決策過程系統(tǒng)[9-10](Markov decision process system，MDP)極其重要，從計(jì)算模型的演變過程看：Markov過程(Markov process)(也稱為Markov系統(tǒng)，Markov process system，MP)是基礎(chǔ)模型，引入獎(jiǎng)勵(lì)函數(shù)和執(zhí)行行為，并以狀態(tài)集到行為集的一個(gè)映射作為策略[11]，求解Markov決策問題。在給定策略π下，Markov決策系統(tǒng)退化到帶獎(jiǎng)勵(lì)函數(shù)的Markov系統(tǒng)MDPπ。一旦策略π給定，帶獎(jiǎng)勵(lì)函數(shù)的Markov系統(tǒng)的主要任務(wù)是演化生成在每一個(gè)狀態(tài)下的期望收集到的獎(jiǎng)勵(lì)值。Markov決策系統(tǒng)MDPπ的主要目標(biāo)是求一個(gè)最優(yōu)策略π*，使得在此策略下，在Markov鏈上收集到的期望獎(jiǎng)勵(lì)值最大。

在通常的Markov決策系統(tǒng)中，形式上是一個(gè)智能體在學(xué)習(xí)演化的過程。然而，在實(shí)際中往往會遇到這樣的兩類問題：

第一類是多個(gè)智能體在同一個(gè)環(huán)境中共同完成一個(gè)目標(biāo)任務(wù)。這類系統(tǒng)稱為協(xié)同[12]或合作系統(tǒng)[13]。在這類系統(tǒng)中，智能個(gè)體單獨(dú)執(zhí)行策略行為，智能體之間相互配合、共同完成一個(gè)目標(biāo)任務(wù)。其最優(yōu)策略組合表現(xiàn)為智能體策略向量(或組)，獎(jiǎng)勵(lì)值體現(xiàn)為組合執(zhí)行的社會綜合價(jià)值。

第二類是多個(gè)智能體在同一個(gè)環(huán)境中相互制約完成各自的目標(biāo)任務(wù)。這類系統(tǒng)稱為對抗或博弈系統(tǒng)[14-15]。在這類系統(tǒng)中，智能個(gè)體單獨(dú)執(zhí)行策略行為，智能體之間相互制約或博弈，各自完成自己的目標(biāo)任務(wù)。其最優(yōu)策略表現(xiàn)為智能體策略向量(或組)，獎(jiǎng)勵(lì)值體現(xiàn)為自身執(zhí)行的獎(jiǎng)勵(lì)價(jià)值。文獻(xiàn)[16]提出了多智能體非零和MDPs(Markov decision processes)對策的增強(qiáng)學(xué)習(xí)模型和算法，并通過預(yù)測對手的策略模型來修正自己的策略。

為方便起見，文中僅考慮兩個(gè)智能體的聯(lián)合Markov決策系統(tǒng)(CMDP)，這樣的系統(tǒng)適用于兩個(gè)智能體之間合作(或?qū)?決策的演化學(xué)習(xí)系統(tǒng)。文中引入了聯(lián)合Markov決策系統(tǒng)的形式定義，在此形式系統(tǒng)中，兩個(gè)智能體(Alice和Bob)交替依據(jù)自己的策略執(zhí)行行為動作，在給定策略對的Markov系統(tǒng)(帶獎(jiǎng)勵(lì)函數(shù))中演化學(xué)習(xí)，系統(tǒng)求優(yōu)是針對策略求優(yōu)。

2 Markov決策系統(tǒng)的進(jìn)化過程

本節(jié)介紹從Markov系統(tǒng)模型到Markov決策系統(tǒng)的演化過程。

2.1 Markov系統(tǒng)

設(shè)S為一個(gè)有窮狀態(tài)集(含有n個(gè)狀態(tài))，一個(gè)序?qū)?S,T>構(gòu)成一個(gè)有限Markov系統(tǒng)，其中對每一個(gè)s∈S，定義一個(gè)概率分布Ts:S→[0,1]，Ts(s')表示由狀態(tài)s轉(zhuǎn)移到狀態(tài)s'的概率。

通常，將概率轉(zhuǎn)移函數(shù)T寫成如下形式：

(1)

由一個(gè)Markov系統(tǒng)，可以規(guī)定一個(gè)Markov鏈：X0,X1,…,Xt,Xt+1,…，它是狀態(tài)集S上的一個(gè)隨機(jī)變量序列，滿足如下條件：

Pr[Xt+1=st+1|X0=s0,X1=s1,…,Xt=st]=

Pr[Xt+1=st+1|Xt=st]=T(st,st+1)

(2)

πP=π

其中：

π=(π(s1),π(s2),…,π(sn))

P=(pi,j),pi,j=T(si,sj)

2.2 帶狀態(tài)轉(zhuǎn)移獎(jiǎng)勵(lì)的Markov系統(tǒng)

設(shè)S={s1,s2,…,sn}，函數(shù)T可由概率轉(zhuǎn)移矩陣P=(pi,j)n×n決定。進(jìn)一步，引入一個(gè)獎(jiǎng)勵(lì)函數(shù)R:S×S→(實(shí)數(shù)集)，R(s,s')表示由狀態(tài)s轉(zhuǎn)移到狀態(tài)s'所獲得的獎(jiǎng)勵(lì)值。類似地，函數(shù)R寫成一個(gè)n階方陣R=(ri,j)n×n，并將最大值記為Rmax。

遞歸定義一個(gè)(向后)期望收集到的獎(jiǎng)勵(lì)值：

(3)

其中，0<γ<1稱為折扣因子，以保證一個(gè)無窮級數(shù)收斂。式(3)表明，狀態(tài)s為初始狀態(tài)，在Markov鏈X0,X1,…,Xt,Xt+1,…上得到的獎(jiǎng)勵(lì)值。在式(3)中，項(xiàng)R(s,s')+γ·V(s')表明：從s開始，一步轉(zhuǎn)移到s'獲得的獎(jiǎng)勵(lì)值加上從s'開始收集的期望值打折。

為便于計(jì)算，可以將式(3)改寫成如下方程：

i=1,2,…,n

(4)

其向量形式寫成：

(5)

在迭代計(jì)算過程中，式(4)可以寫成如下迭代公式：

(6)

其中，RT表示矩陣R的轉(zhuǎn)置，diag(A)表示矩陣A對角線上元素構(gòu)成的向量。

例1：概率矩陣P、獎(jiǎng)勵(lì)函數(shù)R、折扣因子取值如下。通過算例觀察函數(shù)V的迭代計(jì)算收斂性。

γ=0.9

初始V0取為零向量(全取0)，則收斂狀況如圖1所示，其中橫坐標(biāo)表示迭代步數(shù)，縱坐標(biāo)表示V(s)收斂值。

圖1 V-函數(shù)收斂示意圖

2.3 Markov決策系統(tǒng)

Markov決策系統(tǒng)是在帶獎(jiǎng)勵(lì)函數(shù)的Markov系統(tǒng)中引入行為，并將獎(jiǎng)勵(lì)函數(shù)修改到行為執(zhí)行步上。

獎(jiǎng)勵(lì)函數(shù)修改為：R:S×A×S→(實(shí)數(shù)集)。

引入策略概念，形如π:S→A的函數(shù)稱為一個(gè)策略。π(s)=a代表在狀態(tài)s下執(zhí)行行為a。對于一個(gè)給定的策略π，可以將式(4)改寫為：

γ·Vπ(sj)],i=1,2,…,n

或

γ·Vπ(s')]

(7)

式(7)稱為Bellman遞歸方程。它是一個(gè)不動點(diǎn)方程，V-函數(shù)作為一個(gè)不動點(diǎn)。可以看出：對于給定的策略，Markov決策系統(tǒng)是一個(gè)帶獎(jiǎng)勵(lì)函數(shù)的Markov系統(tǒng)。

根據(jù)函數(shù)Vπ，將行為作為一個(gè)變量，可以誘導(dǎo)出另一種類型的獎(jiǎng)勵(lì)函數(shù)：Q-函數(shù)，如式(8)所示：

(8)

其中，Qπ(s,a)理解為：在指定策略π下，在s狀態(tài)下執(zhí)行行為a后期望收集到的獎(jiǎng)勵(lì)值。

Markov決策系統(tǒng)的主要目標(biāo)是尋找一個(gè)最優(yōu)策略π，使函數(shù)Vπ最大化。

3 Markov決策系統(tǒng)中求解最優(yōu)策略方法

由上一節(jié)介紹，一個(gè)有限Markov決策系統(tǒng)是一個(gè)四元組，其中S是一個(gè)有窮的狀態(tài)集，A是一個(gè)有窮的行為集，T:S×A×S→[0,1]是概率轉(zhuǎn)移函數(shù)，R:S×A×S→R+是獎(jiǎng)勵(lì)函數(shù)。

對于策略π:S→A，由于表示期望收集獎(jiǎng)勵(lì)值的V-函數(shù)和Q-函數(shù)依賴π，并且由Vπ函數(shù)可以決定Qπ。因此，目標(biāo)是尋找一個(gè)策略π，使函數(shù)Vπ最大化。

一個(gè)V-函數(shù)V*是最優(yōu)的，如果對于任意策略π，對于任意狀態(tài)s∈S，有V*(s)≥Vπ(s)。

一個(gè)策略π*是最優(yōu)的，如果對于任意策略π，對于任意狀態(tài)s∈S，有Vπ*(s)≥Vπ(s)。

顯然，函數(shù)Vπ*是一個(gè)最優(yōu)V-函數(shù)，其中，對于任意的狀態(tài)s∈S，取V*(s)=Vπ*(s)。

一個(gè)自然的問題是：最優(yōu)策略π*的存在性。其次，如果存在，如何計(jì)算得到π*。理論結(jié)果表明[18]：一個(gè)有限Markov決策系統(tǒng)的最優(yōu)策略存在。

最優(yōu)V-函數(shù)V*與最優(yōu)策略π*有如下關(guān)系：

(1)如果已經(jīng)得到最優(yōu)函數(shù)V*，利用如下方法可得到最優(yōu)策略π*：

γ·V*(s')]

(9)

(2)如果已經(jīng)得到最優(yōu)策略π*，利用如下方法可得到最優(yōu)函數(shù)V*：

π*(s),s')+γ·Vπ*(s')]

(10)

式(9)和式(10)提供了一個(gè)交叉迭代，并求解得到最優(yōu)策略π*和最優(yōu)函數(shù)V*。

在具體計(jì)算過程中，用一個(gè)給定誤差(ε>0)控制給定策略下Markov系統(tǒng)演化計(jì)算的停機(jī)條件，其計(jì)算方法及步驟如下：

第0步：初始化V-函數(shù)V0(可以隨機(jī)取值，如取V0(s)=0(s∈S))

貪心計(jì)算一個(gè)策略π0：

γ·V0(s')]

(1)Markov系統(tǒng)演化計(jì)算。

γ·Vm(s')]

即當(dāng)πk給定后，用式(7)迭代計(jì)算，當(dāng)‖Vm+1-Vm‖<ε時(shí)，定義(s)=Vm+1(s)(s∈S)。

(2)貪心計(jì)算。

算法終止條件：當(dāng)πk+1=πk，終止計(jì)算，并定義最優(yōu)策略π*=πk。

注：算法終止條件‖Vm+1-Vm‖<ε也可以用單點(diǎn)比較達(dá)到誤差條件：|Vm+1(s)-Vm(s)|<ε。上述計(jì)算過程可以用圖2表示。

圖2 最優(yōu)策略求解算法框架

例2：考慮一個(gè)Markov決策系統(tǒng)，其中S={s0,s1,s2},A={a0,a1}，概率轉(zhuǎn)移函數(shù)T和獎(jiǎng)勵(lì)函數(shù)R分別如下：

折扣因子γ=0.95，誤差控制取ε=0.000 1。

如圖3所示，描述了所有策略下狀態(tài)si對應(yīng)的V(si)的收斂值。其中縱坐標(biāo)表示V(s)收斂值。橫坐標(biāo)表示8(8=2×2×2)種策略，考慮有s0、s1、s2三個(gè)狀態(tài)，且每個(gè)狀態(tài)有a0、a1兩種行為，因此橫坐標(biāo)上的每個(gè)數(shù)值對應(yīng)一定的二進(jìn)制碼，進(jìn)而表示相應(yīng)的策略。表1為不同策略不同狀態(tài)下的具體值。

圖3 不同策略下的V-函數(shù)比較

表1 不同策略的具體值

實(shí)際計(jì)算中，最優(yōu)策略可以由“迭代+演化”過程得到。此例中得到的最優(yōu)策略下的概率轉(zhuǎn)移矩陣P和獎(jiǎng)勵(lì)函數(shù)R分別為：

4 聯(lián)合Markov決策過程系統(tǒng)(CMDPs)

本節(jié)引入兩個(gè)智能體在同一個(gè)Markov決策過程中運(yùn)行的聯(lián)合形式系統(tǒng)。

4.1 兩個(gè)Markov系統(tǒng)的乘積系統(tǒng)

設(shè)A=(ai,j)n×n,B=(bi,j)m×m為兩個(gè)矩陣，矩陣A與B的張積定義為：A?B=(ai,jB)。

容易驗(yàn)證：如果P1,P2均為概率矩陣(不一定同階)，則P1?P2也為概率矩陣。

可分離的Markov系統(tǒng)：設(shè)(S,P)為一個(gè)Markov系統(tǒng)，如果它可以表示成兩個(gè)Markov系統(tǒng)的積系統(tǒng)，則稱(S,P)是可分離的。

4.2 兩個(gè)智能體參與的聯(lián)合Markov決策系統(tǒng)

現(xiàn)在考慮：在同一個(gè)系統(tǒng)中，具有兩個(gè)智能體Agent0,Agent1(Alice和Bob)分別執(zhí)行各自的行為動作，以合作方式完成目標(biāo)任務(wù)。對于“合作”類型：兩者協(xié)同完成同一個(gè)目標(biāo)；對于“對抗”類型：兩者之間相互制約(如：博弈)各自完成自己的目標(biāo)任務(wù)。

形式上，這樣的系統(tǒng)為如下元組：

其中，

S為一個(gè)有窮狀態(tài)集；

A為一個(gè)行為動作集；

Ti為Agenti的概率轉(zhuǎn)移函數(shù)(i=0,1)，定義為：

Ti:S×S×A×S×A→[0,1]。

直觀上，T0(s1,s2,a,s',a')表示：“當(dāng)Agent0,Agent1處于狀態(tài)對(s1,s2)時(shí)，執(zhí)行行為動作a后，Agent0轉(zhuǎn)移到狀態(tài)s'，合作者(或?qū)狗?Agent1響應(yīng)執(zhí)行行為a'”的概率。

Ri為Agenti的獎(jiǎng)勵(lì)函數(shù)(i=0,1)，定義為：

Ri:S×S×A×S×A→(實(shí)數(shù)集)

直觀上，R0(s1,s2,a,s',a')表示：“當(dāng)Agent0,Agent1處于狀態(tài)對(s1,s2)時(shí)，Agent0執(zhí)行行為動作a后，Agent0轉(zhuǎn)移到狀態(tài)s'，合作者(或?qū)狗?Agent1響應(yīng)執(zhí)行行為a'”時(shí)，Agent0獲取的獎(jiǎng)勵(lì)值。

5 聯(lián)合Markov決策系統(tǒng)策略迭代方法

文中僅考慮兩個(gè)智能體合作執(zhí)行的聯(lián)合Markov決策系統(tǒng)。

形式上，兩個(gè)智能體Agent0,Agent1對應(yīng)兩個(gè)V-函數(shù)：Vi:S×S→(i=0,1)。在聯(lián)合形式下，用社會價(jià)值描述聯(lián)合V-函數(shù)V:S×S→。形式上定義為：

V(s,s')=αV0(s,s')+(1-α)V1(s,s'),0<α<1

其中，參數(shù)α稱為平衡參數(shù)。

策略函數(shù)定義為：πi:S×S→A(i=0,1)。將πi(s,s')=a理解為：當(dāng)Agenti處于s狀態(tài)，并觀察到Agent1-i處于狀態(tài)s'時(shí)，執(zhí)行動作a。

對于給定的策略對(π0,π1)，演化聯(lián)合Markov系統(tǒng)CMDP(π0,π1)得到一個(gè)穩(wěn)定的V-函數(shù)，其迭代方程為：

(11)

請注意：在式(11)中，帶打折因子的倍乘項(xiàng)是基于S上的邊緣分布求期望值：

其中，視s,t固定。

(12)

6 合作類型最優(yōu)策略對的求解算法

第0步：給定誤差參數(shù)ε以及平衡參數(shù)α；

(1)Markov系統(tǒng)演化計(jì)算。

[R0(s,t,π0(s,t),s',a)+γ·Vm(s',t)]

[R1(s,t,π1(s,t),t',a)+γ·Vm(s,t')]

當(dāng)‖Vm+1-Vm‖<ε時(shí)，做如下定義：

(2)貪心計(jì)算(π0,k+1,π1,k+1)。

t')]

最終，Vm+1為最優(yōu)V-函數(shù)，(π0,k+1,π1,k+1)為最優(yōu)策略對。

7 結(jié)束語