Policy Gradient Methods for Reinforcement Learning with Function Approximation 论文精读

Policy Gradient Methods for Reinforcement Learning with Function Approximation 论文精读

强化学习学习笔记

笔者通过阅读文献结合自己的知识理解，将相关论文全部粗读一边后开始精读各个方法文献，总结强化学习方法的研究路径和方向，并上传至csdn网站进行留存，同时欢迎各位对本文中出现的错误和问题进行指正和交流。

Policy Gradient Methods发表于2000年，是强化学习方法的源头，其中涉及到了策略、状态动作价值、智能体的目标函数、AC算法的原理。
智能体的目标函数的求解方法便是使用基于梯度的方法进行迭代寻优，若问题为凸优化问题，则该问题最终会收敛到全局最优解。

1. Policy Gradient 策略梯度法

发表时间：2000年

论文全程：Policy Gradient Methods for Reinforcement Learning with Function Approximation

主要内容：

梯度更新方向：∆θ ≈ α*∂ρ/∂θ 学习率乘对应策略的性能对θ的偏导数。

定理1：
∂ ρ ∂ θ = ∑ s d π ( s ) ∑ a ∂ π ( s , a ) ∂ θ Q π ( s , a ) (1) frac{∂ρ}{∂θ} = sum_sd^π(s)sum_afrac{∂π(s, a)}{∂θ}Q^π(s, a)tag1 ∂θ∂ρ​=s∑​dπ(s)a∑​∂θ∂π(s,a)​Qπ(s,a)(1)
推导过程：

策略的定义：

首先我们可以知道当前策略 π ( s , a , θ ) pi(s,a,theta) π(s,a,θ) ，其中 s , a s,a s,a为变量， θ theta θ为参数，该表示方式的意义为，给定 s , a , θ s,a,theta s,a,θ三个值，将会输出在参数组为 θ theta θ，当前状态 s s s下，采取动作 a a a的概率值，或者该策略直接包含了概率选取，直接给出动作，由于 θ theta θ是参数可以省略不写，所以策略就被定义为了 π ( s , a ) pi(s,a) π(s,a)。

智能体的目标函数

1.平均奖励最大
ρ ( π ) = l i m n − > ∞ 1 n E { r 1 + r 2 + ⋯ + r n ∣ π } = ∑ s d π ( s ) ∑ a π ( s , a ) R s a (2) rho(pi)=lim_{n->infin}frac{1}{n}E{r_1+r_2+cdots+r_n|pi}=sum_sd^pi(s)sum_api(s,a)R_s^atag 2 ρ(π)=limn−>∞​n1​E{r1​+r2​+⋯+rn​∣π}=s∑​dπ(s)a∑​π(s,a)Rsa​(2)
上式即表示当 n n n趋于无穷时，即在无限长的时间中平均所有的奖励值，这一式子也可使用统计学的方式表示，即用 d π ( s ) d^π(s) dπ(s)表示在当前策略下，状态 s s s的出现频率，再乘该状态下基于所有动作下所获得的奖励值，理论上来讲 ∑ a π ( s , a ) R s a sum_api(s,a)R_s^a ∑a​π(s,a)Rsa​ 是策略所得到奖励的期望值，但Agent在行动的时候只会采取一种动作，因此采取的动作为 π ( s , a s e l e t e d _ a c t i o n ) pi(s,a_{seleted_action}) π(s,aseleted_action​)的值为1，那么其余 π ( s , a e l s e ) pi(s,a_{else}) π(s,aelse​)就为0了。

当我们知道了平均奖励，那么每一个 s t e p ( s , a ) step (s,a) step(s,a)对应的价值即为当前的奖励减去平均奖励，价值函数使用 Q π ( s , a ) Q^pi(s,a) Qπ(s,a)来表示，这一表示的含义为在策略 π pi π下，面对状态 s s s所采取动作 a a a的价值。

