---

前言

关于动态规划法的详细介绍：动态规划法

---

一、动态规划法简单认识

1.基本概念

我们在这里关注的是作为一种算法设计技术，作为一种使用多阶段决策过程最优的通用方法。
它是应用数学中用于解决某类最优化问题的重要工具。
假设问题是由交叠的子问题所构成，我们就能够用动态规划技术来解决它。一般来说，这种子问题出如今对给定问题求解的递推关系中，这个递推关系包括了同样问题的更小子问题的解。动态规划法建议，与其对交叠子问题一次重新的求解，不如把每一个较小子问题仅仅求解一次并把结果记录在表中（动态规划也是空间换时间的）。这样就能够从表中得到原始问题的解。

2.适用情况

能采用动态规划求解的问题的一般要具有3个性质：

1. 最优化原理：假设问题的最优解所包括的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
2. 无后效性：即某阶段状态一旦确定。就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响曾经的状态。仅仅与当前状态有关；（该性质与马尔科夫性非常相似，这也是为什么动态规划会用在强化学习中）
3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到（该性质并非动态规划适用的必要条件，可是假设没有这条性质。动态规划算法同其它算法相比就不具备优势）。

3.求解步骤

实际应用中能够按下面几个简化的步骤进行设计：

1. 分析最优解的性质。并刻画其结构特征。
2. 递归的定义最优解。
3. 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。
4. 依据计算最优值时得到的信息，构造问题的最优解。

4.典型案例

在这里列举一个三角数塔的问题，从顶点出发，能够向左走或向右走，要求从顶点开始走到最底层，请找出一条路径，使路径之和最大。

正确路径为13-8-26-15-24（和为86）。
我淦，好难写。。。
我觉得大部分人一看到这个问题会想到从起点开始，一步步尝试，计算总和，然后对比不同的路线，但是这么操作非常地麻烦，会遇到重复计算的部分。
用动态规划法来求解：
拆分问题：从顶点开始的最优路径，就是从第二行两个点开始的最优路径取最大，按照这个思路逐次推广到最底层。问题就被逐渐拆分了。
由底向上：最底层的问题无法继续拆分，从最底层开始，比如比较底层12和7的大小，就能知道倒数第二行6的位置对应的后续最优路径（$6\to 12$）。
算法流程：
1.初始化层数N,$Q_N=0$
2. 比较第n层相邻两个数大小，将最大值与（n-1）层对应的数相加并记录为$Q_{n-1}$
迭代公式：$Q_{n-1}^i=Max(n_i+Q_n^i,n_{i+1}+Q_n^{i+1})$

该问题具体解法可以参看博客：动态规划法
动态规划算法讲解

---

二、值函数

MDP序列：$s_0,a_0,r_1\to s_1,a_1,r_2\to s_2,a_2,r_3\to s_3,a_3,r_4\dots s_t,a_t,r_{t+1}\to \dots s_{T-1},a_{T-1},r_T\to s_T(终止状态)$

1.累计折扣奖励

$G_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{r+3}+\cdots +{\gamma }^{T-t-1}{r}_T$

2.状态值函数

从当前状态开始的累计折扣奖励的期望,与策略有关
$V_{\pi }(s)=E[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{r+3}+\dots |s_t=s]$
对求期望的理解：后续的马尔科夫链有多条（多种可能），我们用期望表示，以状态$s$开始的一条MDP序列可以计算一个$V_{\pi }$，多条MDP序列求平均就是估计。
观察改公式的形式，可改写成如下形式：
$V_{\pi }(s)=E[r_{t+1}+\gamma V_{\pi }(s_{t+1})|s_t=s]=E[r_{t+1}|s_t=s]+\gamma E[V_{\pi }(s_{t+1})|s_t=s]$
状态值函数的理解：
$E[r_{t+1}|s_t=s]$：当$t$时刻状态为$s$时，采取动作$a^{\prime }$未知，但$a^{\prime }\backsim \pi (a^{\prime }|s)$，$t+1$时刻的奖励可以用期望$E[r_{t+1}]$表示,更进一步：
$E[r_{t+1}|s_t=s]=\sum [\pi (a^{\prime }|s_t)\ast Rsa(s_t,a^{\prime })]$
$E[V_{\pi }(s_{t+1})|s_t=s]$：状态由$s$转移为$s_{t+1}=s^{\prime }$未知，但$s^{\prime }\sim Psa(s^{\prime })$,所以$t+1$时刻的状态值函数也用期望表示，类似的：
$E[V_{\pi }(s_{t+1})|s_t=s]=\sum (\pi (a^{\prime }|s_t)\ast \sum (Psa(s_{t+1}=s^{\prime })\ast V_{\pi }[s^{\prime }]\left)\right)$

