Q-learning算法初窥及路径寻优案例（第二回） | 山人刷强化 | 6th

0.引言

上回书说到Q-Learning介绍、算法原理，并引出了路径寻优的故事，这回我们仔细说一下如何利用Q-Learning算法解决这个问题。

上次故事的传送门：

Q-learning算法初窥及路径寻优案例（第一讲） | 山人刷强化 | 5th

1.问题的抽象

回顾一下问题的设定：从任意地点出发，如何让机器寻到最优路径达到地址5。

抽象一下，无论是走房间还是路径寻优，本质上都可以抽象成以下的“节点-路径”关系。

因此，我们可以为路线进行奖励设定，所有可到达节点5的行动连接设定为100，其他均为0。如下图所示。

2.R矩阵设定

根据上图，设定action和state两个RL参数的含义：

1.state，定义为所处的地点/节点。

2.action，定义为移动行为，即从一个地点到另一个地点的行为。

这样我们就可以得到一个奖励函数的矩阵：R（s,a）。我们将列向量定义为state、行向量定义为action，其中的值为连接的值，主要有三类初始值：

0，即通过action没有到达节点5的行动

100，通过action到达节点5的行动

-1，没有连接关系的节点，也意味着系统不鼓励这种行为，如地点1无法到达地点2

得到R矩阵如下：

3.Q矩阵设定及Q值函数定义

Q矩阵形式上与R矩阵类似，Q矩阵是智能体的核心矩阵，主要作用是基于当前状态指导下一步可能的最佳行动策略。我们不知道任何一个步骤是否可以到达地点5，因此初始化时Q矩阵全部为0，然后通过做出行动、获得反馈、更新Q矩阵来迭代生成Q矩阵。

Q值更新的策略是一个比较简单的公式：

Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)]

上式表明，Q值更新取决于本次状态、执行后的R值，加上基于下一个状态所有可能行动策略的Q的最大值乘以一个gamma系数，即折扣系数。折扣系统通常在0~1之间，代表了未来行动对当前影响的大小，是人为设定的超参数。

这也反应了其所遵从的马尔科夫决策过程的理念，在序列决策过程中，当前行动的决策不受历史行为的影响，而是受到后续行动的影响是最大的，其中越接近当前的行动影响越大。

4.Q-learning算法

我们的智能体将会通过经验学习，而不是监督学习，通常将其称之为无监督学习。智能体可以通过状态更新寻到最优策略，并到达目的地。每轮迭代包括了智能体从出发地到目的地整个过程的行动、状态和Q值计算等。当智能体到达目的地后，再开始下一轮更新，具体算法如下所示：

Q-learning算法如下所示：

1. Set the gamma parameter, and environment rewards in matrix R.

2. Initialize matrix Q to zero.

3. For each episode:

Select a random initial state.

Do While the goal state hasn't been reached.

• Select one among all possible actions for the current state.
• Using this possible action, consider going to the next state.
• Get maximum Q value for this next state based on all possible actions.
• Compute: Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)]
• Set the next state as the current state.

End Do

5.Q值迭代获得Q矩阵并进行路径优化

通过Q值迭代得到Q矩阵后，智能体就可以按照Q矩阵的来进行路径选择了。即按照当前状态寻找奖励最大化的行动。具体策略如下：

Algorithm to utilize the Q matrix:

1. Set current state = initial state.

2. From current state, find the action with the highest Q value.

3. Set current state = next state.

4. Repeat Steps 2 and 3 until current state = goal state.

6.计算过程举栗?

关于Q值迭代和Q矩阵路径寻优，我们将计算过程举个栗子，便于理解。

1）Q矩阵初始化为0矩阵。

2）R矩阵初始化为连接关系矩阵，具体参见R矩阵设定环节。

3）做一次Q值迭代，求解Q（1，5）

Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)]

Q(1, 5) = R(1, 5) + 0.8 * Max[Q(5, 1), Q(5, 4), Q(5, 5)] = 100 + 0.8 * 0 = 100

其中R（1，5）通过查找R矩阵获得，Q（5，1）、Q（5，4），Q（5，5）为三个可能在状态5选择的行为，Q值通过查找Q矩阵获得，而此时的Q矩阵中的值均为0，结果如上式所示。更新后Q矩阵如下所，Q（1，5）变为100。

4）重复步骤1-3多次，最终会收敛得到一个固定的Q矩阵如下所示。

5）归一化，所有值除以5，得到Q矩阵如下。

6）在任何状态下，按照Q矩阵寻优，即如下图所示，在状态3算则3->1或3->4，因为两个的Q值均为最大值80，然后1->5或4->5。

结语

到这里，我们说到了Q-Learning路径寻优问题的抽象、R矩阵设定、Q矩阵设定及Q值函数定义、Q-learning算法、Q值迭代获得Q矩阵并进行路径优化，以及计算过程举例。

下一次将呈现出完整的代码，并对代码进行讲解，有兴趣的小伙伴可以尝试自己实现先，并分享你们的经验心得。

参考资料

http://mnemstudio.org/path-finding-q-learning-tutorial.htm