第1期 张文旭，等：基于事件驱动的多智能体强化学习研究 83. 络等领域。但是，目前事件驱动与强化学习的结合 还相对不足[8-]，并主要集中在对多智能体的控制 2 触发规则设计 器设计上，较少有学者关注其在学习策略层的应用。 在事件驱动思想中，智能体把从环境中得到的 在现有的多智能体强化学习算法中，由于智能体携 观测误差作为重要的评判标准，当它超过一个预设 带的通信设备和微处理器性能有限，其学习过程中 的阈值时事件被触发，智能体更新状态并计算联合 通常存在两个问题：1)智能体间的信息交互需占用 策略，而事件触发的关键在于对触发函数的设计。 较大的通信带宽；2)在学习的试错和迭代过程中， 2.1自事件触发设计 消耗了大量的计算资源。以上问题都将减少智能体 DEC-MDPs模型中，每一个智能体通过独立的 的工作时间，或增加设计上的复杂性。本文区别于 观测获取局部信息，然后广播到全队，所以每一个智 传统的多智能体学习算法，侧重于事件驱动在多智 能体首先需要自触发设计。在时刻t,当每一个智能 能体学习策略层的研究，首先从自触发和联合触发 体观测结束后，其根据上一刻观测与当前观测的变 两个方面定义触发函数，然后在分布式马尔可夫模 化率，进行一次自触发过程，智能体用自触发方式来 型中设计了基于事件驱动的多智能体强化学习算 判断是否需要广播自身的观测信息。智能体i从t- 法，最后对算法的收敛性进行了论证。 1时刻到t时刻的观测变化率定义为 e.(t)=o:(t)-o,(t-1)/o.(t-1)(1) 1 问题描述 式中：o.(t)为在t时刻的观测值。定义0<e<1为自 1.1分布式马尔可夫模型 事件触发函数阈值，当智能体ⅱ观测信息的变化率 考虑一个分布式马尔可夫模型(decentralized e,(t)大于e时进行通信。此时，不一定所有的智能 体都被驱动，没有采集到新观测信息的智能体仅接 markov decision processes,DEC-MDPs),是由一个五 元组(1，{S},{A},P,R〉构成的，其中，I表示有限 收信息。在自事件触发过程，智能体无需每一时刻 的智能体集合：{S}表示一个有限的系统状态集合： 进行通信，因此减少智能体的通信消耗。 2.2联合事件触发设计 {A:}表示智能体i可采取的动作的集合：P表示系 联合事件触发的对象是智能体团队，考虑的是 统的转移；R表示回报函数。DEC-MDPs与多智能 一个联合观测的变化情况。假设在时刻：智能体团 体的马尔可夫模型(multi agent--MDPs,M-MDPs)的 队获得当前的联合观测0(t)=(0,(t),02(t),…, 唯一区别在于，在M-MDPs中系统的全局信息被所 O(t)。此时，智能体团队从t-1时刻到t时刻的 有智能体完全获得，而在DEC-MDPs中，每一个智 联合观测变化率定义为 能体仅具有局部的观测，或者说是全局信息的一个 E(t)=(e(t),e2(t),e(t)) (2) 子集，当所有的子集放在一起求并集时，这些局部信 式中：e.(t)=|o.(t)-o:(t-1)l/o.(t-1)。 息能够合成一个完整的全局信息，在完全通信的情 利用方差计算两个时刻的误差偏移程度，令联 况下，DEC-MDPs可以被简化为M-MDPs模型。求 解DEC-MDPs的目的是找到一个联合策略元=（π1， 合观测变化率期塑为F()= ,e,(t)/n,方差为 T2,·,T.)来最大化回报函数R。求解DEC-MDPs 问题的计算复杂度为NEXPliO]难度，即问题的状态 D)=(e,()-F()2p (3) i= 随着步数增加呈现双指数增长。 式中：p=l/n为e,(t)的分布律，令 1.2 Q学习 H(t)=D(t)-F(t)/F(t) (4) 文献[11]提出了一类通过引入期望的延时回 定义0<G<1为团队的联合事件触发函数阈值，当 报，求解无完全信息的MDPs类问题的方法，称为 H(t)大于G时，认为智能体团队的状态已经发生较大 Q-学习(Q-learning)。Q-学习是一种模型无关的强 改变，需要对Q值表进行遍历，并计算一个新的联合策 化学习方法，通过对状态-动作对的值函数进行估 略，否则智能体直接延用上一刻的联合策略。 计，以求得最优策略。Q学习算法的基本形式如下： 自事件触发和联合事件触发的区别在于： Q(s,a)=Rs,a）+y∑P(s,a,s')maxQ^(s',a） 1)自事件触发的对象是单个智能体，对应的事 件由智能体自身的观测变化率所触发，触发后的行 式中：Q°(s,a)表示智能体在状态s下采用动作a 动为进行广播式通信，自事件触发的目的是为了减 所获得的奖赏折扣总和；y为折扣因子；P(s,a,s') 少通信资源消耗：而联合事件触发针对的是智能体 表示概率函数：最优策略为智能体在状态s下选用 团队的联合观测变化率，触发后的行动是计算联合 Q值最大的策略。Q学习存在的最大问题为，智能 策略，目的在于减少计算资源消耗。 体需要通过试错的方式找到最优策略，这样的方式 2)当单个智能体的观测发生变化时，并不一定 使得Q学习需要考虑所有的可能策略，从而需要消 导致团队的联合观测变化率发生较大改变。即当环 耗大量计算资源。 境整体发生变化时，虽然每一个智能体的观测都发络等领域。 但是，目前事件驱动与强化学习的结合 还相对不足［８－９］ ，并主要集中在对多智能体的控制 器设计上，较少有学者关注其在学习策略层的应用。 在现有的多智能体强化学习算法中，由于智能体携 带的通信设备和微处理器性能有限，其学习过程中 通常存在两个问题：１）智能体间的信息交互需占用 较大的通信带宽；２） 在学习的试错和迭代过程中， 消耗了大量的计算资源。 以上问题都将减少智能体 的工作时间，或增加设计上的复杂性。 本文区别于 传统的多智能体学习算法，侧重于事件驱动在多智 能体学习策略层的研究，首先从自触发和联合触发 两个方面定义触发函数，然后在分布式马尔可夫模 型中设计了基于事件驱动的多智能体强化学习算 法，最后对算法的收敛性进行了论证。 １ 问题描述 １．１ 分布式马尔可夫模型 考虑一个分布式马尔可夫模型（ ｄｅｃｅｎｔｒａｌｉｚｅｄ ｍａｒｋｏｖ ｄｅｃｉｓｉｏｎ ｐｒｏｃｅｓｓｅｓ， ＤＥＣ⁃ＭＤＰｓ），是由一个五 元组〈Ｉ，｛ Ｓ｝，｛Ａｉ｝，Ｐ，Ｒ〉构成的，其中，Ｉ 表示有限 的智能体集合；｛Ｓ｝表示一个有限的系统状态集合； ｛Ａｉ｝表示智能体 ｉ 可采取的动作的集合；Ｐ 表示系 统的转移；Ｒ 表示回报函数。 ＤＥＣ⁃ＭＤＰｓ 与多智能 体的马尔可夫模型（ｍｕｌｔｉ ａｇｅｎｔ⁃ＭＤＰｓ， Ｍ⁃ＭＤＰｓ）的 唯一区别在于，在 Ｍ⁃ＭＤＰｓ 中系统的全局信息被所 有智能体完全获得，而在 ＤＥＣ⁃ＭＤＰｓ 中，每一个智 能体仅具有局部的观测，或者说是全局信息的一个 子集，当所有的子集放在一起求并集时，这些局部信 息能够合成一个完整的全局信息，在完全通信的情 况下，ＤＥＣ⁃ＭＤＰｓ 可以被简化为 Ｍ⁃ＭＤＰｓ 模型。 求 解 ＤＥＣ⁃ＭＤＰｓ 的目的是找到一个联合策略 π → ＝ （π１ ， π２ ，…，πｎ ）来最大化回报函数 Ｒ。 求解 ＤＥＣ⁃ＭＤＰｓ 问题的计算复杂度为 ＮＥＸＰ ［１０］ 难度，即问题的状态 随着步数增加呈现双指数增长。 １．２ Ｑ⁃学习 文献［１１］提出了一类通过引入期望的延时回 报，求解无完全信息的 ＭＤＰｓ 类问题的方法，称为 Ｑ⁃学习（Ｑ⁃ｌｅａｒｎｉｎｇ）。 Ｑ⁃学习是一种模型无关的强 化学习方法，通过对状态－动作对的值函数进行估 计，以求得最优策略。 Ｑ⁃学习算法的基本形式如下： Ｑ ∗ （ｓ，ａ） ＝ Ｒ（ｓ，ａ） ＋ γ∑ｓ′∈Ｓ Ｐ（ｓ，ａ，ｓ′）ｍａｘＱ ∗ （ｓ′，ａ′） 式中：Ｑ ∗ （ｓ，ａ） 表示智能体在状态 ｓ 下采用动作 ａ 所获得的奖赏折扣总和；γ 为折扣因子；Ｐ（ ｓ，ａ，ｓ′） 表示概率函数；最优策略为智能体在状态 ｓ 下选用 Ｑ 值最大的策略。 Ｑ⁃学习存在的最大问题为，智能 体需要通过试错的方式找到最优策略，这样的方式 使得 Ｑ⁃学习需要考虑所有的可能策略，从而需要消 耗大量计算资源。 ２ 触发规则设计 在事件驱动思想中，智能体把从环境中得到的 观测误差作为重要的评判标准，当它超过一个预设 的阈值时事件被触发，智能体更新状态并计算联合 策略，而事件触发的关键在于对触发函数的设计。 ２．１ 自事件触发设计 ＤＥＣ⁃ＭＤＰｓ 模型中，每一个智能体通过独立的 观测获取局部信息，然后广播到全队，所以每一个智 能体首先需要自触发设计。 在时刻 ｔ，当每一个智能 体观测结束后，其根据上一刻观测与当前观测的变 化率，进行一次自触发过程，智能体用自触发方式来 判断是否需要广播自身的观测信息。 智能体 ｉ 从 ｔ－ １ 时刻到 ｔ 时刻的观测变化率定义为 ｅｉ（ｔ） ＝ ｏｉ（ｔ） － ｏｉ（ｔ － １） ／ ｏｉ（ｔ － １） （１） 式中：ｏｉ（ｔ）为在 ｔ 时刻的观测值。 定义 ０＜ｅ＜１ 为自 事件触发函数阈值，当智能体 ｉ 观测信息的变化率 ｅｉ（ｔ）大于 ｅ 时进行通信。 此时，不一定所有的智能 体都被驱动，没有采集到新观测信息的智能体仅接 收信息。 在自事件触发过程，智能体无需每一时刻 进行通信，因此减少智能体的通信消耗。 ２．２ 联合事件触发设计 联合事件触发的对象是智能体团队，考虑的是 一个联合观测的变化情况。 假设在时刻 ｔ 智能体团 队获得当前的联合观测 Ｏ（ ｔ） ＝ （Ｏ１（ ｔ），Ｏ２（ ｔ），…， Ｏｎ（ｔ））。 此时，智能体团队从 ｔ－１ 时刻到 ｔ 时刻的 联合观测变化率定义为 Ｅ（ｔ） ＝ （ｅ１（ｔ），ｅ２（ｔ），…ｅｎ（ｔ）） （２） 式中：ｅｉ（ｔ）＝ ｏｉ（ｔ）－ｏｉ（ｔ－１） ／ ｏｉ（ｔ－１）。 利用方差计算两个时刻的误差偏移程度，令联 合观测变化率期望为 Ｆ（ｔ） ＝ ∑ ｎ ｉ ＝ １ ｅｉ（ｔ） ／ ｎ，方差为 Ｄ（ｔ） ＝ ∑ ｎ ｉ ＝ １ （ｅｉ（ｔ） － Ｆ（ｔ）） ２·ｐ （３） 式中：ｐ ＝ １ ／ ｎ 为 ｅｉ（ｔ）的分布律，令 Ｈ（ｔ） ＝ Ｄ（ｔ） － Ｆ（ｔ） ／ Ｆ（ｔ） （４） 定义 ０＜Ｇ＜１ 为团队的联合事件触发函数阈值，当 Ｈ（ｔ）大于 Ｇ 时，认为智能体团队的状态已经发生较大 改变，需要对 Ｑ 值表进行遍历，并计算一个新的联合策 略，否则智能体直接延用上一刻的联合策略。 自事件触发和联合事件触发的区别在于： １）自事件触发的对象是单个智能体，对应的事 件由智能体自身的观测变化率所触发，触发后的行 动为进行广播式通信，自事件触发的目的是为了减 少通信资源消耗；而联合事件触发针对的是智能体 团队的联合观测变化率，触发后的行动是计算联合 策略，目的在于减少计算资源消耗。 ２）当单个智能体的观测发生变化时，并不一定 导致团队的联合观测变化率发生较大改变。 即当环 境整体发生变化时，虽然每一个智能体的观测都发 第 １ 期 张文旭，等：基于事件驱动的多智能体强化学习研究 ·８３·