强化学习David Silver课程Lecture2 笔记

Lecture Two--Markov Decision Process

这一节我们学习了马尔科夫决策过程，这个在强化学习中也是很重要的一个概念。

首先简略介绍一下MDP（Markov Decision Process），他一般描述的是强化学习中的环境，该环境是可完全观测的，现在所处的状态完全描述了该过程，即只关心现在，过去信息没有任何影响。几乎所有的强化学习问题都可以变为MDP，这里可能会有疑问，比如局部观测的强化学习问题可以转变吗？但是这句话中的MDP不仅仅限于一般的MDP，后面有提到关于MDP的扩展。

我们开始之前看看马尔科夫特性是什么。

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

更好的数学定义如下所示

由此可以看出MDP确实是只管现在，不顾过去。

说完这个，我们再介绍一个概念：状态转移矩阵 State Transition Matrix

对于现在状态s和接下来状态s‘来说，这个状态转移概率可以被定义为：

所以状态转移矩阵就是描述了从状态s到所有可能状态s'的概率的矩阵：

然后我们正式开始介绍MDP，由浅及深，我们先介绍Markov Process 然后 Markov Reward Process(添加奖励R和价值value)再到 Markov Decision Process(添加动作A和策略)。

Markov Process

Markov过程只由状态集S和状态转移矩阵两部分构成，在这个定义中一个Markov链就是,...状态之间的变化,具体定义如下：

Markov Reward Process

马尔科夫奖励过程就是在上面的基础上加了奖励这个概念，也更跟我们生活实际切合，强化学习的目的可以说就是找到是奖励最大的一种状态变化。

Markov Reward Process的具体定于如下：

可以看出上面概念其实引进了两个新的值，Rs其实就是在状态s下一步能获得的奖励的期望，而是一个折扣值，由于我们不能只看下一步状态好不好，比如下棋其实我们是要看得更远一点的，但是后面的信息可能没有下一步的那么有效，所以我们引出了一个折扣值，使最近的状态最有影响力，之后的要打上折扣。

既然现在引入了奖励R，联系强化学习想解决的问题，我们很自然地推出一个概念：Return，以反映我们想要得到的累计奖励。

在这个定义中，我们就用到了折扣，0<=<=1,当为0时，我们只关注后面一步，相当于近视眼，我们看不到后面的了，极其贪心，而当=1时，后面每一步我们都关注，而且都是同等的优先级，这样可能会计算更复杂。

很自然地，现在对于每个状态，在不同地马尔科夫链中，我们都会有Return值（看得更远），使问题更好求解，我们对于每个状态定义一个价值Value,表示该状态的好坏

引入另外一个概念，针对MRP的贝尔曼方程,贝尔曼方程(Bellman Equation)也被称作动态规划方程(Dynamic Programming Equation),由理查·贝尔曼（Richard Bellman）发现,贝尔曼方程通常指离散时间（discrete-time）最佳化问题的动态规划方程,下面的贝尔曼方程表示了当前状态值函数与下一个状态值函数的关系：

由此我们可以看出价值函数可以分为两部分，一个是及时Reward ，另外一部分为之后状态的折扣价值，为了方便计算我们也可以得到针对MRP的贝尔曼方程的矩阵形式：

此时的v为一个元素代表一个状态的价值的列向量。

解决这个贝尔曼方程：

直接变成 ,但是可以发现这样的计算复杂度为O(),只能针对小型的MRP问题，针对大型的MRP问题，我们可以采用的方法如下,暂时先了解名词：

• 动态规划(DP)
• 蒙特卡洛评估（Monte-Carlo Evaluation）
• 时间差分学习（TD learning）

Markov Decision Process

A Markov decision process (MDP) is a Markov reward process with decisions. It is an environment in which all states are Markov.

MDP是带有决策的MRP过程，其实就是在MRP的基础上再加上了Action-动作

引进了动作，此时相当于下棋我们现在不仅仅有棋面作为状态了，而且还有在某个状态上，我们该将棋子放到哪个位置作为动作了，而关于在某一状态上该选什么动作，我们引入一个概念--策略Policy.

策略是与时间无关的，有确定策略和随机策略，前者是指在某一个状态上agent采取什么动作是肯定的，

