强化学习系列之一:马尔科夫决策过程

文章目录 [隐藏]

  • 1. 马尔科夫决策过程
  • 2. 策略和价值
  • 3. 最优策略存在性和贝尔曼等式
  • 强化学习系列系列文章

机器学习一共有三个分支,有监督学习、无监督学习和强化学习。强化学习是系统从环境学习以使得奖励最大的机器学习。强化学习和有监督学习的不同在于教师信号。强化学习的教师信号是动作的奖励,有监督学习的教师信号是正确的动作。

我最近在学习强化学习。为了整理学习心得,开始写这个强化学习系列博客。由于学识浅薄,内容难免有些错误,还望各路大神不吝赐教。

1. 马尔科夫决策过程

要说强化学习,就必须说说马尔科夫决策过程 (Markov Decision Processes, MDP)。马尔可夫决策过程是基于马尔可夫过程理论的随机动态系统的决策过程,其分五个部分:

1.

表示状态集 (states); 2.

表示动作集 (Action); 3.

表示状态 s 下采取动作 a 之后转移到 s’ 状态的概率; 4.

表示状态 s 下采取动作 a 获得的奖励; 5.

是衰减因子。

和一般的马尔科夫过程不同,马尔科夫决策过程考虑了动作,即系统下个状态不仅和当前的状态有关,也和当前采取的动作有关。还是举下棋的例子,当我们在某个局面(状态s)走了一步 (动作 a )。这时对手的选择(导致下个状态 s’ )我们是不能确定的,但是他的选择只和 s 和 a 有关,而不用考虑更早之前的状态和动作,即 s’ 是根据 s 和 a 随机生成的。

下图是一个机器人从任意一个状态出发寻找金币的例子。找到金币则获得奖励 1,碰到海盗则损失 1。找到金币或者碰到海盗则机器人停止。

我们可以把这个问题建模成马尔科夫决策过程。图中不同位置为状态,因此 S = {1,…,8}。机器人采取动作是向东南西北四个方向走,因此A={‘n’,’e’,’s’,’w’}。转移概率方面,当机器人碰到墙壁,则会停在原来的位置;当机器人找到金币时获得奖励 1,当碰到海盗则损失 1, 其他情况不奖励也不惩罚。因此除了

,

之外,其他情况

。衰减因子

在后面介绍。写成代码下面所示。

class Mdp:

    def __init__(self):

        self.states         = [1,2,3,4,5,6,7,8] # 0 indicates end
        self.terminal_states      = dict()
        self.terminal_states[6]   = 1
        self.terminal_states[7]   = 1
        self.terminal_states[8]   = 1

        self.actions        = ['n','e','s','w']

        self.rewards        = dict();
        self.rewards['1_s'] = -1.0
        self.rewards['3_s'] = 1.0
        self.rewards['5_s'] = -1.0

        self.t              = dict();
        self.t['1_s']       = 6
        self.t['1_e']       = 2
        self.t['2_w']       = 1
        self.t['2_e']       = 3
        self.t['3_s']       = 7
        self.t['3_w']       = 2
        self.t['3_e']       = 4
        self.t['4_w']       = 3
        self.t['4_e']       = 5
        self.t['5_s']       = 8 
        self.t['5_w']       = 4

        self.gamma          = 0.8

    def transform(self, state, action): ##return is_terminal,state, reward
        if state in self.terminal_states:
            return True, state, 0

        key = '%d_%s'%(state, action);
        if key in self.t: 
            next_state = self.t[key]; 
        else:
            next_state = state       
 
        is_terminal = False
        if next_state in self.terminal_states:
            is_terminal = True
      
        if key not in self.rewards:
            r = 0.0
        else:
            r = self.rewards[key];
           
        return is_terminal, next_state, r;

马尔科夫决策过程是强化学习的理论基础。不管我们是将强化学习应用于五子棋游戏、星际争霸还是机器人行走,我们都假设背后存在了一个马尔科夫决策过程。只不过有的时候我们知道马尔科夫决策过程所有信息(状态集合,动作集合,转移概率和奖励),有的时候我们只知道部分信息 (状态集合和动作集合),还有些时候马尔科夫决策过程的信息太大无法全部存储 (比如围棋的状态集合总数为

)。强化学习算法按照上述不同情况可以分为两种: 基于模型 (Model-based) 和非基于模型 (Model-free)。基于模型的强化学习算法是知道并可以存储所有马尔科夫决策过程信息,非基于模型的强化学习算法则需要自己探索未知的马尔科夫过程。

2. 策略和价值

强化学习技术是要学习一个策略 (Policy)。这个策略其实是一个函数,输入当前的状态 s,输出采取动作 a 的概率

。有监督学习希望分类器正确地对实例分类,那么强化学习的目标是什么呢?强化学习希望把策略训练什么样呢? 假设我们的系统在一个状态 s 中,我们不会选择当前奖励

