• 动态规划
  • 预测
    • 同步备份
    • 异步备份
  • 控制
    • 策略迭代
    • 值迭代
    • 策略迭代 vs 值迭代
  • 总结
  • 技巧

动态规划

动态表示的是一种问题有时间上的特性，问题一步一步的改变。

动态规划的基本思想是将一个大的问题分解成小的问题，再将小问题的答案结合起来得到最终结果。

动态规划用于解决具有以下两个性质的问题：

1. 具有最优化子结构：可以将问题分解成小问题，分别解决从而解决最终问题
2. 相同的子问题会多次出现，结果可以复用

马尔可夫决策过程（MDP）满足以上两个性质。

• 贝尔曼方程将问题递归的分解成子问题
• 价值函数存储和复用子问题的结论，从而获得最终价值函数

动态规划假定可以了解完整的环境信息，也就是假定它知道状态转移概率和奖励函数。也就是动态规划解决的是：如果我们知道状态转移概率和奖励函数，那么我们该如何找到状态价值函数和最优策略

动态规划的过程可以分为两部分：

1. 预测：评估，也就是根据已知策略获得价值函数的过程
   1. 输入：
      • MDP $<S, A, P, R, \gamma>$ 和策略 $\pi$
      • MRP $<S, P^{\pi}, R^{\pi}, \gamma>$
   2. 输出：
      • 价值函数$v_{\pi}$
2. 控制：根据当前的价值函数，找最优策略和最优价值函数的过程
   1. 输入：
      • MDP $<S, A, P, R, \gamma>$
   2. 输出：
      • 最优价值函数$v_{*}$
      • 最优策略 $\pi_*$

预测

简单来说，动态规划的预测就是迭代的使用贝尔曼期望备份公式（也就是利用q与v的相互转化公式获得v和下一时刻v的关系公式）。

同步备份

过程：

