Abstract

Lecture 2 主要介绍了马尔科夫决策过程（Markov Decision Process，MDP）。马尔科夫决策过程形式化地描述了强化学习的environment，且这个environment是完全可观测的，即当前state完全特征化了这一过程。几乎所有的强化学习都可以形式化为一个MDP。

1. Markov Property

“The future is independent of the past given the present"

• State从历史中获取了所有的相关信息；
• 一旦$t$t时刻的state已知，则t时刻之前的history可以被抛弃掉；
• State是对未来的充分统计。

可以用下面的状态转移概率公式来描述马尔科夫性（$s'$s′是$s$s的下一个state）：

状态转移矩阵定义了所有state $s$s到所有后续state $s’$s’的转移概率：

（其中n为状态数量，矩阵每一行的和为1）
上述矩阵的每一行告诉我们接下来会以什么概率发生什么。

2. Markov Chain

Markov Process是一个无记忆的随机过程，即一个具有马尔科夫性的随机状态序列。

2.1. Example：Student Markov Chain

从Class 1 开始采样，我们从上图的随机过程中可以得到下述的随机序列：

状态转移矩阵如下：

3. Markov Reward Process

Markov Reward Process是带有value判断的Markov process，即在马尔科夫过程的基础上增加了奖励$R$R和衰减系数$\gamma$γ。

$R$R是一个奖励函数。$s$s状态下的奖励是某一时刻$(t)$(t)状态$s$s在下一个时刻$(t+1)$(t+1)能获得的奖励期望。

很多人纠结为什么奖励是$(t+1)$(t+1)时刻的。照此理解起来相当于离开这个状态才能获得奖励而不是进入这个状态即获得奖励。David指出这仅是一个约定，为了在描述RL问题中涉及到的观测O、行为A、和奖励R时比较方便。他同时指出如果把奖励改为$R_t$Rt​ 而不是 $R_{t+1}$Rt+1​，只要规定好，本质上意义是相同的，在表述上可以把奖励描述为“当进入某个状态会获得相应的奖励”。

衰减系数Discount Factor: $\gamma \in [0, 1]$γ∈[0,1], 它的引入有很多理由，其中优达学城的“机器学习-强化学习”课程对其进行了非常有趣的数学解释。David也列举了不少原因来解释为什么引入衰减系数，其中有数学表达的方便，避免陷入无限循环，远期利益具有一定的不确定性，符合人类对于眼前利益的追求，符合金融学上获得的利益能够产生新的利益因而更有价值等等。

3.1. Example: Student Markov Reward Process

下图是一个“马尔科夫奖励过程”图示的例子，在“马尔科夫过程”基础上增加了针对每一个状态的奖励，由于不涉及衰减系数相关的计算，这张图并没有特殊交代衰减系数值的大小。

3.2. Return（回报）

回报$G_t$Gt​为在一个马尔科夫奖励链上从$t$t时刻开始往后所有的奖励的有衰减的总和。

• 衰减指数$\gamma \in [0, 1]$γ∈[0,1] 体现了未来奖励在当前时刻的价值比例；
• 在$k+1$k+1时间步后获得的奖励$R$R在$t$t时刻体现出的价值是$\gamma^kR$γkR；
• $\gamma$γ趋于0，则导致"myopic" evaluation（更在乎眼前的reward）；
• $\gamma$γ趋于1，则导致"far-sighted" evaluation（倾向于考虑长远利益）。

Why Discount ？
为何需要衰减系数？前面已经有过简单地回答，下图是详细解答。

3.3. Value function

价值函数给出了某一状态或某一行为的长期价值。

注： Value可以仅描述state，也可以描述某一state下的某个action，在一些特殊情况下还可以仅描述某个action。在整个视频公开课中，除了特别指出，约定用状态价值函数或价值函数来描述针对state的value；用行为价值函数来描述某一状态下执行某一action的价值，严格意义上说价值函数是“状态行为对”价值函数的简写。

3.3.1. Example: Student MRP Returns

各状态圈内的数字表示该状态的value，圈外的$R=-2$R=−2等表示的是该状态的即时奖励。



各状态价值的确定是很重要的，RL的许多问题可以归结为求状态价值的问题。因此如何求解各状态的价值，也就是寻找一个价值函数（从状态到价值的映射）就变得很重要了。

3.4. Bellman Equation

Value function 可被分解为两部分，一个是即将得到的奖励（immediate reward $R_{t+1}$Rt+1​），另一个是衰减后的下一个state的value。Bellman Equation基本思想是对value function进行递归分解。

这个推导过程相对简单，仅在导出最后一行时，将$G_{t+1}$Gt+1​变成了$v(s_{t+1})$v(st+1​) 。其理由是收获的期望等于收获的期望的期望。

通过方程可以看出$v(s)$v(s)由两部分组成，一是该状态的即时奖励期望，即时奖励期望等于即时奖励，因为根据即时奖励的定义，它与下一个状态无关；另一个是下一时刻状态的价值期望，可以根据下一时刻状态的概率分布得到其期望。如果用$s'$s′表示$s$s状态下一时刻任一可能的状态，那么Bellman方程可以写成：

3.4.1. Example: Bellman Equation for Student MRP

下图中$\gamma=1$γ=1，$R$R指的是当你走出这个state后会立即获得$R$R的reward。

