第1期 张文旭，等：基于事件驱动的多智能体强化学习研究 ·85· 根据贝尔曼迭代，Q值逐渐收敛到一个最优Q 空间并进行策略评估，否则直接使用上一时刻的策 值，在传统的强化学习中，每一个学习步智能体都需 略。假设在t时刻，智能体没有被事件所触发，那么 要通过查表方式找到最大的Q值，其迭代表达式为 智能体在t时刻不参与式(9)的迭代，直接使用t-1 AQ(s,,a,)=r+y maxQ(s1,a)-Q(s,,a) 时刻迭代后的Q值。此时，在达到最优策略的过程 (7) 中，Q值的迭代计算过程由每一时刻都计算，减少为 事件触发时刻才计算。 Q(s,a)=Q(s,a,)+aAQ(s.,a)= T。→Qm→T1→Q1→T2→Q2→π3→Q→T Q(s,,a,)+a(r+y maxQ(s,a)-Q(,,a,))= (10) (1-a)Q(s,,a,)+a(r,+ymaxeQ(s1,a,)) T0→Q0→m1→Q1→T2→Q2→T2→Q→…m1 (8) (11) 事件驱动的思路则不同，当智能体没有被触发 如图4(a)和式(10)所示，Q值从初始到收敛至 情况下，将直接选用上一个Q值作为当前的Q值， 最优Q·的过程，是一个渐进收敛的过程，Q值通过 在基于事件驱动的Q学习中，Q值迭代过程可以表 迭代，从t-1时间到t时刻逐渐接近最优：如图4(b) 示为 和式(11)所示，在智能体不被驱动的情况下，Q值 Q.(s,a,e)=(1-a)Q-k(s,a,e)+ 不进行迭代，在t-1时刻直接使用t时刻的Q值，减 a(r:+y maxQ(s+1,a,,e)) (9) 少了Q值的迭代计算。 式中k表示上次触发时刻和当前时刻的差值。 3.2计算资源消耗 Q学习中的计算资源消耗，主要体现在智能体 需要对所有策略进行试错。从决策树角度看，树根 和树枝对应着智能体团队的状态与观测，其在每一 次观测后，根据不同的观测都会转移到不同的下一 刻状态，即{s15,I(6,)}。在每一个树层中，智 能体团队需要通过遍历Q值表，查找得到一个最优 (a)经典的Q.学习策略迭代 策略。Q值表的实现采用Lookup表格来表示Q函 数。设Q(s,a)为一个Lookup表格，s∈S和a∈A -I 为有限集合，表的大小等于S×的笛卡尔乘积中的 元素的个数。举例说明，假设存在i个智能体，每一 个智能体有m个动作，每一时刻有n个状态，Q值 表的大小为n×m,在第t步，智能体共需遍历 (n'xm)x1次Q值，当参与学习的智能体数量较多， 以及每一个智能体的动作和状态集合较大时，查表 (b)基于事件驱动的O学习策略迭代 需要占用极大的计算资源。 图4两种方式策略迭代 对于基于事件驱动的决策树，在智能体不被驱 Fig.4 Policy iteration of two methods 动的树层中，下一刻状态将直接等于当前状态，即 推论1基于事件驱动的Q学习算法，不会影 S+1=3,状态转移概率为 响算法的收敛性。 P1=Pr6s1=s,la+1=a,}=1 引理1收敛引理。令X为一个任意的集 状态转移概率P=1意味着，此时整棵决策树中不 合，假设B是X中一个空间有界的集合，即B), 被驱动的树层不生成树枝，进而也减少下一层中树 T:BK)→BK)。·为T的一个固定点，令r= 枝对应的树根。同理，不生成新的树枝，智能体也无 (T,T,…)为来自F。(w)的初值，r在v°点逼近 需对当前树层里所有的Q值进行遍历。上述例子 T,假设F。为r中一个不变式。令V。∈F。(u),定 中，假设t步中存在k次不被驱动，那么在t步学习 义V+1=T,(V,V,)。如果存在随机函数0≤F(x)≤ 过程中，遍历Q值的次数为(nxm)×(t-k)次。 1和0≤G,(x)≤1以概率1满足以下条件，那么在 3.3算法收敛性分析 B仪)中V,以概率1收敛到v·: 智能体每次的策略评估，即策略迭代，都是从前 1)对所有的U1和U2∈F。,对所有的x∈X, 一个策略的值函数开始。在事件驱动的强化学习 |T.(U,v)(x)-T,(U,)(x)|≤ 中，智能体只有在观测信息变化情况下，才更新信念 G,(x)U(x)-U2(x) (12)根据贝尔曼迭代，Ｑ 值逐渐收敛到一个最优 Ｑ 值，在传统的强化学习中，每一个学习步智能体都需 要通过查表方式找到最大的 Ｑ 值，其迭代表达式为 ΔＱ（ｓｔ，ａ → ｔ） ＝ ｒｔ ＋ γ ｍａｘ ａ →∈ＡＱｔ（ｓｔ＋１ ，ａ → ｔ） － Ｑｔ（ｓｔ，ａ → ｔ） （７） Ｑｔ（ｓｔ，ａ → ｔ） ＝ Ｑｔ（ｓｔ，ａ → ｔ） ＋ αΔＱｔ（ｓｔ，ａ → ｔ） ＝ Ｑｔ（ｓｔ，ａ → ｔ） ＋ α ｒｔ ＋ γ ｍａｘ ａ →∈ＡＱｔ（ｓｔ＋１，ａ → ｔ） － Ｑｔ（ｓｔ，ａ → ( ｔ）) ＝ （１ － α）Ｑｔ（ｓｔ，ａ → ｔ） ＋ α ｒｔ ＋ γ ｍａｘ ａ →∈ＡＱｔ（ｓｔ＋１ ，ａ → ( ｔ） ) （８） 事件驱动的思路则不同，当智能体没有被触发 情况下，将直接选用上一个 Ｑ 值作为当前的 Ｑ 值， 在基于事件驱动的 Ｑ⁃学习中，Ｑ 值迭代过程可以表 示为 Ｑｔ（ｓｔ，ａ → ｔ，ｅ） ＝ （１ － α）Ｑｔ－ｋ（ｓｔ，ａ → ｔ，ｅ） ＋ α ｒｔ ＋ γ ｍａｘ ａ →∈ＡＱｔ（ｓｔ＋１ ，ａ → ( ｔ，ｅ） ) （９） 式中 ｋ 表示上次触发时刻和当前时刻的差值。 ３．２ 计算资源消耗 Ｑ⁃学习中的计算资源消耗，主要体现在智能体 需要对所有策略进行试错。 从决策树角度看，树根 和树枝对应着智能体团队的状态与观测，其在每一 次观测后，根据不同的观测都会转移到不同的下一 刻状态，即 ｓｔ＋１←ｓｔ ｜ ｏ → ，ａ → { ( ) } 。 在每一个树层中，智 能体团队需要通过遍历 Ｑ 值表，查找得到一个最优 策略。 Ｑ 值表的实现采用 Ｌｏｏｋｕｐ 表格来表示 Ｑ 函 数。 设 Ｑ（ｓ，ａ → ） 为一个 Ｌｏｏｋｕｐ 表格，ｓ∈Ｓ 和 ａ →∈Ａ → 为有限集合，表的大小等于 Ｓ×Ａ → 的笛卡尔乘积中的 元素的个数。 举例说明，假设存在 ｉ 个智能体，每一 个智能体有 ｍ 个动作，每一时刻有 ｎ 个状态，Ｑ 值 表的大小为 ｎ ｉ × ｍ ｉ ， 在第 ｔ 步， 智能体共需遍历 ｎ ｉ×ｍ ｉ ( ) ×ｔ 次 Ｑ 值，当参与学习的智能体数量较多， 以及每一个智能体的动作和状态集合较大时，查表 需要占用极大的计算资源。 对于基于事件驱动的决策树，在智能体不被驱 动的树层中，下一刻状态将直接等于当前状态，即 ｓｔ＋１ ＝ ｓｔ，状态转移概率为 Ｐ ａ → ｓ ｔ ｓ ｔ＋１ ＝ Ｐｒ ｓｔ＋１ ＝ ｓｔ { ａ → ｔ＋１ ＝ ａ → ｔ } ＝ １ 状态转移概率 Ｐｒ ＝ １ 意味着，此时整棵决策树中不 被驱动的树层不生成树枝，进而也减少下一层中树 枝对应的树根。 同理，不生成新的树枝，智能体也无 需对当前树层里所有的 Ｑ 值进行遍历。 上述例子 中，假设 ｔ 步中存在 ｋ 次不被驱动，那么在 ｔ 步学习 过程中，遍历 Ｑ 值的次数为 ｎ ｉ×ｍ ｉ ( ) ×(ｔ－ｋ) 次。 ３．３ 算法收敛性分析 智能体每次的策略评估，即策略迭代，都是从前 一个策略的值函数开始。 在事件驱动的强化学习 中，智能体只有在观测信息变化情况下，才更新信念 空间并进行策略评估，否则直接使用上一时刻的策 略。 假设在 ｔ 时刻，智能体没有被事件所触发，那么 智能体在 ｔ 时刻不参与式（９）的迭代，直接使用 ｔ－１ 时刻迭代后的 Ｑ 值。 此时，在达到最优策略的过程 中，Ｑ 值的迭代计算过程由每一时刻都计算，减少为 事件触发时刻才计算。 π０ →Ｑ π０ →π１ →Ｑ π１ →π２ →Ｑ π２ →π３ →Ｑ π３ →…π ∗ （１０） π０ →Ｑ π０ →π１ →Ｑ π１ →π２ →Ｑ π２ →π２ →Ｑ π２ →…π ∗ （１１） 如图 ４（ａ）和式（１０）所示，Ｑ 值从初始到收敛至 最优 Ｑ ∗的过程，是一个渐进收敛的过程，Ｑ 值通过 迭代，从 ｔ－１ 时间到 ｔ 时刻逐渐接近最优；如图４（ｂ） 和式（１１）所示，在智能体不被驱动的情况下，Ｑ 值 不进行迭代，在 ｔ－１ 时刻直接使用 ｔ 时刻的 Ｑ 值，减 少了 Ｑ 值的迭代计算。 （ａ）经典的 Ｑ⁃学习策略迭代 （ｂ）基于事件驱动的 Ｑ⁃学习策略迭代 图 ４ 两种方式策略迭代 Ｆｉｇ．４ Ｐｏｌｉｃｙ ｉｔｅｒａｔｉｏｎ ｏｆ ｔｗｏ ｍｅｔｈｏｄｓ 推论 １ 基于事件驱动的 Ｑ⁃学习算法，不会影 响算法的收敛性。 引理 １ 收敛引理［１２］ 。 令 χ 为一个任意的集 合，假设 Ｂ 是 χ 中一个空间有界的集合，即 Ｂ (χ ) ， Ｔ：Ｂ (χ ) → Ｂ (χ ) 。 ｖ ∗ 为 Ｔ 的一个固定点， 令 τ ＝ (Ｔ０ ，Ｔ１ ，…) 为来自 Ｆ０ ｖ ∗ ( ) 的初值，τ 在 ｖ ∗ 点逼近 Ｔ，假设 Ｆ０ 为 τ 中一个不变式。 令 Ｖ０∈Ｆ０ ｖ ∗ ( ) ，定 义 Ｖｔ＋１ ＝ Ｔｔ Ｖｔ，Ｖｔ ( ) 。 如果存在随机函数 ０≤Ｆｔ (ｘ) ≤ １ 和 ０≤Ｇｔ（ｘ）≤１ 以概率 １ 满足以下条件，那么在 Ｂ(χ ) 中 Ｖｔ 以概率 １ 收敛到 ｖ ∗ ： １）对所有的 Ｕ１ 和 Ｕ２∈Ｆ０ ，对所有的 ｘ∈χ， Ｔｔ（Ｕ１ ，ｖ ∗ ）（ｘ） － Ｔｔ（Ｕ，Ｖ）（ｘ） ≤ Ｇｔ（ｘ） Ｕ１（ｘ） － Ｕ２（ｘ） （１２） 第 １ 期 张文旭，等：基于事件驱动的多智能体强化学习研究 ·８５·