David Silver 强化学习 第二讲

马尔可夫决策过程

Posted by Pelhans on January 10, 2018

MDP是对完全可观测环境描述的,也就是说观测到的状态内容完整的决定了决策需要的特征。几乎所有学习问题都可以转化为MDP。

简介

总结自叶强的David Silver强化学习公开课中文讲解及实践专栏

什么是马尔可夫过程?

马尔可夫过程是一个无记忆的随机过程,可以用一个元组<S, P>表示,其中S是有限数量的状态集,P是状态转移概率矩阵。这里吐槽一下。之前接触的转移概率都用T表示,这里用P还真不适应。。。。

马尔科夫奖励过程

马尔科夫奖励过程在马尔科夫过程的基础上增加了奖励R和衰减系数,即<S, P, R, >。

奖励

S状态下的奖励是某一时刻t在状态s下,在t+1时刻能获得的奖励期望:

在表述上可理解为“奖励是当进入某个状态会获得相应的奖励”。

衰减系数

衰减系数(DIscount Factor) (每次输入好麻烦啊。。。后面用r代替吧。。。)衰减系数是对远期利益的衰减。对于它的引入有各种各样的解释,如避免陷入无限循环、远期利益具有一定的不确定性等等。下图给出学生MRP的示例:

由上图可以看出,相比于单马尔科夫过程,在每个状态上增加了红色的奖励R,表示进入该状态能够获得的奖励。

收获 Return

收获的定义为在一个马尔科夫链上从t时刻开始往后所有的奖励的有衰减的总和。公式表示为:

其中衰减系数体现了未来的奖励在当前时刻的价值比例,r越接近0则表明更注重短期利益,反之则租用长期利益。

价值函数

价值函数给出了某一状态或某一行为的长期价值,其定义为从该状态开始的马尔科夫链收获的期望,公式表示为:

需要注意的是价值可以描述状态,也可以描述某状态下的某个行为,在本公开课中,采用状态价值函数或价值函数来描述针对状态的价值;用行为价值函数来描述某一状态下执行某一行为的价值,严格意义上说行为价值函数是“状态行为”对价值函数的简写。

来个例子

看完上面的定义一定很懵吧。。。傻傻分不清吧~现在通过一个学生MRP来说明。

下图将图1的例子表格化,其中Reward表示进入该状态能够获得的奖励,如C1下面的-2表示进入状态C1就能获得奖励-2.奖励下面的数表示状态转移概率,其中竖向的是发出概率,横向的为接收概率,因此横向概率和为1.

考虑下图中的几个马尔科夫链,当时,在t=1时刻()的状态的收获

从上表也可以看到,收获是针对马尔科夫链中的某一个状态来说的。而价值则可以看做某一状态收获的期望。下图给出当r=0.9时的状态价值。

价值函数的推导

Bellman方程-MRP

由价值的的定义公式可知:

由此得到针对MRP的Bellman方程:

由方程可以看出,_v(s)_有两部分组成,一个是该状态的即时奖励期望,另一个是下一时刻状态的价值期望,可以根据下一时刻状态的概率分布得到其期望。因此,Bellman方程可以写作:

由上式推广得到Bellman方程的矩阵形式为:

Bellman方程是一个线性方程组,因此理论上可以直接求解:

然而在实际的计算中,该算法的计算复杂度为,n为状态数量,因此直接求解仅适用于小规模的MRPs,在大规模的MRP中,常用的迭代算法有:动态规划、蒙特卡洛苹果、时序差分学习。这些都会在以后的课程中逐一讲解。

马尔科夫决策过程 MDP

相比于MRP,MDP多了一个行为集合A,即<S, A, P, R, r>.需要注意的是这里的P和R都与具体的行为a对应,而不想MRP中仅对应某个状态。具体的数学表达式为:

由公式可知,相比与MRP,即时奖励与行为对应了,同一状态下采取不同的行为得到的即时奖励是不一样的。下图给出学生MDP的示意图:

策略 Policy

这个概念是重中之重,策略是概率的集合或分布,其元素$$\pi(a s)\pi(a s) = P[A_{t} = a S_{t} = s]$$。

一个策略完整的定义了个体的行为方式,也就是说定义了个体在各个状态下的各种可能的行为方式及其概率大小。

1:策略仅和当前状态有关,与历史信息无关;
2:同时某一确定的策略是静态的,与时间无关;
3:个体可以随时更新策略.

在定义策略后,我们就可以求得状态从s转移到的概率,它等于在执行当前策略时,执行某一个行为的概率与从s到的转移概率的乘积。

类比于此,我们还定义了奖励函数,即当前状态s下执行某一个制定策略得到的即时奖励是该策略下所有可能行为得到的奖励与该行为发生的概率的乘积的和。

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

基于策略的价值函数

定义是在MDP下的给予策略的状态价值函数,表示从状态s开始,遵循当前策略时获得的收获的期望。数学表示为:

定义为行为价值函数,表示在执行策略时,对当前状态s执行某一具体行为a所能得到的收获的期望,公式表示为:

从定义可以看出,行为价值函数一般都是与某一个特定的状态相对应的。下图给出行为价值函数的例子:

MDP下的Bellman期望方程

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

因此状态s的价值体现为在该状态下遵循某一策略而采取所有可能行为的价值按行为发生概率的乘积求和:

展开成状态价值函数的形式后带入则有:

它表明,一个某一个状态下采取一个行为的价值,可以分为两部分:其一是离开这个状态的价值,其二是所有进入新的状态的价值于其转移概率乘积的和。相应也可得到行为价值函数的状态价值函数形式:

下图给出学生MDP中红圈状态的价值是如何计算的,遵循策略为随机策略。

最优价值函数

对应于状态价值函数和行为价值函数,最优价值函数也分为最优状态价值函数和最优行为价值函数。最优价值函数明确了MDP的最优可能表现,当我们知道了最优价值函数,也就知道了每个状态的最优价值,这是就可以认为这个MDP获得了解决。

### 寻找最优策略

首先定义什么是最优策略。对于任何状态s,遵循策略的价值不小于遵循策略下的价值,则策略优于策略.

我们可以通过最大化最有行为价值函数来找到最优策略:

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

Bellman 最优方程

由前面的推理我们知道,一个状态的最优价值等于从该状态出发采取的所有行为产生的行为价值最大的那个行为价值。而最优行为价值则是离开状态s的即时奖励和所有能到达的最优状态价值的期望加和。因此我们得到最优Bellman方程:

求解Bellman最优方程

Bellman最优方程是非线性的,没有固定的解决方案,通过一些迭代方法来解决:价值迭代、策略迭代、Q学习、Sarsa等。后续会逐步讲解展开。