使用Q-Learning 和Sara算法解决GridWorld炸弹环境，分为两个类：gridWorld.py和Agent.py:
环境类：继承gym.Wrapper，主要实现了render（显示每次的地图）。step（和环境交互，计算奖励值）
Agent类：包括两种算法，主要实现了learn（学习方法，每次更新Q-table）predict（根据输入的观察值，预测输出的动作）。sample(根据输入的观察值，采样输入的动作)
整体步骤为，首先根据grdiWordl创建出环境，每次机器人根据环境选择动作并更新。
使用Q-Learning 和 Sara 解决GridWorld 炸弹环境
代码链接
一.实验原理
1.1 Q-learning 和 Sara 的异同
1.1.1 相似之处
- 两种算法本质都是通过策略迭代得到最优策略。
- 两种算法都是基于时序差分法进行更新，可以看作蒙特卡洛仿真和动态规划的结合。
- 在选择策略时，都使用 $\epsilon - greedy$ 算法，即以$\epsilon$ 的概率选择使得动作-值函数最大的动作，以$1-\epsilon$的概率随机选择。
1.1.2 不同之处
Q-Learning是强化学习算法中value-based的算法，Q即为Q（s,a）就是在某一时刻的 s 状态下(s∈S)，采取 动作a (a∈A)动作能够获得收益的期望，环境会根据agent的动作反馈相应的回报reward r，所以算法的主要思想就是将State与Action构建成一张Q-table来存储Q值，然后根据Q值来选取能够获得最大的收益的动作。
Q-learing 算法可用如下伪代码表示：
Sara和Q-Learning基本一致，可用如下伪代码表示：
从两个算法的伪代码可以看出，两者的最大区别在于Q-table的更新方式不同：
Q-Learning更新Q值的公式为：
$Q(S_t,A_t) \leftarrow Q(S_t, A_t) + \alpha[R_{t+1}+\gamma \underset{a}{max}Q(S_{t+1},a)-Q(S_t,A_t)]$
Sara更新Q值的公式为：
$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]$
- Q-learning：在状态$S_t$下，根据 $\epsilon-greedy$策略选择动作$A_{t}$ 到达$S_{t+1}$后，利用状态$S_{t+1}$下的最佳Q值$Q(S_{t+1},a)$来更新$Q(S_t,A_{t})$，但并不真正采取动作$(S_{t+1},a)$ 。更新Q-table用到的值有$
- Sara: 在状态$S_t$下,根据 $\epsilon-greedy$ 策略选择动作$A_t$到达$S_{t+1}$之后，选择最大的$(S_{t+1},a)$并真正采取该动作。更新Q-table用到的值有$
- Q−learning选取动作和更新Q表值的方法不同，而Sarsa选取动作和更新Q表值的方法相同。Q-Learning算法，先假设下一步选取最大奖赏的动作，更新值函数。然后再通过ε-greedy策略选择动作。Sarsa算法，先通过ε-greedy策略执行动作，然后根据所执行的动作，更新值函数。
- 可以看出Q-Learning使用的更新方法更激进，即直接选择下一个状态下的最大值进行更新。而Sara算法更保守，基于现有的步骤进行更新，整体上来说Sara更偏向于避免陷阱。
1.2 算法图解
两种算法的基本流程出了训练过程中更新参数的方法不同，其余流程相同。可用下图表示：
二.算法实现
整体分为环境类和代码类。
2.1 环境
定义类FronzenLakeWapper(gym.Wrapper)，主要实现以下接口：
draw_box: 绘制一个坐标处的矩形框，并做以下填充：
起点：红色
出口：黄色
- 炸弹：黑色
- 平地：白色
move_player(self, x, y):将智能体移动到对应的坐标
render(self):渲染一帧图像
step(self,action):根据传入的动作，计算智能体的新坐标，以及对应的返回值。为了训练智能体避免炸弹并且尽量减少路径长度，将奖励值设置如下：
- 起点或空地:
reward = -2 - 炸弹：
reward = -20 - 终点：
reward = 10
2.2 智能体
根据使用的算法不同，分别创建类QLearningAgent(object) 和 SaraAgent(object) 。
两个类有以下相同接口：
sample(self, obs)：根据输入的观察值，使用$\epsilon-greedy$ 策略选择动作。
predict(self, obs): 根据输入的观察值，预测输出的动作值。
save(self, npy_file): 将Q表保存到文件中。
restore(self, npy_file): 从文件中读取Q表数据。
根据Q表更新公式的不同，实现不同的学习函数。
QLearningAgent.learn(self,obs,action,next_obs,reward,done):根据当前状态和动作以及下个状态更新Q表。
QLearningAgent.learn(self,obs,action,next_obs,next_action,reward,done):根据当前状态和动作以及下个状态和下个动作更新Q表。
三.实验结果及分析
3.1 输入
使用文件输入，在input.txt中输入矩阵，例如下图，输入一个$7\times 17$ 的矩阵，其中S表示起点，F表示空地，H表示炸弹，G表示出口。
3.2 可视化环境及移动轨迹
运行结果，使用乌龟模拟机器人，从起点出发到达终点需要六步，分别如下：
3.3 学习参数对策略收敛的影响
训练过程中，当连续五局游戏都成功且总奖励值不变时，认为模型已经收敛
3.3.1 Q-Learning 算法
模型的收敛速度随着回报衰减系数变化如下图：
从图中可以看出，随着gamma值的增大，模型收敛速度越来越快，从Q-Learning的Q表更新公式可以看出，gamma值越大，更新程度越大，所需的训练次数也越小。
对各个gmma值下的收敛模型进行1000次测试，所得的成功率和平均步数如下：
从图中可以看出，当gamma=0.6时，模型的成功率最高并且平均步数最少。原因可能是：gamma值教小时，无法充分学习每步的未来收益，而gamma值过大时，模型采取的策略过于激进，可能出现过拟合。
3.3.2 Sara 算法
模型的收敛速度随着回报衰减系数变化如下图：
可以看出，整体来说，随着gamma值的变大，模型收敛所需的训练次数逐渐减少。但gamma从0.1变为0.2时，训练次数显著增加，可能是gamma=0.1时模型陷入局部最优。
对各个gmma值下的收敛模型进行1000次测试，所得的成功率和平均步数如下：
从图中可以看出，当 gamma=0.7时，模型的成功率最高并且平均步数最少，原因可能是取一个适中的gamma值更能平衡当前收益和未来收益。同时可以看出，当gamma值由0.1变为0.2时，平均步数显著减少，可能是gamma=0.1时模型陷入局部最优。
3.4 探究模型鲁棒性
选取五个规模的地图，分别如下：
分别统计训练到收敛所需回合数以及成功率和平均步数(测试1000回合)：
| 地图规模 | 收敛所需回合数 | 成功率 | 平均步数 |
|---|---|---|---|
| $2\times2$ | 44 | 97.2% | 2.17 |
| $4\times4$ | 48 | 91.5% | 2.22 |
| $6\times6$ | 403 | 93% | 3.50 |
| $8\times8$ | 115 | 96.4% | 3.32 |
| $10\times10$ | 998 | 91.6% | 6.50 |
从结果可以看出，随着地图的变大，均能保持较高的准确率，说明模型鲁棒性较高。
3.5 可视化Q表
从3.3可以看出，Q-learning算法效果较好，下面以Q-learning算法为例，当gamma=0.6时，每训练500个episode输出一次Q表中间结果：
可以看出Q表中部分坐标的值始终为0（这些点包括炸弹，出口，以及距离出口较远的点），同时可以看出episode=1500时的对应Q表和episode=2000时对应的Q表几乎没有变化，这也和3.3.1中”当gamma=0.6时，模型训练1136个episode达到收敛“相符合。
