机器学习：面向资源分配问题的Q-CF多智能体强化学习

·100. 智能系统学报 第6卷 [9]王醒策，张汝波，顾国昌.基于强化学习的多机器人编队 参考文献： 方法研究[J].计算机工程，2002,28(6)：15-16， [1]CHONGJIE Z,LESSER V,SHENOY P.A multi-Agent WANG Xingce,ZHANG Rubo,GU Guochang.Research on learning approach to resource sharing across computing multi-Agent team formation based on reinforcement learning clusters[R].Computer Science Department,University of [J].Computer Engineering,2002,28(6):15-16. Massachusetts Computer Science Amherst UMass,UM-CS- [10]HU J,WELLMAN M P.Nash Q-learning for general-sum 2008035,2008. stochastic games [J].Journal of Machine Learning Re- [2]KO P C,LIN P C,YOU J A,et al.Multi-layer allocated search,2003,4:1039-1069. leaming based neural network for resource allocation optimi- [11]ALPAYDM E.机器学习导论[M].范明，等译.北京： zation[C]//Proceedings of the 9th Joint Conference on In- 北京工业出版社，2009：244255， formation Sciences(JCIS 2006).Taibei,China,2006:35- [12]LAGOUDAKIS M G,PARR R.Least-squares policy itera- 41. tion[J].Joural of Machine Leaming Research,2003 [3]TESAURO G.Online resource allocation using decomposi- (4):1107-1149. tional reinforcement learning [C]//Proceedings of AAAI [13]XU X,HU D W,LU X C.Kemel based least-squares pol- 2005.Pittsburgh,USA,2005:886-891. icy iteration[J].IEEE Transactions on Neural Networks, [4]LITTMAN M L,STONE P.Leading best-response strategies 2007,18(4):973992. in repeated games[C]//The 17th Annual International Joint 作者简介： Conference on Artificial Intelligence Workshop on Economic 连传强，男，1986年生，硕士研究生， Agents,Models,and Mechanism.Seattle,Washington, 主要研究方向为模式识别与机器学习. USA,2001:745-756. [5]HU J,WELLMAN M P.Multiagent reinforcement learning in stochastic games OL].Citeseer.ist.psu.edu/ hu99multiagent.Html,1999. [6]BUSONIU L,De SCHUTTER B,BABUSKA R.Multiagent reinforcement learning with adaptive state focus[C]//Pro- 徐昕，男，1974年生，研究员，博士， ceedings of the 17th Belgium-Netherlands Conference on Ar- 主要研究方向为增强学习、自适应动态 tificial Intelligence.Brussels,Belgium,2005:35-42. 规划理论和算法、智能移动机器人、智 [7]KOK J R,VLASSIS N.Collaborative multiagent reinforce- 能系统 ment leaming by payoff propagation[J].Joural of Machine Learning Research,2006,7:1789-1828. [8]杨佩，陈兆乾，陈世福.机器学习在RoboCup中的应用研 究[J].计算机科学，2003,30(6)：118-121. 吴军，男，1980年生，博士研究生. YANG Pei,CHEN Zhaoqian,CHEN Shifu.RoboCup 主要研究方向为多机器人系统、机器学 multi-Agent system machine-learning [J].Computer Sci- 习与智能系统。 ences,2003,30(6):118-121

