Dynamic Programming

动态规划方法（Dynamic Programming）

在智能体已知或能够学习到环境模型（状态转移概率 $\mathcal{P}$、奖励函数 $\mathcal{R}$）时可以采取动态规划算法进行求解。

策略迭代

策略评估

在有限期规划（$t \in [0,\ \mathrm{T}]$）中，贝尔曼期望方程实质上是一个动态规划转移方程，其中动态规划状态为每个规划时间步上的价值函数 $v^{(t)}(s)$ 和 $q^{(t)}(s,\ a)$，初始状态即 $\mathrm{T}$ 时刻的价值函数：

$q^{(\mathrm{T})}(s,\ a) = \mathcal{R}(s,\ a) \qquad v^{(\mathrm{T})}(s) = \sum_{a} q^{(\mathrm{T})}(s,\ a) \pi^{(\mathrm{T})}(a \mid s)$

其中 $\pi^{(t)}$ 为 $t$ 时间步上的马尔可夫随机策略，进而通过前向递推即可得到每个时刻的状态价值函数：

$q^{(t)}(s,\ a) = \mathcal{R}(s,\ a) + \gamma \sum_{s'} v^{(t + 1)}(s') p(s' \mid s,\ a) \qquad v^{(t)}(s) = \sum_{a} q^{(t)}(s,\ a) \pi^{(t)}(a \mid s)$

由于贝尔曼期望算子 $\mathscr{L}_{\pi} : \mathcal{V} \mapsto \mathcal{V}$ 是度量空间 $\langle \mathcal{V},\ \mathcal{L}_{\infty} \rangle$ 上的压缩映射：

$\begin{aligned} \Big\| \mathscr{L}_{\pi}(v_{1}) - \mathscr{L}_{\pi}(v_{2}) \Big\|_{\infty} &= \gamma \left\| \sum_{s'} \Big( v_{1}(s') - v_{2}(s') \Big) p_{\pi}(s' \mid s) \right\|_{\infty} = \gamma \max_{s} \left| \sum_{s'} \Big( v_{1}(s') - v_{2}(s') \Big) p_{\pi}(s' \mid s) \right| \\[7mm] &= \gamma \left| \sum_{s'} \Big( v_{1}(s') - v_{2}(s') \Big) p_{\pi}(s' \mid s^{\star}) \right| \le \gamma \sum_{s'} \Big| v_{1}(s') - v_{2}(s') \Big| p_{\pi}(s' \mid s^{\star}) \\[7mm] &\le \gamma \max_{s'} \Big| v_{1}(s') - v_{2}(s') \Big| = \gamma \Big\| v_{1} - v_{2} \Big\|_{\infty} \end{aligned}$

因此通过转移方程反复迭代后 $v(s)$ 会收敛到算子 $\mathscr{L}_{\pi}$ 的不动点，即贝尔曼期望方程 $v = \mathscr{L}_{\pi} (v)$ 的解 $v_{\pi}$。

策略提升

贝尔曼期望方程的解实质上是对策略 $\pi$ 的评估，为了提升策略的状态价值，可以对策略进行单步提升：

$\pi^{+} \in \argmax_{\delta \in \mathcal{D}^{\mathrm{A}}} \mathscr{L}_{\delta} (v_{\pi}) = \argmax_{\delta \in \mathcal{D}^{\mathrm{A}}} \sum_{a} q_{\pi}(s,\ a) \delta(a \mid s) = \argmax_{\delta \in \mathcal{D}^{\mathrm{A}}} \left\{ \mathcal{R}_{\delta} (s) + \gamma \sum_{s'} v_{\pi}(s') p_{\delta}(s' \mid s,\ a) \right\}$

单步提升可以直接利用贪心的方法得到一个确定性的策略 $\pi^{+} \in \mathcal{D}$

$\pi^{+}(s) \in \argmax_{a} q_{\pi}(s,\ a)$

单步提升后的策略 $\pi^{+}$ 满足

$\mathcal{R}_{\pi^{+}} + \gamma \mathcal{P}_{\pi_{+}} v_{\pi} = \mathscr{L}_{\pi^{+}}(v_{\pi}) = \max_{\delta \in \mathcal{D}^{\mathrm{A}}} \mathscr{L}_{\delta}(v_{\pi}) = \mathscr{L}(v_{\pi}) \ge \mathscr{L}_{\pi}(v_{\pi}) = v_{\pi}$

因此

$\underset{\mathscr{L}_{\pi^{+}}(v_{\pi^{+}}) = v_{\pi^{+}}}{\underbrace{\mathcal{R}_{\pi^{+}} + \gamma \mathcal{P}_{\pi^{+}} v_{\pi^{+}}}} + \gamma \mathcal{P}_{\pi^{+}} v_{\pi} - \gamma \mathcal{P}_{\pi^{+}} v_{\pi^{+}} \ge v_{\pi}\ \Rightarrow\ (\boldsymbol{I} - \gamma \mathcal{P}_{\pi^{+}}) v_{\pi^{+}} \ge (\boldsymbol{I} - \gamma \mathcal{P}_{\pi^{+}}) v_{\pi}$

由于 $(\boldsymbol{I} - \gamma \mathcal{P}_{\pi})^{-1} = \lim_{n \to \infty} \sum_{k = 0}^{n} \gamma^{k} \mathcal{P}_{\pi}^{k}$，当 $u \ge v$ 时，经过 $(\boldsymbol{I} - \gamma \mathcal{P}_{\pi})^{-1}$ 变换后仍然可以保持偏序关系：

$(\boldsymbol{I} - \gamma \mathcal{P}_{\pi})^{-1} u = \lim_{n \to \infty} \sum_{k = 0}^{n} \gamma^{k} \mathcal{P}_{\pi}^{k} u \ge \lim_{n \to \infty} \sum_{k = 0}^{n} \gamma^{k} \mathcal{P}_{\pi}^{k} v = (\boldsymbol{I} - \gamma \mathcal{P}_{\pi})^{-1} v$

在经过单步策略提升后 $v_{\pi^{+}} \ge v_{\pi}$。由于贝尔曼最优方程 $v = \mathscr{L}(v)$ 的解存在且唯一，进而可得：

$\mathscr{L}_{\pi^{+}}(v_{\pi}) = \mathscr{L}(v_{\pi}) = v_{\pi}\ \Rightarrow\ v_{\pi} = v^{\star},\ \pi = \pi^{\star}$

价值迭代

策略迭代算法的一次迭代包含策略评估和策略提升，而价值迭代则直接利用贝尔曼最优方程算子 $\mathscr{L}$ 的压缩映射性质迭代得到最优状态价值函数 $v^{\star}(s)$，同时在有限期规划中也可以看做是动态规划的转移方程：

$v^{(t)}(s) = \mathscr{L}(v^{(t + 1)}) = \max_{a} q^{(t)}(s,\ a) = \max_{a} \left\{ \mathcal{R}(s,\ a) + \gamma \sum_{s'} v^{(t + 1)}(s') p(s' \mid s,\ a) \right\}$

其中初始状态为 $q^{(\mathrm{T})}(s,\ a) = \mathcal{R}(s,\ a)$，通过不断向前迭代即可得到每个时间步的最优动作价值函数 $q^{\star}(s,\ a)$，通过最优动作价值函数可以恢复出每个时间步的最优确定性策略 $\pi^{(t)}(s) \in \argmax_{a} q^{(t)}(s,\ a)$。