参考链接：https://blog.csdn.net/liweibin1994/article/details/79093453

一、动态规划求Q和V

我们的目标是要得到最优策略，使得累积回报函数最大。因此我们的强化学习的优化方法有两种：

• 基于策略的优化（类似于上一篇chap2中的Q*(s,a)的优化）
• 基于累积回报函数的优化（类似于上一篇chap2中V*(s)的优化）

1.1 策略评估(迭代法)

问题：评估一个给定的策略π。

bellman方程：
$V^{\pi }(s)=E^{\pi }(R_{t+1}+\gamma V^{\pi }(s_{t+1})|S_t=s)$
$Q^{\pi }(s,a)=E^{\pi }[R_{t+1}+\gamma Q^{\pi }(S_t+1,A_{t+1})|S_t=s,A_t=a]$
最优值迭代公式：注意上下两者比较
$Q^{\ast }(s,a)=R_s^a+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{\max }_{a\in A}{Q}^{\ast }(s^{\prime },a^{\prime })$，
$V^{\ast }(s)={\max }_{a\in A}(R_S^a+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^{a}V\ast (s^{\prime }))$
解决方法：利用bellman方程反向迭代。

具体做法：每次迭代过程中，用所有的状态s的第k次迭代得到的的$v_k(s\prime )$的期望值(而不是最大值)来计算第k+1次的$v_{k+1}(s)$的值。经过这种方法的反复迭代，最终是可以收敛到最优的$v^{\ast }(s)$。迭代的公式如下
$v_{k+1}(s)={\sum }_{a\in A}\pi (a|s)(R_s^a+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_k(s^{\prime }))$
$=R_s^a+{\sum }_{a\in A}\pi (a|s){\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_k(s^{\prime }))$

