前言

 首先我们将强化学习算法分为基于模型的和不基于模型的，本期博客将会首先介绍基于模型的强化学习算法，基于模型的强化学习算法，主要包括动态规划策略求解算法，以及Dyna-Q，本次先从介绍动态规划入手。

前期回顾

强化学习:基础知识篇(包含Gym库的简单实践)——手把手教你入门强化学习（一）
强化学习:Markov决策过程(MDP)——手把手教你入门强化学习(二)
强化学习:实践理解Markov决策过程(MDP)——手把手教你入门强化学习(三)

一、基本概念

强化学习算法分类

在这里，我们从强化学习算法是否基于MDP(马尔可夫决策过程)模型进行划分，也就是第一期所讲的P(s ′∣s,a)(转移概率)、R(s,a)（奖励）,看算法是否显式利用 P 和 R 进行规划。
1 基于模型的强化学习算法
定义：通过显式估计 P (s'|s,a) 和 R (s,a)构建环境模型，再利用模型进行规划(Planning)。
典型算法：1）动态规划（DP） 2） 蒙特卡洛规划（MCP） 3 )Dyna 系列（Dyna-Q）
2 不基于模型的强化学习算法
定义：不显式建模 P/R，直接通过与环境的实时交互采样，学习价值函数（如 Q (s,a)）或策略（π(a|s)）。
典型算法：1）Q-learning 2) 策略梯度（PG）3) DQN 4) PPO
本期我们就先从基于模型的强化学习算法——动态规划入手，来入门。

动态规划

动态规划是一种建模和解题的思路。在这种思路的指导下，原始的问题（大的、复杂的问题）会被分解成多个可解的且结果可保存的子问题。一旦所有的子问题获解，原始的问题就获解了。

基于策略π的状态价值函数

在上期内容中，我们就提过，不懂的友友可以看一下状态价值函数，这里我就罗列一下它的计算公式(贝尔曼的期望方程公式):

此外，一个状态的价值也可以用该状态下所有行为价值来表达,因为行为是连接马尔可夫决策过程中状态转换的桥:

基于策略π的行为价值函数

这个也是一样，我列一下它的计算公式(贝尔曼的期望方程公式)：

类似地，一个行为的价值可以用该行为所能到达的后续状态的价值来表达：

二、动态规划求解

状态估值

因为v(s)可以用q(s,a)表示，q(s,a)也可以用v(s)表示，所以，我们尝试用q(s,a)来代换v(s)，写出表达式

反过来，把q(s,a)表示成v(s)，会得到什么呢？

以下图举例，在状态s下，动作空间a中有a1和a2两个动作，在做a1和a2这两个动作的时候，会分别转移到s′1、s′2及s′3、s′4。那么，根据状态估值的定义，v(s)应该等于什么呢？应该是某种加权平均值。

举个例子：就是这4个状态各自的概率和这4个状态各自估值的积的平均值。打个比方，我有10000元，用其中的10% 的投资了一个收益率为5% 的理财产品，用其中的40% 投资了一个收益率为10% 的理财产品，分别用其中的25% 投资了收益率为8% 和6% 的理财产品，现在要评价我的投资盈利金额是多少。计算这个组合策略的收益：

这个投资组合的收益率为8%。

我们可以看到，整个公式的计算过程是一个二重嵌套的循环：遍历这棵树上的每一个分支，不管是1个动作，还是100个动作，不管是有100个不同的状态s′，还是有10000个不同的状态s′，总而言之，相当于一个加权平均的过程。平均计算在这个公式里面没有直接体现，因为它已经包含在概率计算里面了。这样一来，求解vπ(s)就依赖于 π(a|s)、$R{s}^{a}$、$P{ss'}^{a}$ 和v(s′)的准确值了。
我们很快得出结论：
1 如果每一层都能够通过这样的方式逐级估算，这棵树不管有多高，都可以一层一层向上估算，直到把顶层的任何一个节点的vπ(s)估值都计算准确——大不了多花些时间，方法肯定是可行的。
2 毫无疑问，这个方法严重依赖Model（至少应该是一个满足MDP的对象）​。如果π(a|s)、$R{s}^{a}$、$P{ss'}^{a}$和v(s′)里面有任何一个不知道，就不能直接使用这个方法，就没有办法进行计算。所以，这种方法的局限性很大，对条件的要求也比较苛刻。(这也就是我们所说的需要基于MDP模型的方法)

策略优化

使用动态规划（或者说值迭代）的方法，怎么做优化呢？方法也是非常简单的，有下面3个步骤。
1 以一种策略π开始在环境中做动作，这个时候，就会得到相应的$v{π}(s)$和$q{π}(s,a)$。
2 因为在时序上属于树遍历问题，所以，要想准确估算树上部的状态节点的值，就要先估算树下部的状态节点的值。树下部的状态节点的值容易估算吗？节点位置越靠下，邻近时间终点的位置越近，计算的代价就越小（节点位置越靠上，就表示距离开始的时间越长，在计算估值的时候要参考的时间就更长一些）​。从下向上，逐层估算vπ(s)，用类似递归的方式向上传递。举个例子，我到底树的最底层的终点状态s''，这时候v(s'')肯定等于0，再从下往上通过公式逐层递推，
表达式写出来是这样的：

$$R_{s}^a + \gamma \sum_{s'\in S}P_{ss'}^av_{\gamma -old}(s')$$表示，一个由动作a引发的“现世报”的奖励值加上它达到各个状态的概率和各个状态的估值——仍然可以通过本章开头提到的那个投资组合的例子来理解。
$$max_{a\in A}$$
的意思是，在众多不同的a里，只取那个能保证后面的外层括号里的表达式的值最大的a。也就是说，如果有一个动作“力压群雄”​，比其他的动作都要好，那么，上一层的s的估值，就可以考虑只做这一个动作，并以这个前提进行迭代更新。道理很容易理解：如果知道有一个动作比其他动作都要好，为什么还要做其他动作？这就是这个表达式的基本含义。
3 持续以这个逻辑进行更新，vπ(s)就会不断地变化。直到最后，vπ(s)基本上不再变化了，就停止更新。此时的策略，就是每次都选择能够导致状态迁移到最有价值状态的动作a。

动态规划中两个核心性质：最优子问题（最优子结构）和重叠子问题,它们在这里体现的非常经典。
1 最优子结构
定义：问题的最优解包含子问题的最优解。
我们是从树的最下面，自下往上开始计算，每一步都是算的max。值迭代通过贝尔曼方程，强制要求每个状态的最优值必须基于后续状态的最优值，直接体现了最优子结构。

2 重叠子问题
定义：不同的父问题共享相同的子问题，导致子问题被重复计算。
同一子问题（如 s' 的 v 值）要被多个父状态（如 s1→s'，s2→s'）反复使用。

这也正体现了动态规划的本质「多阶段决策优化」。

总结

 本期详细介绍了动态规划求解最优状态价值函数。下期会介绍蒙特卡罗法，希望大家点点关注！！！如果想要更深入强化学习的内容，关注我，下期更精彩，感兴趣的友友也可以关注我的csdn账号。
 https://blog.csdn.net/qq_53769632?spm=1000.2115.3001.5343