[ 强化学习  ]

强化学习基础 3:Dynamic Programming

强化学习中的动态规划 (Dynamic Programming, DP) 算法在假设环境为“完美的 MDP 模型”的前提下,计算最优策略。这里“完美的 MDP 模型”的意思是我们提前知道环境的状态转移函数(动态) $p(s’,r\mid s, a)$。由于 DP 的假设比较严格,并且计算量太大,所以实际应用场景不多。但它提供了理解强化学习中其他算法的重要思想。事实上,其他的强化学习方法都可以看作是努力完成与 DP 同样的效果,但提供更高的效率。

DP 的核心思想是利用价值函数来帮助最优策略的搜索(这也是强化学习中的核心思想之一)。本文将介绍如何使用 DP 来计算价值函数,并且进而获得最优策略。

一、策略评估(预测)

对任意一个策略 $\pi$,如何得到这个这个策略下的价值函数?这个过程被称为策略评估 (Policy Evaluation),也被称为一个预测问题 (Prediction Problem)。DP 算法实际上是把 Bellman 方程变成赋值表达式,即迭代更新式,通过迭代来近似所需的价值函数。前一篇文章中有 Bellman 方程

而 DP 按照下式产生一个序列 ${v_k}$:

很明显,$v_k=v_\pi​$ 是上式的一个不动点,因此有理论可以证明 ${v_k}​$ 在 $k\to\infty​$ 时收敛到 $v_\pi​$(当然 $v_\pi​$ 要存在)。这个算法被称为迭代策略评估 (iterative policy evaluation)

这种更新被称为 expected update,因为每次更新是基于所有的下一状态的期望,而不是对下一状态的一个采样

算法实现上,可以用两个数组,一个存储 $v_k$,一个存储 $v_{k+1}​$,这种风格的算法被称为 Jacobi 风格; 但也可以只用一个数组,对数组进行原址更新 (update in place),直接用新的值覆盖旧的值即可,这种被称为 Gauss-Seidel 风格。实际上仅用一个数组的收敛速度更快,因此我们的也采用这种 in-place 的算法。

\begin{algorithm}
\caption{Iterative Policy Evaluation}
\begin{algorithmic}
\INPUT $\pi$, the policy to be evaluated\\
\INPUT $\theta>0$, a small threshold determining accuracy of estimation
\OUTPUT $V\approx v_\pi$