Vπ(s)=∑a∈Aπ(a∣s){Rss′a+γ∑s′∈SVπ(s′)}V^{\pi}(s)=\sum_{a\in A}\pi(a|s)\{R^a_{ss'}+\gamma\sum_{s'\in S} V^{\pi}(s')\}Vπ(s)=∑a∈A​π(a∣s){Rss′a​+γ∑s′∈S​Vπ(s′)}
$Q^{\pi }(s,a)=R_S^a+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{\sum }_{a^{\prime }\in S}\pi (a|s)Q^{\pi }(s^{\prime },a^{\prime })$
$V^{\pi }(s)={\sum }_{a\in A}\pi (a|s)Q^{\pi }(s,a)$

例子：

• 即时奖励：上图是一个九宫格，左上角和右下角是终点，它们的reward是0，其他的状态，reward都是-1。
• 状态空间：除了灰色两个格子，其他都是非终点状态
• 动作空间：在每个状态下，都有四种动作可以执行，分别是上下左右(东西南北)。
• 转移概率：任何想要离开格子的动作将保持其状态不变，也就是原地不动。其他时候都是直接移动到下一个状态。所以状态转移概率是确定性的。
• 折扣因子：γ=1γ=1
• 当前策略：在任何状态下，agent都采取随机策略，也就是它的动作是随机选择的，即
  $\pi (e|\ast )=\pi (w|\ast )=\pi (s|\ast )=\pi (n|\ast )=0.25$

• 问题：评估在这个九宫格里给定的策略。也就是说，在策略给定的情况下(这里是随机策略)，求解在该策略下所有状态的v(s)值。
  
  注意：上图中，每个格子的数字是对应状态的v值(这里的V值感觉不像是状态值函数，而是状态-动作值函数)。图中只显示了迭代三次的结果，还需要一直迭代下去。大概在153次迭代之后，V值就收敛了。
  

思考：注意，在我们迭代的过程中，我们并没有对策略进行修改，一直都是保持随机策略。

显然，我们不可能采用chap2中的假设法，我们使用3.1中的迭代法直到收敛。对一个确定的策略(随机策略)，我们根据(逆用bellman等式)得来的迭代公式可以得到状态值V和状态-动作值Q。在迭代到V值收敛后，我们可以对策略进行改进(Policy Improvement)。我们可以使用贪婪算法来进行策略改进，即：

${\pi }^{\ast }=\underset{a\in A}{\mathrm{argmax}}{Q}^{\pi }(s,a)$
等价于
${\pi }^{\ast }(a|s)=\{\begin{array}{ll}1,& ifa=\arg ma{x}_{a\in A}{Q}^{\ast }(s,a)\\ 0,& else\end{array}$

注意到：$Q^{\ast }(s,a)={\max }_{\pi }{Q}^{\pi }(s,a)$,$V^{\ast }(s)={\max }_{\pi }{V}^{\pi }(s)$
含义为：旧策略$\pi \in \Pi$，新的策略为${\pi }^{\ast }$。对当前状态s,使用不同策略$\pi$下，动作$a\in A$, 使得$Q(s,a)$最大值的那个$a$，在新策略下(当前状态)的概率为1，其他动作在新策略(当前状态)下的概率为0。
(由于所有旧策略的)值函数已经收敛了(V值已经确定了)，所以此时用贪婪算法构建的新策略是当前最大的值函数，所以是最优策略。
上面讲的方法的前提是策略π在一开始就没有改变，只是通过不断地迭代计算v(s)的值，直到最后v(s)收敛才停止迭代。事实上，这样需要迭代很多次才会收敛，可能我们会想，我们可不可以每迭代计算一次v(s)的值，就改进一下我们的策略，而不是得到v(s)收敛了才来改进策略呢？所以接下来我们就来讲策略迭代，它就是这么干的

1.2 Policy Iteration(策略迭代)

适用情况：对于一个状态空间和动作空间有限的MDP。
前面讲的九宫格的例子就是为了给策略迭代做铺垫。
策略迭代分为两部分，第一个部分是策略评估，第二部分是策略改进。

所谓策略评估就是在当前的策略下计算v(s)v(s)的值。策略改进则是利用策略评估得到的v(s)来进行策略改进。然后继续重复策略评估，策略改进，直到最后收敛到最优策略。算法的伪代码如下：

代码解释：
原来的迭代公式：
$v_{k+1}(s)={\sum }_{a\in A}\pi (a|s)(R_s^a+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_k(s^{\prime })),\gamma =1$
等价于：
$v_{k+1}(s)={\sum }_{a\in A}\pi (a|s){\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a(R_{s{s}^{\prime }}^a+v_k(s^{\prime }))$

现在的迭代公式：
$V_{k+1}(s)={\sum }_{a\in A}\pi (a|s){\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a(\frac{1}{t}{R}_{s{s}^{\prime }}^a+\frac{t-1}{t}{V}_k(s^{\prime }))$
为什么这么修改策略，我不不明白。

1.3 Value Iteration（值迭代）

优化原则：

• 所以如果我们求解出了v∗(s′)我们就可以利用下面的公式求解出v∗(s)。
  $V^{\ast }(s)={\max }_{a\in A}(R_S^a+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^{a}V\ast (s^{\prime }))$
  根据以上的bellman等式得到迭代公式：
  $V_{k+1}(s)={\max }_{a\in A}(R_s^a+\gamma {\sum }_{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_k(s^{\prime }))$
  例子：
  比如这个问题：
  

• 状态：终点是左上角写着g的灰色格
• 报酬：除了g点的reward=0，其他的状态reward=-1
• 策略：策略可以忽略掉
• 状态转移概率:$P_{s{s}^{\prime }}^a$

迭代过程：

1. 初始值V0(x)=0,x∈{g,A，B，C,...,O}V_0(x)=0,x\in \{g,A，B，C,...,O\}V0​(x)=0,x∈{g,A，B，C,...,O}
2. 第一次迭代：根据迭代公式， 除了g以外，所有的状态的即时报酬为-1，因此，V1(x)=−1,x∈{A,B,..,O}V_1(x)=-1,x\in \{A,B,..,O\}V1​(x)=−1,x∈{A,B,..,O}
3. 第2次迭代：$V_2(s)=\underset{a}{\max }[r(s,a)+\gamma {\sum }_{s^{\prime }\in S}p(s^{\prime }|a,s)V_1(s^{\prime })]$
   除了A和D分别向左、向上运动到达g外，其他状态的任意动作到达的结果都在格子里，且任意动作的报酬为V2(x)=−2,x∈{B,c,E,F,...,O}V_2(x)=-2,x\in \{B,c,E,F,...,O\}V2​(x)=−2,x∈{B,c,E,F,...,O}.以A点为例，向左运动为$-1+v_1(g)=-1$,其他方向则为$-1+(-1)=-2$,这时候根据V值最大的原则，选择$V_2(A)=-1$,同理，$V_2(D)=-1$
4. 第3次迭代：$V_3(s)=\underset{a}{\max }[r(s,a)+\gamma {\sum }_{s^{\prime }\in S}p(s^{\prime }|a,s)V_2(s^{\prime })]$
   …

下图就是迭代过程中每个格子的V值变化：