策划师_共享办公室租赁平台_百度后台管理_中国市场营销网

本系列为学习赵世钰老师的《强化学习的数学原理》所作的学习笔记.

本节我们将介绍强化学习中的策略迭代求解方法.

2.2.1 算法步骤

跟值迭代类似, 策略迭代也是一个迭代的方法, 主要分为策略计算(PE)和策略提升(PI)两步.

2.2.1.1 策略计算(PE)

首先在当前策略${\pi }_k$的基础上, 计算状态值$v_{{\pi }_k}$, 实际就是求解贝尔曼公式:

$$v_{{\pi }_k}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k},$$

在1.4.4 贝尔曼公式求解中, 我们介绍了有两种求解方式:解析解和迭代求解. 但是解析解需要求逆矩阵, 所以常采用迭代求解的方式:

$$v_{{\pi }_k}^{(j+1)}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}^{(j)},j=0,1,2,\dots$$

它的展开形式为:

$$\begin{gathered} v_{{\pi }_k}^{(j+1)}(s)=\sum _a{\pi }_k(a\mid s)\left(\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p\left(s^{\prime }\mid s,a\right)v_{{\pi }_k}^{(j)}\left(s^{\prime }\right)\right), \\ s\in \mathcal{S} \end{gathered}$$

其中$v_{{\pi }_k}^{(j)}$是上一轮迭代的状态值, 初值可以设置为任意值. 直到$\Vert v_{\pi k}^{(j+1)}-v_{\pi k}^{(j)}\Vert <epsilon$, 则认为已经收敛.

2.2.1.2 策略提升(PI)

有了状态值$v_{{\pi }_k}$之后, 我们求解最优化问题, 得到新的最优策略${\pi }_{k+1}$:

$${\pi }_{k+1}=\arg \underset{\pi }{\max }\left(r_{\pi }+\gamma P_{\pi }{v}_{{\pi }_k}\right).$$

${\pi }_{k+1}$一定优于${\pi }_k$, 详细证明可以前往书中查看. 展开形式写作:

$$\begin{gathered} {\pi }_{k+1}(s)=\arg \underset{\pi }{\max }\sum _a\pi (a\mid s)\underset{q_{{\pi }_k}(s,a)}{\underbrace{\left(\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p\left(s^{\prime }\mid s,a\right)v_{{\pi }_k}\left(s^{\prime }\right)\right)}}, \\ s\in \mathcal{S}, \end{gathered}$$

之前我们介绍过, 最优策略一定是贪婪确定策略:

