其他lecture

【1】搬砖的旺财：David Silver 增强学习——笔记合集（持续更新）

目录

**David Silver 增强学习——Lecture 2 马尔可夫决策过程（一）** 1. 前言
----1.1 数学规范
----1.2 马尔可夫性
----1.3 状态转移矩阵
----1.4 片段（episode）
----1.5 马尔可夫过程（Markov Process，MP）
----1.6 马尔可夫链（Markov Chain）
----1.7 生成模式（Generating Patterns）
--------1.7.1 确定性模式（Deterministic Patterns）：确定性系统
--------1.7.2 非确定性模式（Non-deterministic patterns）：马尔可夫
--------1.7.3 隐藏模式（Hidden Patterns）：隐马尔科夫

**David Silver 增强学习——Lecture 2 马尔可夫决策过程（二）** 2. 马尔科夫决策过程（Markov Decision Process，MDP）
----2.1 马尔科夫奖励过程（Markov Reward Process，MRP）
----2.2 举例说明收获和价值的计算

**David Silver 增强学习——Lecture 2 马尔可夫决策过程（三）**
----2.3 Bellman方程的矩阵形式和求解

**David Silver 增强学习——Lecture 2 马尔可夫决策过程（四）**
----2.4 马尔可夫决策过程（Markov Decision Processes，MDPs）
--------2.4.1 示例——学生MDP
--------2.4.2 策略（Policy）
--------2.4.3 基于策略

的价值函数

--------2.4.4 Bellman期望方程（Bellman Expectation Equation）
--------2.4.5 学生MDP示例
--------2.4.6 Bellman期望方程矩阵形式
--------2.4.7 最优价值函数
--------2.4.8、最优策略
--------2.4.9 寻找最优策略

**David Silver 增强学习——Lecture 2 马尔可夫决策过程（五）**
--------2.4.10 学生MDP最优策略示例
--------2.4.11 Bellman最优方程（Bellman Optimality Equation）
--------2.4.12 Bellman最优方程求解学生MDP示例
--------2.4.13 求解Bellman最优方程

3. 参考文献

2. 马尔科夫决策过程（Markov Decision Process，MDP）

2.4 马尔可夫决策过程（Markov Decision Processes，MDPs）

• MP和MRP中，我们都是作为观察者，去观察其中的状态转移现象，去计算回报值
• 对于一个RL问题，我们更希望去改变状态转移的流程，去最大化回报值
• 相较于马尔可夫奖励过程，马尔可夫决策过程多了一个行为集合
  ，它是这样的一个元组:

1. 是有限的状态集
2. 是有限的动作集
3. 是状态转移矩阵，
4. 是奖励函数，
   ，描述了在状态
   做动作
   的奖励
5. 是衰减系数，并且

看起来很类似马尔科夫奖励过程，但这里的

和

都与具体的行为

对应，而不像马尔科夫奖励过程那样仅对应于某个状态。

2.4.1 示例——学生MDP

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

2.4.2 策略（Policy）

策略

是概率的集合或分布，其元素

为对过程中的某一状态

采取可能的行为

的概率，用

表示：

。

例如，

1. 一个策略完整定义了个体的行为方式，也就是说定义了个体在各个状态下的各种可能的行为方式以及其概率的大小；
2. 策略是RL问题的终极目标；
3. Policy仅和当前的状态有关，与历史信息无关；
4. 某一确定的Policy是静态的，与时间无关；
5. 个体可以随着时间更新策略；
6. 如果策略的概率分布输出都是独热的（one-hot，指一个向量只有一个元素为1，其他均为 0）的，那么称为确定性策略，否则即为随机策略。

当给定一个MDP：

和一个策略

，那么状态序列

是一个马尔科夫过程

；同样，状态和奖励序列

是一个MRP：

，并且在这个奖励过程中满足下面两个方程：

用文字描述是这样的，在执行策略

时，状态从

转移至

的概率等于一系列概率的和，这一系列概率指的是在执行当前策略时，执行某一个行为的概率与该行为能使状态从

转移至

的概率的乘积。

奖励函数表示如下：

用文字表述是这样的：当前状态

下执行某一指定策略得到的即时奖励是该策略下所有可能行为得到的奖励与该行为发生的概率的乘积的和。

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

2.4.3 基于策略

定义

