多Agent自动协商中机器学习的应用研究

1、多Agent自动协商中机器学习的应用研究杨明 杨明，女，博士生，讲师，主要研究方向：机器学习，分布式人工智能。E-mail: yangming。，鲁瑞华2，邱玉辉3( 1,3 西南师范大学计算机与信息科学学院，重庆北碚 400715; 2西南师范大学电子与信息工程学院，重庆北碚 400715) 摘 要：目前将机器学习理论应用到多Agent自动协商系统中已成为电子商务领域的最新研究课题。本文即是利用贝叶斯法则来更新协商中的环境信息（即信念），利用强化学习中的Q学习算法生成协商中的提议，建立了一个具有学习机制的多Agent自动协商模型。并且对传统Q学习算法进行了扩充，设计了基于Agent的当前信念

2、和最近探索盈余的动态Q学习算法，实验验证了算法的收敛性。关键词：贝叶斯学习；信念更新；强化学习；自动协商；Q学习算法；生成提议1. 引言随着人工智能以及Agent技术的发展,利用具有一定自主推理、自主决策能力的Agent以及由其组成的多Agent系统已经成为电子商务中的热门工具，由于Agent能模拟人类商业交往中的协商而无需引入一些无关的倾向，使协商过程更加理性。然而协商是在不完全信息条件下进行的，协商过程本身存在许多不确定和不稳定因素，因此在多Agent系统中引入学习机制，使每个Agent通过学习来协调自身的行为，则能有效地完成协商目的。目前将机器学习理论应用到自动协商系统中已成为电子商务领

3、域的最新研究课题，现有自动协商系统中涉及到的机器学习方法主要有以下几种：贝叶斯学习、遗传算法、强化学习等。本文即是利用贝叶斯法则来更新协商中的环境信息（即信念），利用强化学习中的Q学习算法生成协商中的提议，从而建立了一个具有学习机制的多Agent自动协商模型。2.协商的相关理论在多Agent系统中，协商是指在一个特定领域中，一群Agent为了就某事达成相互都可以接受的协议而进行交流的过程。协商的目的是参与协商的各方在追求自己的需求，或者自己所代表的某个组织的需求时，应该通过交换提议而进行磋商，共同寻找双方都能接受的方案。协商不是无限制地满足自己的利益，而是有一定的利益界限。协商者之间是既竞争又

4、合作的关系，协商双方必须存在协商的可行区域。2.1 协商协议协商协议（Negotiation Protocol）是保证Agent之间解决冲突并达成合作协议的机制，它规定了协商Agent之间通信的语言、规范以及语义。换句话说，协商协议定义了在协商实体之间的消息流，规定了在何时采取何种行动等行为约束，该约束便是协商实体间交互所必须遵守的行为规则。比较常用的协商协议有监听协议、合同网协议、分布匹配协议、竞价协议、拍卖协议、统一协商协议等。2.2 协商策略协商策略（Negotiation Strategy）是协商所用的推理模型，是Agent进行决策和选择行动的一种战术。协商策略由与协商协议相应的元协商

5、策略和选择策略算法组成，一般分为：竞争策略、一方让步策略、延迟协议策略、变更协议策略。协商协议是Agent协商的外在限制，而协商策略是Agent协商的内在限制，二者相对独立又相互影响。 2.3 协商流程为描述方便，以电子商务中卖方Agent与买方Agent之间的协商执行过程为例，假设Agent之间的通信通道已建立。首先卖方Agent权衡盈利值，选择一个能获得最佳利润的提议。接收到提议的买方Agent，根据对方的提议，更新当前信念；然后检查约束，评估该提议是否可接受；如果不可接受，则调整协商策略，生成新的提议。具体描述如下：1)更新信念。信念包括对协商对手的私有信息和当前环境状态的基本看法，各方

6、Agent的信念模型随着协商的进行以及从对方接收到的提议中不断更新。通过协商过程中提议与反提议的交互，双方Agent可以根据交互的信息以及自己的领域知识来更新信念，从而对对方Agent的提议结构及策略逐步了解，生成有利于己方的提议。 2)检查约束，评估提议。约束检查是在协商Agent收到提议后，根据用户约束库中的相应属性和约束，对属性或属性间的约束进行检查，最先检查那些不可协商的属性。当违反约束时，应用松弛规则自动松弛约束或人工增加、修改约束松弛规则1。在协商过程中，收到提议的Agent要对提议进行评估，判断该提议是否与它的期望值相近。3)调整策略，生成新提议。根据协商环境和协商对手的提议来调

7、整策略，如做出让步等，从而生成新的提议。2.4协商模型由上述协商流程可以看出：协商Agent在协商过程中交替交换提议，它们在每次收到协商对手的提议后按照一定的策略生成反提议作为应答，因此，基于Agent的自动协商可以看作是一个连续决策过程。连续决策模型2将决策过程划分为一系列相互依赖的决策点，决策方可以在执行决策和接受反馈后更新自己的知识，因此连续决策模型以及改进的连续决策模型成为多Agent间自动协商的模型主流, 为研究协商中的学习提供了方便。作者在文献3中采用多属性效用理论和连续决策过程相结合的方法建立了一个多问题自动协商的形式化模型。限于篇幅，此处不再描述。3.贝叶斯学习的引入在机器学习

