首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >强化学习系列之二:模型相关的强化学习

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

作者头像
AlgorithmDog
发布2018-01-08 15:59:19
9010
发布2018-01-08 15:59:19
举报

文章目录 [隐藏]

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

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

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

image.png
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
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)

\begin{eqnarray*} v(s)  = \sum_{a \in A}\pi(s,a)(R_{s,a}+\gamma \sum_{s' \in S}T_{s,a}^{s'}v_{t}(s'))   \nonumber  \end{eqnarray*}
\begin{eqnarray*} v(s) = \sum_{a \in A}\pi(s,a)(R_{s,a}+\gamma \sum_{s' \in S}T_{s,a}^{s'}v_{t}(s')) \nonumber \end{eqnarray*}

由于状态之间是可以相互转移的,比如 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
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
image.png

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

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

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016年4月10日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 策略迭代
    • 1.1 策略评估
      • 1.2 策略改进
      • 2. 价值迭代
      • 3. 总结性结尾(好魔性的标题)
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档