最大的动作 a。因此这个动作可能导致系统进入死胡同,即系统之后会受到很大的处罚。为了避免这种情况,策略要考虑到后续的影响。因此我们最大化递减奖励的期望

(1)

其中

是马尔科夫决策过程的第五个部分:衰减因子。

用于平衡当前奖励和远期奖励的重要性,也是用来避免计算结果无穷。

是系统在当前策略下第 k 步之后获得的奖励。这种目标既考虑了当前奖励又考虑了远期奖励,避免了下一个状态是死胡同的问题。

根据上面的目标,人们提出了价值的概念。一个策略下的一个状态的价值定义:这个状态下,按照这个策略,系统能够获得的递减奖励期望。

(2)

上面机器人找金币的例子中,设定衰减因子

等于 0.5。如果策略是一直往西走碰壁之后立马向南,那么状态 2 的价值

。如果策略是随机一个方向,那么所有状态的价值如下图所示。

后来人们进一步扩展了价值的概念,将价值扩展到状态-动作对上。一个状态-动作对的价值定义如下所示。

(3)

3. 最优策略存在性和贝尔曼等式

根据上面的介绍,我们发现强化学习的目标是找到一个策略

, 使得这个策略下每个状态的价值最大。但是这里有一个问题啊。对于两个策略,有可能出现:策略

状态 a 的价值大于策略

状态 b 的价值,但策略

状态 c 的价值大于策略

状态 d 的价值。因此我们不确定,是否存在一个策略

的所有状态价值大等于其他策略的状态价值。如果不存在这么一个策略,我们的目标是迷茫的。

但是万幸啊,下面的定理保证了这么一个策略存在。这么一个所有状态价值大等于其他所有的状态价值,我们可以称之为最优策略。强化学习算法的目标就是找到最优策略。

另外一个重要的点是贝尔曼等式。贝尔曼登等式表明了当前状态的值函数与下个状态的值函数的关系,具有很简明的形式。

(4)

贝尔曼等式在强化学习中有很重要作用,这个我们后面会了解到。

文中所涉及代码可以在 GitHub 上找到。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

从基础概念到数学公式,这是一份520页的机器学习笔记(图文并茂)

23260
来自专栏技术翻译

5分钟理解人工智能与机器学习的区别

人工智能不是一个新名词,它已有数十年历史。从80年代初开始,计算机科学家设计了能够学习和模仿人类行为的算法。

14200
来自专栏云时之间

NLP系列学习:生成型模型和判别型模型

在学习机器学习的过程中我们总会遇见一些模型,而其中的一些模型其实可以归类于生成模型或者是判别模型中去,而这一篇文章我将会简单的概述下我最近所遇到的一些模型,并且...

330100
来自专栏ATYUN订阅号

将深度学习专门化: 吴恩达的21节Deeplearning.ai课程学习经验总结

截止到2017年10月25日,吴恩达在Coursera上目前有3门新的深度学习课程: 1.神经网络和深度学习(Neural Networks and Deep...

40590
来自专栏AI研习社

教程 | Hinton 机器学习视频中文版:ANN的MNIST学习范例(1.4)

本套课程中,Hinton 重点介绍了人工神经网络在语音识别和物体识别、图像分割、建模语言和人类运动等过程中的应用,及其在机器学习中发挥的作用。与吴恩达的《Mac...

37480
来自专栏应兆康的专栏

26. 训练集误差分析

18050
来自专栏程序生活

生物医学文本挖掘BioNLP1、简介2、国内相关资讯3、论文/文章4、BioNLP-ST 20165、论文阅读6、相关实战(待更)

1、简介 BioNLP Shared Task(BioNLP-ST)是一个生物文本挖掘领域的国际比赛,截止到2016年,已经举办了10年,每年都吸引了来自剑桥大...

43950
来自专栏钱塘大数据

【干货】从基础概念到数学公式,学霸的机器学习笔记

导读:近日,来自SAP(全球第一大商业软件公司)的梁劲(Jim Liang)公开了自己所写的一份 520 页的学习教程(英文版),详细、明了地介绍了机器学习中的...

16820
来自专栏机器之心

学界 | 腾讯提出并行贝叶斯在线深度学习框架PBODL:预测广告系统的点击率

选自arXiv 机器之心编译 参与:蒋思源 近日,腾讯发表了一篇介绍并行贝叶斯在线深度学习(PBODL)框架的论文,该论文表示这一框架已经用于腾讯广告系统的点击...

36740
来自专栏ATYUN订阅号

伯克利人工智能研究:基于模型的强化学习与神经网络动力学

让机器人在现实世界中自主行动是很困难的。即使拥有昂贵的机器人和世界级的研究人员,机器人在复杂的、非结构化的环境中仍然难以自主导航和交互。 ? ? 图1:一个学习...

38050

扫码关注云+社区

领取腾讯云代金券