强化学习极简例子--迷宫问题

迷宫

图1为一个小型迷宫，其中S为入口， $-$ 表示墙， $+$ 表示出口。你说出口不在边缘？对的，就是这么任性。
强化学习极简例子--迷宫问题

图1. 迷宫

解法1: 单源最短路径

我们把迷宫的各个可达状态进行编号，获得图2.
强化学习极简例子--迷宫问题

图2. 编号后的迷宫

将各可达状态看成节点并编号，则相邻节点之间的距离为1，则迷宫可以转成无向图。令0号节点为源，18号节点为目的，则该问题为单源最短路径问题。
但是，我们偏不。

解法2: 强化学习

强化学习有两个实体: 一是环境，即这里的迷宫；二是智能体(Agent)，即一个在迷宫是瞎转悠的人。
Agent从源开始在迷宫里跌跌撞撞地走，到达目的算作一个episode。可以让他转很多（如1000）个episode，然后找到最短路径。
作为一个Agent而不是傻子，他会在曾经（包括本episode和以前的episode）到达过的每个节点作标记。具体的标记就是向四个方向（上下左右）的奖励值。对于本例而言，有25个状态，就是25行4列的一个Q矩阵。
强化学习Q-learning的核心就是学习这个Q矩阵！
下面令UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3.
Episode 0

在状态0，UP和LEFT是不可达的，首先就被否定了，因此， $q_{0, 0}$ 和 $q_{0, 2}$ 值没有意义。
从状态0如果尝试向DOWN方向走，就会碰壁并留在状态0，Agent很伤心，所以令 $q_{0, 1} = -100$ , 发誓下次再也不这样走。
从状态0尝试向RIGHT方向走，会走到状态1，状态1什么都没有，但耗费了Agent的体力，所以 $q_{0, 3} = -0.19$ . 为什么是-0.19, 后面再解释。
…很久很久以后…
Agent在状态19惊喜地发现, 自己向左边走居然就是出口！迷宫想给他100金币作为奖励，但他令 $q_{19, 2} = +100 * 0.1 = +10$ . 乘以系数0.1是让自己不要太傲娇。
我们得到了图4所示的Q矩阵。
图3. Episode 0之后的Q矩阵
Episode 4
我们得到了图4所示的Q矩阵。从这里可以看到，14号的DOWN, 17号的RIGHT都为正奖励，19号的LEFT奖励值也增加了。也就是说，奖励值是从出口逐渐往入口渗透，且呈现递减趋势。
图4. Episode 4之后的Q矩阵
Episode 99
我们得到了图5所示的Q矩阵。
图5. Episode 99之后的Q矩阵及相应迷宫中的路径
从Q矩阵中可以看出：
多轮奖励之后 $q_{19, 2} = 46.855$ , 而 $q_{17, 3} = 99.995$ , 后者更大, 且未超过100.
按照第0行最大元素来看，状态0应向RIGHT方向走至状态1，状态1应该向DOWN方向走至状态6，然后依次是状态11，16，17，18. 这就是Q矩阵指示出来的最短路径。
故事结束。

不是说好了“后面再解释-0.19产生的原因”吗？由于是极简例子，我反悔了。

彩蛋来咯

完整的Java代码见https://github.com/FanSmale/MFReinforcement

强化学习极简例子--迷宫问题

迷宫

解法1: 单源最短路径

解法2: 强化学习

彩蛋来咯

相关推荐