第6卷第2期 智能系统学报 Vol.6 No.2 2011年4月 CAAI Transactions on Intelligent Systems Apr.2011 doi:10.3969/j.issn.1673-4785.2011.02.001 面向资源分配问题的Q-CF多智能体强化学习 连传强，徐昕，吴军，李兆斌 (国防科技大学机电工程与自动化学院，湖南长沙410073) 摘要：多智能体强化学习算法在用于复杂的分布式系统时存在着状态空间大、学习效率低等问题.针对网络环境中 的资源分配问题对多智能体强化学习算法进行了研究，将Q-学习算法和链式反馈(chain feed山ack,CF)学习算法相结 合，提出了Q-C℉多智能体强化学习算法，利用一种称为信息链式反馈的机制实现了多智能体之间的高效协同.仿真结 果表明，和已有的多智能体Q学习算法相比，该方法具有更加快速的收敛速度，同时保证了协同策略的性能优化 关键词：多智能体系统；强化学习；资源分配；协同控制 中图分类号：TP391.1文献标识码：A文章编号：16734785(2011)02009506 Q-CF multi-Agent reinforcement learning for resource allocation problems LIAN Chuangiang,XU Xin,WU Jun,LI Zhaobin (College of Mechatronics and Automation,National University of Defense Technology,Changsha 410073,China) Abstract:When a multi-Agent reinforcement learning algorithm is used in complex distributed systems,problems such as huge state space and low learning efficiency arise.In this paper,a multi-Agent reinforcement learning algo- rithm was studied for the resource allocation problem in a network environment.By combining the Q-learning algo- rithm and the chain feedback learning mechanism,a novel Q-CF multi-Agent reinforcement learning algorithm was presented.In the Q-CF algorithm,multi-Agent cooperation was realized based on the mechanism of information chain feedback.Simulation results show that compared with the multi-Agent Q-learning algorithm in existence,the proposed algorithm in this paper has a faster convergence speed while at the same time ensures the performance op- timization of cooperation policy. Keywords:multi-Agent system;reinforcement learning;resource allocation;cooperation control 近些年来，在网络环境中的资源分配问题因为强学习或再励学习，是与监督学习和无监督学习并 其广泛的应用，如网络服务、传感器网络等，所以受 列的一大类机器学习方法.作为一种以环境的状态 到越来越多的关注.它的特点在于，在网络环境中， 和评价性反馈为输入的机器学习方法，强化学习通 资源实现了共享，因而能够满足更多的应用需求.然 过与环境交互，不断改进策略，最终获得最优行为策 而随着需求的不断增大，网络环境中的资源分配问 略.而由多个并发的强化学习主体组成的多智能体 题规模也越来越大，因此如何合理分配资源以优化 系统近年来受到了越来越多的关注.Littman基于随 系统的性能，提高系统的效率是亟待解决的问题.许 机决策理论框架提出了零和策略下的多智能体强化 多学习算法已经被应用到资源分配问题中13]，其 学习算法[4]，Hu和Wellman将这种方法扩展到非零 中机器学习在资源分配问题中的应用是当前的一个 和决策]，这种算法可以看作是单个智能体Q学习 研究热点 的扩展；L.Busoniu等人提出适应性的状态聚焦Q 强化学习(reinforcement learning,RL)又称为增 学习算法[6]，其特点在于状态空间由简变繁直至学 习的收敛性满足要求，提高了学习效率；J.R.Kok等 收稿日期：2010-0325. 基金项目：国家自然科学基金资助项目(60774076,90820302) 人将整体的行为值函数分解并利用决定性的传播算 通信作者：连传强.E-mail:wzdslcg@163.com. 法，使得问题的规模仅为线性7

