MDPs —— 马尔可夫决策定义与算法
创始人
2024-06-01 20:34:46
0

文章目录

  • MDPs 定义——由实例开始
    • 时序决策问题
    • 给游戏增点乐子
      • *为什么要有折扣
    • 游戏的解——原则
    • 所以,什么是 MDPs?
  • MDPs 的基本原理、表示
    • 光环原理
    • 效用的求解是反向传播的
    • 原则不变条件
    • MDPs 的表示
  • MDPs 求解
    • 效用迭代法
      • 缺点
    • 原则迭代法

MDPs 定义——由实例开始

时序决策问题

假设有一个 agent,从下图的 start 开始,移动到图中的 +1、-1 两个状态时,游戏结束。其中阴影部分是 agent 的无法移动区域,图如下:
在这里插入图片描述
在这个游戏中,很明显可以用几个状态表示,首先是 agent 目前所在的状态(位置)集合,S = {s1,s2,…,sn},以及可以采取的动作集 A(s)。在此游戏中,很明显 A(s) = { 上下左右 }。

对于马尔可夫过程而言, A(s) 是不可靠的。具体地说,假设当前的 agent 采用了 “上”,那么在现实的实现中,有 80% 的概率走上,10% 的概率走右,10% 走左。因此,假如 agent 目前处于状态(位置) s,那么下一个动作后,agent 来到 s’ 需要用一个新的变量——状态转移模型 来表示,记为 P(s’|s,a);

可以看到,这个游戏的下一个状态,取决于上一个状态。而且这几个格子里面是什么情况,这几个格子的布局是什么,终点在哪里,都是已知的。这个游戏,其实也是一个时序决策过程。也就是说,环境已知,状态是通过上一个状态,转移到下一个状态。

给游戏增点乐子

当然,如果这个游戏只是单纯地走到 +1、-1,然后游戏结束,未免太过无聊。为了给游戏增加乐趣,我们给每一个格子都加入一个附加回报。所以 agent 在进行状态转移时(从一个格子,到另一个格子),都会积累一个回报,记为 R(s’,a,s)。当然,这个 R(s’,a,s) 可正可负,并且具有上下界。

然后,我们修改一下游戏获胜规则。为此定义一个效用函数,其定义为:agent 从当前状态(不是初始状态)到目标状态所经历的轨迹中,所有 回报之和。

当然,效用有两种计算方式,如下:

在这里插入图片描述

*为什么要有折扣

如果 agent 可以走无限多步,且 R 有正数,那么可以无限地来回走动,来实现效用无穷大,这样就没有意思了。采用折扣累加,就不会出现无穷大的情况,证明如下:
在这里插入图片描述

举个例子,加入上图除了+1/-1 格子外,所有格子的回报都是 -0.04。如果 agent 走了 10 步到了 +1,那么 start 的效用就是:-0.04x9 +1 = 0.64。

那么,如果是你玩这个游戏,你会采用哪种动作(从 start 开始),从而使得:从初始状态开始,到目标状态所经历的轨迹中,所有回报之和最高。

这个游戏显然由于状态转移的概率性,所以具有一定的随机性。也就是说,没有一种万金油的动作套路,使得积累回报最高。

游戏的解——原则

那么,加入给一个机器人来解决上面的游戏,我们需要给出所有格子,可以采用的最优动作。何谓最优?由于有了概率的参与,最优很显然变成期望最大。什么期望最大呢?当然是所有行动轨迹的效用的期望。

由于状态转移是随机的,因此,我们可以列出的解,就是每一个当 agent 由任意的 s 拉倒 任意的 s’ 时,应该采取的动作组成的集合,我们称这个集合为原则。很显然,原则是一个大小为 |S|^2 的集合,我们记为 π。当 agent 采取某个原则 π 时,显然状态 s 有的期望效用为:
在这里插入图片描述
因此,如果要解这个游戏,我们就要找到最优原则:
在这里插入图片描述
如果步长无限的情况下,很显然最优原则与初始状态是独立的。

所以,什么是 MDPs?

MDPs 是由以下部分组成的:

  1. agent 的状态集合 S
  2. 动作集合 A(s)
  3. 状态转移概率 P(s’|s,a)
  4. 效用函数 U(s)

要求的是一个动作原则,使得轨迹中回报的折扣累计的期望最大(效用期望最大)

MDPs 的基本原理、表示

光环原理

下图给出了每个格子的效用(效用将从后面的算法中求出),很明显,离 +1 越近,则效用越大。因为他走到 +1 所需要的步数最小。注意,MDPs 不会直接给出效用
在这里插入图片描述

