多Agent自動協(xié)商中機器學(xué)習(xí)的應(yīng)用研究

1、多Agent自動協(xié)商中機器學(xué)習(xí)的應(yīng)用研究楊明 楊明，女，博士生，講師，主要研究方向：機器學(xué)習(xí)，分布式人工智能。E-mail: yangming。，魯瑞華2，邱玉輝3( 1,3 西南師范大學(xué)計算機與信息科學(xué)學(xué)院，重慶北碚 400715; 2西南師范大學(xué)電子與信息工程學(xué)院，重慶北碚 400715) 摘 要：目前將機器學(xué)習(xí)理論應(yīng)用到多Agent自動協(xié)商系統(tǒng)中已成為電子商務(wù)領(lǐng)域的最新研究課題。本文即是利用貝葉斯法則來更新協(xié)商中的環(huán)境信息（即信念），利用強化學(xué)習(xí)中的Q學(xué)習(xí)算法生成協(xié)商中的提議，建立了一個具有學(xué)習(xí)機制的多Agent自動協(xié)商模型。并且對傳統(tǒng)Q學(xué)習(xí)算法進(jìn)行了擴充，設(shè)計了基于Agent的當(dāng)前信念

2、和最近探索盈余的動態(tài)Q學(xué)習(xí)算法，實驗驗證了算法的收斂性。關(guān)鍵詞：貝葉斯學(xué)習(xí)；信念更新；強化學(xué)習(xí)；自動協(xié)商；Q學(xué)習(xí)算法；生成提議1. 引言隨著人工智能以及Agent技術(shù)的發(fā)展,利用具有一定自主推理、自主決策能力的Agent以及由其組成的多Agent系統(tǒng)已經(jīng)成為電子商務(wù)中的熱門工具，由于Agent能模擬人類商業(yè)交往中的協(xié)商而無需引入一些無關(guān)的傾向，使協(xié)商過程更加理性。然而協(xié)商是在不完全信息條件下進(jìn)行的，協(xié)商過程本身存在許多不確定和不穩(wěn)定因素，因此在多Agent系統(tǒng)中引入學(xué)習(xí)機制，使每個Agent通過學(xué)習(xí)來協(xié)調(diào)自身的行為，則能有效地完成協(xié)商目的。目前將機器學(xué)習(xí)理論應(yīng)用到自動協(xié)商系統(tǒng)中已成為電子商務(wù)領(lǐng)

3、域的最新研究課題，現(xiàn)有自動協(xié)商系統(tǒng)中涉及到的機器學(xué)習(xí)方法主要有以下幾種：貝葉斯學(xué)習(xí)、遺傳算法、強化學(xué)習(xí)等。本文即是利用貝葉斯法則來更新協(xié)商中的環(huán)境信息（即信念），利用強化學(xué)習(xí)中的Q學(xué)習(xí)算法生成協(xié)商中的提議，從而建立了一個具有學(xué)習(xí)機制的多Agent自動協(xié)商模型。2.協(xié)商的相關(guān)理論在多Agent系統(tǒng)中，協(xié)商是指在一個特定領(lǐng)域中，一群Agent為了就某事達(dá)成相互都可以接受的協(xié)議而進(jìn)行交流的過程。協(xié)商的目的是參與協(xié)商的各方在追求自己的需求，或者自己所代表的某個組織的需求時，應(yīng)該通過交換提議而進(jìn)行磋商，共同尋找雙方都能接受的方案。協(xié)商不是無限制地滿足自己的利益，而是有一定的利益界限。協(xié)商者之間是既競爭又