整理状态值函数公式(Bellman方程)：
$V_{\pi }(s)=\sum (\pi (a^{\prime }|s)\ast (Rsa(s,a^{\prime })+\gamma \sum (Ps{a}^{\prime }(s^{\prime })\ast V_{\pi }(s^{\prime })\left)\right))$
由该公式可以看出，只要我们已知状态转移概率$Psa$以及奖励函数$Rsa$，即已知环境模型，那么通过该公式就可以评价策略函数$\pi$的好坏。

3.动作值函数

从当前状态开始（不包括当前状态），采取动作$a$，所得到的后续累计折扣奖励的期望。$Q_{\pi }:S\ast A\to R$
$Q_{\pi }(s,a)=E[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{r+3}+\dots |s_t=s,a_t=a]$，其中$r_{t+1}$是常数
易看出动作值函数与状态值函数之间的关系：
$Q_{\pi }(s,a)=E[r_{t+1}+\gamma V_{\pi }(s_{t+1})|s_t=s,a_t=a]$
还是用概率计算期望：
$Q_{\pi }(s,a)=r_{t+1}+\gamma \sum Psa(s^{\prime })\ast V_{\pi }(s^{\prime })=Rsa(s,a)+\gamma \sum Psa(s^{\prime })\ast V_{\pi }(s^{\prime })$

4.状态值函数与动作值函数的关系

$Q_{\pi }(s,a)=Rsa(s,a)+\gamma \sum Psa(s^{\prime })\ast V_{\pi }(s^{\prime })$
$V_{\pi }(s)=\sum \pi (a|s)\ast Q_{\pi }(s,a)$

5.贝尔曼方程（动态规划法核心）

