利用动态规划求解马尔可夫决策过程 (Planning by Dynamic Programming)

强化学习系列

范叶亮 / 2020-06-13

分类: 机器学习, 强化学习 / 标签: 动态规划, Dynamic Programming, DP, 马尔可夫决策过程, Markov Decision Process, MDP, 策略评估, Policy Evaluation, 策略改进, Policy Improvement, 策略迭代, Policy Iteration, 价值迭代, Value Iteration, 异步动态规划, Asynchronous Dynamic Programming, 广义策略迭代, Generalised Policy Interation / 字数: 3552

本文为《强化学习系列》文章
本文内容主要参考自：
1.《强化学习》1
2. CS234: Reinforcement Learning 2
3. UCL Course on RL 3

动态规划（Dynamic Programming，DP）是一种用于解决具有如下两个特性问题的通用算法：

1. 优化问题可以分解为子问题。
2. 子问题出现多次并可以被缓存和复用。

马尔可夫决策过程正符合这两个特性：

1. 贝尔曼方程给定了迭代过程的分解。
2. 价值函数保存并复用了解决方案。

在强化学习中，DP 的核心思想是使用价值函数来结构化地组织对最优策略的搜索。一旦得到了满足贝尔曼最优方程的价值函数 v∗ 或 q∗，得到最优策略就容易了。对于任意 s∈S（状态集合），a∈A(s)（动作集合）和 s′∈S+（在分幕式任务下 S 加上一个终止状态），有：

(1)v∗(s)=maxaE[Rt+1+γv∗(St+1)|St=s,At=a]=maxa∑s′,rp(s′,r|s,a)[r+γv∗(s′)]

(2)q∗(s,a)=E[Rt+1+γmaxa′q∗(St+1,a′)|St=s,At=a]=∑s′,rp(s′,r|s,a)[r+γmaxa′]q∗(s′,a′)]

将贝尔曼方程转化成为近似逼近理想价值函数的递归更新公式，我们就得到了 DP 算法。

对于一个策略 π，如何计算其状态价值函数 vπ 被称为策略评估。对于任意 s∈S，有：

(3)vπ(s)≐Eπ[Gt|St=s]=Eπ[Rt+1+γGt+1|St=s]=Eπ[Rt+1+γvπ(St+1)|St=s]=∑aπ(a|s)∑s′,rp(s′,r|s,a)[r+γvπ(s′)]

其中 π(a|s) 表示在环境 s 中智能体在策略 π 下采取动作 a 的概率。只要 γ<1 或者任何状态在 π 下都能保证最后终止，则 vπ 唯一存在。

考虑一个近似的价值函数序列 v0,v1,⋯，从 S+ 映射到 R，初始的近似值 v0 可以任意选取（除了终止状态必须为 0 外）。下一轮迭代的近似可以使用 vπ 的贝尔曼方程进行更新，对于任意 s∈S 有：

(4)vk+1(s)≐Eπ[Rt+1+γvk(St+1)|St=s]=∑aπ(a|s)∑s′,rp(s′,r|s,a)[r+γvk(s′)]

显然，vk=vπ 是这个更新规则的一个不动点。在保证 vπ 存在的条件下，序列 {vk} 在 k→∞ 时将会收敛到 vπ，这个算法称作 迭代策略评估。

对于任意一个确定的策略 π，我们已经确定了它的价值函数 vπ。对于某个状态 s，我们想知道是否应该选择一个不同于给定的策略的动作 a≠π(s)。如果从状态 s 继续使用现有策略，则最后的结果就是 v(s)，但我们并不知道换成一个新策略后是得到更好的结果还是更坏的结果。一种解决方法是在状态 s 选择动作 a 后，继续遵循现有的策略 π，则这种方法的价值为：

(5)qπ(s,a)≐E[Rt+1+γvπ(St+1)|St=s,At=a]=∑s′,rp(s′,r|s,a)[r+γvπ(s′)]

一个关键的准则就是这个值是大于还是小于 vπ(s)。如果这个值更大，则说明在状态 s 选择动作 a，然后继续使用策略 π 会比使用始终使用策略 π 更优。

上述情况是策略改进定理的一个特例，一般来说，如果 π 和 π′ 是任意两个确定的策略，对于任意 s∈S：

(6)qπ(s,π′(s))≥vπ(s)

则称策略 π′ 相比于 π 一样好或更好。也就是说，对于任意状态 s∈S，这样肯定能得到一样或更好的期望回报：

(7)vπ′(s)≥vπ(s)

