多Agent自動協(xié)商中機器學習的應用研究

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

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

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

4、合作的關系，協(xié)商雙方必須存在協(xié)商的可行區(qū)域。2.1 協(xié)商協(xié)議協(xié)商協(xié)議（Negotiation Protocol）是保證Agent之間解決沖突并達成合作協(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進行決策和選擇行動的一種戰(zhàn)術。協(xié)商策略由與協(xié)商協(xié)議相應的元協(xié)商

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

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

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

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

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

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

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

12、學習算法是強化學習中最重要的學習算法之一，它實際是馬爾可夫判定過程（MDP）的一種變化形式，MDP也可看作是強化學習的數(shù)學模型。通常，一個MDP可以用一個四元組來表示：<S,A,R,T> 其中：S是環(huán)境狀態(tài)空間；A是Agent的行為動作空間；R是獎賞函數(shù)R：S×A R；T是狀態(tài)轉移函數(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、的目標是在每個離散的環(huán)境狀態(tài)空間發(fā)現(xiàn)最優(yōu)策略以使期望的折扣獎賞和最大。定義Q值為狀態(tài)動作對的估計，根據(jù)對MDP的定義，有： 其中 sS ，aA ，S ，是狀態(tài)s經(jīng)過動作a后到達的下一個狀態(tài)，為折扣因子，0<<1 。在已知R和T條件下，可以得到最終的Q值。由于Q值是未來獎賞的精確總和，所以此學習方法將Q值作為即時獎賞的替代，每次選擇最高Q值就可以得到MDP的最優(yōu)策略。4.2引入Q學習的多Agent自動協(xié)商模型在協(xié)商過程中，由于雙方都不愿過早暴露自己的私有信息，即雙方Agent都具有不完全信息的特點，因此對手的提議便是了解對方私有信息、效用函數(shù)，并更新己方策略的重要信息來源。這樣看來，

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

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

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

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

18、的提議動作，基于信念，根據(jù)公式（2），Agent選擇當前的最佳行為；Step 3. 執(zhí)行在Step 2中選擇的；Step 4. 在時刻t，環(huán)境改變到新的狀態(tài)，從對方Agent接收到動作，根據(jù)公式（6），Agent計算回報值，并修改當前學習率： (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對當前提議滿意（收斂于s*狀態(tài)），則接受提議；否則轉至Step

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

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

21、念和最近探索盈余的動態(tài)Q學習算法。用兩臺PC機模擬兩個Agent，用工作站模擬環(huán)境的變化，構建了一個分布式環(huán)境，對算法中一些主要參數(shù)的影響作了一個比較實驗，實驗結果證明了該模型能夠較好地解決實驗環(huán)境中的協(xié)商問題。參考文獻：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 著.曾華軍、張銀奎等譯，機器學習 ，機械工業(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