而随机策略是指的定义中的式子，表明处于状态s时，采取每个动作的概率。

到此，我们可以理解成，一个agent处于一种环境中，可以按很多轨迹进行移动，每一个轨迹就是马尔科夫链，由于策略是指在某一状态下采取哪一种动作的决策，所以我们依照不同的策略会有不同的轨迹，从状态1到状态2，从状态1到状态i都有可能，在没有引进策略的时候，我们的概率转移以及奖励R都是考虑全部的，即在每个状态上采取任何动作都是同等权重的，没有偏爱的动作，但引进策略这个概念之后，我们就要考虑在这个策略下我们会移动的轨迹了。同样，由Markov Process到Markov Reward Process，我们引入了奖励，于是原来的轨迹中每一个状态可以衡量自己的价值，即该状态得到的累积奖励的期望。再回到MDP，由于此时机油状态又有动作，所以我们衡量价值的时候也有两种选择，一是只根据状态衡量v，而是结合状态和动作衡量q。

然后针对这个,我们也可以得出他们的bellman方程：

将两者联系起来我们可以得到以下形式：

 

 

 

 

 

然后推导得到q值与q值的关系，v值和v值的关系：

 

 

 

 

 

 

 

贝尔曼方程的矩阵形式也变为

Optimal Value Function

由于现实问题中我们用强化学习最后要得到的是一个策略，所以我们先引入最优价值函数的定义，这个函数定义了MDP的有可能的最好表现。如果我们得到了最优价值，我们也可以说这个MDP问题被解决了。

然后我们引入最优策略这个概念

  对于最优策略和最优价值函数，这里也有一些理论成立

即对于任何MDP，都存在最优策略，以及在最优策略中，价值函数也是最优价值函数。

所以最终问题来了，我们怎么得到这个最优策略呢？很自然的想法是我们可以通过最大化得到，在每个状态，选择最大的q值所对应的动作，所以如果我们知道，我们可以立马得到最优策略，但往往我们是不能在问题开始就知道的，联系之前的贝尔曼方程，我们可以迭代地求出

然后进一步推导得到

此时可以发现这个贝尔曼最优方程是非线性的，我们可以采取一些迭代的方式求取，比如(之后会具体说明)

• Value Iteration 基于价值的迭代
• Policy Iteration 基于策略的迭代
• Q-learning
• Sarsa

MDP的扩展

无限的连续的MDP（像之前Roadef就觉得问题是状态空间连续，但是在理论方面貌似早就解决了，只是简略提到，具体之后再完善）

部分观测的MDP---隐马尔科夫（统计学习方法上面有提到，但自己还没有看到那里）

另外一种是 无折扣的平均奖励的MDP 这些都没有涉及过，课程中也有提到一个遍历的马尔科夫过程，但没看太懂，如果之后遇到再详细写吧。

记录一下暂时觉得自己掌握的点：

1.这些奖励R以及这些由动作转移到每个状态的概率都是自己定义的嘛？

对，我们最后的目的就是求出最优价值函数以及最优策略，其余的都是提前定义以及无模型时我们从采样中得到的。即算法最后只是确定在那个状态选择动作的概率大小，其余的都是已知。

2.Bandit-----mult-armed bandit problem

背景：一个*n个握把，每个握把i由Pi的概率中奖，每次可以选择一个握把进行尝试，成功1，失败0，调整策略找到成功概率最大的arm

我们可以把这个看作只有一个状态的MDP，选择arm就是他的动作，有多少个arm就有多大的动作空间，这个问题可以在现实中有很多应用，比如推荐广告之类的。

记录一下问题：

1.针对MRP的贝尔曼方程的矩阵形式 ,可以直接求解，意味着我们在这种情况下v值直接由方程求出来，迭代方式也可以求出来，方程也可以直接求出来，两者有什么证明是可以相等的嘛？针对于大的MRP或者最优解我们只能迭代来完成，但是对于小的，我们可以直接求解或者迭代完成？

2.所以所有问题分为两部分？构建MDP model 解决 MDP model? 不一定是MDP模型？在无模型的时候，我们模型不限定是要为MDP模型？但所有RL问题都可以转变为MDPs?