首页 > 编程语言 >经典强化学习算法:分层强化学习算法—options算法2(理解篇)

经典强化学习算法:分层强化学习算法—options算法2(理解篇)

时间:2024-09-29 11:05:01浏览次数:6  
标签:option 学习 算法 状态值 强化 options



论文地址:

https://people.cs.umass.edu/~barto/courses/cs687/Sutton-Precup-Singh-AIJ99.pdf



例子:

image

image

这是一个寻路问题,该问题使用强化学习算法解决,准确的来说是使用“表格表示的强化学习算法中的规划算法”来进行解决的;之所以没有说是使用规划算法来说是因为这里使用了学习型算法,即强化学习算法,虽然只是使用表格记录的方式,但是依旧使用了强化学习算法的形式进行;该问题的解决中对每个方格的状态值表示为V(s),整体使用策略迭代或值迭代的强化学习的规划算法来解决。


image

在这个问题中,agent有四个方向可以选择走,但是每次走只有2/3的概率会正确执行,1/3的概率会随机走其他三个方向中的一个;需要注意的是,agent的每一步行走的reward都是零,也就是说这个问题建模后形成的强化学习模型是一个稀疏模型。


options算法的核心内容:

image

image

image


options算法在计算过程中的各个位置在表格中的状态值的变化过程示意图:(该问题就是计算所有房间的位置到到达初始位置的状态值V(state)的值大小)

其中下图方块中涂黑的面积大小表示对应的状态值V(s)的值的大小,最大时为1,完全空白为0。

下图中上一行中options的动作为单步,下一行中的options的动作为multi-steps。

multi-steps的options动作指的就是在一次状态值更新时是对划分后问题的一整个option动作覆盖的空间进行计算,下图中则是对整个房间(room)进行更新计算。

image



可以看到,上面的每个room有两个通道(两个空白格),这两个空白格(通道)可以分别作为一个option的target,除了target之外的其他空格都为可行区域(可以作为option的起始点),也就是所对原始任务进行划分后的每个room任务都是可以有两个option的,每个option的终点分布对应room边缘的target hallway。

给出一个room的其中一个option的状态值的示意图(该option的target为右侧边缘的空格,另一个option的target为下侧边缘的空格):

image





options算法的学习规则:(参数更新的具体方式)

给出一个状态的option示意图:

假设下图中红色状态为s,绿色状态为 \(s^,\)。

红色状态在下图中的option的Q值记作Q(s, o),绿色状态的Q值记作Q(\(s^,\), \(o^,\))。

红色状态关于绿色状态的一次采样后的Q值更新具体为:

image

image

image

image

image

image



使用options方法来进行动态规划计算的一些不足:

image

其中,最为注意的就是在使用options进行动态规划的话并不一定能保证加快计算(加快收敛);一般情况下动态规划时初始所有状态的状态V值为0,但是如果使用乐观的初始化方式(optimistic)那么就是在初始化时将所有的状态V值都初始化为一个较大的数值,比如为100,那么使用options这种multi-steps分层的方法反而会减慢值迭代的动态规划算法的收敛速度。



PS:

个人感觉,这个分层强化学习算法中的经典options算法其实和分层 \(A^*\) 算法很像,其基本思想是一致的,如果有读者不是很难理解这个options算法可以先去读“分层 \(A^*\) 算法”。

本文的options算法本质上是“表格型强化学习算法”。

分层强化学习算法options其本质就是对问题进行分层划分。

本文算法的解决方法是使用表格记录每个位置的状态值V(s)。



由于options发表的较早,20多年前发表的,因此这篇文章大篇幅谈的是动态规划算法,即如何使用options方法来提升动态规划算法的性能,然后才谈了options算法在learning算法上的一些应用。




标签:option,学习,算法,状态值,强化,options
From: https://www.cnblogs.com/xyz/p/18439180