效用的求解是反向传播的

假如 agent 的目前状态是 s ,那么最佳原则应该采取的动作 a 应满足:
在这里插入图片描述
其中 s’ 为采用 a 后转移的状态,U(s’) 可由下述公式求出,即后续状态序列的折扣累计效用的期望:
在这里插入图片描述
此时, 状态 s 的效用是:
在这里插入图片描述
这个公式也叫 bellman 公式。

举个例子:
在这里插入图片描述
由此也可以看出,一个状态的效用,要从下一个状态的效用求出。而效用的求解,是回报沿着轨迹的累加。因此,效用的求解是反向传播的。

原则不变条件

假如回报 R(s) 进行了线性变化,如 R(s) = aR(s)+b (a>0),那么原则不变。

更进一步的,如果 R’(s’,a,s) = R(s’,a,s) + γ f(s’) - f(s) ,f(s) 是 s 的函数,那么原则也不变。

MDPs 的表示

  1. 用一个三维表列举所有状态,以及采取动作后来到的下一个状态的效用来表示。显然这个三维表的大小是 S by S by A。
  2. 用一个动态贝叶斯网络,创建一个动态决策网络,来表示 MDP;这里不详细解释。

MDPs 求解

效用迭代法

从上面的所有内容中,我们大致可以看出,要求解一个最好的 原则 π,必须先求出所有格子、在最优动作下的效用。我们可以用 bellman 公式来求取动作 + 效用:
在这里插入图片描述
假如 s 的取值有 n 个,U(s’) 、U(s) 为未知数,那么上式就可以得出 n 个方程组,这个方程组里有 n 个未知数。很显然,联立以上方程,就可以求出方程的解,即所有的 U(s)。

由于这个方程是一个非线性方程(带有 max),所以不能够直接求取。一个求解的方法是数值迭代法,具体如下:
在这里插入图片描述
R(s) 也就是 R(s’,a,s),通常是已知的。

用这个算法可以求解出 U(s):
在这里插入图片描述

缺点

经过测试,当 δ 还很大的时候,求出来的 原则 π 就已经是最优原则了。由此推出另一个算法,原则迭代算法。

原则迭代法

首先取一个初始原则 π0,求出每一个状态的效用 U(s):
在这里插入图片描述
之后:
在这里插入图片描述
如是迭代,直到原则不变即可。具体算法如下:
在这里插入图片描述

相关内容

热门资讯

喜欢穿一身黑的男生性格(喜欢穿... 今天百科达人给各位分享喜欢穿一身黑的男生性格的知识,其中也会对喜欢穿一身黑衣服的男人人好相处吗进行解...
发春是什么意思(思春和发春是什... 本篇文章极速百科给大家谈谈发春是什么意思,以及思春和发春是什么意思对应的知识点,希望对各位有所帮助,...
网络用语zl是什么意思(zl是... 今天给各位分享网络用语zl是什么意思的知识,其中也会对zl是啥意思是什么网络用语进行解释,如果能碰巧...
为什么酷狗音乐自己唱的歌不能下... 本篇文章极速百科小编给大家谈谈为什么酷狗音乐自己唱的歌不能下载到本地?,以及为什么酷狗下载的歌曲不是...
华为下载未安装的文件去哪找(华... 今天百科达人给各位分享华为下载未安装的文件去哪找的知识,其中也会对华为下载未安装的文件去哪找到进行解...
怎么往应用助手里添加应用(应用... 今天百科达人给各位分享怎么往应用助手里添加应用的知识,其中也会对应用助手怎么添加微信进行解释,如果能...
家里可以做假山养金鱼吗(假山能... 今天百科达人给各位分享家里可以做假山养金鱼吗的知识,其中也会对假山能放鱼缸里吗进行解释,如果能碰巧解...
一帆风顺二龙腾飞三阳开泰祝福语... 本篇文章极速百科给大家谈谈一帆风顺二龙腾飞三阳开泰祝福语,以及一帆风顺二龙腾飞三阳开泰祝福语结婚对应...
四分五裂是什么生肖什么动物(四... 本篇文章极速百科小编给大家谈谈四分五裂是什么生肖什么动物,以及四分五裂打一生肖是什么对应的知识点,希...
美团联名卡审核成功待激活(美团... 今天百科达人给各位分享美团联名卡审核成功待激活的知识,其中也会对美团联名卡审核未通过进行解释,如果能...