96 智能系统学报 第6卷 多智能体强化学习在多机器人系统中的应用最 用集合(C,A,T,D,R)来描述资源分配系统，其中： 为广泛，如多机器人足球赛8]、多机器人编队控 C={C,C2,…,Cn}是所有簇的集合 制]等，此外在其他领域如资源分配、游戏、网络路 A=[a;]是任务在相邻簇之间的传递时间矩 由选择、口语对话系统等也有了一定的应用，目前己 阵，其中ag表示任务在相邻簇C:和C之间传递所 成为机器学习领域研究的热点之一 花费的时间. 目前的多智能体强化学习算法基本还是以 T={t,2,…,tn}是所有任务类型的集合 Q学习算法为主，由于Q-学习算法是一种表格式的 D={dg}是任务类型到达的分布，其中dg表示 算法；因此在面临大规模空间的分布式优化决策问 任务类型到达簇C的分布. 题时，往往存在学习效率低、计算收敛性差等缺点 R={R,R2,…,R}是每个簇所能提供资源类 因此如何改进多智能体强化学习算法就显得尤为重 型的集合. 要.本文通过网络环境中的资源分配问题来研究多 每个簇都有自己的一些计算节点，每个节点都 智能体强化学习算法.虽然一些学习算法已经被应 拥有若干种资源类型以及相应的资源量.一般来说， 用到资源分配问题，但这些学习算法的效率往往不 一个任务可以被几个节点共同完成，但是为了简化 能令人满意；因此通过资源分配问题来研究多智能 问题的复杂度，这里假设一个任务只能被一个节点 体强化学习算法对优化资源分配问题、改进多智能 完成，因此对任务类型t可用集合(D,D,D,D) 体强化学习算法具有重要的意义， 来描述，其中：D={(R,Da),…,(R2,Da)}表示 本文研究的网络环境中的资源分配问题模型是 的是一个任务类型所需求的资源分布，其中D表 一个由若干个共享簇组成的网络结构，每个簇拥有 示的是对资源类型R,的需求量的分布；D:表示的 一定数量的计算节点，每个节点都拥有一定的资源 是任务的服务时间分布；D:表示的是任务的效用率 针对其特点，提出了Q-CF多智能体强化学习算法， 分布；D表示的是任务最大等待时间的分布， 它将资源分配问题的决策分解成2步决策：本地分 通过以上的定义，不难得出系统的平均效用率为 配决策和任务传递决策，其中分布式Q-学习算法的 AUR ∑∑'4∑e() 学习任务是学习本地分配策略，而利用C℉学习算 T 法来学习任务的传递决策.仿真结果表明，和已有的 式中：T为仿真总时间，T,为t时刻在簇C:上所有正 多智能体Q学习算法相比，该方法具有更加快速的 在运行的任务集合，u(x)为任务x的效用率，而该 收敛速度，同时保证了协同策略的性能优化， 文的目的就是通过学习使得系统的AUR最大化， 1.2多智能体强化学习 1资源分配问题描述与多智能体强化 学习的过程通常是一个马尔可夫决策过程 学习 (MDP),可用集合(S,A,P,r)来描述这一过程，其 中：S为状态空间，A为行为空间，P是状态转移矩 1.1资源分配问题描述 阵，P(s+1ls,a)表示的是在t时刻状态为s,时执 对于一个网络环境中的资源分配系统，每个簇可 行动作a,使得在t+1时刻状态为S,1的概率，r为 以从外部接收任务，也可以从邻居簇接收任务.在每个 回报函数，r(s'Is,a)表示为在状态s执行a动作使 时间步，簇都必须做出决策任务在本地如何分配以及 得状态转移到s时所得到的立即回报值.而智能体 未分配的任务该传递给哪个邻居簇，每个任务都有自 的学习目标就是最大化如下的折算累计回报： 己的效用率，当任务在本地被成功地分配，那么系统将 在每个时间步都获得相应的效用值直到任务完成；反 V=∑yr(s11,马) (1) 之，如果一个任务在它的最大等待时间内没有被分配， 式中：y∈(0,1)为折算因子. 那么这个任务将从系统中清除.当任务完成以后，它所 作为一种强化学习算法，Q学习算法中的评估 占用的资源将被返还给系统.而研究这个问题的目的 函数Q(s,a)定义为从状态s执行动作a的立即回 就是最大化整个系统的平均效用率 报加上以后遵循最优策略的值（用y折算），其更新