4、合作的關(guān)系，協(xié)商雙方必須存在協(xié)商的可行區(qū)域。2.1 協(xié)商協(xié)議協(xié)商協(xié)議（Negotiation Protocol）是保證Agent之間解決沖突并達(dá)成合作協(xié)議的機制，它規(guī)定了協(xié)商Agent之間通信的語言、規(guī)范以及語義。換句話說，協(xié)商協(xié)議定義了在協(xié)商實體之間的消息流，規(guī)定了在何時采取何種行動等行為約束，該約束便是協(xié)商實體間交互所必須遵守的行為規(guī)則。比較常用的協(xié)商協(xié)議有監(jiān)聽協(xié)議、合同網(wǎng)協(xié)議、分布匹配協(xié)議、競價協(xié)議、拍賣協(xié)議、統(tǒng)一協(xié)商協(xié)議等。2.2 協(xié)商策略協(xié)商策略（Negotiation Strategy）是協(xié)商所用的推理模型，是Agent進(jìn)行決策和選擇行動的一種戰(zhàn)術(shù)。協(xié)商策略由與協(xié)商協(xié)議相應(yīng)的元協(xié)商

5、策略和選擇策略算法組成，一般分為：競爭策略、一方讓步策略、延遲協(xié)議策略、變更協(xié)議策略。協(xié)商協(xié)議是Agent協(xié)商的外在限制，而協(xié)商策略是Agent協(xié)商的內(nèi)在限制，二者相對獨立又相互影響。 2.3 協(xié)商流程為描述方便，以電子商務(wù)中賣方Agent與買方Agent之間的協(xié)商執(zhí)行過程為例，假設(shè)Agent之間的通信通道已建立。首先賣方Agent權(quán)衡盈利值，選擇一個能獲得最佳利潤的提議。接收到提議的買方Agent，根據(jù)對方的提議，更新當(dāng)前信念；然后檢查約束，評估該提議是否可接受；如果不可接受，則調(diào)整協(xié)商策略，生成新的提議。具體描述如下：1)更新信念。信念包括對協(xié)商對手的私有信息和當(dāng)前環(huán)境狀態(tài)的基本看法，各方

6、Agent的信念模型隨著協(xié)商的進(jìn)行以及從對方接收到的提議中不斷更新。通過協(xié)商過程中提議與反提議的交互，雙方Agent可以根據(jù)交互的信息以及自己的領(lǐng)域知識來更新信念，從而對對方Agent的提議結(jié)構(gòu)及策略逐步了解，生成有利于己方的提議。 2)檢查約束，評估提議。約束檢查是在協(xié)商Agent收到提議后，根據(jù)用戶約束庫中的相應(yīng)屬性和約束，對屬性或?qū)傩蚤g的約束進(jìn)行檢查，最先檢查那些不可協(xié)商的屬性。當(dāng)違反約束時，應(yīng)用松弛規(guī)則自動松弛約束或人工增加、修改約束松弛規(guī)則1。在協(xié)商過程中，收到提議的Agent要對提議進(jìn)行評估，判斷該提議是否與它的期望值相近。3)調(diào)整策略，生成新提議。根據(jù)協(xié)商環(huán)境和協(xié)商對手的提議來調(diào)

7、整策略，如做出讓步等，從而生成新的提議。2.4協(xié)商模型由上述協(xié)商流程可以看出：協(xié)商Agent在協(xié)商過程中交替交換提議，它們在每次收到協(xié)商對手的提議后按照一定的策略生成反提議作為應(yīng)答，因此，基于Agent的自動協(xié)商可以看作是一個連續(xù)決策過程。連續(xù)決策模型2將決策過程劃分為一系列相互依賴的決策點，決策方可以在執(zhí)行決策和接受反饋后更新自己的知識，因此連續(xù)決策模型以及改進(jìn)的連續(xù)決策模型成為多Agent間自動協(xié)商的模型主流, 為研究協(xié)商中的學(xué)習(xí)提供了方便。作者在文獻(xiàn)3中采用多屬性效用理論和連續(xù)決策過程相結(jié)合的方法建立了一個多問題自動協(xié)商的形式化模型。限于篇幅，此處不再描述。3.貝葉斯學(xué)習(xí)的引入在機器學(xué)習(xí)

