本章内容主要参考了UC Berkeley Deep RL Bootcamp的内容，由作者按照自己的理解整理而成
一、介绍和Markov Decision Process
Markov Decision Process（马尔科夫决策过程）指的是一种随机过程，是强化学习最重要的理论基础之一。简单的说，马尔科夫决策过程中最重要的对象有两个，一个是Agent，另一个是Environment。在强化学习的过程中，Agent和Environment不断进行互动，信息相互流动，互动的结果提供给Agent作为其进行下一步行动（action）的依据，同时互动的经验也会被纳入到学习的过程中，完成强化学习这一过程。简单的说，在时间t时，Agent处于某个当前状态（state） s t s_t st中，根据自身行动策略 π t \pi_t πt做出动作（action） a t a_t at，反馈给Environment后Environment给出奖励（Reward） r t r_t rt，Agent的状态也由 s t s_t st变到了 s t + 1 s_{t+1} st+1状态，之后再重复这一过程。所谓强化学习最重要的就是学习这个策略 π \pi π，也就是学习在这个环境下给定一个state，进行什么样的action才能获得最大的reward的问题。
好像有点扯远了，具体对Markov Decision Process下一个定义的话是这样的，Markov过程是一个典型的序列决策过程，下一个状态的产生只和当前的状态有关，与历史状态没有直接关系，但是当前的状态s实际上是和历史状态相关联的，但是我们在进行决策的时候并不需要考虑这一点，这就是Markov的特点。下面结合课程中所给的 G r i d w o r l d Gridworld Gridworld例子对MDP过程的一系列术语进行解释
Gridworld小游戏如下图所示，机器人（Agent）处在一个4*3的棋盘（Environment）中，棋盘上有12个方格，每个方格就是一个状态，机器人在不同位置的不同方格中就是处于不同的状态，从一个方格移动到另一个方格就是从一个状态转移到另一个状态。注意到棋盘上有一些障碍物，这就是不能达到的状态，另外有标注"+1"的宝石和标注"-1"的爆炸，这些表示离开这个状态的时候可以获得的reward（注意！在移动过程中某个状态奖励获得的时刻是在进行了action离开这个状态的时候才能够获得），其他没有标注数字的格子状态的reward都是零。
-
Set of states S S S
Agent 当前所处的状态集合，就是棋盘上所有的方格，每个方格代表一个状态
-
Set of actions A A A
Agent 可以进行的动作集合，对Gridworld的机器人来说，就是上下左右四个移动方向，所以集合 A A A中包含四个元素
-
Transition function P ( s ′ ∣ s , a ) P(s'|s, a) P(s′∣s,a)
转移方程，也被称作模型（Model），是环境的重要组成部分，表示机器人在状态 s s s下进行动作 a a a之后转移到状态 s ′ s' s′的概率，注意这个概率并不总是0和1，比如在Gridworld游戏中，如果由于路面比较滑，机器人明明想要向上移动一格，但是最终向右移动了，这种情况也是可能存在的。我们在确定环境的时候就需要对这些给出定义，例如可以定义机器人成功移动到期望方向的概率是0.8，但是向左和向右移动的概率各是0.1，这就确定了转移方程。
-
Reward function R ( s , a , s ′ ) R(s, a, s') R(s,a,s′)
奖励方程，指的是机器人从状态 s s s进行动作 a a a移动到状态 s ′ s' s′的动作进行完（离开状态s），环境给出的奖励
-
Start state s 0 s_0 s0
初始状态
-
Discount factor γ \gamma γ
折扣因子，举个例子来说明一下。Agent在进行决策的时候不能仅仅考虑眼前立刻就能获得的reward，也需要考虑进行决策转移到新的state之后下一步决策以及更往后的一系列决策能获得的reward如何，这就是所谓的长远考虑。但是考虑到很多步以后获得的奖励和现在一步就能获得的奖励重要性不同，我们在计算的时候给以后获得的reward的项乘上 γ \gamma γ的系数，获得这个奖励的状态与当前状态差多少个单位时间，系数就是 γ \gamma γ的多少次方。
-
Horizon H H H
最大移动的步数
在这个游戏中，我们希望学的的策略 π \pi π就相当于一张路线图，记录了每个格子机器人应该朝哪个方向走，最终能够走到宝石的位置。也就是 max π E [ ∑ t = 0 H γ t R ( s t , a t , s t + 1 ) ∣ π ] \max_{\pi}E[\sum_{t=0}^{H}\gamma^tR(s_t,a_t,s_{t+1})|\pi] maxπE[∑t=0HγtR(st,at,st+1)∣π]，目的是找到最合适的 π ∗ \pi^* π∗用来最大化这个总奖励的期望。
目标已经清楚了，达成这个目标有两个主要途径，这两个途径都是之后强化学习发展的重要基石，分别是价值迭代（value iteration）和策略迭代（policy iteration）
二、价值迭代
1. V ∗ ( s ) V^*(s) V∗(s)价值函数迭代
我们的目标是获得一个最优的价值函数
V
π
(
s
)
V^\pi(s)
Vπ(s)，最优的价值函数是准确的。价值函数的自变量是状态，函数值代表着这个状态的“价值”，也就是从该状态出发期望能够获得的最大reward（含折扣因子），这个值越高的状态价值越大。当我们获得了价值函数以后，在进行决策的时候，就可以选择价值函数中当前所在的状态对应的值所对应的action（使用argmax函数），从而获得了策略。最优价值函数满足如下式子：
V
∗
(
s
)
=
max
π
E
[
∑
t
=
0
H
γ
t
R
(
s
t
,
a
t
,
s
t
+
1
)
∣
π
,
s
0
=
s
]
V^*(s)=\max_\pi E[\sum_{t=0}^H\gamma^tR(s_t,a_t,s_{t+1})|\pi,s_0=s]
V∗(s)=πmaxE[t=0∑HγtR(st,at,st+1)∣π,s0=s]
价值迭代试图用动态规划的思路求得这一最优价值函数，动态规划的思路如下:
也就是（1）首先定义函数
V
k
∗
(
s
)
V_k^*(s)
Vk∗(s)，表示剩余k步可走的情况下的价值函数，并且有
V
0
∗
(
s
)
=
0
V_0^*(s)=0
V0∗(s)=0成立，事实上这是合适的，就算考虑gridworld中宝石所在位置的状态，由于已经没有步数可走，agent无法离开这个状态，也就不能获得这个状态的reward**（奖励在离开状态的时候获得）。之后有状态转移方程如下
V
k
∗
(
s
)
=
max
a
∑
s
′
P
(
s
′
∣
s
,
a
)
(
R
(
s
,
a
,
s
′
)
+
γ
V
k
−
1
∗
(
s
′
)
)
V_k^*(s)=\max_a\sum_{s'}P(s'|s,a)(R(s,a,s')+\gamma V_{k-1}^*(s'))
Vk∗(s)=amaxs′∑P(s′∣s,a)(R(s,a,s′)+γVk−1∗(s′))
其中转移概率函数和此
s
′
s'
s′下期望获得的奖励乘积求和表示
s
′
s'
s′下期望获得的奖励的期望，经过若干轮次的迭代，最终达到收敛即可获得
V
∗
(
s
)
V^*(s)
V∗(s)满足要求，此时有
V
∗
(
s
)
=
max
a
∑
s
′
P
(
s
′
∣
s
,
a
)
(
R
(
s
,
a
,
s
′
)
+
γ
V
∗
(
s
′
)
)
V^*(s)=\max_a\sum_{s'}P(s'|s,a)(R(s,a,s')+\gamma V^*(s'))
V∗(s)=amaxs′∑P(s′∣s,a)(R(s,a,s′)+γV∗(s′))
上式被称作Bellman Equation**，是一个非常著名的等式。综上所述，通过这种方式，我们就可以获得最优价值函数
V
∗
(
s
)
V^*(s)
V∗(s)，之后就可以通过每个状态的函数值确定每个状态最优策略对应的action，即
π
∗
(
s
)
=
arg
max
a
V
∗
(
s
)
=
arg
max
a
∑
s
′
P
(
s
′
∣
s
,
a
)
(
R
(
s
,
a
,
s
′
)
+
γ
V
∗
(
s
)
)
\pi^*(s) = \arg\max_aV^*(s) = \arg\max_a\sum_{s'}P(s'|s,a)(R(s,a,s')+\gamma V^*(s))
π∗(s)=argamaxV∗(s)=argamaxs′∑P(s′∣s,a)(R(s,a,s′)+γV∗(s))
这里补充一点，正是由于折扣因子
γ
\gamma
γ的存在，保证了价值函数每个函数值都是有限值，原理类似于等比数列求和，就不再赘述，试想，如果价值函数存在若干无穷大函数值，那么argmax函数也就无法正常使用，因此折扣因子也是价值迭代策略能够生效的必要因素。
2. Q ∗ ( s , a ) Q^*(s,a) Q∗(s,a)价值函数迭代
Q函数指的是 Q ∗ ( s , a ) Q^*(s,a) Q∗(s,a)这一函数，其中自变量s表示当前agent所处的状态，a表示agent所选择的action，Q函数的值表示在此状态下进行这一动作能获得的期望奖励大小，其中最优Q函数 Q ∗ ( s , a ) Q^*(s,a) Q∗(s,a)准确表示了这个量。使用Q函数相比于V状态函数的优点是：在计算完成最终选择策略 π ∗ \pi^* π∗的时候，Q函数不需要通过argmax的计算，可以直接比较当前状态各action对应的Q函数的值，选择值最大的一个就可以了，较为方便，但是相应的，Q函数函数值的个数一共KaTeX parse error: Undefined control sequence: \cross at position 4: |S|\̲c̲r̲o̲s̲s̲|A|个，要超过V价值函数函数值的个数 ∣ S ∣ |S| ∣S∣，因此全部存储下来的话需要更大的存储空间，这也就为策略参数化以及DQN算法埋下了伏笔。关于Q函数的迭代方法Q - learning，在下一个Lecture中有详细的介绍
二、策略迭代
回忆 V ∗ ( s ) V^*(s) V∗(s)价值函数迭代的内容， V k ∗ ( s ) V^*_k(s) Vk∗(s)代表还剩下k步可以走的时候的价值函数，此时对每个状态来说，价值函数的值所对应的action都是最优的action，即argmax函数计算的结果，如果所选择的action不是最优action而是遵循特定策略 π \pi π呢？这样就可以获得 V k π ( s ) V^{\pi}_k(s) Vkπ(s)如上。经过迭代最终可以获得 V π ( s ) V^{\pi}(s) Vπ(s)函数如上。这样就完成了Policy Evaluation的过程，即策略评估，通过获得此策略下各状态的价值函数，然后遍历所有状态，用获得的价值函数值调整现在的策略，即讲此状态下选择的action调整成奖励期望函数的最大值对应的action
需要注意的是，在进行策略调整的时候，所使用的价值函数是旧策略对应的价值函数
三、总结
以上介绍了MDP的定义，以及使用value Iteration与policy iteration两种简单方法完成了确定有限状态下的强化学习。
主要有两个重大缺陷：
- 价值函数需要存储所有的状态和动作的价值信息，需要状态-动作空间离散并且需要占用大量存储空间，当状态-动作空间维数较高的时候难以完成
- 需要知道转移概率方程，也就需要知道模型才能完成，但是这个条件往往无法得到满足