第2期 连传强，等：面向资源分配问题的Q-CF多智能体强化学习算法 ·97 规则为 时候，定义为low,反之定义为high,那么一个计算节 Q(s,a)+Q(s,a)+a[r+yQ-Q(s,a)]. 点的资源状态可用(low,low)、(low,hi冲)、(high, (2) low)、(high,high)中的一种来表示.因此，定义s= 式中：0=∑p(s'1s,a)∑aπ(s',a)Q(s',a'),T (n1,2,n3,n4),其中n1表示一个簇中节点状态为 (s',a)为在s'状态下执行a'动作的概率.a∈(0,1) (low,low)的数量，n2表示(low,high)的数量，n3表示 为学习率，y∈(0,1)为折算因子，r为在s状态下执 (high,low)的数量，n4表示(high,high)的数量. 行a动作的立即回报 动作空间a:a=(actionl,action2),其中actionl 在状态s上的最优动作a为 表示选取的任务类型，action2表示为选取的任务分 π*(s)=arg max Q(s,a) 配到哪一种类型的节点.例如a=(3,4),表示将第 Hu和Wellman将单智能体的Q-学习算法推广 3种任务类型的任务分配到状态为(hig,high)的节 到了多智能体系统[.在他们的算法中，假设一个 点.如果任务中有多个相同的任务类型，将优先选取 智能体可以感知其他智能体的行动和从环境中得到 效用率高的任务。 的回报，所有智能体的Q值表都被保存.在假设有2 状态转移矩阵p:通过实验可以实现对状态转 个智能体的系统中，当智能体在状态s选择动作 移矩阵p的估计. (a1,a2)到达状态s'时，智能体得到回报(r1,r2),Q 回报函数：如果相应的任务完成了，r=u,其中 值表通过下式进行更新： 4为任务的效用率；反之，r=0. Q(s,a1,a2)←-(1-x)Q.(s,a1,a2)+ 定义好(S,A,P,)之后，就可以利用Q值更新 air;+yvi(s'). 规则(1)以及搜索策略(e-greedy)进行Q-学习： 式中：V(s)是智能体i在双矩阵决策〈A1,A2, e(s,a;).T T(s,a:）= Q1(S),Q2(S)〉的平衡点 ∑，e(s,4)/4 式中：e、r均为大于0的常量. 2Q-C多智能体强化学习算法 本地策略的分布式Q-学习算法流程为 QCF学习算法是一个异步的强化学习算法，即 对簇i每个s,a初始化表项Q:(s,a)为0，t时刻 通过Q学习算法和C℉学习算法相结合实现异步学 簇i的状态为s,等待本地分配的任务数为n; 习，其中利用Q学习算法来学习任务的本地分配策 循环（循环次数为n): 略，而通过CF学习算法来学习任务的传递对象选 1)利用&greedy方法选择1个动作a并执行它； 择策略。 2)接收到立即回报r； 2.1本地策略的分布式Q-学习算法 3)观察新状态s'; 每个簇均独立地使用Q学习算法学习任务在 4)对Q:(s,a)按照式(3)进行更新； 本地的分配策略.当一个簇接收到一定数量的任务 5)s←-s; 时，如何根据簇的资源状态合理地分配这些任务使 6)若r=0,则将该任务放入等待传递队列，否 得平均效用率最大，这是学习的目的.首先定义集合 则移除该任务； (S,A,p,r). 结束 状态空间S:为了便于对比，采用了文献[1]中的 2.2智能体之间任务传递策略的CF学习算法 问题模型，原问题模型有2种资源，即cpu资源和net- CF学习算法学习的是本地未分配的任务该如 work资源，将每种资源按照数量的多少分成n个层 何选择传递对象，以便让其他簇完成该任务.它的学 次，再将每个节点各资源的层次联合起来，便成为描 习算法思想来源于K臂赌博机问题，对(S,A,P, 述这个节点的资源状态，n越大，对节点状态的描述 )中的各项定义如下： 能力就越强，但同时状态空间也急剧变大，严重影响 状态空间s:状态只有1个，那就是k个簇。 了Q学习的效果.因此在这里每种资源只分为2个 动作空间a:a=(G,),表示将任务类型为的 层次，设定一个阈值，比如60，当资源低于这个阈值的 任务传递给编号为i的簇