$${\pi }_{k+1}(a\mid s)=\{\begin{array}{ll}1,& a=a_k^{\ast }(s),\\ 0,& a\ne a_k^{\ast }(s).\end{array}$$

并且就是使得动作值$q_{{\pi }_k}$最大的动作$a=a_k^{\ast }(s)$:

$$a_k^{\ast }(s)=\arg \underset{a}{\max }{q}_{{\pi }_k}(s,a)$$

2.2.1.3 伪代码

完整的伪代码如图, 算法的策略迭代最终一定会收敛到最优解, 书中也给出了详细证明

$$v_{{\pi }_0}\le v_{{\pi }_1}\le v_{{\pi }_2}\le \cdots \le v_{{\pi }_k}\le \cdots \le v^{\ast }$$

2.2.2 例子1

仿真世界如图所示, 奖励设计如下:

• 抵达边界的奖励是-1: $r_{\text{boundary }}=-1$
• 抵达终点的奖励是1: $r_{\text{target }}=1$
• $\gamma =0.9$
• 其他行为奖励是0

我们将初始策略随机设置为图示: 动作都是往左.

2.2.2.1 k=0

(1) 策略计算(PE)

首先求解贝尔曼公式, 因为这个式子非常简单, 我们可以直接求出解析解:

$$\begin{array}{rl}& v_{{\pi }_0}\left(s_1\right)=-1+\gamma v_{{\pi }_0}\left(s_1\right)\Rightarrow v_{{\pi }_0}\left(s_1\right)=-10,\\ & v_{{\pi }_0}\left(s_2\right)=0+\gamma v_{{\pi }_0}\left(s_1\right)\Rightarrow v_{{\pi }_0}\left(s_2\right)=-9.\end{array}$$

不过一般我们会用迭代方法计算, 过程如下:

$$\begin{gathered} \begin{array}{rl}& \{\begin{array}{l}{v}_{{\pi }_0}^{(1)}\left(s_1\right)=-1+\gamma v_{{\pi }_0}^{(0)}\left(s_1\right)=-1,\\ v_{{\pi }_0}^{(1)}\left(s_2\right)=0+\gamma v_{{\pi }_0}^{(0)}\left(s_1\right)=0,\end{array}\\ & \{\begin{array}{l}{v}_{{\pi }_0}^{(2)}\left(s_1\right)=-1+\gamma v_{{\pi }_0}^{(1)}\left(s_1\right)=-1.9,\\ v_{{\pi }_0}^{(2)}\left(s_2\right)=0+\gamma v_{{\pi }_0}^{(1)}\left(s_1\right)=-0.9,\end{array}\\ & \{\begin{array}{l}{v}_{{\pi }_0}^{(3)}\left(s_1\right)=-1+\gamma v{v}_{{\pi }_0}^{(2)}\left(s_1\right)=-2.71,\\ v_{{\pi }_0}^{(3)}\left(s_2\right)=0+\gamma v_{{\pi }_0}^{(2)}\left(s_1\right)=-1.71,\end{array}\end{array} \\ ... \end{gathered}$$

最终的结果也是收敛到: $v_{{\pi }_0}\left(s_1\right)=-10,v_{{\pi }_0}\left(s_2\right)=-9$

(2) 策略提升(PI)

这里我们需要计算最优动作值, 因此需要计算出所有的动作值. 这个仿真场景, 完整的计算公式如下:

我们将$v_{{\pi }_0}\left(s_1\right)=-10,v_{{\pi }_0}\left(s_2\right)=-9$ 代入到式子中

可以看得出来, 最优动作是:

$${\pi }_1\left(a_r\mid s_1\right)=1,{\pi }_1\left(a_0\mid s_2\right)=1$$

因为这个例子非常简单, 显然可以看出来这已经是最优解了.

2.2.3 例子2

这里我们给出了一个更复杂的例子:

仿真世界如图所示, 奖励设计如下:

• 抵达禁止格或边界的奖励是-1: $r_{\text{boundary }}=r_{\text{forbidden }}=-1$
• 抵达终点的奖励是1: $r_{\text{target }}=1$
• $\gamma =0.9$
• 其他行为奖励是0

这里我们将初始策略全部初始化为原地不动, 然后开始迭代. 迭代的过程不再详细描述, 用图片展示每一轮迭代的结果

2.2.4 截断策略迭代

2.2.4.1 值迭代和策略迭代对比

之前我们介绍了这两种迭代方式, 这里我们归纳一下它们的迭代过程:

(1) 策略迭代

$${\pi }_0\stackrel{PE}{\to }{v}_{{\pi }_0}\stackrel{PI}{\to }{\pi }_1\stackrel{PE}{\to }{v}_{{\pi }_1}\stackrel{PI}{\to }{\pi }_2\stackrel{PE}{\to }{v}_{{\pi }_2}\stackrel{PI}{\to }\dots$$

• PE(已知${\pi }_k$, 求解$v_{{\pi }_k}$): $v_{{\pi }_k}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}.$
• PI(已知$v_{{\pi }_k}$, 求解${\pi }_{k+1}$): ${\pi }_{k+1}=\arg {\max }_{\pi }\left(r_{\pi }+\gamma P_{\pi }{v}_{{\pi }_k}\right).$

(2) 值迭代

$$v_0\stackrel{PU}{\to }{\pi }_1^{\prime }\stackrel{VU}{\to }{v}_1\stackrel{PU}{\to }{\pi }_2^{\prime }\stackrel{VU}{\to }{v}_2\stackrel{PU}{\to }\dots$$

• PU(已知$v_k$, 求解${\pi }_{k+1}$): ${\pi }_{k+1}=\arg {\max }_{\pi }\left(r_{\pi }+\gamma P_{\pi }{v}_k\right).$
• VU(已知${\pi }_{k+1}$, 求解$v_{k+1}$): $v_{k+1}=r_{{\pi }_{k+1}}+\gamma P_{{\pi }_{k+1}}{v}_k.$

2.2.4.2 截断策略迭代

这里通过一个表格展现他们的迭代的过程区别, 可以看到一个比较明显的区别是

值迭代的$v_{k+1}$是直接计算出来的; 但是策略迭代的$v_{{\pi }_k}$是通过一个小迭代算法计算的:

$$\begin{array}{rl}{v}_{{\pi }_1}^{(0)}& =v_0\\ v_{{\pi }_1}^{(1)}& =r_{{\pi }_1}+\gamma P_{{\pi }_1}{v}_{{\pi }_1}^{(0)}\\ v_{{\pi }_1}^{(2)}& =r_{{\pi }_1}+\gamma P_{{\pi }_1}{v}_{{\pi }_1}^{(1)}\\ ⋮& \\ \text{ 截断策略迭代 }\leftarrow {\bar{v}}_1⟵v_{{\pi }_1}^{(j)}& =r_{{\pi }_1}+\gamma P_{{\pi }_1}{v}_{{\pi }_1}^{(j-1)}\\ ⋮& \\ \text{ 策略迭代 }\leftarrow {\bar{v}}_1⟵v_{{\pi }_1}^{(\infty )}& =r_{{\pi }_1}+\gamma P_{{\pi }_1}{v}_{{\pi }_1}^{(\infty )}\end{array}$$

截断策略迭代就是在策略迭代的基础上, 限制计算$v_{{\pi }_k}$的最大迭代次数; 比如上式中, 迭代$j$次之后直接结束迭代.

因为限制了小迭代的次数, 求得的$v_{{\pi }_k}$可能并未完全收敛到$v_{{\pi }_k}^{\ast }$附近; 因此阶段策略迭代整体收敛速度, 是慢于策略迭代的, 优于值迭代, 如上图所示.

但是每一次迭代的计算时间, 显然是值迭代<截断策略迭代<策略迭代. 所以算法的整体效率是由两方面决定的.