$\{\begin{array}{l}{Q}_{\pi }(s,a)=Rsa(s,a)+\gamma \sum Psa(s^{\prime })\ast V_{\pi }(s^{\prime })\\ V_{\pi }(s)=\sum \pi (a|s)\ast Q_{\pi }(s,a)\end{array}$
$\Rightarrow V_{\pi }(s)=\sum (\pi (a^{\prime }|s)\ast (Rsa(s,a^{\prime })+\gamma \sum (Ps{a}^{\prime }(s^{\prime })\ast V_{\pi }(s^{\prime })\left)\right))$
$\Rightarrow Q_{\pi }(s,a)=Rsa(s,a)+\gamma (\sum Psa(s^{\prime })\ast (\sum \pi (a^{\prime }|s)\ast Q_{\pi }(s^{\prime },a^{\prime })))$

---

三、策略评估

给定一个策略$\pi$，求在这一策略下的值函数

1.基于状态值函数评估策略

$V_{\pi }(s)=\sum (\pi (a^{\prime }|s)\ast (Rsa(s,a^{\prime })+\gamma \sum (Ps{a}^{\prime }(s^{\prime })\ast V_{\pi }(s^{\prime })\left)\right))$

2.基于动作值函数评估策略

$Q_{\pi }(s,a)=Rsa(s,a)+\gamma (\sum Psa(s^{\prime })\ast (\sum \pi (a^{\prime }|s)\ast Q_{\pi }(s^{\prime },a^{\prime })))$

---

四、策略改进（策略求解）

已知状态值函数或动作值函数，求在这一值函数下的最优策略，也叫做贪心策略或者确定性策略

1.基于状态值函数的策略改进

$\pi (s|a)=\{\begin{array}{ll}1& \text{if }a=argmax(R(s,a)+\gamma \sum Psa(s^{\prime })\ast V_{\pi }(s^{\prime }))\\ 0& \text{else }\end{array}$

2.基于动作值函数的策略改进

$\pi (s|a)=\{\begin{array}{ll}1& \text{if }a=argmax(Q_{\pi }(s,a))\\ 0& \text{else }\end{array}$
这两种改进策略在我看来实质是一样的，都是要去找最大的$Q(s,a)$,然后将对应的$\pi (s|a)=1$（贪心策略）

---

在已知环境模型的情况下，策略迭代法就是策略评估$\to$策略改进$\to$策略评估$\to$策略改进$\dots$

五、动态规划法与强化学习的联系

为了评估策略的好坏，我们定义了动作值函数$Q_{\pi }(s|a)$与状态值函数$V_{\pi }(s)$，在贪心策略下，我们需要求解$Max(Q_{\pi }(s|a))$
值函数记录了单个小问题的解，Bellman方程将序列求最优问题拆分成递归问题。
参照博客：动态规划与强化学习
1.动态规划和前面的有什么联系？

答：强化学习前面已经说过，是一种序列决策问题，一开始不清楚环境的工作方式，不知道执行什么动作是对的，什么是错的，然后就只好不断的在环境试错，进而发现一个好的策略。同样，规划(planning)也属于序列决策问题，不同的是规划的环境是已知的，比如游戏的规则已知等，那么agent就不需要靠与环境的交互来获取下一个状态了，而是知道自己执行某个动作后的状态是什么，然后再优化自己的策略。这两者是不一样的。

动态规划可以将一个复杂问题分为一系列简单的子问题，一旦解决了这些简单的子问题，再将这些子问题的解结合起来就变成复杂问题的解了，并且同时将它们的解保存起来，如果下次遇到相同的子问题，就不用重新计算了。动态规划本质上就是一种环境模型已知的规划方法(planning)。

2.动态规划到底是干什么的？

动态规划的“动态”，指的是某个问题由序列化状态组成，状态的转换是step-by-step进行的。因此，可以step-by-step解决问题。“规划”就是优化子问题。上一节我们提到，通过Bellman方程MDP被递归的切分成子问题，同时它有值函数，保存了每一个子问题的解，因此它能通过动态规划来求解。针对MDP，切分成的子问题就是在每个状态下应该选择的action是什么，MDP的子问题是以一种递归的方式存在，这一时刻的子问题取决于上一时刻的子问题选择了哪个action。

动态规划简单说可以分为两部分，一是预测(prediction)，也就是已知MDP的状态、动作、奖励、转移概率、折扣因子和策略，求出每一个状态下的值函数，也就是每个状态下能获得的reward是多少。第二就是控制，什么意思呢，就是在前面的状态、动作等等都已知，但策略未知的情况下，计算出最优的值函数，并且借此计算出最优的策略。动态规划的目的就是完成上面的两件事。适用于动态规划的问题，一般状态转移矩阵都是已知的，简单说就是环境模型已知了，这个时候就可以看做planning问题了。

总结

定义值函数来求解累计折扣奖励，并进一步写出值函数的迭代公式 （Bellman方程），在环境已知的条件下（Model Base），通过求解一组Bellman方程（策略评估）就可以评价当前策略好坏，在通过动作值函数按照贪心策略更新策略，当策略不再改变就代表求出了最优策略。该过程也叫做策略迭代法，依靠模型。

---

经典强化学习算法后续：
蒙特卡罗法不依赖模型，大致原理是通过采集大量MDP序列后，抽样求解状态转移概率（打比方，抛硬币1000次，记录正反出现的次数，我们就可以计算出正面出现的概率为0.5），同样的我们从大量的MDP序列中求出$Psa$。后面更新策略的方法同策略迭代类似。该方法也是需要再大量采集数据后才能进行更新策略。
时序差分法可以做到在线学习，即实时更新。大致原理：随机初始化Q表，每执行一步动作通过以前记录的Q表+当前动作奖励来更新Q表，最后的策略是通过最大Q值来反推（或者说动作选择基于Q表，选取最大Q值对应的动作）。