·98 智能系统学报 第6卷 状态转移矩阵p:学习环境为单状态，状态转移 给它的任务增多而立即减小，从而引起传递策略的 矩阵p(sls)=1. 改变将任务传递给别的邻居簇，这样就避免了任务 回报函数r:这里的回报函数有2个，第1个是 的堆积，整体上平衡了任务的分布 立即回报，1=-1，表示的是将任务传递给簇的立即 task task task task 回报，或者说是惩罚，它存在的意义在后面将做出分 B 析；第2个是延迟回报r2=B”,其中B∈(0,1)为折 算率，n为任务经过n次传递才被分配，n=0表示为 图1信息链式反馈示意 Fig.1 Information chain feedback sketch map 任务在本地就被分配了，如果在任务的最大等待时 因为任务最后的分配情况会沿着它所经过的所 间内没有被分配，则n=∞，即T2=0. 有簇将信息逐级地反馈回去，因此称之为链式反馈 定义好了以上各项之后，再定义值函数Q的更 学习算法.从算法流程容易看出，此算法的特点在于 新规则.它的更新规则是异步的，其中当任务j到达 值函数的更新是异步的，这对平衡任务分布，提高学 簇i时，更新规则为 习速度和效果起到了重要作用. Q(a)←-Q(a)+r. 当任务被成功分配以后，此任务经过的所有 3实验结果及分析 簇则按照更新规则： 3.1实验设计 Q(a)-Q(a)+r2 为了便于比较，实验完全采用文献[1]中的实 来更新Q值. 验模型，模型如图2所示，图中圆圈内的数字表示为 簇i对任务j的传递策略为 簇的编号，相应的圆圈外的数字表示该簇所拥有的 argmax,Neighbors). (3) 节点数，每个节点都有2种资源：cpu和network,它 式中：j为任务类型为专的任务，Neighbors为第i个 们的初始值范围均为[50,150]，其中显示为带阴影 簇的所有邻居簇。 的4个簇6、7、10和11可以接受外部输入的任务， 智能体之间任务传递策略的C℉学习算法流程 所有的簇均可以接收内部簇之间传递的任务. 如下： 066-6-605-6 18 13 2116 19 15 t时刻，簇i有n个任务等待传递. 循环（循环次数为n): 1)对任一任务j按策略(3)传递到邻居簇'； 2)对簇'进行此任务的Q值更新，更新规则 6—⑤—④—③—1②@⑩—（⑨ 13 14 221611201519 为：Q(a)←Q(a)+r1; 图2实验模型 3)若任务j在簇被成功分配，则对任务j之前 Fig.2 Experiment model 经过的所有簇进行Q值更新，更新规则为：Q(α)←Q 假设所有任务的最大等待时间均为10，每种任 (a)+r2;反之，则将任务j放入簇'的等待传递队列； 务类型可用集合(d。,dn,u,t,)表示，其中d。表示为 4)将任务j从簇i的等待传递队列中移除， 对cpu的需求量；dn表示对network的需求量；u表 由图1所示，假如任务task按照策略(3)如图 示任务的效用率，.，表示任务的服务时间.假设d。、 中实线方向进行传递，直到簇5才被成功分配，那么 dn、山服从泊松分布，5，服从指数分布，实验的任务类 成功分配的信息将会按照虚线的方向反馈回给每个 型有4种： 此任务经过的簇，此信息具体的表现形式为B,也就 t1=(9,8,1,20),2=(15,48,6,35), 是相应簇的延迟回报2，不难看出，只有当任务在经 =(45,8,5,30),t4=(47,43,25,50) 历了次传递直到被分配以后，B的值才会反馈回 另外，外部任务的到达也服从参数如下的泊松分 给每一个它经历过的簇，因此这个回报是有延迟的， 布：簇6：(4.5,0.5,2.5,1)，簇7：(3.5,0.5,2,0.5)，簇 也就是说经过一段时间才会对Q值有所影响，引进 10:(4,2,0.5,1),簇11：(1.5,2.5,0.5,0.5). ,1立即惩罚函数以后，在某个时刻Q值会随着传递 最后，实验采用了3种方法进行效果的对比，具