Q π ( s , a ) = ∑ t = 1 ∞ E { r t − ρ ( π ) ∣ s 0 = s , a 0 = a , π } , ∀ s ∈ S , a ∈ A (3) Q^pi(s,a)=sum_{t=1}^infin E{r_t-rho(pi)|s_0=s,a_0=a,pi},forall sin S,a in Atag3 Qπ(s,a)=t=1∑∞​E{rt​−ρ(π)∣s0​=s,a0​=a,π},∀s∈S,a∈A(3)
上式表示对于任意的 s 和 a s和a s和a，首先找到在 t ∈ [ 1 , ∞ ) t in [1,infin) t∈[1,∞)范围中找到对应的时间，然后以该时间所给的 r t r_t rt​，即奖励值减去平均奖励。

2.折扣因子表示

平均奖励的计算方法将各个时间点的奖励视为同等重要，而折扣因子则表示过去、现在和未来的奖励权重是不同的，要乘上一个折扣因子，并且现在的奖励包含未来的折扣奖励。

ρ ( π ) = E { ∑ t = 1 ∞ γ t − 1 r t ∣ s 0 , π } rho(pi)=E{sum_{t=1}^infingamma^{t-1}r_t|s_0,pi} ρ(π)=E{∑t=1∞​γt−1rt​∣s0​,π}

Q π ( s , a ) = E { ∑ k = 1 ∞ γ k − 1 r t + k ∣ s t = s , a t = a , π } Q^pi(s,a)=E{sum_{k=1}^infingamma^{k-1}r_{t+k}|s_t=s,a_t=a,pi} Qπ(s,a)=E{∑k=1∞​γk−1rt+k​∣st​=s,at​=a,π}

第一个式子即为智能体的优化目标，即从起始点开始，最大化总奖励。

第二个式子同样为价值函数，等式含义为在 t t t时之后的所有折扣奖励综合。

3.两种 Q π ( s , a ) Q^pi(s,a) Qπ(s,a)表示方法的对比

平均奖励方法的价值函数考虑了整个阶段的平均奖励，假设了整个阶段已经完成，因此单步的价值与当前的奖励和整个过程的奖励有关。

折扣因子方法的价值函数即人为真实的奖励包含当前奖励和未来奖励，从式子中可以看出，单步的价值与当前的奖励和其之后的过程奖励有关。

两种表示方法可借由 d π ( s ) d^pi(s) dπ(s)进行统一

即折扣因子方法中使得

d π ( s ) = ∑ t = 0 ∞ γ t P r { s t = s ∣ s 0 , π } d^pi(s)=sum_{t=0}^infingamma^tPr{s_t=s|s_0,pi} dπ(s)=∑t=0∞​γtPr{st​=s∣s0​,π}

因此目标函数变为：

ρ ( π ) = ∑ s d π ( s ) ∑ a π ( s , a ) R s a rho(pi)=sum_sd^pi(s)sum_api(s,a)R_s^a ρ(π)=∑s​dπ(s)∑a​π(s,a)Rsa​

因此得出定理1：
∂ ρ ∂ θ = ∑ s d π ( s ) ∑ a ∂ π ( s , a ) ∂ θ Q π ( s , a ) (4) frac{partialrho}{partialtheta}=sum_sd^pi(s)sum_afrac{partialpi(s,a)}{partialtheta}Q^pi(s,a)tag 4 ∂θ∂ρ​=s∑​dπ(s)a∑​∂θ∂π(s,a)​Qπ(s,a)(4)
该式子即为通过优化 θ theta θ来使得Agent的目标函数更好所需的梯度。当然，这也可以理解为目标函数对 θ theta θ偏导数，可通过求极值的方式直接求取最优解 θ theta θ。

近似策略梯度

该部分指出了价值函数 Q π ( s , a ) Q^pi(s,a) Qπ(s,a)是可以被某些符合条件的函数近似表示的，假设函数 f w ( s , a ) f_w(s,a) fw​(s,a)为 Q π ( s , a ) Q^pi(s,a) Qπ(s,a)的近似函数，使用误差的平方作为优化的目标，因此就有。

Δ w t ∝ ∂ ∂ w [ Q π ( s t , a t ) − f w ( s t , a t ) ] 2 ∝ [ Q π ( s t , a t ) − f w ( s t , a t ) ] ∂ f w ( s t , a t ) ∂ w Delta w_t propto frac{partial}{partial w}[Q^π(s_t, a_t) − f_w(s_t, a_t)]^2propto [Q^π(s_t, a_t) − f_w(s_t, a_t)] frac{partial f_w(s_t,a_t)}{partial w} Δwt​∝∂w∂​[Qπ(st​,at​)−fw​(st​,at​)]2∝[Qπ(st​,at​)−fw​(st​,at​)]∂w∂fw​(st​,at​)​