延伸到所有状态和所有可能的动作，即在每个状态下根据 qπ(s,a) 选择一个最优的，换言之，考虑一个新的贪心策略 π′，满足：

(8)π′(s)≐arg⁡maxaqπ(s,a)=arg⁡maxaE[Rt+1+γvπ(St+1)|St=s,At=a]=arg⁡maxa∑s′,rp(s′,r|s,a)[r+γvπ(s′)]

这样构造出的贪心策略满足策略改进定理的条件，所以它和原策略相比一样好或更好。这种根据原策略的价值函数执行贪心算法，来构造一个更好策略的过程称之为策略改进。如果新的贪心策略 π′ 和原策略 π 一样好而不是更好，则有 vπ=vπ′，对任意 s∈S：

(9)vπ′(s)=maxaE[Rt+1+γvπ′(St+1)|St=s,At=a]=maxa∑s′,rp(s′,r|s,a)[r+γvπ′(s′)]

这同贝尔曼方程完全相同，因此 vπ 一定与 v∗ 相同，π 与 π′ 均必须为最优策略。因此，在除了原策略即为最优策略的情况下，策略改进一定会给出一个更优的结果。

一个策略 π 根据 vπ 产生了一个更好的策略 π′，进而我们可以通过计算 vπ′ 来得到一个更优的策略 π″。这样一个链式的方法可以得到一个不断改进的策略和价值函数序列：

(10)π0⟶Evπ0⟶Iπ1⟶Evπ1⟶Iπ2⟶E⋯⟶Iπ∗⟶Ev∗

其中 ⟶E 表示策略评估，⟶I 表示策略改进。每一个策略都能保证同前一个一样或者更优，由于一个有限 MDP 必然只有有限种策略，所以在有限次的迭代后，这种方法一定收敛到一个最优的策略与最优价值函数。这种寻找最优策略的方法叫做策略迭代。整个策略迭代算法如下：

\begin{algorithm}
\caption{迭代策略算法}
\begin{algorithmic}
\FUNCTION{PolicyIteration}{}
\STATE \COMMENT{初始化}
\FOR{$s \in \mathcal{S}$}
  \STATE 初始化 $V \left(s\right) \in \mathbb{R}$
  \STATE 初始化 $\pi \left(s\right) \in \mathcal{A} \left(s\right)$
\ENDFOR
\WHILE{true}
  \STATE \COMMENT{策略评估}
  \REPEAT
    \STATE $\Delta \gets 0$
    \FOR{$s \in \mathcal{S}$}
      \STATE $v \gets V \left(s\right)$
      \STATE $V \left(s\right) \gets \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, \pi \left(s\right)\right)\left[r+\gamma V\left(s^{\prime}\right)\right]$
      \STATE $\Delta \gets \max\left(\Delta, \left|v - V \left(s\right)\right|\right)$
    \ENDFOR
  \UNTIL{$\Delta < \theta$}
  \STATE \COMMENT{策略改进}
  \STATE policy-stable $\gets$ true
  \FOR{$s \in \mathcal{S}$}
    \STATE $\pi' \left(s\right) \gets \pi \left(s\right)$
    \STATE $\pi \left(s\right) \gets \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma V\left(s^{\prime}\right)\right]$
    \IF{$\pi' \left(s\right) \neq \pi \left(s\right)$}
      \STATE policy-stable $\gets$ flase
    \ENDIF
  \ENDFOR
  \IF{policy-stable $=$ true}
    \BREAK
  \ENDIF
\ENDWHILE
\RETURN $V, \pi$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

以杰克租车（Jack’s Car）问题为例：杰克在两地运营租车公司，每租出一辆车获得 10 元收益，为了保证每个地点有车可用，杰克需要夜间在两地之间移动车辆，每辆车的移动代价为 2 元。假设每个地点租车和还车的数量符合泊松分布 λnn!e−λ，其中 λ 为期望值，租车的 λ 在两地分别为 3 和 4，还车的 λ 在两地分别为 3 和 2。假设任何一个地点不超过 20 辆车，每天最多移动 5 辆车，折扣率 γ=0.9，将问题描述为一个持续的有限 MPD，时刻按天计算，状态为每天结束时每个地点的车辆数，动作则为夜间在两个地点之间移动的车辆数。策略从不移动任何车辆开始，整个策略迭代过程如下图所示：

上例代码实现请参见这里。

策略迭代算法的一个缺点是每一次迭代都涉及了策略评估，这是一个需要多次遍历状态集合的迭代过程。如果策略评估是迭代进行的，那么收敛到 vπ 理论上在极限处才成立，实际中不必等到其完全收敛，可以提前截断策略评估过程。有多种方式可以截断策略迭代中的策略评估步骤，并且不影响其收敛，一种重要的特殊情况是在一次遍历后即刻停止策略评估，该算法称为价值迭代。可以将此表示为结合了策略改进与阶段策略评估的简单更新公式，对任意 s∈S：

(11)vk+1(s)≐maxaE[Rt+1+γvk(St+1)|St=s,At=a]=maxa∑s′,rp(s′,r|s,a)[r+γvk(s′)]

可以证明，对任意 v0，在 v∗ 存在的条件下，序列 {vk} 都可以收敛到 v∗。整个价值迭代算法如下：

\begin{algorithm}
\caption{价值迭代算法}
\begin{algorithmic}
\FUNCTION{ValueIteration}{}
\STATE \COMMENT{初始化}
\FOR{$s \in \mathcal{S}^{+}$}
  \STATE 初始化 $V \left(s\right)$，其中 $V \left(\text{终止状态}\right) = 0$
\ENDFOR
\STATE \COMMENT{价值迭代}
\REPEAT
  \STATE $\Delta \gets 0$
  \FOR{$s \in \mathcal{S}$}
    \STATE $v \gets V \left(s\right)$
    \STATE $V \left(s\right) \gets\sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma V\left(s^{\prime}\right)\right]$
    \STATE $\Delta \gets \max\left(\Delta, \left|v - V \left(s\right)\right|\right)$
  \ENDFOR
