13. 强化学习编程实验1-在格子世界中寻宝

1.实验目的

• 了解强化学习算法的基本框架；
• 掌握策略迭代算法的编程技术；
• 掌握值迭代算法的编程技术；
• 理解策略迭代与值迭代的异同；

2.任务描述

有一个网格，它是1个含有$n$行$n$列单元格的方阵，方阵中的单元格$(i,j)$(第$i+1$行,第$j+1$列,$0\le i,j\le n?1$）有宝藏，有1个智能体，当前所处的位置为$(a,b)$,$0\le a,b\le n?1$,该智能体可上下左右移动，每次只能从其当前单元格移动1步，到达与当前单元格相邻的单元格（若当前单元格处于方阵边缘，且智能体移动时超出方阵范围，则智能体只能回到当前单元格）。该智能体一开始不知道宝藏的准确位置，也不知道网格边界有多大，它只能观测到其当前位置和当前位置是否为宝藏所在处，并从上下左右移动四个行为空间中选取1个动作，选取该动作后转向的下一个网格由环境决定。请你设计一套算法，为该智能体找出最优移动方向序列，使得该智能体能以最短的时间找到宝藏。

要求：
程序运行时，输入方阵行、列数$n$、宝藏位置$(i,j)$、智能体当前位置$(a,b)$,即可按如下格式显示出规划好最优行为序列：
左→右→右→左→$?$
并以可视化的方式显示出路径。

3.任务分析

任务分析要回答以下问题：

• 待求解的问题是多步决策问题否？若不是，则不宜采用强化学习算法解决，若是，则继续回答下述问题
• 环境是什么？环境的状态具有马尔科夫性吗？是否涉及行为选择？如果回答是，则继续确定如下问题答案
• 环境的状态如何表示？环境的状态空间是什么？智能体的行为（动作）如何表示，智能体的行为空间是什么？环境的状态转移函数如何表示？环境的立即回报如何表示？

3.1 待求问题是多步决策问题否

智能体每一步都需要作出行为选择（向上、右、下还是向左移动），因此，这是一个多步决策问题。

3.2 问题求解过程是一个马尔科夫决策过程

智能体每走一步前，要确定选取何种移动方向（行为），智能体未来的位置与当前位置有关，与历史位置无关，所以满足马尔科夫性。智能体每一步都需要作出行为选择，因此，这是一个多步决策问题。智能体在当前状态下找到宝藏，就能得到1个立即回报，找不到回报就为0。我们希望从当前位置位置开始尽早找到宝藏，这说明找到宝藏所需的步骤越多，得到的回报打的折扣越多）。
故而：- 上述问题可以用马尔科夫决策模型$<S,A,P,R,\gamma >$描述

3.3 状态空间S的确定

这个环境是1个网格世界，由于智能体以找到宝藏为目标，而能否在智能体作出一个行为响应（上下作用移动1步）后找到宝藏，与智能体所处位置有关，因此，智能体所处位置可以看做是环境的状态，状态决定了其能否在下一步找到宝藏。
为此，需要一种数据结构描述该状态，最适合的数据结构当属列表了。假设列表对象为S，则：
S[k]表示索引号为k的状态取值，这个值的数据类型，可以设为元组(a,b)，a，b分别对应单元格的行、列索引号,故：
只要知道状态的索引号k，这个状态所代表的意义，即智能体所在位置就知道了，即为S[k]。

3.4 动作空间A的确定

与状态空间类似，其数据结构也可以用列表描述，假设为列表A，则A[k]表示索引号为k的动作表示，为了后续编程方便
，元素值用执行该动作后的智能体的位置增量表示，即：
A=[[-1,0],[0,1],[1,0],[0,-1]]，各元素依次表示向上、向右、向下、向左移动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$的确定

本实验设$\gamma =1$。
问题：设为1表示未来回报都不打折，这样能评估越早找到宝藏越好这一要求吗？
答案：可以。
证明：
假设从当前时间步$t$(当前时间步的立即回报不算）开始，到第$K$步找到宝藏，则累积回报为：
$$G_t=\sum _{k=0}^{K?1}{\gamma }^k{R}_{t+k+1}$$
将$\gamma =1,R_{t+m}=\{\begin{array}{l}?10<m<K\\ 0m=K\end{array}$代入上式，得
$$G_t=R_{t+1}+?+R_{t+K}=1?K$$
可见，找到宝藏的时间越长，即K越大，累积回报$G_t$越小，因此，当立即回报按照上式取值,且$\gamma =1$时，能累积回报能反映越早找到宝藏越好的需求。
思考：若$R_{t+m}=\{\begin{array}{l}00<m<K\\ 1m=K\end{array}$，即找到宝藏时，立即回报为1，没有找到立即回报为0，此时，还能取$\gamma =1$吗？为什么不能？

4. 编程架构

本实验涉及到的程序的设计，采用面向对象架构。
为此，首先分析，程序运行中，有哪些对象？这些对象属于哪些类？然后定义类，最后在主程序中创建类对象，调用对象方法，解决问题。

4.1 程序中有哪些对象和类

根据强化学习原理，可知，在强化学习环境中，有两个最基本的对象，分别为：

• 环境
• 智能体

4.2 环境类的设计

4.2.1 采用面向抽象编程架构

面向抽象编程的本质体现为：针对一组对外提供相同服务接口的具体类，实施如下工作：
（1）设计出能体现这组具体类对外通用服务接口的抽象类；
（2）从抽象类中派生出一个个具体类；
（3）使用具体类解决问题时，把具体类对象看作是抽象类类型进行编程。
面向抽象编程的优势：具体类的内部实现（具体解决方案细节）的更改，不影响客户对服务的调用，有利于程序的维护。因为客户调用服务时，是面向稳定不变的接口协议（抽象方法）来实施的。
回到本实验的具体问题，我们看到，网格世界环境，可以通过一个具体类来实现，但如果从更广泛的意义来看，网格世界环境具体类，不过是可以用马尔科夫决策过程$S,A,R,P,\gamma$来描述的一个典型例子罢了,因此，本实验的环境类可以采用面向抽象编程方法加以实现：
（1）设计一个抽象类MdpEnv，向智能体提供访问MDP环境动力学特性的一般接口；
（2）网格世界环境等具体MDP环境类，都派生自MdpEnv；
（3）智能体算法设计，面向MdpEnv编程。
个人评述：邹伟教授等人编著的一书的示例代码，没有很好地设计编程架构，在代码的可维护性上稍有不足。

4.2.2 抽象类MdpEnv的设计

4.2.2.1 抽象方法设计

无论哪一个派生自抽象的马尔科夫决策环境类MdpEnv，都需要提供类似于以下的（抽象）方法（或接口）：

• get_state_space()->List[Any]:返回状态空间,Any表示任意数据类型，环境类的具体类可以用实际类型替代
• get_action_space()->List[Any]:返回行为空间
• get_state_trans_prob(i,j,k):返回状态转移概率$P_{s_i{s}_j}^{a_k}$
• get_immediate_return(i,k):返回立即回报期望$R_{s_i}^{a_k}$
• get_gamma():返回折扣系数

4.2.2.2 具体方法设计

为了给智能体（解决环境对象类型为MdpEnv的决策问题的算法）提供更好的服务，MdpEnv还可以提供一些具体方法，从而可以使智能体方便快捷地使用numpy数组操作：

• getP()->NDArray[float]:返回状态转移概率数组（维度为(nA,nS,nS）,nA，nS分别为行为空间长度，状态空间长度）
• getR()->NDArray[float]:返回立即回报数组（维度为(nS,nA)）
  这两个具体方法，都是建立在调用上面的抽象方法基础上，返回的是多维数组，这两个多维数组综合描述了马尔科夫决策环境的动力学模型，只需要通过索引，即可实现高效访问（当然牺牲了一定的内存空间，但这是值得的）
  getP(),getR()都可以调用前面的几个方法实现。
  因此，完全可以先定义一个描述马尔科夫决策过程（MDP）的抽象类MdpEnv，GridWorld继承自该抽象类，实现该抽象类的方法即可，以后若是有其他的MDP具体环境，只需要实现这些方法即可。

4.3 智能体类的设计

智能体，代表了强化学习算法。一个具体的智能体，代表了一类具体的强化学习算法。以MDP（马尔科夫决策过程）五元组已知的情况为例，我们知道，目标有最常用的两种算法，即：策略迭代算法和值迭代算法，这两类算法对应两个智能体，这两个智能体具有共同的对外提供服务的接口，因而智能体类的设计，仍然可以采用面向抽象编程架构：
（1）设计一个名为MdpAgent的抽象类
（2）策略迭代算法（用类名PolicyAgent表示）从MdpAgent类派生并实现它
（3）值迭代算法（用类名ValueAgent表示）从MdpAgent类派生并实现它

4.3.1 MdpAgent类的设计

它应该提供类似如下的抽象方法（接口）：

• train():通过训练更新策略矩阵$P_l$(该类的属性之一），$P_l[i,k]$表示$\pi (a_k|s_i)$
• get_action(i:int)->int:根据当前状态$a_i$，基于当前的策略矩阵policy，输出动作$a_k$的索引$k$
  该类的构造函数的设计也别有一番风味，以下是我的设计：

from abc import ABC,abstractmethod
from np.typing import NDArray
class MdpAgent(ABC):
    def __init__(self,env:MdpEnv):
        self.env = env
        self.S = self.env.get_state_space()
        self.A = self.env.get_action_space()
        self.P = self.env.getP()
        self.R = self.env.getR()
        self.nS = len(self.S)
        self.nA = len(self.A)
        # 策略矩阵
        self.Policy = np.ones((self.nS,self.nA),dtype=float)
    @abstractmethod
    def train(self)->NDArray[float]:
        pass
    
    def get_action(self,i:int):
        return np.random.choice(self.nA,p=self.Policy[i])

4.3.2 PolicyAgent与ValueAgent的设计

都从MdpAgent派生，只需要实现train方法即可。如何实现？
就是利用前面介绍的策略迭代算法和值迭代算法编写具体代码。
这里的代码共有兴趣的读者自己实现。我的看法是，照抄他人代码而不去独立思考，是不可能对算法进行优化的。

5. 最终程序设计运行结果画面

最终程序包括了主程序
这里给出我的最终结果画面（用到了turtle库可视化最终策略矩阵，向该库的作者（Wally Feurzeig，Seymour Papert和Cynthia Solomon）致敬，它让我的小孩对计算机产生了兴趣）

还原各位读者在本站的git开源库中展示各自的代码。