4. Dynamic Programming

4.0 Preface

DP的思想也可以用在具有连续状态和动作的问题上，但是只在某些特殊情况下才存在精确解。一种常见的近似解法是，将连续的状态和动作量化为离散集合，然后再使用有限状态下的DP算法。

在RL中，DP的核心思想是使用价值函数来结构化地组织对最优策略的搜索。

4.1 Policy Evaluation (Prediction)

在PE的过程中，使用$v$ or $q$，对于一个Greedy policy来说，从概念上和数学公式上来说，并没有本质区别，也就是说，直接将公式中的$v$更换为$q$，也是正确的。

在编程实现的过程中，可以采用两种不同的更新方式：

双数组
1. 存储旧的价值函数$v_k(s)$
2. 存储新的价值函数$v_{k + 1}(s)$
in-place

每次用新的价值函数，替换旧的价值函数。in-place算法一旦获得了新数据就可以马上使用，比双数组的传统更新算法相比，收敛速度更快。

在讨论DP算法时，一般使用in-place

4.2 Policy improvement

如何证明，PI后的$\pi^\prime \ge \pi$？即$v_{\pi^\prime}(s) \ge v_{\pi}(s)$

对于greedy policy，$q_\pi(s, \pi^\prime(s)) = v_{\pi^\prime}(s)$

$\begin{aligned} v_\pi(s) & \le q_\pi(s, \pi^\prime(s)) \\ & = \mathbb{E}[R_{t + 1} + \gamma v_\pi(S_{t + 1}) \mid S_t = s, A_t = \pi^\prime(s)] \\ & = \mathbb{E}_{\pi^\prime}[R_{t + 1} + \gamma v_\pi(S_{t + 1}) \mid S_t = s] \\ & \le \mathbb{E}_{\pi^\prime}[R_{t + 1} + \gamma q_\pi(S_{t + 1}, \pi^\prime(S_{t + 1})) \mid S_t = s] \\ & = \mathbb{E}_{\pi^\prime}[R_{t + 1} + \gamma \mathbb{E}[R_{t + 2} + \gamma v_\pi(S_{t + 2}) \mid S_{t + 1}, A_{t + 1} = \pi^\prime(S_{t + 1})] \mid S_t = s] \\ & = \mathbb{E}_{\pi^\prime}[R_{t + 1} +\gamma R_{t + 2} + \gamma^2 v_{\pi}(S_{t + 2}) \mid S_t = s] \\ & = \mathbb{E}_{\pi^\prime}[R_{t + 1} +\gamma R_{t + 2} + \gamma^2 R_{t + 3} + \gamma^3 v_{\pi}(S_{t + 3)} \mid S_t = s] \\ & \vdots \\ & \le \mathbb{E}_{\pi^\prime}[R_{t + 1} +\gamma R_{t + 2} + \gamma^2 R_{t + 3} + \gamma^3 R_{t + 4} + \dots \mid S_t = s] \\ & = v_{\pi^\prime}(s) \end{aligned}$

4.3 Policy iteration

4.4 Value iteration

4.5 Asynchronous Dynamic Programming

DP的主要缺点：设计对整个状态集的操作，效率比较低
Asunchronous DP（异步DP）的方法是：in-place iterative（就地迭代）

使用任意可用的状态值，按照任意顺序来更新状态值。在某些状态的值更新一次之前，另一些状态的值可能已经更新了好几次。

但是为了能够正确收敛，异步算法必须不断更新所有状态的值，在某个计算节点之后，不能忽略任何一个状态。

可以选择一些特定状态来更新，从而加快算法的速度。例如，在智能体访问状态的时候更新这个状态，能够聚焦到部分与智能体最相关的状态。

4.6 Generalized Policy Iteration

GPI：指代让策略评估和策略改进相互作用的一般思路

$\pi_* \stackrel{\text{Greedy}}{\underset{\text{Consistent}}{\rightleftharpoons}} v_*$

价值函数只有与当前策略consistent时才稳定
策略只有在对当前价值函数Greedy时才稳定

可以将GPI的evaluate && improvement看成是竞争与合作，尽管每一个流程都改变了另一个流程，但是他们的相互作用总体上可以一起找到一个联合的解，最终两条世界线会收束到最优的价值函数与策略，而最优价值函数和策略，不会被任何一个流程改变。

在某些情况下，GPI可以被证明为收敛，比如DP；但是在其它情况下，并不能证明收敛。

4.7 Efficiency of Dynamic Programming

DP算法的实际效率很高，在忽略部分技术细节、最坏情况下，DP找到最优策略的时间，与状态和动作的数量呈多项式级关系
DP算法的效率指数级，由于任何直接在策略空间中搜索的方法
虽然DP算法容易陷入维度灾难，但是相比于直接搜索、线性规划，DP反而更适合解决大规模状态空间的问题
面对巨大的状态空间，可以考虑异步DP / GPI的变体，在较好的初始价值函数 or 策略时，效率依旧不错

4.8 Summary

DP算法中，所有的方法都根据对后续状态价值的估计，来更新当前状态，==称为：自举法==