值迭代_值迭代算法介绍 - CSDN
精华内容
参与话题
  • 这次我们来学习求解强化学习模型的2种思路——值迭代与策略迭代动态规划这里面我要简单介绍一下动态规划,因为严格来说,值迭代与策略迭代是用来解决动态规划问题的两种规划方法。而强化学习又有另外一个昵称——...

    上一次我分享了强化学习相关基础概念,推导了Bellman方程。这次我们来学习求解强化学习模型的2种思路——值迭代与策略迭代

    动态规划

    这里面我要简单介绍一下动态规划,因为严格来说,值迭代与策略迭代是用来解决动态规划问题的两种规划方法。而强化学习又有另外一个昵称——就是拟动态规划。说白了强化学习就是模拟动态规划算法。

    用一句话来总结动态规划就是,对一个复杂问题给出一个一般性的解决办法。它主要由两个性质:

    1. 最优子结构:最优解法能被分解到多个子问题中
    2. 重叠子问题:子问题能重复多次且解法能被重复利用

    马尔科夫决策过程(MDP)满足以上两个性质,所以任何MDP都可以用动态规划来解。动态规划与强化学习的区别就是动态规划假设MDP模型是全知的(即参数可知)强化学习可以使MDP未知

    MDP需要解决的问题有两种,第一种是prediction,它已知MDP的S,A,P,R,γ以及policy,目标是算出在每个状态下的value function(值函数其实就是问题的目标,一般都是跟reward有关的函数,例如Atari小游戏,一般值函数就是累计的得分的期望。目标一般就是最大化这个值函数。而第二种是control,它已知MDP的S,A,P,R,γ但是policy未知(即动作at未知),因此它的目标不仅是计算出最优的value function而且要给出最优的Policy。

    策略迭代 (policy iteration)

    策略迭代就是在policy未知的情况下,根据每次的reward学到最优policy。
    对一个具体的MDP问题,每次先初始化一个策略,根据这个策略计算值函数v(s), 通过这个re值函数来根据贪心策略更新策略,不断迭代最终得到最优策略与最优值函数。总结下来就两个阶段。

    • Policy evaluation :根据每一次的给出策略估计vπ
    • Policy improvement:根据Greedy poilcy和之前得到的vπ获得当前策略π

    图解如下:
    这里写图片描述
    这里写图片描述

    给一个例子:下图是一个叫Small Gridworld的例子,左上角和右下角是终点,γ=1,移动一步reward减少1,起始的random policy是朝每个能走的方向概率相同,先单独看左边一列,它表示在第k次迭代每个state上value function的值,这一列始终采用了random policy,这里的value function就是通过Bellman Expectation Equation得到的,考虑k=2的情况,-1.7 = -1.0 + 2*(1/3.0)(-1),-2.0 = -1.0 + 4(1/4.0)*(-1)。而右边一列就是在当前的value function情况下通过greedy算法找到当前朝哪个方向走更好。

    这里写图片描述
    这里写图片描述

    值迭代(value iteration)

    值迭代就是在已知policy和MDP模型的情况下,根据策略获得最优值函数和最优策略。
    只不过这是确定策略,在值函数vπ取得最大值的at(策略)
    通过每次迭代bellman方程获得vi, 知道值函数收敛。图解如下:这里写图片描述

    最后对策略迭代和值迭代进行一个比较:
    这里写图片描述

    展开全文
  • 【强化学习】值迭代和策略迭代 在强化学习中我们经常会遇到策略迭代与值迭代,但是很多人都搞不清楚他们两个之间的区别,他们其实都是强化学习中的动态规划方法(DP)。 ——《Reinforcement Learning:An ...

    【强化学习】值迭代和策略迭代

    在强化学习中我们经常会遇到策略迭代与值迭代,但是很多人都搞不清楚他们两个之间的区别,他们其实都是强化学习中的动态规划方法(DP)。 ——《Reinforcement Learning:An Introduction》

    (一)值迭代

    对每一个当前状态 s ,对每个可能的动作 a 都计算一下采取这个动作后到达的下一个状态的期望价值。看看哪个动作可以到达的状态的期望价值函数最大,就将这个最大的期望价值函数作为当前状态的价值函数 V(s) ,循环执行这个步骤,直到价值函数收敛。

    400


     

    (二)策略迭代

    从一个初始化的策略出发,先进行策略评估,然后改进策略,评估改进的策略,再进一步改进策略,经过不断迭代更新,直达策略收敛,这种算法被称为“策略迭代”

     

     

     


     

    References:

     [1] 【强化学习】值迭代与策略迭代

     

     

     

     

    转载于:https://www.cnblogs.com/xxxxxxxxx/p/11536460.html

    展开全文
  • 强化学习笔记(三)-----值迭代算法

    千次阅读 2018-08-20 22:49:27
    强化学习有两种常见迭代训练算法:策略迭代算法和值迭代算法。在上一篇博客<<强化学习笔记(二)>>中已经详细描述了策略迭代算法,其实值迭代算法和策略迭代算法的基本...

    强化学习有两种常见迭代训练算法:策略迭代算法和值迭代算法。在上一篇博客<<强化学习笔记(二)>>中已经详细描述了策略迭代算法,其实值迭代算法和策略迭代算法的基本思想是一致的,其最大的区别在于,策略迭代算法在进行策略改善的时候,使用的每个状态的值函数,是稳定的,在进行策略评估的时候,计算得到了当前策略的稳定值函数;而值迭代算法交替进行策略评估和策略改善的过程,并不是等到值函数稳定的时候再进行策略改善,其过程更为动态。

    gym的样例代码展示

    通过对下面的问题进行编程,加深对值迭代算法的理解。问题的描述同<<强化学习笔记(二)>>中的内容

    这里写图片描述

    该图的状态空间由下置上,从左到右,分别为1 – 36

    import numpy as np
    import random
    from gym import spaces
    import gym
    from gym.envs.classic_control import rendering
    
    #模拟环境类
    class GridWorldEnv(gym.Env):
        #相关的全局配置
        metadata = {
            'render.modes':['human', 'rgb_array'],
            'video.frames_per_second': 2
        }
    
        def __init__(self):
            self.states = [i for i in range(1, 37)] #初始化状态
            self.terminate_states = [3, 7, 11, 15, 19, 20, 23, 30,  33, 34] #终结态
            self.actions = ['up', 'down', 'left', 'right'] #动作空间
    
            self.v_states = dict() #状态的值空间
            for state in self.states:
                self.v_states[state] = 0.0
    
            for state in self.terminate_states: #先将所有陷阱和黄金的值函数初始化为-1.0
                self.v_states[state] = -1.0
    
            self.v_states[34] = 1.0  #黄金的位置值函数初始化为 1
    
            self.initStateAction() #初始化每个状态的可行动作空间
            self.initStatePolicyAction() #随机初始化当前策略
    
            self.gamma = 0.8 #计算值函数用的折扣因子
            self.viewer = None #视图对象
            self.current_state = None #当前状态
            return
    
        def translateStateToRowCol(self, state):
            """
            将状态转化为行列坐标返回
            """
            row = (state - 1) // 6
            col = (state - 1) %  6
            return row, col
    
        def translateRowColToState(self, row, col):
            """
            将行列坐标转化为状态值
            """
            return row * 6 + col + 1
    
        def actionRowCol(self, row, col, action):
            """
            对行列坐标执行动作action并返回坐标
            """
            if action == "up":
                row = row - 1
            if action == "down":
                row = row + 1
            if action == "left":
                col = col - 1
            if action == "right":
                col = col + 1
            return row, col
    
        def canUp(self, row, col):
            row = row - 1
            return 0 <= row <= 5
    
        def canDown(self, row, col):
            row = row + 1
            return 0 <= row <= 5
    
        def canLeft(self, row, col):
            col = col - 1
            return 0 <= col <= 5
    
        def canRight(self, row, col):
            col = col + 1
            return 0 <= col <= 5
    
        def initStateAction(self):
            """
            初始化每个状态可行动作空间
            """
            self.states_actions = dict()
            for state in self.states:
                self.states_actions[state] = []
                if state in self.terminate_states:
                    continue
                row, col = self.translateStateToRowCol(state)
                if self.canUp(row, col):
                    self.states_actions[state].append("up")
                if self.canDown(row, col):
                    self.states_actions[state].append("down")
                if self.canLeft(row, col):
                    self.states_actions[state].append('left')
                if self.canRight(row, col):
                    self.states_actions[state].append('right')
            return
    
    
        def initStatePolicyAction(self):
            """
            初始化每个状态的当前策略动作
            """
            self.states_policy_action = dict()
            for state in self.states:
                if state in self.terminate_states:
                    self.states_policy_action[state] = None
                else:
                    self.states_policy_action[state] = random.sample(self.states_actions[state], 1)[0]
            return
    
    
        def seed(self, seed = None):
            random.seed(seed)
            return [seed]
    
        def reset(self):
            """
            重置原始状态
            """
            self.current_state = random.sample(self.states, 1)[0]
    
        def step(self, action):
            """
            动作迭代函数
            """
            cur_state = self.current_state
            if cur_state in self.terminate_states:
                return cur_state, 0, True, {}
            row, col = self.translateStateToRowCol(cur_state)
            n_row, n_col = self.actionRowCol(row, col, action)
            next_state = self.translateRowColToState(n_row, n_col)
            self.current_state = next_state
            if next_state in self.terminate_states:
                return next_state, 0, True, {}
            else:
                return next_state, 0, False, {}
    
        def policy_evaluate_and_improve(self):
            """
            遍历状态空间,对策略进行评估和改善
            """
            error = 0.0 #迭代的值函数误差
            for state in self.states:
                if state in self.terminate_states:
                    continue
                action = self.states_policy_action[state]
                self.current_state = state
                next_state, reward, isTerminate, info = self.step(action)
                new_value = reward + self.gamma * self.v_states[next_state]
                new_action = action
    
                for _action in self.states_actions[state]:
                    self.current_state = state
                    next_state, reward, isTerminate, info = self.step(_action)
                    if new_value < reward + self.v_states[next_state]:
                        new_value = reward + self.gamma * self.v_states[next_state]
                        new_action = _action
                error = max(error, abs(new_value - self.v_states[state]))
                self.v_states[state] = new_value
                self.states_policy_action[state] = new_action
            return error
    
    
        def createGrids(self):
            """
            创建网格
            """
            start_x = 40
            start_y = 40
            line_length = 40
            for state in self.states:
                row, col = self.translateStateToRowCol(state)
                x = start_x + col * line_length
                y = start_y + row * line_length
                line = rendering.Line((x, y), (x + line_length, y))
                line.set_color(0, 0, 0)
                self.viewer.add_onetime(line)
                line = rendering.Line((x, y), (x, y  + line_length))
                line.set_color(0, 0, 0)
                self.viewer.add_onetime(line)
                line = rendering.Line((x + line_length, y), (x + line_length, y  + line_length))
                line.set_color(0, 0, 0)
                self.viewer.add_onetime(line)
                line = rendering.Line((x, y + line_length), (x + line_length, y  + line_length))
                line.set_color(0, 0, 0)
                self.viewer.add_onetime(line)
    
        def createTraps(self):
            """
            创建陷阱,将黄金的位置也先绘制成陷阱,后面覆盖画成黄金
            """
            start_x = 40 
            start_y = 40
            line_length = 40
            for state in self.terminate_states:
                row, col = self.translateStateToRowCol(state)
                trap = rendering.make_circle(20)
                trans = rendering.Transform()
                trap.add_attr(trans)
                trap.set_color(0, 0, 0)
                trans.set_translation(start_x + line_length * col + 20, start_y + line_length * row + 20)
                self.viewer.add_onetime(trap)
    
        def createGold(self):
            """
            创建黄金
            """
            start_x = 40 
            start_y = 40
            line_length = 40
            state = 34
            row, col = self.translateStateToRowCol(state)
            gold = rendering.make_circle(20)
            trans = rendering.Transform()
            gold.add_attr(trans)
            gold.set_color(1, 0.9, 0)
            trans.set_translation(start_x + line_length * col + 20, start_y + line_length * row + 20)
            self.viewer.add_onetime(gold)
    
        def createRobot(self):
            """
            创建机器人
            """
            start_x = 40 
            start_y = 40
            line_length = 40
            row, col = self.translateStateToRowCol(self.current_state)
            robot = rendering.make_circle(15)
            trans = rendering.Transform()
            robot.add_attr(trans)
            robot.set_color(1, 0, 1)
            trans.set_translation(start_x + line_length * col + 20, start_y + line_length * row + 20)
            self.viewer.add_onetime(robot)
    
        def render(self, mode="human", close=False):
            """
            渲染整个场景
            """
            #关闭视图
            if close:
                if self.viewer is not None:
                    self.viewer.close()
                    self.viewer = None
    
            #视图的大小
            screen_width = 320
            screen_height = 320
    
    
            if self.viewer is None:
                self.viewer = rendering.Viewer(screen_width, screen_height)
    
            #创建网格
            self.createGrids()
            #创建陷阱
            self.createTraps()
            #创建黄金
            self.createGold()
            #创建机器人
            self.createRobot()
            return self.viewer.render(return_rgb_array= mode == 'rgb_array')
    注册环境模拟类到gym
    from gym.envs.registration import register
    try:
        register(id = "GridWorld-v4", entry_point=GridWorldEnv, max_episode_steps = 200, reward_threshold=100.0)
    except:
        pass
    进行策略迭代算法的过程和模拟动画的代码
    from time import sleep
    env = gym.make('GridWorld-v4')
    env.reset()
    
    #策略评估和策略改善 
    not_changed_count = 0
    for _ in range(10000):
        error = env.env.policy_evaluate_and_improve()
        if error < 0.00001:
            break
    else:
        #打印迭代的次数
        print("iter count:" + str(_))
    
    
    #观察env到底是个什么东西的打印信息。
    print(isinstance(env, GridWorldEnv))
    print(type(env))
    print(env.__dict__)
    print(isinstance(env.env, GridWorldEnv))
    
    env.reset()
    
    for _ in range(1000):
        env.render()
        if env.env.states_policy_action[env.env.current_state] is not None:
            observation,reward,done,info = env.step(env.env.states_policy_action[env.env.current_state])
        else:
            done = True
        print(_)
        if done:
            sleep(0.5)
            env.render()
            env.reset()
            print("reset")
        sleep(0.5)
    env.close()
    动画效果

    这里写图片描述

    展开全文
  • 策略迭代与值迭代的区别

    万次阅读 多人点赞 2017-08-31 21:12:32
    策略迭代与值迭代都属于强化学习里面策略求解中的动态规划方法。其区别是什么呢? 首先看一张图片: 首先看策略迭代: 1.initialization 初始化所有状态的v(s)以及π(s)(初始化为随机策略) 2....

    策略迭代与值迭代都属于强化学习里面策略求解中的动态规划方法。其区别是什么呢?


    首先看一张图片:


    这里写图片描述

    首先看策略迭代:

    这里写图片描述


    1.initialization
    初始化所有状态的v(s)以及π(s)(初始化为随机策略)
    2.poicy evaluation
    用当前的v(s)对当前策略进行评估,计算出每一个状态的v(s),直到v(s)收敛,才算训练好了这个状态价值函数V(s)
    3.policy improvement
    既然上一步已经得到了当前策略的评估函数V(s),那么就可以利用这个评估函数进行策略改进啦。
    在每个状态s时,对每个可能的动作a,都计算一下采取这个动作后到达的下一个状态的期望价值。看看哪个动作可以到达的状态的期望价值函数最大,就选取这个动作。以此更新了π(s)
    然后再次循环上述2、3步骤,直到V(s)与π(s)都收敛。
    正如下面所说:

    In Policy Iteration algorithms, you start with a random policy, then find the value function of that policy (policy evaluation step), then find an new (improved) policy based on the previous value function, and so on. In this process, each policy is guaranteed to be a strict improvement over the previous one (unless it is already optimal). Given a policy, its value function can be obtained using the Bellman operator.


    再来看值迭代:
    1.initialization
    初始化所有状态的v(s)
    2.finding optimal value function(找到最优的价值函数)
    注意伪代码里的max,对每一个当前状态s,对每个可能的动作a,都计算一下采取这个动作后到达的下一个状态的期望价值。看看哪个动作可以到达的状态的期望价值函数最大,就将这个最大的期望价值函数作为当前状态的价值函数v(s) 循环执行这个步骤,直到价值函数收敛,就可以得到最优optimal的价值函数了
    3.policy extraction
    利用上面步骤得到的optimal价值函数和状态转移概率,就计算出每个状态应该采取的optimal动作,这个是deterministic呦。

    In Value Iteration, you start with a randon value function and then find a new (improved) value function in a iterative process, until reaching the optimal value function. Notice that you can derive easily the optimal policy from the optimal value function. This process is based on the Optimality Bellman operator.

    区别及联系


    1.策略迭代的第二步policy evaluation与值迭代的第二步finding optimal value function十分相似,除了后者用了max操作,前者没有max.因此后者可以得出optimal value function, 而前者不能得到optimal function.

    2.策略迭代的收敛速度更快一些,在状态空间较小时,最好选用策略迭代方法。当状态空间较大时,值迭代的计算量更小一些。

    展开全文
  • 值迭代网络

    2018-11-29 14:54:54
    值迭代网络论文信息1. 论文介绍2. 代码实现2.1 基础知识Model.pyTrain.pydata.py功能快捷键生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants新的甘特图功能,丰富你的文章FLowchart流程图 ...
  • 本篇博客对“有模型学习”的两种方法进行介绍,分别是策略迭代和值迭代。 我们之前已经说到了MDP可以表示成一个元组(X, A, Psa, R),我们对最优策略的求解方法自然也就与这个元组密切相关:如果该过程的四元组均为...
  • 【强化学习】值迭代与策略迭代

    万次阅读 2019-02-25 17:48:47
    在强化学习中我们经常会遇到策略迭代与值迭代,但是很多人都搞不清楚他们两个之间的区别,他们其实都是强化学习中的动态规划方法。 科普:动态规划dynamic programming简称(DP) 【强化学习】值迭代与策略...
  • 迭代算法

    万次阅读 2018-08-24 18:39:09
    迭代法也称辗转法,迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题的过程,为实现 ...在可以用迭代算法解决的问题中,至少存在一个直接或间接不断由旧递推出新的变量,称...
  • C语言实现牛顿迭代法解方程

    万次阅读 多人点赞 2016-02-09 23:28:06
    在可以用迭代算法解决的问题中,我们可以确定至少存在一个可直接或间接地不断由旧递推出新的变量,这个变量就是迭代变量。 二、建立迭代关系式 所谓迭代关系式,指如何从变量的前一个推出其下一个的...
  • Python可迭代对象,迭代器,生成器的区别

    万次阅读 多人点赞 2018-04-01 10:25:26
    本篇文章简单谈谈可迭代对象,迭代器和生成器之间的关系。 三者简要关系图 可迭代对象与迭代器 刚开始我认为这两者是等同的,但后来发现并不是这样;下面直接抛出结论: 1)可迭代对象包含迭代器。 2)如果一个...
  • 1.简单理解牛顿迭代法 举例:求出非负实数x的平方根的近似。 解:假设我猜测x的平方根是y。 通过对y的不断迭代赋值:y =(y+x/y)/2,求出趋近于x的平方根的近似,而该近似与2的平方根必定有误差。 (我们...
  • Matlab 数值计算----牛顿迭代

    万次阅读 多人点赞 2017-04-09 12:05:44
    Newton.m函数 function [x_star,index,it] = Newton(fun,x,ep,it_max) %求解非线性方程的牛顿法 %第一个分量是函数值,第二个分量是导...% it_max为最大迭代次数,缺省为100 % x_star为当迭代成功时,输出方程的根 %
  • 当图像由暗色背景和较亮物体组成时,从背景中提取出物体的方法是选择一个将两种灰度分开的阈值T,即f(x,y)> T 的任何点(x,y)称 为一个对象点,否则将该点称为背景点。那么,分割后的图像g(x,y)由以下式子给出: ...
  • MATLAB学习笔记之牛顿迭代

    千次阅读 2019-04-20 22:54:21
    牛顿迭代法的公式如下 给定函数f(x)和近似根x0,由上式逐步逼近根;直到误差小于给定; 代码如下: function x1=newton(fun,x0,delta) syms x;%定义符号变量x,用于求导和代入 df=diff(fun(x));%对f(x)进行...
  • 迭代最优化求最优

    千次阅读 2018-04-04 14:29:06
    最后,综合之前提到的所有子项,求和,就得到了能量函数。当求出能量函数E(x)的最小值时,就得到了每一帧...(也就是初值)(3)如何迭代计算该最优 (4)迭代次数对最优有没有影响(5)迭代到最后是否一定得到最优...
  • 牛顿迭代法解非线性方程(组)

    千次阅读 2012-10-22 07:25:36
    1、牛顿迭代思想 借助对函数f(x)=0做泰勒展开而构造的一种迭代格式 将f(x)=0在初始x0做泰勒展开: 当h趋近于0时,在[x,x+h]区间内用直线表示曲线,故而去展开式的线性部分做f(x)≈0的近似 则即得 则得到...
  • 梯度下降法迭代结束的条件

    万次阅读 2015-01-09 17:05:54
    梯度的方向总是函数值越来越大的方向,如果是求极大,沿着梯度的方向迭代接口;如果是求极小,沿着梯度相反的方向迭代即可,即梯度下降法。 梯度下降法(梯度上升法应该也适用)迭代结束的条件,常用的有两种: ...
  • print('练习:请使用迭代查找一个list中最小和最大,并返回一个tuple:')def findMinAndMax(L): if L !=[]: (min,max)=(L[0],L[0]) for x in L: if max&lt;x: max=x if min&gt;x: min=x ...
  • 图像的阈值分割(迭代法选择阈值)

    万次阅读 多人点赞 2015-07-27 14:46:36
    迭代法阈值选择算法是对双峰法的改进,他首先选择一个近似的阈值T,将图像分割成两个部分,R1和R2,计算出区域R1和R2的均值u1和u2,再选择新的 阈值T=(u1+u2)/2; 重复上面的过程,知道u1和u2不在变化为止, 详细...
  • c++ 里面的map容器的迭代

    千次阅读 2018-04-17 13:54:14
    c++ 里面的map容器的迭代器里面 有个first 和 second 例如 map&lt;string, int&gt; m; m["one"] = 1; map&lt;string, int&gt;::iterator p = m.begin(); p-&gt;first; // 这个是 ...
1 2 3 4 5 ... 20
收藏数 592,308
精华内容 236,923
关键字:

值迭代