是在MDP下的基于策略

的状态价值函数，表示从状态

开始，遵循当前策略时所获得的收获的期望；或者说在执行当前策略

时，衡量个体处在状态

时的价值大小。数学表示如下：

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

定义

为行为价值函数，表示在执行策略

时，对当前状态

执行某一具体行为

所能得到的收获的期望；或者说在遵循当前策略

时，衡量对当前状态执行行为

的价值大小。行为价值函数一般都是与某一特定的状态相对应的，更精细的描述是

下图用例子解释了状态价值函数：

2.4.4 Bellman期望方程（Bellman Expectation Equation）

MDP下的状态价值函数和行为价值函数与MRP下的价值函数类似，可以改用下一时刻状态价值函数或行为价值函数来表达，具体方程如下：

可以看出，在遵循策略

时，状态

的价值体现为在该状态下遵循某一策略而采取所有可能行为的价值按行为发生概率的乘积求和，可以表达为：

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

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

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

刻画了后继状态

的状态价值函数

与当前状态

的状态价值函数

的关系。

本质上而言等价于

。

刻画了后继状态

和后继行为

的行为价值函数

与当前状态

和当前行为

的行为价值函数

的关系。

本质上而言等价于

。

2.4.5 学生MDP示例

下图解释了红色空心圆圈状态的状态价值是如何计算的，遵循的策略随机策略，即所有可能的行为有相同的几率被选择执行。

，

对于终点方框位置，由于其没有下一个状态，也没有当前状态的动作，因此其状态价值函数为0。

对于其余四个状态S1、S2、S3、S4，我们依次定义其价值为

、

、

、

。我们基于

计算所有的状态价值函数。由此可以列出一个方程组。

对于

位置，我们有：

去掉注释得到

。

对于

位置，我们有：

去掉注释得到

。

对于

位置，我们有：

去掉注释得到

。

对于

位置，我们有：

去掉注释得到

。

于是我们得到一个关于

、

、

、

的方程组：

运用Python求解该方程：

# coding:utf-8

解出这个方程组可以得到：

c

即每个状态的价值函数如上图所示。

同理可以求出随机策略

下的动作价值函数：

2.4.6 Bellman期望方程矩阵形式

用矩阵形式求解学生MDP示例：

（注：

）

用Python求解该方程：

# coding:utf-8

结果：

v

2.4.7 最优价值函数

最优状态价值函数

指的是在从所有策略产生的状态价值函数中，选取使状态

价值最大的函数：

类似的，最优行为价值函数

指的是从所有策略产生的行为价值函数中，选取使状态行为对

价值最大的函数：

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

• 学生MDP问题的最优状态价值

• 学生MDP问题的最优行为价值

上面在学生MDP示例的状态价值求解过程中我们固定了策略

，虽然求出了每个状态的状态价值函数，但是却并不一定是最优价值函数。那么如何求出最优价值函数呢？详细的求解过程将在Bellman最优方程后给出。

2.4.8、最优策略

当对于任何状态

，遵循策略

的价值不小于遵循策略

下的价值，则策略

优于策略

：

定理

对于任何MDP，下面几点成立：
存在一个最优策略

，比任何其他策略更好或至少相等，即

；

所有的最优策略有相同的最优价值函数，即

；

所有的最优策略具有相同的行为价值函数，即

。

（注：证明请参考【11】！）

2.4.9 寻找最优策略

可以通过最大化最优行为价值函数

来找到最优策略。

对于任何MDP问题，总存在一个确定性的最优策略；同时如果我们知道最优行为价值函数，则表明我们找到了最优策略。

3. 参考文献

【1】一个简单的马尔可夫过程例子

【2】机器学习十大算法---10. 马尔科夫

【3】《强化学习》第二讲 马尔科夫决策过程

【4】深度增强学习David Silver（二）——马尔科夫决策过程MDP

【5】马尔可夫决策过程MDP

【6】强化学习(二)：马尔科夫决策过程(Markov decision process)

【7】马尔可夫过程

【8】3 有限马尔可夫决策过程（Finite Markov Decision Processes）

【9】强化学习（二）马尔科夫决策过程(MDP)

【10】matlab奇异矩阵如何处理？

【11】Total Expected Discounted Reward MDPs : Existence of Optimal Policies

请大家批评指正，谢谢 ～