8、中，通常我们感兴趣的是在给定训练数据D时，确定假设空间H中的最优（Best）假设。所谓最优假设，是指定义在给定数据D以及H中不同假设的先验概率知识下的最可能假设。贝叶斯理论提供了一种直接计算这种可能假设的方法(即采用一种概率手段)。它基于如下假设：待考查的量遵循某种概率分布，且可根据这些概率及观察到的数据进行推理，从而做出最优的决策。它为衡量多个假设的置信度提供了定量的方法，可以处理信息不完全、不精确的推理。这里对贝叶斯法则进行简单地描述：代表在没有训练数据前假设h拥有的初始概率，称为h的先验概率，它反映了我们所拥有的关于h是一正确假设的机会的背景知识。如果没有这一先验知识，那么可以简单地将每

9、一候选假设赋予相同的先验概率；：代表将要观察的训练数据D的先验概率；：代表假设h成立的情形下观察到数据D的概率；：代表给定训练数据D时h成立的概率，称为h的后验概率（Posterior Probability），反映了在已知训练数据D后h成立的置信度。后验概率反映了训练数据D的影响，而先验概率是独立于D的。贝叶斯法则是贝叶斯学习方法的基础，因为它提供了从先验概率以及和计算后验概率的方法。即下列贝叶斯公式：本文首先通过建立协商环境的信念模型来解决Agent间的学习问题，参与的Agent在概率的框架下采用贝叶斯方法来更新协商Agent对环境和对方Agent的知识和信念。考虑到贝叶斯分析的计算复杂性

10、问题，这里使用贝叶斯信念网络（Bayesian Brief Network）的表示和更新机制。贝叶斯信念网络提供了一个可表达的建模语言，允许灵活、便捷地对领域知识编码4。在电子商务中，协商各方Agent对自己的商品属性保留值很清楚，但不是很了解对方的保留值及策略，最初只能根据自己的背景知识和了解程度做一假设。通过在协商过程中提议与反提议的交互，双方Agent根据交互的信息以及自己的领域知识来更新信念，从而对对方Agent的提议结构及策略逐步了解，生成有利于己方的提议。协商Agent对对方Agent可能给出的商品属性j的值的信念表示为一个假设集合。根据Agent的先验知识，对每个假设值都有一个概

11、率估计，形成一个概率集合；从对方Agent接收到的提议作为信号e；根据Agent当前观察到的领域知识，对每个假设形成一个先验条件概率。应用贝叶斯法则，生成假设的后验概率： （1）根据新的概率值，Agent更新信念，同时调整自己的协商策略。4. 强化学习中Q学习算法的引入强化学习（Reinforcement Learning）是由动物学习、随机逼近、优化控制等理论发展而来，是一种无导师在线学习技术, 它提供了一种通过奖赏和惩罚对Agent进行规划的方法。其基本原理是：如果Agent的某个行为策略导致环境正的奖赏（强化信号），那么Agent以后产生这个行为策略的趋势便会加强5。4.1 Q学习算法Q

12、学习算法是强化学习中最重要的学习算法之一，它实际是马尔可夫判定过程（MDP）的一种变化形式，MDP也可看作是强化学习的数学模型。通常，一个MDP可以用一个四元组来表示：<S,A,R,T> 其中：S是环境状态空间；A是Agent的行为动作空间；R是奖赏函数R：S×A R；T是状态转移函数T：S×A PD（S），PD是状态空间S的概率分布。记R（s1,a,s2）是Agent 在环境状态 s1 S 下采用动作 aA使环境状态迁移到 s2 S时所获得的奖赏值。T(s1,a,s2)是Agent在环境状态 s1S下采用动作 a A使环境状态迁移到 s2 S的概率。Agent

13、的目标是在每个离散的环境状态空间发现最优策略以使期望的折扣奖赏和最大。定义Q值为状态动作对的估计，根据对MDP的定义，有： 其中 sS ，aA ，S ，是状态s经过动作a后到达的下一个状态，为折扣因子，0<<1 。在已知R和T条件下，可以得到最终的Q值。由于Q值是未来奖赏的精确总和，所以此学习方法将Q值作为即时奖赏的替代，每次选择最高Q值就可以得到MDP的最优策略。4.2引入Q学习的多Agent自动协商模型在协商过程中，由于双方都不愿过早暴露自己的私有信息，即双方Agent都具有不完全信息的特点，因此对手的提议便是了解对方私有信息、效用函数，并更新己方策略的重要信息来源。这样看来，

14、协商Agent具有在线学习能力是十分重要的。由于第三小节中已经讨论了采用贝叶斯学习对当前协商状态下的环境以及对手信息等信念的更改，接下来我们只考虑协商的动态学习过程，即采用动态Q学习来生成提议。在MDP中，环境状态的转换由转移概率函数定义，它是不随时间变化的。考虑到在多个Agent在线学习的环境里，每个Agent的行为是随它的学习情况而改变的。当环境中有其他Agent存在时，转移函数应随时间而变化，也就是说MDP模型不再适用了6。然而，现有的许多基于MDP模型的强化学习方法并没有做更多的改进。本文设计了一个基于Agent对当前协商环境的信念的动态Q学习算法，根据当前更新了的环境信念做出估计值Q