8、中，通常我們感興趣的是在給定訓(xùn)練數(shù)據(jù)D時，確定假設(shè)空間H中的最優(yōu)（Best）假設(shè)。所謂最優(yōu)假設(shè)，是指定義在給定數(shù)據(jù)D以及H中不同假設(shè)的先驗概率知識下的最可能假設(shè)。貝葉斯理論提供了一種直接計算這種可能假設(shè)的方法(即采用一種概率手段)。它基于如下假設(shè)：待考查的量遵循某種概率分布，且可根據(jù)這些概率及觀察到的數(shù)據(jù)進(jìn)行推理，從而做出最優(yōu)的決策。它為衡量多個假設(shè)的置信度提供了定量的方法，可以處理信息不完全、不精確的推理。這里對貝葉斯法則進(jìn)行簡單地描述：代表在沒有訓(xùn)練數(shù)據(jù)前假設(shè)h擁有的初始概率，稱為h的先驗概率，它反映了我們所擁有的關(guān)于h是一正確假設(shè)的機會的背景知識。如果沒有這一先驗知識，那么可以簡單地將每

9、一候選假設(shè)賦予相同的先驗概率；：代表將要觀察的訓(xùn)練數(shù)據(jù)D的先驗概率；：代表假設(shè)h成立的情形下觀察到數(shù)據(jù)D的概率；：代表給定訓(xùn)練數(shù)據(jù)D時h成立的概率，稱為h的后驗概率（Posterior Probability），反映了在已知訓(xùn)練數(shù)據(jù)D后h成立的置信度。后驗概率反映了訓(xùn)練數(shù)據(jù)D的影響，而先驗概率是獨立于D的。貝葉斯法則是貝葉斯學(xué)習(xí)方法的基礎(chǔ)，因為它提供了從先驗概率以及和計算后驗概率的方法。即下列貝葉斯公式：本文首先通過建立協(xié)商環(huán)境的信念模型來解決Agent間的學(xué)習(xí)問題，參與的Agent在概率的框架下采用貝葉斯方法來更新協(xié)商Agent對環(huán)境和對方Agent的知識和信念?？紤]到貝葉斯分析的計算復(fù)雜性

10、問題，這里使用貝葉斯信念網(wǎng)絡(luò)（Bayesian Brief Network）的表示和更新機制。貝葉斯信念網(wǎng)絡(luò)提供了一個可表達(dá)的建模語言，允許靈活、便捷地對領(lǐng)域知識編碼4。在電子商務(wù)中，協(xié)商各方Agent對自己的商品屬性保留值很清楚，但不是很了解對方的保留值及策略，最初只能根據(jù)自己的背景知識和了解程度做一假設(shè)。通過在協(xié)商過程中提議與反提議的交互，雙方Agent根據(jù)交互的信息以及自己的領(lǐng)域知識來更新信念，從而對對方Agent的提議結(jié)構(gòu)及策略逐步了解，生成有利于己方的提議。協(xié)商Agent對對方Agent可能給出的商品屬性j的值的信念表示為一個假設(shè)集合。根據(jù)Agent的先驗知識，對每個假設(shè)值都有一個概

11、率估計，形成一個概率集合；從對方Agent接收到的提議作為信號e；根據(jù)Agent當(dāng)前觀察到的領(lǐng)域知識，對每個假設(shè)形成一個先驗條件概率。應(yīng)用貝葉斯法則，生成假設(shè)的后驗概率： （1）根據(jù)新的概率值，Agent更新信念，同時調(diào)整自己的協(xié)商策略。4. 強化學(xué)習(xí)中Q學(xué)習(xí)算法的引入強化學(xué)習(xí)（Reinforcement Learning）是由動物學(xué)習(xí)、隨機逼近、優(yōu)化控制等理論發(fā)展而來，是一種無導(dǎo)師在線學(xué)習(xí)技術(shù), 它提供了一種通過獎賞和懲罰對Agent進(jìn)行規(guī)劃的方法。其基本原理是：如果Agent的某個行為策略導(dǎo)致環(huán)境正的獎賞（強化信號），那么Agent以后產(chǎn)生這個行為策略的趨勢便會加強5。4.1 Q學(xué)習(xí)算法Q