第2期 连传强，等：面向资源分配问题的Q-CF多智能体强化学习算法 ·99· 体如表1. 的仿真时间才能保证其准确性，学习速度因此变慢 表13种决策方法 图4对Q-R与Q-CF各簇的平均效用率进行了 Table 1 Three decision-making methods 比较，容易看出中间部分QR各簇的平均效用率略 决策方法 G-R Q-R Q-CF 高于Q-C℉，这是因为Q-R第2步分配采取了随机策 第1步决策算法 贪婪 Q Q 略，任务很难传递得很远，因此几乎都堆积在这些簇 第2步决策算法 随机 随机 CF 中而使得这些簇的值较高；而在两边的那些簇中，Q- 3.2 实验结果及分析 CF要远远好于Q-R,这是因为Q-R第2步决策采取 与文献[1]中的实验结果进行了比较，文献[1] 随机策略使得任务的传递很难达到远离能够接受外 中采用的是FAL多智能体强化学习算法，其本质上 部任务的那些簇，而Q-CF则因为第2步决策采用 也是多智能体Q学习算法的一种，而本文采用的为 C℉学习算法而能够将任务量在系统中很好的平衡， Q-C℉多智能体强化学习算法 因此各簇平均效用率的值分布得比较好， 6.010 610 ▣Q-R Q-CF 5.5 5.0 日日日日日日0日日日 4.5 4.0 G-R 3.5 Q-R -e-0-CF 10 3.0 0.5 10百2.0253ǒ10 簇的编号 仿真时间/s 图4Q-R与Q-CF各簇的平均效用率 图3平均效用率 Fig.4 Average utility rate of clusters of Q-R and Q-CF Fig.3 Average utility rate 从图3中不雅看出，Q-CF曲线在t=250008 4结束语 左右趋于平稳，而文献[1]的方法在t=60000s左 本文通过网络环境中的资源分配问题对多智能 右才趋于平稳，2种方法的学习效果几乎相当.因此 体强化学习算法进行了深入的研究，提出了Q-CF 本文的Q-CF算法在保证了学习效果的同时，具有 学习算法，实现了智能体之间的高效协同，达到了学 更快的收敛速度，下面对其原因进行分析 习的目的.实验结果表明，本文方法和已有的多智能 对分布式Q学习算法的分析：文献[1]在学习 体Q学习算法相比，具有更加快速的收敛速度，同 本地分配策略时也用到了Q学习算法，但因为其在 时保证了协同策略的性能优化.这对以后相关问题 对状态的定义中还包含了对任务状态的定义（其实 的研究以及多智能体强化学习算法在分布式系统中 只是非常粗略的定义)，这使得状态空间为本文的 的应用具有一定的意义 16倍，因此影响了其学习速度.而本文在Q学习中 由于Q学习算法是一种表格式的算法，因此当 对任务的到达情况进行了统计，将这种统计用到学 状态动作空间较大时学习速度和效果都不能令人满 习中，在一定程度上弥补了状态定义的精简，因此学 意，而本文也是将状态空间进行了离散化之后才将 习的效果没有太大变化： Q-学习算法用于其中，这样势必会影响学习的效果. 对CF学习算法分析：因为引人了立即惩罚函 而更高级的强化学习算法，如最小二乘策略迭代 数，，使得Q值的更新能够更加准确地反映实际情 (LSP)[2]、基于核的最小二乘策略迭代(KLS 况，而延迟回报2至多在任务的最大等待时间内就 PI)[3]等均采用逼近的方式，解决了状态动作空间 能够反馈给相应的Q值，因此CF学习算法的时效 连续或者巨大的问题，因此用更高效的算法来替代 性非常强，大大提高了学习速度；而文献[1]中的Q- Q-学习算法应用到多智能体系统中将是以后要继续 学习因为状态空间特别大，而且需要不断地统计邻 的工作。 居簇在各种状态下各任务的完成情况，这需要一定