第1期 王学宁，等：增强学习中的直接策略搜索方法综述 ·19· 足一定的条件，才能保证算法的收敛. 假设利用具有参数w的函数f。:SXA→R来 :山=+：亚aL++ 逼近Q,并且参数w满足条件： T(0,m) (s1 a) 又TSH.LaH,1 w arg min >(oi-f(s,.a))2. 14) (SH.1,aH-1 式中：⑨为O”的某种估计值，比如可以是R.如果 所以 函数f满足式14)，同时又满足相容性条件： atd-迹dL 15) a(s.n H.I v(s a) Cw 00 n(s,a) 21) 那么 =dw∑急.sw 此时可以看出，估计式Am就是在￠(s,a)= 16) 式16)的证明过程，请参看文献[81. 'n前提下，对梯度估计H次的平均值。 关于值函数逼近器的选择，一种可行的方案是 Baxter等分析了折扣因子y的取值对上述算 采用如下的形式： 法的影响：Y越接近于1，梯度估计越精确，事实上 (s.a wT Tais.al 估计的偏差正比于1-》，但是，Y1时，方差也无 (s,a 17) 限增大，所以，梯度估计的精确性与方差是一对矛 由式(17)方法可以很容易地构造出策略迭代方 盾，必须选择适当的Y对二者进行折衷处理.因此， 法1，并且该方法的收敛性也很容易证明.但是，由 尽管可以通过减小Y来减小方差，但是，这种方法的 于每次更新actor的参数之后，critic的参数需要重 调整能力有限. 新求解，从这个意义上来说，critic的参数并不具有 GPOMDP解除了REINFORCE算法只能求解 “学习"功能，并且求解critic参数的过程可能也比 周期性马氏决策问题的限制，但是仍然没能提高算 较耗时，这就影响了整个算法的收敛速度 法的收敛速度 2.2.3 GPOMDP算法 2.3现有策略梯度算法的推广 Baxter等提出了GPOMDP算法，尽管作者给 根据时域差分的思想，在策略梯度算法中可以 出了一种比较复杂的证明方法，但是，从迭代过程来 利用截断回报作为Q(s,ad的近似值，例如，t时刻的 看，GPOMDP仍然是利用式(12)来估计梯度，只不 Q(sr,a可以用一步截断回报来估计 过是行为值函数的估计采用了以下公式： Q(s,d≈R0=n+1+10(s+1,a+1.(22) H.t (s:.a)= (18 式中：Q为Q的某种估计值.也就是利用1+1时刻 的估计值，来对1时刻的估计值进行更新 下面证明这个结论： 把上式推广到k步截断回报为 GPOMDP算法中，迭代公式为 1=么，+404L Q(s,d≈Rw=n+1++2+…+ 80 (s:a) (19) 1n+k+(s+,a+ 23) △+1=△，++12+1. (20) 当k=时，就是实际回报 式中：，称为适合度轨迹，初始化为0向量，△。也初 始化为0向量.上述公式迭代H次后，梯度的估计 R=R=+.因此，REINFORCE算 法是截断回报算法的一种特例 值为品产为了简化证明过程，只分析△ 继续推广，可以利用各种截断回报的加权和来 为了书写简便，定义m(s,d=应心 Q(s,ad近似 08 因为0=0，所以 24 1=z4 (so ao) 只要是权系数满足a=1,则R为Qs,W的 a=yYT。L+I4 无偏估计.对比式18)和式(24，可以看出，GPOM T(0,w) T(S1,) DP其实是式24在a4=时的一个特例。 23=Y7匹4m y匹al+匹4mL H (so co) +y(s,a) T(2, 当然也可以利用回报来计算Q(s,d近似值： 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net足一定的条件 ,才能保证算法的收敛[8 ,19 ] . 假设利用具有参数 w 的函数 f w : S ×A →R 来 逼近 Q ,并且参数 w 满足条件 : w = arg min w ∑ t (Q^ π t - f (st , at) ) 2 . (14) 式中 :Q^ π t 为 Q π t 的某种估计值 ,比如可以是 Rt . 如果 函数 f 满足式(14) ,同时又满足相容性条件 : 5 f w (s, a) 5w = 5π(s, a) 5θ 1 π(s, a) . (15) 那么 5η 5θ = ∑s d π (s) ∑a 5π 5θ f w (s, a) . (16) 式(16) 的证明过程 ,请参看文献[8 ]. 关于值函数逼近器的选择 ,一种可行的方案是 采用如下的形式 : f w (s, a) = w T ý θπ(s, a) π(s, a) . (17) 由式(17) 方法可以很容易地构造出策略迭代方 法[8 ] ,并且该方法的收敛性也很容易证明. 但是 ,由 于每次更新 actor 的参数之后 ,critic 的参数需要重 新求解 ,从这个意义上来说 ,critic 的参数并不具有 “学习”功能 ,并且求解 critic 参数的过程可能也比 较耗时 ,这就影响了整个算法的收敛速度. 2. 2. 3 GPOMDP 算法 Baxter 等提出了 GPOMDP 算法 ,尽管作者给 出了一种比较复杂的证明方法 ,但是 ,从迭代过程来 看 , GPOMDP 仍然是利用式 (12) 来估计梯度 ,只不 过是行为值函数的估计采用了以下公式 : Q^ (st , at) = ∑ H- t k =1 γk- 1 rt+k . (18) 下面证明这个结论 : GPOMDP 算法中 ,迭代公式为 zt+1 = γzt + 5π(st , at) 5θ 1 π(st , at) . (19) Δt+1 = Δt + rt+1 zt+1 . (20) 式中 :zt 称为适合度轨迹 ,初始化为 0 向量 ,Δ0 也初 始化为 0 向量. 上述公式迭代 H 次后 ,梯度的估计 值为 5η 5θ = 1 H ΔH . 为了简化证明过程 ,只分析ΔH . 为了书写简便 ,定义 ýπ(s, a) = 5π(s, a) 5θ . 因为 z0 = 0 ,所以 z1 = ýπ(s0 , a0 ) π(s0 , a0 ) , z2 =γ ýπ(s0 , a0 ) π(s0 , a0 ) + ýπ(s1 , a1 ) π(s1 , a2 ) , z3 =γ2 ýπ(s1 , a0 ) π(s0 , a0 ) +γ ýπ(s1 , a1 ) π(s1 , a1 ) + ýπ(s2 , a2 ) π(s2 , a2 ) , … z H =γH - 1 ýπ(s0 , a0 ) π(s0 , a0 ) +γH - 2 ýπ(s1 , a1 ) π(s1 , a1 ) + …+ ýπ(s H - 1 , a H - 1 π(s H - 1 , a H - 1 , 所以 , ΔH = ∑ H t =1 rtzt = ∑ H t = 1 ýπ(st , at) π(st , at) ∑ H- t k =1 γk- 1 rt+k . (21) 此时可以看出,估计式 1 H ΔH 就是在 Q^ π (st , at) = ∑ H - t k = 1 γk - 1 rt + k前提下 ,对梯度估计 H 次的平均值. Baxter 等分析了折扣因子γ的取值对上述算 法的影响 :γ越接近于 1 ,梯度估计越精确 ,事实上 , 估计的偏差正比于(1 - γ) ,但是 ,γ→1 时 ,方差也无 限增大 ,所以 ,梯度估计的精确性与方差是一对矛 盾 ,必须选择适当的γ对二者进行折衷处理. 因此 , 尽管可以通过减小γ来减小方差 ,但是 ,这种方法的 调整能力有限. GPOMDP 解除了 REINFORCE 算法只能求解 周期性马氏决策问题的限制 ,但是仍然没能提高算 法的收敛速度. 2. 3 现有策略梯度算法的推广 根据时域差分的思想 ,在策略梯度算法中可以 利用截断回报作为 Q(s, a) 的近似值 ,例如 , t 时刻的 Q (st , at) 可以用一步截断回报来估计 Q(s, a) ≈ R (1) t = rt+1 +γQ^ (st+1 , at+1 ) . (22) 式中 :Q^ 为 Q 的某种估计值. 也就是利用 t + 1 时刻 的估计值 ,来对 t 时刻的估计值进行更新. 把上式推广到 k 步截断回报为 Q(s, a) ≈ R ( k) t = rt+1 +λrt+2 + …+ γk- 1 rt+k +γkQ^ (st+k , at+k ) . (23) 当 k = ∞时 ,就是实际回报 R ( ∞) t = Rt = ∑ ∞ k = 1 γk - 1 rt + k . 因此 , REINFORCE 算 法是截断回报算法的一种特例. 继续推广 ,可以利用各种截断回报的加权和来 Q(s, a) 近似 Q(s, a) ≈ R a t = ∑ H k =1 αk R ( k) t . (24) 只要是权系数满足 ∑ H k = 1 αk = 1 ,则 R α t 为 Q (s, a) 的 无偏估计. 对比式(18) 和式(24) ,可以看出 , GPOM2 DP 其实是式(24) 在αk = 1 H 时的一个特例. 当然也可以利用λ2回报来计算 Q (s, a) 近似值 : 第 1 期 王学宁 ,等 :增强学习中的直接策略搜索方法综述 ·19 ·