12、學(xué)習(xí)算法是強化學(xué)習(xí)中最重要的學(xué)習(xí)算法之一，它實際是馬爾可夫判定過程（MDP）的一種變化形式，MDP也可看作是強化學(xué)習(xí)的數(shù)學(xué)模型。通常，一個MDP可以用一個四元組來表示：<S,A,R,T> 其中：S是環(huán)境狀態(tài)空間；A是Agent的行為動作空間；R是獎賞函數(shù)R：S×A R；T是狀態(tài)轉(zhuǎn)移函數(shù)T：S×A PD（S），PD是狀態(tài)空間S的概率分布。記R（s1,a,s2）是Agent 在環(huán)境狀態(tài) s1 S 下采用動作 aA使環(huán)境狀態(tài)遷移到 s2 S時所獲得的獎賞值。T(s1,a,s2)是Agent在環(huán)境狀態(tài) s1S下采用動作 a A使環(huán)境狀態(tài)遷移到 s2 S的概率。Agent

13、的目標(biāo)是在每個離散的環(huán)境狀態(tài)空間發(fā)現(xiàn)最優(yōu)策略以使期望的折扣獎賞和最大。定義Q值為狀態(tài)動作對的估計，根據(jù)對MDP的定義，有： 其中 sS ，aA ，S ，是狀態(tài)s經(jīng)過動作a后到達(dá)的下一個狀態(tài)，為折扣因子，0<<1 。在已知R和T條件下，可以得到最終的Q值。由于Q值是未來獎賞的精確總和，所以此學(xué)習(xí)方法將Q值作為即時獎賞的替代，每次選擇最高Q值就可以得到MDP的最優(yōu)策略。4.2引入Q學(xué)習(xí)的多Agent自動協(xié)商模型在協(xié)商過程中，由于雙方都不愿過早暴露自己的私有信息，即雙方Agent都具有不完全信息的特點，因此對手的提議便是了解對方私有信息、效用函數(shù)，并更新己方策略的重要信息來源。這樣看來，

14、協(xié)商Agent具有在線學(xué)習(xí)能力是十分重要的。由于第三小節(jié)中已經(jīng)討論了采用貝葉斯學(xué)習(xí)對當(dāng)前協(xié)商狀態(tài)下的環(huán)境以及對手信息等信念的更改，接下來我們只考慮協(xié)商的動態(tài)學(xué)習(xí)過程，即采用動態(tài)Q學(xué)習(xí)來生成提議。在MDP中，環(huán)境狀態(tài)的轉(zhuǎn)換由轉(zhuǎn)移概率函數(shù)定義，它是不隨時間變化的?？紤]到在多個Agent在線學(xué)習(xí)的環(huán)境里，每個Agent的行為是隨它的學(xué)習(xí)情況而改變的。當(dāng)環(huán)境中有其他Agent存在時，轉(zhuǎn)移函數(shù)應(yīng)隨時間而變化，也就是說MDP模型不再適用了6。然而，現(xiàn)有的許多基于MDP模型的強化學(xué)習(xí)方法并沒有做更多的改進(jìn)。本文設(shè)計了一個基于Agent對當(dāng)前協(xié)商環(huán)境的信念的動態(tài)Q學(xué)習(xí)算法，根據(jù)當(dāng)前更新了的環(huán)境信念做出估計值Q

15、。該方法采用的是估計對手和環(huán)境的信念而非Q函數(shù)，因而就不用觀察對手的實際回報值和它的Q學(xué)習(xí)參數(shù)。這里采用聯(lián)合策略（，）對狀態(tài)-動作對的Q值進(jìn)行估計，其中，表示該Agent采取的行動，表示對方Agent采取的行動。Agent在當(dāng)前環(huán)境狀態(tài)s下，估計對手Agent的行動，基于隨機策略（Boltzmann方法）選擇自己的行動： ( 2 )其中，是基于狀態(tài)s下的信念的期望Q函數(shù)值，即： （3）在時刻t，環(huán)境改變到新的狀態(tài)，得到行動的獎勵值，Agent基于下面的公式更新Q的值： （4） 其中，為對手Agent實際執(zhí)行的一個行動，表示學(xué)習(xí)率。隨著時間衰減，以利于學(xué)習(xí)算法的收斂。在自動協(xié)商系統(tǒng)中，Agent

