Markov 决策过程中文译为马尔可夫决策过程。英文全称为 Markov Decison Processes，简称 MDP.
为了便于描述，首先定义一个“世界”，如下：
"世界"
从起点开始，每次选择往四个方向走一格子。目标是到达绿色格子，游戏结束，碰到红色则失败，游戏结束。
黑色格子为障碍物，碰到障碍物或撞到墙壁则原地不动。
但是每次移动准确率只有80%，另外有20%的概率向与目标方向垂直的方向移动，这两个垂直的方向概率各是10%.
名词定义
- STATES（状态）：顾名思义，就是智能体当前的状态。在这个世界中，表现为「坐标」。则开始状态就是(1,1)，目标状态是(4,3).
- ACTIONS（动作）：即在一个特定的STATE中所做的事。在这个世界中表现为四向移动。
-
MODEL（转换模型）：模型描述了整个游戏规则。可以抽象为有三个参数的函数：
T(s,a,s')，他生成的其实是一个概率：P(s'|s,a)，即：从状态s，采取动作a，转换到状态s'的概率。 -
REWARD（奖励）：即到达一个状态得到的反馈。例如到达绿色格子可以获得正数奖励。所以可以表述为与状态有关的函数：
R(s)，也可以变形为R(s,a)或R(s,a,s'). -
POLICY（策略）：上面三个定义组成了一个「问题」，则策略就是一个解决方案。它根据所处的状态，返回一个动作。可以表述为函数：
π(s) → a. 而则表示最优策略，它最大化长期期望奖励。
从MODEL定义，可以得出 Markov 特性，即：下一个状态的产生只和当前状态有关。
不同奖励下的策略
无穷时域是前提假设，即：只要不进入红绿格子，游戏可以一直进行下去。
当空白格子奖励为+2，甚至大于目标格子的奖励。那么智能体就会尽可能地留着游戏中不出局。基于此，可得上图策略。
需要注意，第(3,3)格子不可以向下。若向下，则有10%概率结束游戏，若向左则不可能结束游戏。
当空白格子奖励为-2，为了最大化长期期望奖励，智能体应该尽快结束游戏。基于此可得上图策略。
需要注意，第(3,1)格不可以向上。若向上则有10%概率向左，距离结束位置更远。
偏向稳定性
有一个关于状态序列的价值函数 V：
有这样一个事实：
若
则有
同时，价值说明了延迟奖励的意义所在。即采取某一动作当时不会获得高额奖励甚至是负数奖励，但未来可以收获较多奖励。
折扣期望
引例
假设有下面两种奖励序列：
直观上可能会认为
V2 > V1，但是实际上 V2 = V1 = ∞. 实际与直观并不相符。即使这样，我们也可能更偏爱V2. 造成这种现象的直接原因就是时域是无穷的，进而导致奖励不断累积，长期期望奖励趋向于无穷大。
折扣
为了解决上述问题，可以改变一下函数 V.
如此一来，随着时间推移，每一步获得的奖励会越来越小。不难看出这是一个等比数列求和：
这就是折扣期望，也叫折扣数列或折扣总和。他实现了无穷到有穷的转变。即：可以一直走下去，但最终获得的总奖励是有限的。
最优策略
推导
根据定义，最优策略应该最大化长期期望奖励，即：
那么在遵循π策略时的价值就应该是：
需要注意，
. 价值是一个长期的反馈，而奖励是进入某一状态的立即反馈。
在有了价值之后，可以优化一下最优策略的表达式：
即：最大化 加总 进入状态s'的概率与它价值的积。
另外，如果遵循最优策略，那么这个价值就是最优策略价值。即，称之为
状态的真实价值。
所谓最优策略就是：对于每一个状态，返回的动作能够最大化期望价值。
展开价值方程可得 Bellman 方程（贝尔曼方程）：
即：某个状态的真实价值 = 进入此状态得到的奖励 + 所有从此状态开始获得的奖励的折扣。
求解 Bellman 方程
由于实际上有n个状态，所以实际上这是一个n元方程组，包含n个方程。（R/T已知，V未知）
值迭代
思路：
- 从任意价值开始。
- 基于他们临近的状态更新这个价值。
- 重复第二步。
假设每次更新时间为t，则第二步方程可表述为：
此算法叫做值迭代。
实例：
image
对于状态x，求两次迭代后的价值值%2C%20V_2(x))
第一次迭代：
初始价值都是0，对于状态x显然往右走期望最大。因此：
同理，对于状态(3,2)，显然向左走期望最大，为0. 其他方向均小于0. 因此：
第二次迭代：
对于状态x，依然是向右期望最大。因此：
策略迭代
思路：
- 从任意的一个
开始。
- 对于给定的
，令
.
- 更新
.