\PROCEDURE{PolicyEvaluation}{$\pi, \theta$}
\STATE Initialize $V(s)$, for all $s\in\mathcal{S}^+$, arbitrarily except that $V(terminal)=0$
\REPEAT
	\STATE $\Delta \gets 0$
	\FORALL{$s\in\mathcal{S}$}
		\STATE $v\gets V(s)$
		\STATE $V(s)\gets \sum_a\pi(a\mid s)\sum_{s',r}p(s',r\mid a, s)\Big[r+\gamma V(s')\Big]$
		\STATE $\Delta\gets {\rm max}(\Delta, |v-V(s)|)$
	\ENDFOR
\UNTIL{$\Delta<\theta$}
\RETURN $V$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}	

注:伪代码中的大写 $V$ 代表数组,里面存放我们对 $v$ 的估计值。同理,在之后的文章也会出现 $Q$,代表我们对 $q$ 的估计值。

在 DP 中,每个状态的价值的估计值是建立在后继状态的估计值上的,这种“基于估计来估计”的方法也叫做 bootstrapping。这是 DP 的一个特点,后面会讲到的蒙特卡洛方法就不是 bootstrapping 的。

二、策略改进

我们之所以要计算一个策略对应的价值函数,是因为它能帮助我们改进当前的策略

从定义,我们可以有这样一个直观的理解:状态价值函数 $v_\pi(s)$ 给出了在当前状态 $s$ 并在之后状态都按照策略 $\pi$ 来行动的价值(期望的总回报);动作价值函数 $q_\pi(s,a)$ 给出了在当前状态 $s$ 选择动作 $a$ 并在之后状态都按照策略 $\pi$ 来行动的价值。如果在某个状态 $s$,发现这一步如果按策略 $\pi’$ 行动,获得的价值会更大,即 $q_\pi(s,\pi’(s))> v_\pi(s)$,说明策略 $\pi’$ 在这个状态下优于策略 $\pi$。

那如果在每个状态都发生这种情况,那策略 $\pi’$ 应该是在整个状态空间都优于策略 $\pi$ 的。这就引出下面的策略改进定理。

策略改进定理 (Policy Improvement Theorem)

定理(策略改进定理) 若 $\pi$ 和 $\pi’$ 是任意两个确定性策略,并且对任意 $s\in\mathcal{S}$ 有

则说明策略 $\pi’$ 一定等于或优于策略 $\pi$,即

证明只需展开递推即可,这里略去。

通过这个定理,可以贪婪地构造一种比原策略 $\pi$ 获得更好的策略 $\pi’$:

这种贪婪的算法被称为策略改进 (policy improvement)

容易看出(从最优策略的定义),最优策略 $\pi_\ast$ 是上面这个更新式的一个不动点,也就是说如果目前还没有达到最优策略,这个算法将给出一个更好的策略

三、策略迭代

从公式 $2.1$ 可以看到,获得一个更好策略的前提是拥有原始策略的状态价值函数 $v_\pi$。好在本文第一部分策略评估已经给出了获得任意策略价值函数的算法 (iterative policy evaluation),所以我们可以通过下面这个序列过程迭代地改进最初的策略($E$ 代表策略评估,$I$ 代表策略改进):

最后迭代到 $\pi_\ast$,到达不动点。这个过程被称为策略迭代算法 (Policy Iteration)。因为一个有限 MDPs 的策略是有限的,所以此算法在有限的迭代次数后一定能到达最优策略。

\begin{algorithm}
\caption{Policy Iteration}
\begin{algorithmic}
\OUTPUT $V\approx v_\ast$
\OUTPUT $\pi\approx\pi_\ast$
\STATE Initialize $\pi(s)\in\mathcal{A}(s)$, for all $s\in\mathcal{S}$
\REPEAT
	\STATE $V\gets$ PolicyEvaluation($\pi,\theta$)
	\STATE policy-stable $\gets$ \TRUE
	\FORALL{$s\in\mathcal{S}$}
		\STATE old-action $\gets\pi(s)$
		\STATE $\pi(s)\gets \argmax_a\sum_{s',r}p(s',r\mid s,a)\left[r+V(s')\right]$
		\IF{old-action $\ne\pi(s)$}
			\STATE policy-stable $\gets$ \FALSE
		\ENDIF
	\ENDFOR
\UNTIL{policy-stable}
\RETURN $V,\pi$
\end{algorithmic}
\end{algorithm}	

四、值迭代

上面的策略迭代算法虽然有效,但效率比较低:在每次迭代都要调用 PolicyEvaluation 子过程,并等待 PolicyEvaluation 的收敛。

值迭代 (value iteration)算法更加直接:把 Bellman 最优方程变成一个更新式,最后迭代得到的就是最优价值函数,然后利用最优价值函数直接得到最优策略。

\begin{algorithm}
\caption{Value Iteration}
\begin{algorithmic}
\INPUT $\theta>0$, a small threshold determining accuracy of estimation
\OUTPUT $\pi\approx \pi_\ast$

\STATE Initialize $V(s)$, for all $s\in\mathcal{S}^+$, arbitrarily except that $V(terminal)=0$
\REPEAT
	\STATE $\Delta \gets 0$
	\FORALL{$s\in\mathcal{S}$}
		\STATE $v\gets V(s)$
		\STATE $V(s)\gets \max_a\pi(a\mid s)\sum_{s',r}p(s',r\mid a, s)\Big[r+\gamma V(s')\Big]$
		\STATE $\Delta\gets {\rm max}(\Delta, |v-V(s)|)$
	\ENDFOR
\UNTIL{$\Delta<\theta$}
\RETURN $\pi(s)=\argmax_a\sum_{s',r}p(s',r\mid a, s)\Big[r+\gamma V(s')\Big]$
\end{algorithmic}
\end{algorithm}	

五、异步 DP

之前讨论的 DP 算法的一个严重的问题是,它们的每一次迭代(扫描)都需要对 MDP 的整个状态空间进行计算。当问题的状态空间很大时,这也许一次扫描就要上千年的计算时间。

异步 DP 算法 (Asynchronous DP) 提出的解决方案是:每次迭代不一定要走完所有状态空间,也许仅仅更新其中的一部分状态就好,因为这同样能使我们进一步向最优策略这个目标迈进。而这样做的好处时,每次迭代可以选择那些最重要的状态来更新,避免去更新意义不大的状态,这提高了算法的效率。当然从理论上说,如果要保证算法在整个状态空间收敛,每个状态都至少要被更新一次。但我们减少了更新的频率(扫描的次数)。

六、GPI

在 policy iteration 算法中,两个过程——policy evalutionpolicy improvement 交替进行。这种方法可以被推广为通用策略迭代 (Generalized Polity Interation),简称 GPI。在 GPI 中,当前策略的价值函数通过 evaluation 过程产生,而基于当前价值函数的贪婪策略通过 improvement 过程产生,这两个过程不断地为对方产生动态的目标,并向目标迈进,最终收敛到最优点。这个过程如下面两个示意图所示:

几乎所有强化学习算法都能用 GPI 来描述,我们将会在后面的文章中用 GPI 来描述和研究相应的算法。

参考