16、的歷史經(jīng)驗可能會因為對手策略的改變而過時，同時隨著學(xué)習(xí)進(jìn)程的進(jìn)行，Agent所取得的知識趨于精確（表現(xiàn)為Q值收斂于Q*）。如果這時仍然進(jìn)行大量的探索活動，勢必造成系統(tǒng)性能下降。所以，在Agent與環(huán)境充分作用之后，適當(dāng)?shù)販p少探索是必要的。這里將最近探索盈余（Recency Exploration Bonus）7引入到Q學(xué)習(xí)中：（5） 其中，是等待時間的盈余，是探索的盈余。這樣，學(xué)習(xí)Agent僅探索那些最近未到達(dá)過的狀態(tài)，并準(zhǔn)備適應(yīng)對方Agent的任何改變。一般在設(shè)計Q-學(xué)習(xí)算法時，應(yīng)先確定狀態(tài)空間S、動作空間A以及回報值r。這里用狀態(tài)s代表Agent接收到的提議，它是一個n元組：。其中，是所協(xié)

17、商的商品屬性j的取值；所有狀態(tài)s構(gòu)成的集合為狀態(tài)空間S。另外，用s* 代表協(xié)商Agent期望的最佳提議。用動作a代表Agent改變或保持屬性j的取值，即Agent當(dāng)前給出的提議；所有動作a構(gòu)成的集合為動作空間A。回報值r定義為： ( 6 )其中，表示屬性j的值的計分函數(shù)，取值變化見文獻(xiàn)3。由于Agent接收到的提議是由對方Agent根據(jù)該Agent的上次提議所生成的，因而可以使用該Agent的計分函數(shù)來評估對手Agent給出的屬性值，并使用整體的屬性評估值來定義回報值。有了以上定義，下面給出提議生成步驟：Step1. 初始化：，=1， ，=0.5；Step 2. 在當(dāng)前環(huán)境狀態(tài)s下，對所有可能

18、的提議動作，基于信念，根據(jù)公式（2），Agent選擇當(dāng)前的最佳行為；Step 3. 執(zhí)行在Step 2中選擇的；Step 4. 在時刻t，環(huán)境改變到新的狀態(tài)，從對方Agent接收到動作，根據(jù)公式（6），Agent計算回報值，并修改當(dāng)前學(xué)習(xí)率： (7)其中，為到t時刻為止，Agent得到經(jīng)驗的次數(shù)；Step 5. 根據(jù)公式（1），Agent更新信念，得到；Step 6. 根據(jù)公式（4）、（5），Agent依次更新，并存儲值；Step 7. ，根據(jù)對方提議中的信息，產(chǎn)生所有可能的新的提議動作，并以缺省值存儲；Step 8. 若Agent對當(dāng)前提議滿意（收斂于s*狀態(tài)），則接受提議；否則轉(zhuǎn)至Step

19、 2繼續(xù)執(zhí)行。5. 基于信念的動態(tài)Q學(xué)習(xí)實驗 實驗構(gòu)建了一個分布式環(huán)境，用兩臺PC機模擬兩個Agent，用工作站模擬談判環(huán)境的變化。實驗系統(tǒng)基于Java2實現(xiàn)，采用了面向Agent的程序設(shè)計，并用JATLite8包作為Agent的通信支持。使用三類學(xué)習(xí)Agent，第一類是傳統(tǒng)的Q學(xué)習(xí)Agent（可用MDP建模的）；第二類是本文采用的基于信念的Q學(xué)習(xí)Agent；第三類是基于隨機估計的Q學(xué)習(xí)Agent，它對對手的行為估計是隨機的。參數(shù)定義為，=0.3，=0.9，=0.02，所有Q值初始化為0，=0.1。圖1 實驗結(jié)果由圖1可以看出第一類和第二類學(xué)習(xí)Agent工作較優(yōu)，能隨著交互提議的次數(shù)增加而很快