因此收敛到局部最优时有

∑ s d π ∑ a π ( s , a ) [ Q π ( s t , a t ) − f w ( s t , a t ) ] ∂ f w ( s t , a t ) ∂ w = 0 (5) sum_sd^pisum_api(s,a)[Q^π(s_t, a_t) − f_w(s_t, a_t)] frac{partial f_w(s_t,a_t)}{partial w}=0tag 5 s∑​dπa∑​π(s,a)[Qπ(st​,at​)−fw​(st​,at​)]∂w∂fw​(st​,at​)​=0(5)

考虑前式

∂ ρ ∂ θ = ∑ s d π ( s ) ∑ a ∂ π ( s , a ) ∂ θ Q π ( s , a ) frac{partialrho}{partialtheta}=sum_sd^pi(s)sum_afrac{partialpi(s,a)}{partialtheta}Q^pi(s,a) ∂θ∂ρ​=∑s​dπ(s)∑a​∂θ∂π(s,a)​Qπ(s,a)

得出，若

∂ f w ( s t , a t ) ∂ w = ∂ π ( s , a ) ∂ θ 1 π ( s , a ) (6) frac{partial f_w(s_t,a_t)}{partial w}=frac{partial pi(s,a)}{partial theta}frac{1}{pi(s,a)}tag 6 ∂w∂fw​(st​,at​)​=∂θ∂π(s,a)​π(s,a)1​(6)

那么收敛到最优的时候替换掉上面的式子就会变为：

∑ s d π ( s ) ∑ a ∂ π ( s , a ) ∂ θ [ Q π ( s t , a t ) − f w ( s t , a t ) ] = 0 sum_sd^pi(s)sum_afrac{partial pi(s,a)}{partial theta}[Q^π(s_t, a_t) − f_w(s_t, a_t)]=0 ∑s​dπ(s)∑a​∂θ∂π(s,a)​[Qπ(st​,at​)−fw​(st​,at​)]=0

该式子表明函数 f w ( s , a ) 就是 Q w ( s , a ) f_w(s,a)就是Q^w(s,a) fw​(s,a)就是Qw(s,a)的近似函数。

于是，便有了定理2：

如果满足式(5)(6)两个条件，即有：
∂ ρ ∂ θ = ∑ s d π ( s ) ∑ a ∂ π ( s , a ) ∂ θ f w ( s , a ) (7) frac{partial rho}{partial theta}=sum_sd^pi(s)sum_afrac{partial pi(s,a)}{partial theta}f_w(s,a)tag 7 ∂θ∂ρ​=s∑​dπ(s)a∑​∂θ∂π(s,a)​fw​(s,a)(7)
实际上，通过式(6)我们可以推导出更多的特点。

推导算法的应用及优点

