强化学习系列之二:模型相关的强化学习

文章目录 [隐藏]

  • 1. 策略迭代
    • 1.1 策略评估
    • 1.2 策略改进
  • 2. 价值迭代
  • 3. 总结性结尾(好魔性的标题)
  • 强化学习系列系列文章

上一章我们介绍了强化学习的基本假设——马尔科夫决策过程 (Markov Decision Process)。本文将介绍模型相关的强化学习算法。

有的时候,我们完全知道问题背后的马尔科夫决策过程;有的时候,我们不知道问题背后的马尔科夫决策过程 (主要指我们不知奖励函数 (R_{s,a}) 和转移概率 (P_{s,a}^{s’}) 的全貌)。根据马尔科夫决策过程是否可知,强化学习可以分为两类: 模型相关 (Model-based) 和模型无关 (Model-free)。模型相关是我们知道整个马尔科夫决策过程。模型无关则是我们不知道马尔科夫决策过程,需要系统进行探索。今天我们先介绍比较简单的模型相关强化学习。

image.png

本文还是以机器人寻找金币为例子。如下图所示,一个机器人出发寻找金币。找到金币则获得奖励 1,碰到海盗则损失 1。找到金币或者碰到海盗则机器人停止。图中不同位置为状态,因此状态集合 S = {1,…,5}。机器人采取的动作是向东南西北方向走,因此A={‘n’,’e’,’s’,’w’}。转移概率方面,当机器人碰到墙壁,则会停在原来的位置;当机器人找到金币时获得奖励 1,当碰到海盗则损失 1, 其他情况不奖励也不惩罚。因此除了 (R_{1,s} = -1), (R_{3,s} = 1),(R_{5,s} = -1) 之外,其他情况(R_{,}=0)。(\gamma)衰减因子等于 0.8。

image.png

马尔科夫决策过程的具体实现,可以看这里。为了实现今天要介绍的算法,我们先定义表示策略和价值的数据结构。

class Policy_Value:
    def __init__(self, grid_mdp):
        //self.v[state] 等于状态 state 的价值。
        self.v  = [ 0.0 for i in xrange(len(grid_mdp.states) + 1)]
        
        //self.pi[state] 等于策略在状态 state 下采取的动作
        self.pi = dict()
        for state in grid_mdp.states:
            if state in grid_mdp.terminal_states: continue
            self.pi[state] = grid_mdp.actions[ 0 ]

1. 策略迭代

模型相关的强化学习算法主要有:策略迭代 (Policy Iteration) 和价值迭代 (Value Iteration)。策略迭代的主要思想是这样的。先随机初始化一个策略 (\pi_0),计算这个策略下每个状态的价值 (\pmb{v}_0);根据这些状态价值得到新策略 (\pi_1);计算新策略下每个状态的价值 (\pmb{v}_1) … 直到收敛。计算一个策略下每个状态的价值,被称为策略评估 (Policy Evaluation);根据状态价值得到新策略,被称为策略改进 (Policy Improvement)。

1.1 策略评估

策略评估利用了贝尔曼等式。根据贝尔曼等式,一个状态的价值和它后续状态的价值有关。因此我们用后续状态价值 (v(s’)) 去更新当前状态的价值 (v(s))。策略评估遍历所有状态,按照下面公式更新其价值。

(1)

由于状态之间是可以相互转移的,比如 s’ 可以是 s 的后续状态,但反过来 s 也可以是 s’ 后续状态。如果只遍历并更新一遍状态价值,状态价值并不是当前策略的价值。为此我们多次遍历并更新状态价值。策略评估的代码 (代码在这个链接下的 policy_iteration.py 中)。

// grid_mdp 是机器人找金币问题的马尔科夫决策过程
def policy_evaluate(self, grid_mdp): 
        for i in xrange(1000):

            delta = 0.0
            for state in grid_mdp.states:
                if state in grid_mdp.terminal_states: continue
                // 当前策略输出动作
                action        = self.pi[state]
                // t 表示是否到了终止状态
                // s 表示状态 state 下执行动作 action 后的状态
                // r 表示奖励
                t, s, r       = grid_mdp.transform(state, action) 
                //更新状态价值
                new_v         = r + grid_mdp.gamma * self.v[s]  
                delta        += abs(self.v[state] - new_v)
                self.v[state] = new_v  
                
            if delta < 1e-6:
                break;

1.2 策略改进

根据状态价值得到新策略,被称为策略改进。对于一个状态s,让策略选择一个动作a,使得当前状态的价值 (R_{s,a}+\gamma \sum_{s’ \in S}T_{s,a}^{s’}v(s’) ) 最大,即