20、收斂，適應(yīng)環(huán)境變化。第三類Agent雖然也在學(xué)習(xí)，但它沒有學(xué)習(xí)到雙方的聯(lián)合行為，只是隨機選取動作。實驗結(jié)果顯示，前兩類Agent的學(xué)習(xí)性能較為相似，表明我們所使用的基于當(dāng)前信念的學(xué)習(xí)方法是有效的，同時由于采用了固定的貝葉斯法則對信念更新，整個過程都是收斂的，并且通過適當(dāng)?shù)脑O(shè)定，算法也收斂。6. 小結(jié)文章討論了如何將機器學(xué)習(xí)應(yīng)用于自動協(xié)商中去的問題。通過對協(xié)商理論的描述，特別是對協(xié)商流程的分析，利用貝葉斯法則來更新協(xié)商中的環(huán)境信息（即信念），利用強化學(xué)習(xí)中的Q學(xué)習(xí)算法來生成協(xié)商中的提議，從而建立了一個具有學(xué)習(xí)機制的多Agent自動協(xié)商模型。并且對傳統(tǒng)Q學(xué)習(xí)進(jìn)行了擴充，設(shè)計了基于Agent的當(dāng)前信

21、念和最近探索盈余的動態(tài)Q學(xué)習(xí)算法。用兩臺PC機模擬兩個Agent，用工作站模擬環(huán)境的變化，構(gòu)建了一個分布式環(huán)境，對算法中一些主要參數(shù)的影響作了一個比較實驗，實驗結(jié)果證明了該模型能夠較好地解決實驗環(huán)境中的協(xié)商問題。參考文獻(xiàn)：1 Stanley, Y.W., Chunbo Huang and Joachim Hammer, “A Replicable Web-based Negotiation Server for E-commerce”, Thirty-third Hawaii International Conference on System Sciences (HICSS-33), IEE

22、E, Hawaii, January 2000.2 ertsekas, D.P., Dynamic Programming and Optimal Control, Belmont, MA: Athena Scientific, 1995.3 Jia Li, Wang fang and Qiu Yuhui, “ Using Reinforcement Learning to Make Automated Negotiation in Multi-Agent Based E-commerce ”, Proceeding International Conference on Intelligen

23、t Information Technology (ICIIT) , Beijng, CHINA, September 22-25 , 2002. 4 Zeng, D. and Sycara, K., “Benefits of Learning in Negotiation”, Proc. of the National Conf. on Artificial Intelligence (AAAI-97), Menlo Park, pp. 36-41, 1997.5 Tom M. Mitchell 著.曾華軍、張銀奎等譯，機器學(xué)習(xí) ，機械工業(yè)出版社，2003。6 Y. Nagayuki, S.

24、 Ishii and K. Doya, “Multi-Agent Reinforcement Learning: an Approach Based on the Other Agent's Internal Model”, Fourth International Conference on Multi-Agent Systems (ICMAS), pp. 215-221, Los Alamitos: IEEE Computer Society, 2000.7 Henghuo Zhu and Dana H. Ballard, “Overcoming Non-stationarity

25、in Uncommunicative Learning”, Technical Report 762, Computer Science Dept., U. Rochester, 2001.8 JATLite, papers/ JATL.html#G2.Research on Applying Machine Learning to Automated Negotiation in Multi-agent SystemYANG Ming 1, LU Ruihua 2, QIU Yuhui 3(1,3 School of Compute and Information Science , Sou

26、thwest Normal University, Chongqing 400715,China ;2 School of Electronics and Information Engineering , Southwest Normal University, Chongqing 400715,China ) Abstract: At present applying machine learning to automated negotiation in multi-agent system becomes the hotspot research in the field of ele

27、ctronic commerce. In this paper, we use Bayesian learning to revise beliefs , and put Q-learning algorithm to propose counteroffers of negotiation, and we establish an automated negotiation modal with learning mechanism. At the same time, we extend the traditional Q-learning into a dynamic Q-learning algorithm by introducing current beliefs and recent exploration bonus, the results of experiment show that our algorithm is convergent.Key words: Bayesian learning; beliefs revision; Reinforcement learning; automated negotiation; Q-learning algorithm; proposing offers（上接第42頁）A Fingerprint C