假设一个吉布斯分布的策略（当前策略的选择该动作的策略和选择其他策略的概率有关联性）：
π ( s , a ) = e θ T ϕ s a ∑ b e θ T ϕ s b , ∀ s ∈ S , a ∈ A , (8) pi(s,a)=frac{e^{theta^Tphi_{sa}}}{sum_be^{theta^Tphi_{sb}}},forall s in S, a in A,tag 8 π(s,a)=∑b​eθTϕsb​eθTϕsa​​,∀s∈S,a∈A,(8)
使用近似条件(6)可得到：
∂ f w ( s , a ) ∂ w = ∂ π ( s , a ) ∂ θ 1 π ( s , a ) = ϕ s a − ∑ b π ( s , b ) ϕ s b (9) frac{partial f_w(s,a)}{partial w}=frac{partialpi(s,a)}{partial theta}frac{1}{pi(s,a)}=phi_{sa}-sum_bpi(s,b)phi_{sb}tag 9 ∂w∂fw​(s,a)​=∂θ∂π(s,a)​π(s,a)1​=ϕsa​−b∑​π(s,b)ϕsb​(9)
我们知道 f w ( s , a ) f_w(s,a) fw​(s,a)这个函数关于 w w w的偏导是这种形式，那么使用积分很容易可以得到原函数的形式：
f w ( s , a ) = w T [ ϕ s a − ∑ b π ( s , b ) ϕ s b ] . (10) f_w(s,a)=w^T[phi_{sa}-sum_bpi(s,b)phi_{sb}].tag {10} fw​(s,a)=wT[ϕsa​−b∑​π(s,b)ϕsb​].(10)
然后会有细心的人发现在每个阶段都有均值为0这一条件，即：
∑ a π ( s , a ) f w ( s , a ) = w T [ ∑ a π ( s , a ) ϕ s a − ∑ a π ( s , a ) ∑ b π ( s , b ) ϕ s b ] (11) sum_api(s,a)f_w(s,a)=w^T[sum_api(s,a)phi_{sa}-sum_api(s,a)sum_bpi(s,b)phi_{sb}]tag {11} a∑​π(s,a)fw​(s,a)=wT[a∑​π(s,a)ϕsa​−a∑​π(s,a)b∑​π(s,b)ϕsb​](11)
其中 ∑ a π ( s , a ) = 1 sum_api(s,a)=1 ∑a​π(s,a)=1，可得
w T [ ∑ a π ( s , a ) ϕ s a − ∑ a π ( s , a ) ∑ b π ( s , b ) ϕ s b ] = w T [ ∑ a π ( s , a ) − ∑ b π ( s , b ) ] = 0 (12) w^T[sum_api(s,a)phi_{sa}-sum_api(s,a)sum_bpi(s,b)phi_{sb}]=w^T[sum_api(s,a)-sum_bpi(s,b)]=0tag{12} wT[a∑​π(s,a)ϕsa​−a∑​π(s,a)b∑​π(s,b)ϕsb​]=wT[a∑​π(s,a)−b∑​π(s,b)]=0(12)

基于函数逼近的策略迭代收敛性

基于函数逼近为使用近似函数进行策略迭代更新，实际上就是Actor-Critic方法的最源头的原理。

可以简单形容为：在当前策略下我找到一个近似函数 f w ( s , a ) f_w(s,a) fw​(s,a)来表示 Q π ( s , a ) Q^pi(s,a) Qπ(s,a)，那么我们就可以基于当前这个近似函数来更新我们的策略 π ( s , a , θ ) pi(s,a,theta) π(s,a,θ)中的参数 θ theta θ。

但是由于式子(6)表明当策略变了，近似函数 f w π k ( s , a ) f_w^ {pi_k}(s,a) fwπk​​(s,a)就不合理了，也是需要随着策略改变而不断更新的。

综上，我们得到了最终的AC算法的原理，也就是定理3.

定理3 基于函数逼近的策略迭代
w k = w s u c h t h a t ∑ s d π k ∑ a π k ( s , a ) [ Q π k ( s , a ) − f w ( s , a ) ] ∂ f w ( s , a ) ∂ w = 0 (13) w_k=w quad such quad that quad sum_sd^{pi_k}sum_api_k(s,a)[Q^{pi_k}(s,a)-f_w(s,a)]frac{partial f_w(s,a)}{partial w}=0 tag{13} wk​=wsuchthats∑​dπk​a∑​πk​(s,a)[Qπk​(s,a)−fw​(s,a)]∂w∂fw​(s,a)​=0(13)

θ k + 1 = θ k + α k ∑ s d π k ( s ) ∑ a ∂ π k ( s , a ) ∂ θ f w k ( s , a ) , (14) theta_{k+1}=theta_k+alpha_ksum_sd^{pi_k}(s)sum_afrac{partial pi_k(s,a)}{partial theta}f_{w_k}(s,a),tag{14} θk+1​=θk​+αk​s∑​dπk​(s)a∑​∂θ∂πk​(s,a)​fwk​​(s,a),(14)

最终收敛的结果为目标函数为0，即 l i m k → ∞ ∂ ρ ( π k ) ∂ θ = 0 lim_{krightarrowinfin}frac{partialrho(pi_k)}{partialtheta}=0 limk→∞​∂θ∂ρ(πk​)​=0

即表示当前的Agent已经达到局部最优的效果，甚至是全局最优。