3.5. Bellman方程的矩阵形式

3.6. Bellman方程的求解

4. Markov Decision Process

相较于马尔科夫奖励过程，马尔科夫决策过程多了一个行为集合$A$A。看起来很类似马尔科夫奖励过程，但这里的$P$P和$R$R都与具体的行为$a$a 对应，而不像马尔科夫奖励过程那样仅对应于某个状态，$A$A表示的是有限的行为的集合。

4.1. Example：Student MDP

下图给出了一个可能的MDP的状态转化图。图中红色的文字表示的是选择的行为，而不是先前的状态名。对比之前的学生MRP示例可以发现，即时奖励与行为对应了，同一个状态下采取不同的行为得到的即时奖励是不一样的。由于引入了Action，容易与状态名混淆，因此此图没有给出各状态的名称，此图还把Pass和Sleep状态合并成一个终止状态。另外当选择”酒吧”这个行为时，会主动进入了一个临时状态（图中用黑色实心点，此为一个行为，而非状态，即选择“酒吧”这个行为后会有一定几率进入三个状态），随后被动的被环境按照一定几率分配到另外三个状态，也就是说此时Agent没有选择权决定去哪一个状态。

4.2. Policy

上述两公式的文字描述如下：

• 在执行策略$\pi$π时，状态从$s$s转移至$s'$s′的概率等于一系列概率的和，这一系列概率指的是在当前策略下，执行某一个行为的概率与该行为能使状态从$s$s转移至$s'$s′的概率的乘积；
• 当前状态$s$s下执行某一指定策略得到的即时奖励是该策略下所有可能行为得到的奖励与该行为发生的概率的乘积的和。

策略在MDP中的作用相当于agent可以在某一个状态时做出选择，进而有形成各种马尔科夫过程的可能，而且基于策略产生的每一个马尔科夫过程是一个马尔科夫奖励过程，各过程之间的差别是不同的选择产生了不同的后续状态以及对应的不同的奖励。

4.3. Value Function

4.3.1. State value function

从状态$s$s开始，遵循策略$\pi$π时的期望回报。

注意策略是静态的、关于整体的概念，不随状态改变而改变；变化的是在某一个状态时，依据策略可能产生的具体行为，因为具体的行为是有一定的概率的，策略就是用来描述各个不同状态下执行各个不同行为的概率。

4.3.2. Action value function

从状态$s$s开始，遵循策略$\pi$π，执行某一具体行为$a$a的期望回报。

Action与state的区别在于当前state下的action已经由policy给定了。

4.3.3. Example: State-Value Function for Student MDP

下图解释了行为价值函数：

4.3.4. Bellman Expectation Equation

与MRP类似，我们对MDP的两个公式稍加推导可以得到如下的两个贝尔曼期望公式：

4.3.4.1. $v_\pi(s)$vπ​(s)和$q_\pi(s, a)$qπ​(s,a)

上图中，空心圆表示状态，实心圆表示行为，连接状态和行为的线条仅仅把该状态以及该状态下可以采取的行为关联起来。可以看出，在遵循策略$\pi$π时，状态$s$s的价值体现为在该状态下遵循某一策略而采取所有可能行为的价值与行为发生概率的乘积求和（即求期望）。

类似的，一个行为价值函数也可以表示成状态价值函数的形式：

它表明，某一个状态下选择一个行为的价值，可以分为两部分：一是离开这个状态的价值，二是所有进入新的状态的价值与其转移概率乘积的和。

如果组合起来，可以得到下面的结果：

也可以得到下面的结果：

4.3.4.2. Example: Bellman Expectation Equation in Student MDP

4.3.5. Bellman期望方程矩阵形式

4.3.6. 最优价值函数

• 最优价值函数明确了MDP的最优可能表现；
• 当我们知道了最优价值函数，也就知道了每个状态的最优价值，这时便认为这个MDP获得了解决。

4.3.6.1. Example: Optimal Value Function for Student MDP

4.3.6.2. Example: Optimal Action-Value Function for Student MDP

注：Pub行为应是0.2*6+0.4*8+0.4*10+1=9.4

4.3.7 最优策略

4.3.8 寻找最优策略

4.3.8.1. Example: Optimal Policy for Student MDP

红色箭头表示的行为表示最优策略。

4.3.9. Bellman最优方程 Bellman Optimality Equation

对于$v^*$v∗，一个状态的最优价值等于从该状态出发采取的所有行为产生的行为价值中最大的那个行为价值：

对于$q^*$q∗，某个状态$s$s下，采取某个行为的最优价值由2部分组成，一部分是离开状态 $s$s 的即刻奖励，另一部分则是所有能到达的状态 $s'$s′ 的最优状态价值按出现概率求和：

组合起来，对于$v^*$v∗，有：

对于$q^*$q∗有：

4.3.9.1. Example: Bellman Optimality Equation in Student MDP

4.3.10. Solving the Bellman Optimality Equation

5. Extensions to MDPs

简要提及了MDP的一些扩展框架。

后续扩展知识视频信号丢失，有兴趣可以参考David Silver强化学习课程笔记（二）。

References

[1] 《强化学习》第二讲 马尔科夫决策过程：https://zhuanlan.zhihu.com/p/28084942
[2] David Silver强化学习课程笔记（二）：https://blog.csdn.net/u013745804/article/details/78206794