本文次要论述：强化学习基本概念、值函数和状态动作值函数的关系、根本求解问题以及 DP 求解办法。
1. 基本概念
几个重要的概念：
1）第一个是环境的状态 S，t 时刻环境的状态 $S_t$ 是它的环境状态集中某一个状态。
2）第二个是个体的动作 A，t 时刻个体采取的动作 $A_t$ 是它的动作集中某一个动作。
3)第三个是环境的处分 R，t 时刻个体在状态 $S_t$ 采取的动作 $A_t$ 对应的处分 $R_{t+1}$ 会在 t + 1 时刻失去。
4)第四个是个体的策略(policy)π, 它代表个体采取动作的根据，即个体会根据策略 π 来抉择动作。最常见的策略表达方式是一个条件概率分布 π(a|s), 即在状态 s 时采取动作 a 的概率。即 $π(a|s)=P(A_t=a|S_t=s)$. 此时概率大的动作被个体抉择的概率较高。
5)第五个是个体在策略 π 和状态 s 时，采取行动后的价值（value），个别用 $v_π(s)$ 示意。这个价值个别是一个冀望函数。尽管以后动作会给一个延时处分 $R_{t+1}$, 然而光看这个延时处分是不行的，因为以后的延时处分高，不代表到了 t +1,t+2,… 时刻的后续处分也高。比方下象棋，咱们能够某个动作能够吃掉对方的车，这个延时处分是很高，然而接着前面咱们输棋了。此时吃车的动作处分值高然而价值并不高。因而，价值要综合思考以后的延时处分和后续的延时处分 。价值函数 $v_π(s)$ 个别能够示意为：
$v_π(s)=E_π(R_{t+1}+γR_{t+2}+γ^2R_{t+3}+……|S_t=s)$。
不同的算法会有对应的一些价值函数变种，但思路雷同。同时有，
$v_π(s)=E_π(R_{t+1}+γv_π(S_{t+1})|S_t=s)$，
这个递推式子咱们个别将它叫做 贝尔曼方程。
6)$γ$ 是第六个模型因素，即处分衰减因子，在 [0，1] 之间。如果为 0，则是贪心法，即价值只由以后延时处分决定，如果是 1，则所有的后续状态处分和以后处分厚此薄彼。大多数时候，咱们会取一个 0 到 1 之间的数字，即以后延时处分的权重比后续处分的权重大。
7）第七个是环境的状态转化模型，能够了解为一个概率状态机，它能够示意为一个概率模型，即在状态 s 下采取动作 a, 转到下一个状态 s′的概率，示意为 $????^????_{????????′}$。
更具体的，如果依照实在的环境转化过程看，转化到下一个状态 s′的概率既与上一个状态 s 无关，还与上上个状态，以及上上上个状态无关。这一会导致咱们的环境转化模型非常复杂，简单到难以建模。因而咱们须要对强化学习的环境 / 状态转化模型进行简化。简化的办法就是假如状态转化的马尔科夫性，也就是 假如转化到下一个状态 s′的概率仅与上一个状态 s 无关，与之前的状态无关 。
状态转移概率用公式示意为：$????????????????′=E(????_{????+1}=????′|????_????=????,????_????=????)$
这种只思考上一个状态的决策过程称为 马尔科夫决策过程（MDP）。
8）第八个是摸索率 ϵ，这个比率次要用在强化学习训练迭代过程中，因为咱们个别会抉择使以后轮迭代价值最大的动作，然而这会导致一些较好的但咱们没有执行过的动作被错过。因而咱们在训练抉择最优动作时，会有肯定的概 ϵ 不抉择使以后轮迭代价值最大的动作，而抉择其余的动作。
9）第九个是状态 - 动作价值函数 $????_π(????,????)$。同样的办法，咱们能够失去动作价值函数 $????_π(????,????)$ 的 贝尔曼方程：
$????_π(????,????)$
$ = E_π(G_t|S_t=s,A_t=a) $
$= E_π(R_{t+1}+γR_{t+2}+γ^2R_{t+3}+……|S_t=s,A_t=a)$
$= E_π(R_{t+1}+γq_π(S_{t+1},A_{t+1})|S_t=s,A_t=a)$
10）第十个是 return，$G_t$。t 时刻之后将来执行一组 action 后可能取得的 reward，即 t +1，t+2…所有时刻的 reward 之和。
$ G_t=R_{t+1}+γR_{t+2}+ +γ^2R_{t+3}+……$
2. 值函数和状态动作值函数的关系
值函数和状态动作值函数存在肯定的转化关系:
$v_π(s)=∑_{a∈A}π(a|s)*q_π(s,a)$
也就是说，状态价值函数是所有动作价值函数基于策略 π 的冀望。艰深说就是某状态下所有状态动作价值乘以该动作呈现的概率，最初求和，就失去了对应的状态价值。
反过来，利用上贝尔曼方程，咱们也很容易从状态价值函数 $v_π(s)$ 示意动作价值函数 $q_π(s,a)$，即：$q_π(????,????)=????^a_s+γ∑_{s’∈S} P^a_{ss’} * v_π(s’)$
这两个转化过程也能够从下图中直观的看出：
联合下面两个式子，能够失去：
$v_{\pi}(s) = \sum\limits_{a \in A} \pi(a|s)(R_s^a + \gamma \sum\limits_{s’ \in S}P_{ss’}^av_{\pi}(s’))$
$q_{\pi}(s,a) = R_s^a + \gamma \sum\limits_{s’ \in S}P_{ss’}^a\sum\limits_{a’ \in A} \pi(a’|s’)q_{\pi}(s’,a’)$
3. 根本问题
强化学习的两个根本问题。
第一个问题是预测，即给定强化学习的 6 个因素：状态集 $S$, 动作集 $A$, 模型状态转化概率矩阵 $P$, 即时处分 $R$，衰减因子 $\gamma$, 给定策略 $\pi$，求解该策略的状态价值函数 $v(\pi)$;
第二个问题是管制，也就是求解最优的价值函数和策略。给定强化学习的 5 个因素：状态集 $S$, 动作集 $A$, 模型状态转化概率矩阵 $P$, 即时处分 $R$，衰减因子 $\gamma$, 求解该策略的状态价值函数 $v(\pi)\*$ 和最优策略 $\pi\*$。
4. 应用动静布局求解
动静布局并不是求解强化学习问题的最优办法，起因有两个：
1）经典的 DP 算法对 MDP 有完满假如，这在理论环境中通常是不存在的；
2）DP 计算过程耗时重大。
尽管如此，DP 是了解强化学习的根底，后续的强化学习算法都能够看作是：在没有高耗时、完满假如的前提下，对 DP 成果的迫近。
以下内容摘自《Reinforcement Learning:An Introduction》Chapter 4：
The term dynamic programming (DP) refers to a collection of algorithms that can be used to compute optimal policies given a perfect model of the environment as a Markov decision process (MDP). Classical DP algorithms are of limited utility in reinforcement learning both because of their assumption of a perfect model and because of their great computational expense, but they are still important theoretically. DP provides an essential foundation for the understanding of the methods presented in the rest of this book. In fact, all of these methods can be viewed as attempts to achieve much the same effect as DP, only with less computation and without assuming a perfect model of the environment.
4.1. 策略评估求解预测问题
首先，咱们来看如何应用动静布局来求解强化学习的预测问题，即 求解给定策略的状态价值函数的问题 。这个问题的求解过程咱们通常叫做 策略评估(Policy Evaluation)。
策略评估的 基本思路 是从任意一个状态价值函数开始，根据给定的策略，联合贝尔曼冀望方程、状态转移概率和处分同步迭代更新状态价值函数，直至其收敛，失去该策略下最终的状态价值函数。
假如咱们在第 k 轮迭代曾经计算出了所有的状态的状态价值，那么在第 k + 1 轮咱们能够利用第 k 轮计算出的状态价值计算出第 k + 1 轮的状态价值。这是通过贝尔曼方程来实现的。即：
$v_{k+1}(s) = \sum\limits_{a \in A} \pi(a|s)(R_s^a + \gamma \sum\limits_{s’ \in S}P_{ss’}^av_{k}(s’))$
因为策略 $\pi$ 是已知的，所以不须要再应用下标标注。咱们每一轮能够对计算失去的新的状态价值函数再次进行迭代，直至状态价值的值扭转很小(收敛)，那么咱们就得出了预测问题的解，即给定策略的状态价值函数 $v(\pi)$。
4.2. 管制问题
下面咱们讲了应用策略评估求解预测问题，当初咱们再来看如何应用动静布局求解强化学习的第二个问题管制问题（即，求解最优的价值函数和策略）。
4.2.1. 策略迭代求解管制问题
一种可行的办法就是依据咱们之前基于任意一个给定策略评估失去的状态价值来及时调整咱们的动作策略，这个办法咱们叫做 策略迭代(Policy Iteration)。
如果用一副图来示意策略迭代的过程的话，如下图：
在策略迭代过程中，咱们循环进行两局部工作，第一步是应用以后策略 $\pi∗$ 评估计算以后策略的最终状态价值 $v∗$，第二步是依据状态价值 $v∗$ 依据肯定的办法（比方贪心法，或者其余办法）更新策略 $\pi∗$，接着回到第一步，始终迭代上来，最终失去收敛的策略 $\pi∗$ 和状态价值 $v∗$。
对应贝尔曼方程迭代式：$v_{k+1}(s) = \sum\limits_{a \in A} \pi(a|s)(R_s^a + \gamma \sum\limits_{s’ \in S}P_{ss’}^av_{k}(s’))$
集体了解：策略 π 与价值 v 相辅相成迭代更新，这种迭代办法相似于 k 中心点聚类算法中心点与簇划分的迭代思路。
4.2.2. 价值迭代求解管制问题
和上一节相比，咱们没有等到状态价值收敛才调整策略，而是随着状态价值的迭代及时调整策略, 这样能够大大减少迭代次数。那么此时咱们的策略迭代优化为 价值迭代。即，每轮迭代先做策略评估，计算出价值 $v_k(s)$，而后基于肯定的办法（比方贪心法）更新以后策略 π。最初失去最优价值函数 $v∗$ 和最优策略 $\pi∗$。
此时咱们的状态价值的更新办法也和策略迭代不同。当初的贝尔曼方程迭代式子如下：
$v_{k+1}(s) = \max_{a \in A}(R_s^a + \gamma \sum\limits_{s’ \in S}P_{ss’}^av_{k}(s’))$
可见因为策略调整，咱们当初价值每次更新偏向于贪心法抉择的最优策略对应的后续状态价值，这样收敛更快。
集体了解：策略迭代和价值迭代的差异在于：在策略迭代中，策略更新与状态更新交替进行，策略更新能够采纳贪心法，也能够采纳其余办法；在价值迭代中，间接采纳贪心法，跳过策略迭代步骤，所以收敛更快（因为默认了策略采纳贪心法，找到最优价值后天然就会有最优策略）。
4.3. 异步动静布局
参考《Reinforcement Learning:An Introduction》4.5 大节：
所谓异步动静布局算法，每一次迭代并不对所有状态的价值进行更新，而是根据肯定的准则有选择性的更新局部状态的价值，这类算法有本人的一些独特劣势，当然也有一些额定的代价。
常见的异步动静布局算法有三种：
第一种是原位动静布局 (in-place dynamic programming)，此时咱们不会另外保留一份上一轮计算出的状态价值。而是 即时计算即时更新。这样能够缩小保留的状态价值的数量，节约内存。代价是收敛速度可能稍慢。
第二种是优先级动静布局 (prioritised sweeping)：该算法对每一个状态进行优先级分级，优先级越高的状态其状态价值优先失去更新。通常应用贝尔曼误差来评估状态的优先级，贝尔曼误差即新状态价值与前次计算失去的状态价值差的绝对值。这样能够放慢收敛速度，代价是须要保护一个优先级队列。
第三种是实时动静布局 (real-time dynamic programming)：实时动静布局间接 应用个体与环境交互产生的理论经验来更新状态价值，对于那些个体理论经验过的状态进行价值更新。这样个体常常拜访过的状态将失去较高频次的价值更新，而与个体关系不亲密、个体较少拜访到的状态其价值失去更新的机会就较少。收敛速度可能稍慢。
4.4. 动静布局求解的缺点
动静布局是咱们遇到的第一个零碎求解强化学习预测和管制问题的办法。它的算法思路比较简单，次要就是利用贝尔曼方程来迭代更新状态价值，用贪心法之类的办法迭代更新最优策略。
动静布局算法应用全宽度（full-width）的回溯机制来进行状态价值的更新，也就是说，无论是同步还是异步动静布局，在每一次回溯更新某一个状态的价值时，都要回溯到该状态的所有可能的后续状态，并利用贝尔曼方程更新该状态的价值。这种全宽度的价值更新形式对于状态数较少的强化学习问题还是比拟无效的，然而 当问题规模很大的时候，动静布局算法将会因贝尔曼维度劫难而无奈应用。因而咱们还须要寻找其余的针对简单问题的强化学习问题求解办法。
参考资料
1. 刘建平 Pinard 博客
2. 莫烦 博客
3.《Reinforcement Learning:An Introduction》