15、。该方法采用的是估计对手和环境的信念而非Q函数，因而就不用观察对手的实际回报值和它的Q学习参数。这里采用联合策略（，）对状态-动作对的Q值进行估计，其中，表示该Agent采取的行动，表示对方Agent采取的行动。Agent在当前环境状态s下，估计对手Agent的行动，基于随机策略（Boltzmann方法）选择自己的行动： ( 2 )其中，是基于状态s下的信念的期望Q函数值，即： （3）在时刻t，环境改变到新的状态，得到行动的奖励值，Agent基于下面的公式更新Q的值： （4） 其中，为对手Agent实际执行的一个行动，表示学习率。随着时间衰减，以利于学习算法的收敛。在自动协商系统中，Agent

16、的历史经验可能会因为对手策略的改变而过时，同时随着学习进程的进行，Agent所取得的知识趋于精确（表现为Q值收敛于Q*）。如果这时仍然进行大量的探索活动，势必造成系统性能下降。所以，在Agent与环境充分作用之后，适当地减少探索是必要的。这里将最近探索盈余（Recency Exploration Bonus）7引入到Q学习中：（5） 其中，是等待时间的盈余，是探索的盈余。这样，学习Agent仅探索那些最近未到达过的状态，并准备适应对方Agent的任何改变。一般在设计Q-学习算法时，应先确定状态空间S、动作空间A以及回报值r。这里用状态s代表Agent接收到的提议，它是一个n元组：。其中，是所协

17、商的商品属性j的取值；所有状态s构成的集合为状态空间S。另外，用s* 代表协商Agent期望的最佳提议。用动作a代表Agent改变或保持属性j的取值，即Agent当前给出的提议；所有动作a构成的集合为动作空间A。回报值r定义为： ( 6 )其中，表示属性j的值的计分函数，取值变化见文献3。由于Agent接收到的提议是由对方Agent根据该Agent的上次提议所生成的，因而可以使用该Agent的计分函数来评估对手Agent给出的属性值，并使用整体的属性评估值来定义回报值。有了以上定义，下面给出提议生成步骤：Step1. 初始化：，=1， ，=0.5；Step 2. 在当前环境状态s下，对所有可能

18、的提议动作，基于信念，根据公式（2），Agent选择当前的最佳行为；Step 3. 执行在Step 2中选择的；Step 4. 在时刻t，环境改变到新的状态，从对方Agent接收到动作，根据公式（6），Agent计算回报值，并修改当前学习率： (7)其中，为到t时刻为止，Agent得到经验的次数；Step 5. 根据公式（1），Agent更新信念，得到；Step 6. 根据公式（4）、（5），Agent依次更新，并存储值；Step 7. ，根据对方提议中的信息，产生所有可能的新的提议动作，并以缺省值存储；Step 8. 若Agent对当前提议满意（收敛于s*状态），则接受提议；否则转至Step

19、 2继续执行。5. 基于信念的动态Q学习实验 实验构建了一个分布式环境，用两台PC机模拟两个Agent，用工作站模拟谈判环境的变化。实验系统基于Java2实现，采用了面向Agent的程序设计，并用JATLite8包作为Agent的通信支持。使用三类学习Agent，第一类是传统的Q学习Agent（可用MDP建模的）；第二类是本文采用的基于信念的Q学习Agent；第三类是基于随机估计的Q学习Agent，它对对手的行为估计是随机的。参数定义为，=0.3，=0.9，=0.02，所有Q值初始化为0，=0.1。图1 实验结果由图1可以看出第一类和第二类学习Agent工作较优，能随着交互提议的次数增加而很快

20、收敛，适应环境变化。第三类Agent虽然也在学习，但它没有学习到双方的联合行为，只是随机选取动作。实验结果显示，前两类Agent的学习性能较为相似，表明我们所使用的基于当前信念的学习方法是有效的，同时由于采用了固定的贝叶斯法则对信念更新，整个过程都是收敛的，并且通过适当的设定，算法也收敛。6. 小结文章讨论了如何将机器学习应用于自动协商中去的问题。通过对协商理论的描述，特别是对协商流程的分析，利用贝叶斯法则来更新协商中的环境信息（即信念），利用强化学习中的Q学习算法来生成协商中的提议，从而建立了一个具有学习机制的多Agent自动协商模型。并且对传统Q学习进行了扩充，设计了基于Agent的当前信

21、念和最近探索盈余的动态Q学习算法。用两台PC机模拟两个Agent，用工作站模拟环境的变化，构建了一个分布式环境，对算法中一些主要参数的影响作了一个比较实验，实验结果证明了该模型能够较好地解决实验环境中的协商问题。参考文献：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 著.曾华军、张银奎等译，机器学习 ，机械工业出版社，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