一種合作Markov決策系統(tǒng)

雷 瑩，許道云

(貴州大學 計算機科學與技術(shù)學院，貴州 貴陽 550025)

1 概 述

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

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

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

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

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

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

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

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

2.1 Markov系統(tǒng)

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

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

(1)

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

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)移獎勵的Markov系統(tǒng)

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

遞歸定義一個(向后)期望收集到的獎勵值：

(3)

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

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

i=1,2,…,n

(4)

其向量形式寫成：

(5)

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

(6)

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

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

γ=0.9

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

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

2.3 Markov決策系統(tǒng)

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

獎勵函數(shù)修改為：R:S×A×S→(實數(shù)集)。

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

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

或

γ·Vπ(s')]

(7)

式(7)稱為Bellman遞歸方程。它是一個不動點方程，V-函數(shù)作為一個不動點?？梢钥闯觯簩τ诮o定的策略，Markov決策系統(tǒng)是一個帶獎勵函數(shù)的Markov系統(tǒng)。

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

(8)

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

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

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

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

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

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

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

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

一個自然的問題是：最優(yōu)策略π*的存在性。其次，如果存在，如何計算得到π*。理論結(jié)果表明[18]：一個有限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)提供了一個交叉迭代，并求解得到最優(yōu)策略π*和最優(yōu)函數(shù)V*。

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

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

貪心計算一個策略π0：

γ·V0(s')]

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

γ·Vm(s')]

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

(2)貪心計算。

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

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

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

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

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

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

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

表1 不同策略的具體值

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

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

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

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

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

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

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

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

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

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

其中，

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

A為一個行為動作集；

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

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

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

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

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

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

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

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

形式上，兩個智能體Agent0,Agent1對應兩個V-函數(shù)：Vi:S×S→(i=0,1)。在聯(lián)合形式下，用社會價值描述聯(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理解為：當Agenti處于s狀態(tài)，并觀察到Agent1-i處于狀態(tài)s'時，執(zhí)行動作a。

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

(11)

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

其中，視s,t固定。

(12)

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

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

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

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

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

當‖Vm+1-Vm‖<ε時，做如下定義：

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

t')]

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

7 結(jié)束語