• 在第k + 1轮
• 对于每一个$s \in S$
• 利用$v_{k}(s')$ 更新获得$v_{k + 1}(s)$
• 其中$s'$ 是s的下一个状态，也就是采用前一轮迭代的v函数获得下一轮迭代的v函数

这里待证明收敛性

根据之前的贝尔曼公式得到的q和v的关联函数：

$$\begin{equation} \begin{aligned} v_{\pi}(s) &= \sum\limits_{a \in A}\pi(a|s)q_{\pi}(s, a)\\ q_{\pi}(s, a) &= R_{t + 1} + \gamma \sum\limits_{s' \in S} p_{ss'}^a v_{\pi}(s') \end{aligned} \end{equation}$$

得到，v和下一时刻v的关系：

$$\begin{equation} v_{\pi}(s) = \sum\limits_{a \in A} \pi(a|s)(R_{t + 1} + \gamma \sum\limits_{s' \in S}p_{ss'}^a v_{\pi}(s')) \end{equation}$$

异步备份

并不需要等到前一轮的所有状态更新完，才可以进行下一轮更新。

多线程时候，只需要选状态，更新即可，不用关注先后顺序。最终仍然可以收敛到最优函数。

控制

介绍了预测的方式后，我们将开始介绍两种控制的方法：策略迭代和值迭代。

策略迭代

策略迭代将要解决的问题分解成了子问题：也就是将寻找完整的最优策略的过程，分解为在当前状态下只寻找下一步的action的过程。

策略迭代的方法显式的将过程分成了两部分：预测和控制

预测部分对当前的策略进行评估，得到v函数。这部分在前面已经介绍了。

控制部分根据v函数对策略进行更新，采用greedy的方式，也就是选择当前状态下，最好的q函数对应的action，得到更好的策略。

$$\pi'(s) = \arg\max\limits_{a \in A} q_{\pi}(s, a)$$

对新的策略重新进行预测，新的v函数得到更好的策略。。。直到策略不再改变，模型收敛。

那么，这个过程是如何保证它能够起作用呢？换句话说，它是如何保证模型可以收敛呢？而且如何保证收敛的值就是最优值呢？

这就需要关注到控制部分采用的方法。策略迭代的控制部分，也就是策略的更新部分，采用了greedy的方式。也就是说，它获得的策略至少要比当前的策略要好。

也就是：

$$\begin{equation} \begin{aligned} q_{\pi}(s, \pi'(s)) = \max\limits_{a \in A}q_{\pi}(s, a) \ge q_{\pi}(s, \pi(s)) = v_{\pi}(s) \end{aligned} \end{equation}$$

$v_{\pi}(s)$ 的含义是：当前状态为s的情况下，完全follow $\pi$ 的策略会获得多大的return。

$q_{\pi}(s, a)$的含义是：当前状态为s的情况下，采取a的action后，完全follow $\pi$的策略会得到多大的return。

因此可以理解上式：它只关心一步的action，只要这一步的action后的return比之前大，那么就可以保证q函数比之前的好。

$$\begin{equation} \begin{aligned} v_{\pi}(s) & \le q_{\pi}(s, \pi'(s))\\ & = E_{\pi'}[R_{t + 1} + \gamma q_{\pi}(S_{t + 1}, \pi(S_{t + 1}))|S_t = s]\\ & \le E_{\pi'}[R_{t + 1} + \gamma q_{\pi}(S_{t + 1}, \pi'(S_{t + 1}))|S_t = s]\\ & \le E_{\pi'}[R_{t + 1} + \gamma R_{t + 2} + \gamma^2 q_{\pi}(S_{t + 2}, \pi'(S_{t + 2}))|S_t = s]\\ & ...\\ & \le E_{\pi'}[R_{t + 1} + \gamma q_{\pi'}(S_{t + 1}, \pi'(S_{t + 1}))|S_t = s]\\ &= E_{\pi'}[R_{t + 1} + \gamma v_{\pi'}(S_{t + 1})|S_t = s]\\ &= v_{\pi'}(s) \end{aligned} \end{equation}$$

因此，新的策略一定比之前的策略好。

其中，第二行的含义是：采取了一步的$\pi'$的策略(因此E的下角标是$\pi'$)，之后采用$\pi$的策略（因此使用$q(s, \pi(s))$），得到的均值。

这样，我们始终能保证，下一次得到的策略总是优于或者等于当前策略。当迭代停止了，则此时：

$$v_{\pi}(s) = \max\limits_{a\in A}q_{\pi}(s, a)$$

满足贝尔曼最优等式。因此$v_{\pi}(s) = v_*(s), \forall s \in S$

在理解了策略迭代的整个过程之后，我们开始考虑评估过程的计算是否需要很精确？

因为很多时候，并不需要非常很精确的计算，得到的当前最优策略就可以和精确的情况一致了。这样，多余的评估迭代浪费了资源，导致更新频率低，对于这一点一般有两种解决方案：

1. 设置超参$\varepsilon$, 如果两次的价值函数差值小于$\varepsilon$ 则停止更新。但是，很多时候这样也不够精简。
2. 设置超参k，指定评估的迭代轮数。

对于第二个方式，考虑一种极限情况：k = 1。在这种情况下，过程实际上就转换为值迭代。

值迭代

值迭代将要解决的问题分解成子问题：寻找最优的策略可以分解为先找到最优的第一步$A_*$, 和从$s'$开始的最优策略。

因此，如果我们知道了从$s'$开始的最优策略，那么完整的最优策略可以通过如下公式一步获得：

$$v_*(s) \leftarrow \max\limits_{a \in A}(R^a_s + \gamma \sum\limits_{s' \in S}P^a_{ss'}v_*(s'))$$

对于没有终止状态的情况，比如MDP中存在环。值迭代仍然可以进行，因为有$\gamma$的存在，可以让非常远的rewards足够小。

不同与策略迭代采用贝尔曼公式，值迭代采用贝尔曼最优公式。因为值迭代就是在找最优价值函数的过程。如果公式相等了，说明找到了最优策略了

另一种理解的方式就是，值迭代实际上在用一种隐式的方式学习策略：

一个完整的v函数对应了一个我们没有求解的策略。更新得到的v函数比之前的v函数更好，因此我们找到了一个比之前更好的策略。我们只是没有实际的求出来。

也就是说，策略迭代通过显式的策略求对应v函数，再更新策略。而值迭代直接通过价值函数的更新来隐式的更新策略。

划线的部分表述并不正确，因为值并不会一直变大。 而且并不是所有的v函数都能对应一个策略，它必须保证贝尔曼等式求解时的矩阵可逆。因此这种理解方式是错误的。

另一种理解方式是，值迭代只是特殊形式的策略迭代

可以将值迭代的价值函数更新看作两部分：

1. 策略更新：$R_s^a + \gamma \sum\limits_{s' \in S} P_{ss'}^{a'}v_*(s')$ 是当前的q函数，贪婪的方式获得策略，也就是s状态下最大的q函数对应的action作为策略。
2. 策略评估：只做一轮的策略评估，将得到的新策略根据贝尔曼公式迭代一轮。

这个过程等价于价值迭代的公式。因此它只是一个策略评估只迭代一轮的策略迭代，它用不是很准确的价值函数来更新策略。

有理论可以证明，这个过程可以仍然可以收敛于最优函数。

策略迭代 vs 值迭代

1. 寻找策略的方式
   1. 策略迭代显式的寻找策略：评估，更新策略，再评估，再更新策略。。。
   2. 值迭代隐式的寻找策略：迭代的寻找最优状态函数，再根据最优状态函数直接得到最优策略
2. 更新频率：
   1. 从另一个角度看待值迭代问题会发现：值迭代的一次迭代等价于策略迭代的一次评估+一次更新，隐式的提高了策略的更新频率。
3. 更新方式：
   1. 值迭代是从一个价值函数更新到另一个价值函数。
   2. 策略迭代是从一个价值函数转到新的显式的策略，再求解这个策略确切的价值函数再到新的显式的策略。。。。

总结

动态规划包括两部分：

1. 预测：迭代使用贝尔曼公式
2. 控制：
   1. 策略迭代：策略评估->策略更新->策略评估。。。，基于贝尔曼公式
   2. 价值迭代：价值函数->价值函数。。。,基于贝尔曼最优公式，也可以看作特殊的策略迭代

技巧

1. In-place: 可以不刻意区分v函数是旧的还是新的，直接覆盖，直接取用。
2. 更新的次序非常重要：因此可以向前计算一步，v的变化越大代表越重要
3. real-time：想要忽略到不太重要的状态的更新。可以让一个agent真正去执行，获得experience，只更新agent经历了的状态。