*** QuickLaTeX cannot compile formula:
\begin{eqnarray*}
\pi_{i+1}(s,a) = 
\left{\begin{matrix}
 1  & a = argmax_{a}R_{s,a}+\gamma \sum_{s' \in S}T_{s,a}^{s'}v(s') \ 
 0  & a \neq argmax_{a}R_{s,a}+\gamma \sum_{s' \in S}T_{s,a}^{s'}v(s')
\end{matrix}\right. \nonumber 
\end{eqnarray*}

*** Error message:
Missing delimiter (. inserted).
leading text: \left{

可以向你保证,这样得到的新策略一定是优于旧策略的,即(v_{\pi_{i+1}}(s) \geq v_{\pi_{i}}(s), \forall s) (上一篇文章最后一节介绍的策略偏序关系)。具体证明就不详细列出了,说下大致思路:我们用策略评估计算新策略的状态价值;第一个要更新的状态是 s1,因为新策略选择价值最大的动作,因此新策略使得 v(s1) 上升;如果之前的更新都是使得价值上升,那么更新当前状态 sk 时,新策略还是使得价值上升;即使一个状态被多次更新,价值都是上升的。这样新策略优于旧策略。策略改进的代码如下 (代码在这个链接下的 policy_iteration.py 中)

def policy_improve(self, grid_mdp):
     
        for state in grid_mdp.states:
            if state in grid_mdp.terminal_states: continue
           
            a1      = grid_mdp.actions[0]
            t, s, r = grid_mdp.transform( state, a1 )
            v1      = r + grid_mdp.gamma * self.v[s]    

            //找到当前状态的价值最大的动作 a1
            for action in grid_mdp.actions:
                t, s, r = grid_mdp.transform( state, action )
                if v1 < r + grid_mdp.gamma * self.v[s]:  
                    a1 = action
                    v1 = r + grid_mdp.gamma * self.v[s]                
            //更新策略
            self.pi[state] = a1

策略迭代交替执行策略评估和策略改进直到收敛,从而得到最优策略了。下图是策略迭代在机器人找金币问题中找到的最优解。

image.png

2. 价值迭代

看完策略迭代,我们发现策略迭代计算起来挺麻烦的,代码实现起来也麻烦。我们能不能把策略评估和策略改进结合得更紧密一些。一个状态下选择动作一旦确定,立刻按照这个动作计算当前状态的价值。这个做法其实就是价值迭代。价值迭代的代码如下所示 (代码在这个链接下的 value_iteration.py 中)。

def value_iteration(self, grid_mdp):
        for i in xrange(1000):
   
            delta = 0.0;
            for state in grid_mdp.states:
            
                    if state in grid_mdp.terminal_states: continue

                    a1      = grid_mdp.actions[0]
                    t, s, r = grid_mdp.transform( state, a1 )
                    v1      = r + grid_mdp.gamma * self.v[s]    

                    for action in grid_mdp.actions:
                        t, s, r = grid_mdp.transform( state, action )
                        if v1 < r + grid_mdp.gamma * self.v[s]:  
                            a1 = action
                            v1 = r + grid_mdp.gamma * self.v[s]                

                    delta         += abs(v1 - self.v[state])
                    self.pi[state] = a1
                    self.v[state]  = v1;
 
            if delta <  1e-6:
                break;       

价值迭代一直执行直到收敛,从而获得最优策略。下图是价值迭代在机器人找金币问题中找到的最优解,和策略迭代找到的是一样的。

image.png

3. 总结性结尾(好魔性的标题)

本文介绍了模型相关的强化学习。模型相关的强化学习是指马尔科夫决策过程可知情况下的强化学习,其中策略迭代和价值迭代是主要的两种算法。本文代码可以在 Github 上找到,欢迎有兴趣的同学帮我挑挑毛病。强化学习系列的下一篇文章将介绍模型无关的强化学习,将涉及到 TD 、SARSA 和 Q-Learning 等著名算法。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

【学术】使用机器学习来进行自动化文本分类

数字化已经改变了我们处理和分析信息的方式。信息的在线可用性呈指数增长。从网页到电子邮件、科学期刊、电子书、学习内容、新闻和社交媒体都充满了文本数据。其理念是快速...

39180
来自专栏量子位

AI界的七大未解之谜:OpenAI丢出一组AI研究课题

林鳞 编译自 OpenAI官方博客 量子位 出品 | 公众号 QbitAI 今天,OpenAI在官方博客上丢出了7个研究过程中发现的未解决问题。 OpenAI希...

36690
来自专栏懒人开发

(3.4)James Stewart Calculus 5th Edition:Derivatives of Trigonometric Functions

较复杂,略 (书上证明较严谨,比较长) 简单不太严谨证明,可见百度 http://baike.baidu.com/link?url=dhIeii7Sfgc...

11920
来自专栏PPV课数据科学社区

【技术】从文本挖掘和机器学习中洞悉数据

文本挖掘分析的是包含在自然语言文本中的数据。它可以帮助企业从文本型数据中获得具有潜在价值的商业洞察力,比如Word文档、邮件或Facebook、Tw...

27960
来自专栏AI科技评论

学界 | AAAI 18论文解读:基于强化学习的时间行为检测自适应模型

AI 科技评论按:互联网上以视频形式呈现的内容在日益增多,对视频内容进行高效及时的审核也变得越来越迫切。因此,视频中的行为检测技术也是当下热点研究任务之一。本文...

37760
来自专栏机器学习算法与Python学习

机器学习(1)之入门概念

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 机器学习是什么 机器学习是什么?实际...

296100
来自专栏WOLFRAM

关于卷积去图像模糊化的例子

19540
来自专栏机器学习算法原理与实践

强化学习(二)马尔科夫决策过程(MDP)

    在强化学习(一)模型基础中,我们讲到了强化学习模型的8个基本要素。但是仅凭这些要素还是无法使用强化学习来帮助我们解决问题的, 在讲到模型训练前,模型的简...

26730
来自专栏AI科技大本营的专栏

【AI 技术精选】神经网络结构深入分析和比较

作者 | Eugenio Culurciello 翻译 | AI科技大本营(rgznai100) 深度神经网络和深度学习是既强大又受欢迎的算法。这两种算法取得的...

36960
来自专栏机器之心

业界 | OpenAI 新研究:通过自适应参数噪声提升强化学习性能

选自OpenAI 机器之心编译 参与:黄小天、路雪、李泽南 OpenAI 的研究人员发现,改善强化学习算法参数中的自适应噪声性能可以提升性能。这种探索方式易于实...

29960

扫码关注云+社区

领取腾讯云代金券