马尔科夫决策过程是对强化学习(RL)问题的数学描述。几乎所有的RL问题都能通过MDPs来描述：
注：虽然大部分DL问题都能转化为MDPs，但是以下所描述的MDPs是全观测的情况。
强化学习中的表述符号：
只要知道现在，将来和过去条件独立
定义：如果在t时刻的状态St满足如下等式，那么这个状态被称为马尔科夫状态，或者说该状态满足马尔科夫性。
例子：
有了马尔科夫状态之后
注：这里的相关指问题相关，可能有一些问题无关的信息没有在St中；马尔科夫性和状态的定义息息相关。
定义：状态转移概率是指从一个马尔科夫状态s跳转到后继状态s'的概率：
所有的状态组成行，所有的后继状态组成列，将得到状态转移矩阵：
其中，n表示状态的个数，由于P代表了整个状态转移的集合，所以用个花体。每行元素相加等于1。
我们也可以将状态转移概率写成函数的形式：
其中
一个马尔科夫过程（MP）是一个无记忆的随机过程，即一些马尔科夫状态的序列。
定义：马尔科夫过程可以由一个二元组定义<S, P>。
S表示了状态集合，P描述了状态转移矩阵
注，虽然我们有时候不知道P的具体值，但是通常我们假设P存在且稳定的。
当P不稳定时，不稳定环境，在线学习，快速学习。
举个栗子：
一个学生每天需要学习三个科目，然后通过测试。不过也有可能只学完两个科目之后直接睡觉，一旦挂科有可能需要重新学习某些科目。用椭圆表示普通状态，每一条线上的数字表示从一个状态跳转到另一个状态。方块表示终止状态。终止状态有两种：1是时间终止，2是状态终止。
由于马尔科夫郭晨够可以用图中的方块和线条组成，所以可以称马尔科夫过程为马尔科夫链（MDPs chain）。
片段定义：强化学习中，从初始状态S1到终止状态的序列过程，被称为一个片段（episode），S1, S2，... ，ST
还是来看上面的例子：
假设初始状态是“科目一”，从这个马尔科夫链中，我们可能采样到如下的片段：
分别用 s1 ∼ s7 代表 “科目一”, “科目二”， “科目三”, “通过”, “挂科”, “玩手机”, “睡觉”
马尔可夫过程主要描述的是状态之间的转移关系，在这个转移关系上 赋予不同的奖励值即得到了马尔可夫奖励过程。
定义：马尔可夫奖励 (Markov Reward Process, MRP) 过程由一个四元组组成 ⟨S, P,R, γ⟩。
，某一个状态的注，以上要注意R和R的区别
马尔可夫奖励过程的例子：
奖励值：对每一个状态的评价；
回报值：对每一个片段的评价。
定义：回报值（return Gt）是从时间t处开始的累计衰减奖励
对于片段性任务：
对于连续性任务：
片段的统一化表达：
终止状态等价于自身转移概率为1，奖励为0的状态
因此我们能够将片段任务和连续性任务统一表达：
这里T=∞时，表示连续性任务，否则即为片段性任务。
为什么我们要使用遮掩给定指数衰减？
直观感觉
影响未来的因素不仅仅包含当前
我们对未来的把握也时逐渐衰减的
一般情况下，我们更关注短时间按的反馈
数学便利
为什么要值函数？
定义：一个MRP的值函数定义：
通过一个例子比较值函数和回报值：
针对初始状态S1=“科目一”，且γ=0.5计算不同片段的回报值
虽然都是从相同的初始状态开始，但是不同的片段有不容的回报值，而且值函数是他们的期望值。
针对上述例子当γ取不同的值时对应的V值函数如下图：
值函数的表达式可以分解成两个部分
如果我们已知转移矩阵P，那么
图中我们可以用 v(s1), v(s2), v(s3) 去计算 v(s0)，由后继状态的值函数计算当前状态的值函数。
当γ=1时，我们根据以下例子计算值函数：
套用公式
使用矩阵-向量的形式表达贝尔曼方程，即：
假设状态集合为 S = {s1, s2, . . . , sn}，那么
贝尔曼方程本质上是一个线性方程，可以直接求解：
注：计算复杂度：
马尔科夫过程的最终目的是要产生决策，因此需要重点讨论马尔科夫决策过程
马尔科夫决策过程(MDP)与MP、MRP的区别
马尔科夫决策过程定义：一个马尔科夫决策过程由一个五元组构成 ⟨S, A, P,R, γ⟩。
；
；举个栗子说明马尔科夫决策过程：
针对状态的奖励变成了针对 ⟨s, a⟩ 的奖励；能通过动作进行控制的状态转移，由原来的状态转移概率变成了动作；MDP只关注那些可以做出决策的动作；被动的状态转移关系被压缩成一个状态，被动指无论做任何动作，状态都会发生跳转。这样的状态不属于MDP中考虑的状态，原图中，由于通过后一定去睡觉因此进行了压缩，原图中挂科后的跳转不受到控制。
注，图中除了在“科目三”的状态上执行“不复习”动作外，其他的所有状态跳转都是确定性，我们通过在不同的状态上执行不同的动作，即可实现状态跳转。
能够随意愿改变的就变成了动作。我们关心的是在什么情况先该做什么动作。
我们将之前MRPs中的状态转移矩阵分成了两个部分
定义：在MDPs中，一个策略π是在给定状态下的动作的概率分布，
假设动作是有限的，我们就会写成一个向量，向量上的值对应相应动作的概率，该向量求和为1，不同的状态就会对应不同的向量值。当为确定性策略的时候，就不是一个分布问题了，就是a=π。
对于一个MDP问题 ⟨S, A, P,R, γ⟩，如果给定了策略π，
MDP将会退化成MRP，
此时，
策略π有两个含义，①当为确定性策略的时候，π就等于a表示一个动作；②当策略不确定的时候，就表示一个动作分布。
在 MDPs 问题中，由于动作的引入，值函数分为了两种：①状态值函 数（V 函数）；②状态动作值函数 (Q 函数)。
①状态值函 数（V 函数）定义：MDPs 中的状态值函数是从状态s开始，使用策略π得到的期望回报值。
②状态动作值函数 (Q 函数)定义：MDPs 中的状态动作值函数是从状态 s 开始，执行动作 a，然后使用策略 π 得到的期望回报值
注:MDPs 中，任何不说明策略π 的情况下，讨论值函数都是在耍流氓！
和 MRP 相似，MDPs 中的值函数也能分解成瞬时奖励和后继状态的值 函数两部分：
举个例子说明问题：
对于∀a, s 都有 π(a|s) = 0.5，且 γ = 1时，vπ(s)如下图所示：
将图中的圆圈状态从上到下从左到右分别记为 s1, s2, s3, s4，将终止状态记 为 s5，则当 π(a|s) = 0.5∀a, s 时，状态转移矩阵为：
V 函数与 Q 函数之间的相互转化：
V-Q :
在状态s的情况下，有两个可行的动作，我们采用π分别取执行每一个动作的概率分别为π(a1 | s)和π(a2 | s)。
①执行a1动作的情况下，得到的动作状态值q(s, a 1)；
①执行a2动作的情况下，得到的动作状态值q(s, a 2)；
上图表示，上边圆圈的值可以通过下边圆圈的值求得。
Q-V' :
而q是和下一状态的v是有关系的， q表示当前状态下做了一个动作a，做动作a后就会发生两个跳转，假设跳转也有两种可能分别为s1'和s2'，中间会获得奖励r1和r2。花体的R代表了期望的意思。
贝尔曼期望方程V 函数:
表达了MDP中的vπ(s)和vπ(s′)之间的关系。
实际上等价于
思考：
.... ...
贝尔曼期望方程Q函数：
实际上等价于
思考：
.... ...
当γ=1，π(a|s) = 0.5时，
套用以上公式可以计算图中红圈之内的vπ(s)= 0.5 × (10 + 0) + 0.5 × (−5 + 0.2 ×−3.6 + 0.4 × 0.4 + 0.4 × 2.8)=2.8
MDPs 下的贝尔曼期望方程和 MRP 的形式相同，
同样地，可以直接求解
求解的要求：①已知 π(a|s)；②已知
之前值函数，以及贝尔曼期望方程针对的都是给定策略 π 的情况，是 一个评价的问题。
现在我们来考虑强化学习中的优化问题，即找出最好的策略。
定义：最优值函数指的是在所有策略中的值函数最大值，其中包括最优 V 函 数和最优 Q 函数：
最优值函数指的是一个 MDP 中所能达到的最佳性能；
如果我们找到最优值函数即相当于这个 MDP 已经解决了。
最优 V 函数和最优 Q 函数：
当 γ = 1 时的最优 V 函数 v∗(s)； 当 γ = 1 时的最优 Q 函数 q∗(s, a)；
为了比较不同策略的好坏，我们首先定义策略的比较关系：
定理：
对于任何MDP问题，
怎么得到最优策略?
当我们已知了最优 Q 函数后，我们能够马上求出最优策略，只要根据 q∗(s, a) 选择相应的动作即可。
答：
思考
... ...
再次举个例子说明问题：
当 γ = 1 时的最优策略 π∗(a|s)
之前我们已经探讨了 vπ(s) 和 qπ(s, a) 之间的关系——贝尔曼期望方程，同样地，v∗(s) 和 q∗(s, a) 也存在递归的关系——贝尔曼最优方程。
和贝尔曼期望方程的关系：
贝尔曼最优方程——V 函数； 贝尔曼最优方程——Q 函数
最优值函数和和贝尔曼期望方程的关系:
解贝尔曼最优方程:
无穷或连续 MDPs
部分可观测 MDPs（Partially observable MDPs, POMDPs）
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) | 黑马程序员IT技术论坛 X3.2 |
