Q-learning算法

利用网上的一个简单的例子来说明Q-learning算法。

假设在一个建筑物中我们有五个房间，这五个房间通过门相连接，如下图所示：将房间从0-4编号，外面可以认为是一个大房间，编号为5.注意到1、4房间和5是相通的。

每个节点代表一个房间，每个连接代表一个门。

对这个例子来说，我们可以把Agent放到任何一个房间中，然后从这个房间走出这个建筑物（这就是我们的目标房间，即房间5）。为了把5号房间设成目标房间，我们为每一扇门（节点之间的连接线）分配一个回报值。直接通向目标的门的回报值为100，没有与目标房间直接相连的其他门的回报值为0。因为门都是双向的（0可以到4,4也可以到0），因此每个门由两个箭头来表示。每个箭头都有有一个立即回报值，如下所示：

当然，从房间5到房间5自身的回报值应该是100。而所有直接通向这个目标房间的连接线的回报值为100。在Q-Learning中，目标就是要到达有最高回报值的状态。所以如果Agent到达了目标，它就会一直在那。这种类型的目标被称为吸收目标（absorbing goal）。

想象一下，我们的Agent是一个不会说话的虚拟机器人，但是它可以从经验中学习。Agent可以从一个房间走到另一个房间但是对于周围的环境没有任何了解，不知道哪一种门的顺序可以把它带到外面。

假设我们要为一个Agent从这个建筑物中任何一个房间撤离出去来简单建模，假设我们有一个Agent在房间2中，我们想让这个Agent学着到达这个建筑物的外面。

Q-Learning中的术语包括状态（state）和动作（action）。

我们称包括建筑物外面的所有房间为状态，Agent从一个房间到另一个房间的移动为动作，在图中，一个状态被画成一个节点，而一个动作被箭头表示出来。

假设Agent是在2号房间（状态2）中，那么它可以从2号房间走到3号房间，因为他们是相通的。而从2号房间Agent不能直接走到1号房间，因为没有一个门（所以没有箭头）直接把1号和2号房间连接起来。从状态3.它可以走到状态1,4，或者回到2（注意看与状态3相关的所有箭头）。如果Agent是在状态4，那么它所有可能的动作是走向状态0,5或者3。如果它在状态1，那么它可以到达状态3或者状态5，从状态0，它只可以回到状态4。

我们可以把状态图和即时回报值填入下面的回报表中，即R矩阵

上图中-1代表空值，比如两个状态之间没有箭头。

现在我们添加一个相似的矩阵，“Q”，到我们Agent的大脑中，这个矩阵代表了Agent通过经验所学到的，Q矩阵的行代表Agent的当前状态，Q矩阵的列代表了可能到达下一状态的动作（即状态之间的箭头）。

Q-Learning的转换规则方程：

γ值在0到1之间变化（0<=γ<1）,如果γ值接近0，Agent倾向于只考虑立即回报值；如果γ值接近1，Agent将以更大的权重去考虑未来回报值，愿意将回报延后。

Agent仅仅是跟踪从起始状态到目标状态的状态序列来使用矩阵Q。这个算法在矩阵Q中为当前状态找到有最高回报值的下一步动作。

实例：

初始化Q矩阵为一个零矩阵，参数伽马r=0.8，随机初始状态为房间1

从R矩阵可以看出有两个非负值，即从房间（状态）1到房间（状态）3或者从房间（状态）1到房间（状态）5，随机选取从1到5.

根据公式1.1

此时状态5变为当前状态，因为状态5就是目标状态，故以此episode结束，刷新Q表