相关文章

  • 深度DFS 和 广度BFS搜索算法学习
    深度DFS和广度BFS搜索算法学习 目录广度优先的动态图深度优先的动态图广度和深度的具体步骤深度和广度的应用场景 图的两种遍历方式:深度优先遍历(DFS——DepthFirstSearch)广度优先遍历(BFS——BreathFirstSearch)图的遍历算法里,处理临时数据,依赖两个抽象......
  • 使用表格型强化学习算法解决寻路问题的两种建模方式
    寻路问题示意图:(只有目标点形式的示意图)寻路问题示意图:(带有目标点和起始点形式的示意图,红色位置为起始点,黑色位置为目标点)解决强化问题首先需要建模,只有把目标问题建立为强化学习模型后才能使用强化学习算法进行解决;在这一过程中我们在建立强化学习模型(指定环境,状态迁移函......
  • 关于聚类算法的一份介绍
    在这篇文章中我将介绍无监督算法中“聚类”部分的知识,其中关于K均值聚类、层次聚类、密度聚类部分我将各附上一份实际运用的代码,而其余的像学习向量量化、高斯混合聚类部分则只是简单介绍下概念。一、关于聚类首先我先简单介绍下聚类算法有关的东西。1.1聚类任务我们知道......
  • 搜索:如何用 A*搜索算法实现游戏中的寻路功能?
    搜索:如何用A*搜索算法实现游戏中的寻路功能?在游戏开发中,寻路功能是一个非常重要的部分。它可以让游戏中的角色自动找到从一个位置到另一个位置的最佳路径。A搜索算法是一种常用的寻路算法,它可以在复杂的地图环境中快速找到最短路径。本文将详细介绍如何用A搜索算法实现游......
  • 算法实战:剖析 Redis 常用的数据类型对应的数据结构
    算法实战:剖析Redis常用的数据类型对应的数据结构Redis是一个非常流行的内存数据库,它提供了多种数据类型,每种数据类型都有其特定的数据结构支持。了解这些数据结构对于深入理解Redis的工作原理和优化使用非常重要。本文将剖析Redis常用的数据类型对应的数据结构,并通......
  • 代码随想录算法训练营Day03-链表 | LC203移除链表元素、LC707设计链表、LC206反转链表
    目录前言LeetCode203.移除链表元素思路完整代码LeetCode707.设计链表思路完整代码LeetCode206.反转链表思路完整代码今日总结前言拖延症犯了,哈哈,拖了一天LeetCode203.移除链表元素给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val......
  • LEO卫星网络路由算法介绍(一)——概述
    0.写在前面    笔者学生课题方向涉及卫星路由算法的设计,因此通过阅读相关文献,将学习的内容总结,作为学习笔记记录,如有不对之处欢迎大佬们批评指正。1.背景    6G通信体制下畅想未来网络可以万物互联并提供低延迟、高可靠性数据传输能力来满足用户的多重业务......
  • 【图计算算法‌】广度优先搜索(BFS)算法
    目录一、广度优先搜索算法概述1.1算法原理1.2算法步骤1.3算法特点二、广度优先搜索算法优缺点和改进2.1 广度优先搜索算法优点2.2  广度优先搜索主算法缺点2.3  广度优先搜索算法改进三、广度优先搜索算法编程实现3.1  广度优先搜索算法C语言实现3.2  ......
  • 基于秃鹰算法优化的最小交叉熵图像多阈值分割
    智能优化算法应用:基于秃鹰算法优化的最小交叉熵图像多阈值分割文章目录智能优化算法应用:基于秃鹰算法优化的最小交叉熵图像多阈值分割1.前言2.最小交叉熵阈值分割原理3.基于秃鹰优化的多阈值分割4.算法结果:5.参考文献:6.Matlab代码摘要:本文介绍基于最小交叉熵的图像......
  • 代码随想录算法训练营第三天|203.移除链表元素,707.设计链表,206.反转链表
    203.移除链表元素文章链接:https://programmercarl.com/0203.移除链表元素.html#算法公开课视频讲解:https://www.bilibili.com/video/BV18B4y1s7R9题目出处:https://leetcode.cn/problems/remove-linked-list-elements/卡哥在这里讲解了为什么要使用虚拟头节点,以及使用和不使......