文章目录
- 1.实验目的
- 2.任务描述
- 3.任务分析
- 3.1 待求问题是多步决策问题否
- 3.2 问题求解过程是一个马尔科夫决策过程
- 3.3 状态空间S的确定
- 3.4 动作空间A的确定
- 3.5 状态转移概率P的确定
- 3.6 立即回报R的确定
- 3.7 折扣 γ \gamma γ的确定
- 4. 编程架构
- 4.1 程序中有哪些对象和类
- 4.2 环境类的设计
- 4.3 智能体类的设计
1.实验目的
- 了解强化学习算法的基本框架;
- 掌握策略迭代算法的编程技术;
- 掌握值迭代算法的编程技术;
- 理解策略迭代与值迭代的异同;
2.任务描述
有一个网格,它是1个含有 n n n行 n n n列单元格的方阵,方阵中的单元格 ( i , j ) (i,j) (i,j)(第 i + 1 i+1 i+1行,第 j + 1 j+1 j+1列, 0 ≤ i , j ≤ n − 1 0\le i,j\le n-1 0≤i,j≤n−1)有宝藏,有1个智能体,当前所处的位置为 ( a , b ) (a,b) (a,b), 0 ≤ a , b ≤ n − 1 0\le a,b\le n-1 0≤a,b≤n−1,该智能体可上下左右移动,每次只能从其当前单元格移动1步,到达与当前单元格相邻的单元格(若当前单元格处于方阵边缘,且智能体移动时超出方阵范围,则智能体只能回到当前单元格)。该智能体一开始不知道宝藏的准确位置,也不知道网格边界有多大,它只能观测到其当前位置和当前位置是否为宝藏所在处,并从上下左右移动四个行为空间中选取1个动作,选取该动作后转向的下一个网格由环境决定。请你设计一套算法,为该智能体找出最优移动方向序列,使得该智能体能以最短的时间找到宝藏。
要求:
程序运行时,输入方阵行、列数 n n n、宝藏位置 ( i , j ) (i,j) (i,j)、智能体当前位置 ( a , b ) (a,b) (a,b),即可按如下格式显示出规划好最优行为序列:
左→右→右→左→ ⋯ \cdots ⋯
并以可视化的方式显示出路径。
3.任务分析
任务分析要回答以下问题:
- 待求解的问题是多步决策问题否?若不是,则不宜采用强化学习算法解决,若是,则继续回答下述问题
- 环境是什么?环境的状态具有马尔科夫性吗?是否涉及行为选择?如果回答是,则继续确定如下问题答案
- 环境的状态如何表示?环境的状态空间是什么?智能体的行为(动作)如何表示,智能体的行为空间是什么?环境的状态转移函数如何表示?环境的立即回报如何表示?
3.1 待求问题是多步决策问题否
智能体每一步都需要作出行为选择(向上、右、下还是向左移动),因此,这是一个多步决策问题。
3.2 问题求解过程是一个马尔科夫决策过程
智能体每走一步前,要确定选取何种移动方向(行为),智能体未来的位置与当前位置有关,与历史位置无关,所以满足马尔科夫性。智能体每一步都需要作出行为选择,因此,这是一个多步决策问题。智能体在当前状态下找到宝藏,就能得到1个立即回报,找不到回报就为0。我们希望从当前位置位置开始尽早找到宝藏,这说明找到宝藏所需的步骤越多,得到的回报打的折扣越多)。
故而:- 上述问题可以用马尔科夫决策模型 < S , A , P , R , γ > <S,A,P,R,\gamma> <S,A,P,R,γ>描述
3.3 状态空间S的确定
这个环境是1个网格世界,由于智能体以找到宝藏为目标,而能否在智能体作出一个行为响应(上下作用移动1步)后找到宝藏,与智能体所处位置有关,因此,智能体所处位置可以看做是环境的状态,状态决定了其能否在下一步找到宝藏。
为此,需要1个量描述该状态,有两种描述方法:
(1)用整数对 ( a , b ) (a,b) (a,b)联合描述状态,a,b分别对应单元格的行、列索引号;
(2)用1个整数描述状态,该整数 z z z和单元格所在的行索引号 a a a、列索引号 b b b满足如下关系:
z = n a + b a = z / / n b = z − n a \begin{align*} z&=na+b\\ a&=z//n\\ b&=z-na \end{align*} zab=na+b=z//n=z−na
/ / ‾ − \underline{//}- //−整除求商
本任务选择方法2描述状态,则
S = { 0 , 1 , 2 , ⋯ , n 2 − 1 } S=\{0,1,2,\cdots,n^2-1\} S={0,1,2,⋯,n2−1}
S t = k S_t=k St=k:智能体当前位置为从上至下,从左至右计数的第 k + 1 k+1 k+1个单元格
3.4 动作空间A的确定
A = { 0 , 1 , 2 , 3 } A=\{0,1,2,3\} A={0,1,2,3}:0~3依次表示向上、向右、向下、向左移动1步
3.5 状态转移概率P的确定
在给定状态s和行为a下,状态转移到其他每个状态(包括自身)的概率都是确定的,只有1个为1,其他为0。
例如,当单元格当前位置处于方阵中间时,采取动作A[0],转移到上方相邻单元格的概率就是1,转移到其他相邻单元格的概率就是0,采取其他动作转到下一个状态的概率,情况都类似;当单元格当前位置处于方阵边缘时,如左边缘时,向左移动,后续状态将保持为原先状态。
综上所述,状态转移概率可以通过一个函数实现。
3.6 立即回报R的确定
很显然,只要某个状态不是最终状态(宝藏所在处),立即回报都可以设为0,反之,立即回报设为1,也可以把宝藏所在处状态设为0,其他位置对应的状态立即回报设为-1。总之,要确保当智能体找到宝藏时,获得的立即回报值高于未找到宝藏时状态的立即回报,而且,只要没有找到宝藏,立即回报都应该是一样的。
本实验中,当智能体所处位置不是宝藏所在处,立即回报设为-1,反之,设为0。
3.7 折扣 γ \gamma γ的确定
本实验设 γ = 1 \gamma = 1 γ=1。
问题:设为1表示未来回报都不打折,这样能评估越早找到宝藏越好这一要求吗?
答案:可以。
证明:
假设从当前时间步 t t t(当前时间步的立即回报不算)开始,到第 K K K步找到宝藏,则累积回报为:
G t = ∑ k = 0 K − 1 γ k R t + k + 1 G_t=\sum_{k=0}^{K-1}\gamma^kR_{t+k+1} Gt=k=0∑K−1γkRt+k+1
将 γ = 1 , R t + m = { − 1 0 < m < K 0 m = K \gamma =1,R_{t+m}=\begin{cases} -1\quad 0<m<K\\ 0 \quad m=K \end{cases} γ=1,Rt+m={−10<m<K0m=K代入上式,得
G t = R t + 1 + ⋯ + R t + K = 1 − K G_t=R_{t+1}+\cdots+R_{t+K}=1-K Gt=Rt+1+⋯+Rt+K=1−K
可见,找到宝藏的时间越长,即K越大,累积回报 G t G_t Gt越小,因此,当立即回报按照上式取值,且 γ = 1 \gamma =1 γ=1时,能累积回报能反映越早找到宝藏越好的需求。
思考:若 R t + m = { 0 0 < m < K 1 m = K R_{t+m}=\begin{cases} 0\quad 0<m<K\\ 1 \quad m=K \end{cases} Rt+m={00<m<K1m=K,即找到宝藏时,立即回报为1,没有找到立即回报为0,此时,还能取 γ = 1 \gamma =1 γ=1吗?为什么不能?
4. 编程架构
本实验涉及到的程序的设计,采用面向对象架构。
为此,首先分析,程序运行中,有哪些对象?这些对象属于哪些类?然后定义类,最后在主程序中创建类对象,调用对象方法,解决问题。
4.1 程序中有哪些对象和类
根据强化学习原理,可知,在强化学习环境中,有两个最基本的对象,分别为:
- 环境
- 智能体
4.2 环境类的设计
本程序中的环境对象为格子世界,我给它命名为:GridWorld
很显然,单独为这个具体的环境对象设计一个具体类,通用性不足,因为还有其他的具体类(对应其他的环境),这类环境都可以用马尔科夫决策过程描述,即:它们都需要向用户提供几个
重要的方法:
get_state_space:返回状态空间
get_action_space:返回行为空间
get_state_trans_prob:返回状态转移概率
get_immediate_return:返回立即回报期望
get_gamma:返回折扣系数
因此,完全可以先定义一个描述马尔科夫决策过程(MDP)的抽象类MdpEnv,GridWorld继承自该抽象类,实现该抽象类的方法即可,以后若是有其他的MDP具体环境,只需要实现这些方法即可。
4.3 智能体类的设计
对于马尔科夫决策过程,智能体都需要通过环境的已知信息,即MDP五元组 < S , A , P , R , γ > <S,A,P,R,\gamma> <S,A,P,R,γ>,学到最优策略 π ( a ∣ s ) \pi(a|s) π(a∣s),因此,各种算法(智能体)都有一个共同的抽象类:MdpAgent
它应该提供方法:
- learn:学习MdpEnv环境对象,并返回优化的策略
- find_optimum_action:根据当前状态,基于当前学到的策略,输出最优动作
策略迭代算法和值迭代算法,都可以看做是智能体,它们都从MdpAgent派生,只需要实现以上抽象方法即可。
好了,接下来就是发挥主动能动性,根据上述基本设计思想实现python程序了。暂时写到这里…