\UNTIL{$\Delta < \theta$}
\STATE 输出一个确定的策略 $\pi \approx \pi_*$ 使得 $\pi(s)=\arg \max _{a} \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma V\left(s^{\prime}\right)\right]$
\RETURN $V, \pi$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

以赌徒问题（Gambler’s Problem）为例：一个赌徒下注猜一系列抛硬币实验的结果，如果正面朝上则获得这一次下注的钱，如果背面朝上则失去这一次下注的钱，游戏在达到目标收益 100 元或全部输光时结束。每抛一次硬币，赌徒必须从他的赌资中选取一个整数来下注，这个问题可以表示为一个非折扣的分幕式有限 MDP。状态为赌徒的赌资 s∈{1,2,⋯,99}，动作为赌徒下注的金额 a∈{0,1,⋯,min(s,100−s)}，收益在一般情况下为 0，只有在赌徒达到获利 100 元的终止状态时为 1。

令 ph 为抛硬币正面朝上的概率，如果 ph 已知，那么整个问题可以由价值迭代或其他类似算法解决。下图为当 ph=0.4 时，价值迭代连续遍历得到的价值函数和最后的策略。

上例代码实现请参见这里。

异步动态规划

之前讨论的 DP 方法的一个主要缺点是它们涉及对 MDP 的整个状态集的操作，如果状态集很大，即使单次遍历也会十分昂贵。异步动态规划算法是一类就地迭代的 DP 算法，其不以系统遍历状态集的形式来组织算法。这些算法使用任意可用的状态值，以任意顺序来更新状态值，在某些状态的值更新一次之前，另一些状态的值可能已经更新了好几次。然而为了正确收敛，异步算法必须要不断地更新所有状态的值：在某个计算节点后，它不能忽略任何一个状态。

广义策略迭代

策略迭代包含两个同时进行的相互作用的流程，一个使得价值函数与当前策略一致（策略评估），另一个根据当前价值函数贪心地更新策略（策略改进）。在策略迭代中，这两个流程交替进行，每个流程都在另一个开始前完成。然而这也不是必须的，在异步方法中，评估和改进流程则以更细的粒度交替进行。我们利用广义策略迭代（GPI）一词来指代策略评估和策略改进相互作用的一般思路，与这两个流程的力度和其他细节无关。

几乎所有的强化学习方法都可以被描述为 GPI，几乎所有方法都包含明确定义的策略和价值函数。策略总是基于特定的价值函数进行改进，价值函数也始终会向对应特定策略的真实价值函数收敛。

GPI 的评估和改进流程可以视为两个约束或目标之间的相互作用的流程。每个流程都把价值函数或策略推向其中的一条线，该线代表了对于两个目标中的某一个目标的解决方案，如下图所示：

← 贝叶斯优化 (Bayesian Optimization) 无模型策略预测和控制 - 蒙特卡洛方法 (Model-Free Policy Prediction and Control - Monte-Carlo Learning) →