版本对应:

本网页讨论的机器学习内容,为特定的机器学习内容(并未与CFD结合)。在《无痛苦NS方程笔记》中, 特定的将CFD与机器学习互相结合起来,无普适性机器学习内容。

ML: 强化学习手算Q-Learning

在阅读本文之前,请阅读《无痛苦NS方程笔记》中的监督学习的数学算法一节。

各种监督学习,用白话来讲,就是寻找拟合函数。最简单的情况,甚至可以用excel软件来寻找拟合函数。监督学习就是用计算机寻找多分段的拟合函数。现在来看好像没有什么特别复杂难以理解的地方。好像也没有展现“机器自我学习”这个情况。一般般而已。

在强化学习里面,用户会感觉到机器是在进行某种自我学习,学习某种经验,然后去寻找特定情况下的最优解决方案。与监督学习最大的不同点在于强化学习不需要提供标签。强化学习的某种神秘的力量会自我判断当前所做的选的是错误的还是正确的。接下来我们来看一下强化学习的普适性概念。

几乎所有的强化学习的算法提出,包括各大教材讲义针对强化学习的介绍,都是基于玩电子游戏这个应用而进行的。因此通过玩电子游戏来介绍强化学习的基本概念会非常的通俗易懂。强化学习与CFD的结合,请参考《无痛苦NS方程笔记》

人脑识别的最优过程

如下图显示,假设我们在玩一个游戏,这个游戏需要让里面CFD中文网的猫logo,通过最短的路线去走到dyfluid的logo上。如果是人在玩游戏,那么需要人来操作是左走还是右走。我们想通过计算机去玩游戏,那么操纵左走还是右走的就是计算机。

_images/maze1.JPG

在强化学习里面,操纵左走还是右走的这么个东西,叫智能体(agent)。智能体说,往右走,猫就向右移动一步。往右走往左走的行为,叫做动作(action)。猫具体在哪一个格子里面,称之为一个状态(state)。我们所有的事情都发生在这个图里面,这个图就称之为环境(environment)。强化学习的目的,就是让智能体告诉猫,通过最短的路径去走到目的地。

_images/mases.JPG

在上图中,猫可以存在16个格子里面,因此存在16个状态。我们对每个状态进行编号(如上图)。智能体告诉猫每动一次,状态就要变一下。在这个具体的算例里面,动作可以分为4种,也即上下左右。在下图中,猫在不同的位置,分别对应一个状态。

_images/mazestate.JPG

Q-learning算法的主要目的,就是创建一个表格,这个表格就是智能体。智能体告诉猫,在什么状态下,应该怎么走,才能通过最短的路径去达到终点。目前我们通过人脑可以看出,假设猫处于S(3,1)这个状态,就是终点左边的这个网格,猫需要往右走就可以到达终点,而不是往左走。那么我们最终的Q-learning创建的智能体(也就是这个表格),针对S(3,1)这个状态,可能的情况就是这样的:

状态

S(3,1)

2

-1

4

12

我们来理解一下上面这个表格。针对 S(3,1)这个状态,存在4个动作,每个动作对应1个数字,其中最大的数字是12,这说明在这个状态下,往右走可以达到我们想要的效果。其实表中4个数字都是我拍脑袋写的,最重要的,是S(3,1)对应的向右的这个动作,数字要最大。Q-learning算法,就是要算出下面的这个类似的表格:

状态

S(0,0)

max

max

S(0,1)

max

S(0,2)

max

S(0,3)

max

S(1,0)

max

max

S(1,1)

max

max

S(1,2)

max

S(1,3)

max

max

S(2,0)

max

max

S(2,1)

max

max

S(2,2)

max

S(2,3)

max

max

S(3,0)

max

S(3,1)

max

S(3,2)

0

0

0

0

S(3,3)

max

注意:

上表中空余部分也是有值的。只不过max是最大值。其他的值没有写。

其中的max表示,Q-learning处理出来的数据,相应的max一定是最大值。比如对于S(0,0)这个状态(就是猫处于左上角的网格),往下走和往右走都对应的最优策略,因此动作“下”与动作“右”都对应max的值。在后面会看到Q-learning是一种迭代算法,在收敛的情况下,动作“下”与动作“右”一定都对应max的值。很明显,假定这个表出来之后,把猫放在任意一个状态,他都会遵循max对应的动作,找到最优路径达到终点。上表中的具体的数值,也即Q值。每个\(Q\)对应一个状态\(s\)和一个动作\(a\)。因此\(Q\)是一个关于\(s,a\)的函数,可以写成\(Q(s,a)\)。问题是,这面这个图标是通过人脑看出来的,如何通过计算机处理出这样一个表格?

Q-learning学习的最优过程

我们的问题是让猫通过最短的路径到达终点。那么如何能用数学来描述这个问题。很简单,我们可以把每一次动作想象成对应一个负数,每一次动作的进行,这个负数越来越大。到达路径的负数进行叠加,最大的负数对应最优的路径。比如我们定义每一次移动,对应-1,如果移动5次到达终点,那么总数就是-5。如果移动10次到达终点,那么综述就是-10。很明显,-5对应的路径就要比-10对应的路径好的多。

_images/reward.JPG

在上图中,我们把每个网格点标志了一个数字。比如从S(0,0)网格点移动到S(0,1)网格点,对应的数字是-1,那么我们就认为:猫从S(0,0)网格点,执行了向右的动作,移动到S(0,1)网格点,拿到一个数是-1。这个-1,就是奖励。同理,如果从S(3,1)移动到S(3,2),会发现这一次的奖励为10。

需要注意的是,其中具体的数字,比如是-1,还是-3,这完全是用户给定的。之所以我们给了一个负数,是因为我们的目的是告诉智能体,每多执行一次动作,都会带来一个负的奖励。之所以在终点是一个正的奖励,就是告诉智能体,如果移动到终点,那么可以大幅度的增加奖励的数值(其实也不需要是10,只要是比-1大的数就可以)。那么如何判断什么是最优路径,就是所有的动作带来的奖励的加和,对应的总值如果最大。那就是最优路径。这个所有的动作带来的奖励的加和,被称之为回报。针对这个算例,最优路径的寻找,变成了回报最大化路径的寻找的数学问题。

_images/maze22.JPG

4\(\times\)4网格的算法对于计算机轻而易举,但是如果手算得话还是复杂了点。因此在这里用一个2\(\times\)2网格来进行一个真正的Q-learning算法的计算。

(1)\[\begin{equation} Q_{new}(s, a) = Q(s, a) + \alpha \left(r +\gamma q_{new}^{max}-Q(s, a)\right) \end{equation}\]

其中\(Q(s, a)\)表示当前状态\(s\),进行\(a\)动作的初始\(Q\)值,\(\alpha\)表示学习率,是一个超参数,也即自定义参数,在这里假定是0.1,\(r\)表示当前状态\(s\),进行\(a\)动作达到的奖励值,\(\gamma \)表示折扣因子,是个超参数,假定为0.9,\(q_{new}^{max}\)表示下一个状态下各种可能性动作可能带来的最大\(Q\)值。把自定义参数替换进去有:

(2)\[\begin{equation} Q_{new}(s, a) = Q(s, a) + 0.1\left(r +0.9 q_{new}^{max}-Q(s, a)\right) \end{equation}\]

假定我们的初始化\(Q\)表为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

0

S(0,1)

0

0

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

当前的状态在S(0,0),假定我们的给定的动作是“右”(这里面涉及到另外一个知识叫做\(\epsilon\)-greedy策略,将在后面介绍),我们可以来计算一下\(Q\)值:

(3)\[\begin{equation} Q_{new}(s(0,0), right) = Q(s(0,0), right) + 0.1\left(-1 +0.9\times 0-Q(s(0,0), right)\right) \end{equation}\]

因为初始的表中\(Q\)均为0,因此上式可以写为:

(4)\[\begin{equation} Q_{new}(s(0,0), right) = 0 + 0.1\left(-1 +0.9\times 0-0\right)=-0.1 \end{equation}\]

在这种情况下,\(Q\)表更新为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

-0.1

S(0,1)

0

0

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

下面进行第二次更新。假定我们的给定的动作是“下”,来计算一下\(Q\)值:

(5)\[\begin{equation} \begin{split} Q_{new}(s(0,1), down) &= Q(s(0,1), down) + 0.1\left(10 +0.9\times 0-Q(s(0,1), down)\right) \\\\ &= 0 + 0.1\left(10 +0.9\times 0-0\right) \\\\ &= 1 \end{split} \end{equation}\]

状态

Up

Down

Left

Right

S(0,0)

0

0

0

-0.1

S(0,1)

0

1

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

目前的状态下,我们的猫走到了终点。现在进入下一轮的学习,回到S(0,0),假定我们的给定的动作还是“右”,来计算一下\(Q\)值:

(6)\[\begin{equation} \begin{split} Q_{new}(s(0,0), right) &= Q(s(0,0), right) + 0.1\left(-1 +0.9\times 1-Q(s(0,0), right)\right) \\\\ &= -0.1 + 0.1 (-1 +0.9\times 1 +0.1 ) \\\\ &= -0.1 \end{split} \end{equation}\]

\(Q\)表更新为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

-0.1

S(0,1)

0

1

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

随后假定我们的给定的动作是“下”,来计算一下\(Q\)值:

(7)\[\begin{equation} \begin{split} Q_{new}(s(0,1), down) &= Q(s(0,1), down) + 0.1\left(10 +0.9\times 0-Q(s(0,1), down)\right) \\\\ &= 1 + 0.1 (10 +0.9\times 0-1 ) \\\\ &= 1.9 \end{split} \end{equation}\]

\(Q\)表更新为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

-0.1

S(0,1)

0

1.9

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

进入下一轮的学习,回到S(0,0),假定我们的给定的动作还是“右”,来计算一下\(Q\)值:

(8)\[\begin{equation} \begin{split} Q_{new}(s(0,0), right) &= Q(s(0,0), right) + 0.1\left(-1 +0.9\times 1.9 - Q(s(0,0), right)\right) \\\\ &= -0.1 + 0.1 (-1 +0.9\times 1.9 +0.1 ) \\\\ &= -0.019 \end{split} \end{equation}\]

\(Q\)表更新为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

-0.019

S(0,1)

0

1.9

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

随后假定我们的给定的动作是“下”,来计算一下\(Q\)值:

(9)\[\begin{equation} \begin{split} Q_{new}(s(0,1), down) &= Q(s(0,1), down) + 0.1\left(10 +0.9\times 0-Q(s(0,1), down)\right) \\\\ &= 1.9 + 0.1 (10 +0.9\times 0-1.9 ) \\\\ &= 2.71 \end{split} \end{equation}\]

\(Q\)表更新为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

-0.019

S(0,1)

0

2.71

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

进入下一轮的学习,回到S(0,0),假定我们的给定的动作还是“右”,来计算一下\(Q\)值:

(10)\[\begin{equation} \begin{split} Q_{new}(s(0,0), right) &= Q(s(0,0), right) + 0.1\left(-1 +0.9\times 2.71 - Q(s(0,0), right)\right) \\\\ &= -0.019 + 0.1 (-1 +0.9\times 2.71 +0.019 ) \\\\ &= 0.1268 \end{split} \end{equation}\]

\(Q\)表更新为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

0.1268

S(0,1)

0

2.71

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

随后假定我们的给定的动作是“下”,来计算一下\(Q\)值:

(11)\[\begin{equation} \begin{split} Q_{new}(s(0,1), down) &= Q(s(0,1), down) + 0.1\left(10 +0.9\times 0-Q(s(0,1), down)\right) \\\\ &= 2.71 + 0.1 (10 +0.9\times 0-2.71 ) \\\\ &= 3.439 \end{split} \end{equation}\]

\(Q\)表更新为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

0.1268

S(0,1)

0

3.439

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

进入下一轮的学习,回到S(0,0),假定我们的给定的动作还是“右”,来计算一下\(Q\)值:

(12)\[\begin{equation} \begin{split} Q_{new}(s(0,0), right) &= Q(s(0,0), right) + 0.1\left(-1 +0.9\times 3.439 - Q(s(0,0), right)\right) \\\\ &= 0.1268 + 0.1 (-1 +0.9\times 3.439 -0.1268 ) \\\\ &= 0.32363 \end{split} \end{equation}\]

\(Q\)表更新为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

0.32363

S(0,1)

0

3.439

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

随后假定我们的给定的动作是“下”,来计算一下\(Q\)值:

(13)\[\begin{equation} \begin{split} Q_{new}(s(0,1), down) &= Q(s(0,1), down) + 0.1\left(10 +0.9\times 0-Q(s(0,1), down)\right) \\\\ &= 3.439 + 0.1 (10 +0.9\times 0-3.439 ) \\\\ &= 4.1 \end{split} \end{equation}\]

\(Q\)表更新为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

0.32363

S(0,1)

0

4.1

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

进入下一轮的学习,回到S(0,0),假定我们的给定的动作还是“右”,来计算一下\(Q\)值:

(14)\[\begin{equation} \begin{split} Q_{new}(s(0,0), right) &= Q(s(0,0), right) + 0.1\left(-1 +0.9\times 4.1 - Q(s(0,0), right)\right) \\\\ &= 0.32363 + 0.1 (-1 +0.9\times 4.1 -0.32363 ) \\\\ &= 0.56 \end{split} \end{equation}\]

\(Q\)表更新为:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

0.56

S(0,1)

0

4.1

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

至此,我们不再往下迭代。总结几点规律:

  • 如果一直按照先往右,往下的策略进行计算,S(0,1)状态下,动作“下”的\(Q\)值会越来越大(越来越接近10)。这也就表明了,如果猫处于状态S(0,1)的网格,往下走才是最优策略;

  • 针对S(0,0)也一样,向右走的\(Q\)值会越来越大,表明猫处于状态S(0,1)的网格,往右走才是最优策略;

  • 表格中S(0,0)对应的向下走的动作为0,但是如果先向下走再想右走,同样也是最优策略。但是表格没有体现;

针对第三个情况,可以进行类似的先向下,再向右的迭代。比如进行几次迭代后,可能的\(Q\)表会变为:

状态

Up

Down

Left

Right

S(0,0)

0

0.56

0

0.56

S(0,1)

0

4.1

0

0

S(1,0)

0

0

0

4.1

S(1,1)

0

0

0

0

对于上述的\(Q\)表,表示当猫处于S(0,0),向下与向右都可以达到最优的策略。问题再一次出现,猫是否可能会从S(0,0)向右走到S(0,1),然后向左走回到S(0,0)呢?

同策略与异策略

系统的讨论策略之前,先看一下\(\epsilon\)-greedy策略(policy)。在上面的迭代过程中,猫向哪个方向都都是我拍脑袋指定的。在计算机层面,其原理很简单。假定给定某一步迭代好的Q表如下:

状态

Up

Down

Left

Right

S(0,0)

0

0

0

0.56

S(0,1)

0

4.1

0

0

S(1,0)

0

0

0

0

S(1,1)

0

0

0

0

在使用\(\epsilon\)-greedy策略的时候,首先通过计算机生成一个0与1之间的随机数\(R\),同时用户给定一个超参数\(\epsilon\),S(0,0)状态的猫是向右走还是向下走,取决于\(R\)\(\epsilon\)的大小。如果\(R<\epsilon\),则随机选择一个动作。反之,则选择当前层面Q值最大的动作。在强化学习领域,随机的动作被称之为探索(exploration)。选择当前层面Q值最大而进行移动被称之为利用(exploitation)。探索过程是非常重要的,否则Q-learning可能会在自认为寻找到一个最优路线之后,而放弃寻找其他的最优路线。

同时\(\epsilon\)-greedy策略可以看做是\(\epsilon\)策略与greedy策略的混合。greedy策略意味着完全的利用,不具有任何的随机性。\(\epsilon\)策略意味着随机的探索。现在来看一下Q-learning更新Q表情况下使用了什么策略。回到Q-learning的Q值更新公式:

(15)\[\begin{equation} Q_{new}(s, a) = Q(s, a) + \alpha \left(r +\gamma q_{new}^{max}-Q(s, a)\right) \end{equation}\]

很明显,因为\(q_{new}^{max}\)表示下一个状态下各种可能性动作可能带来的最大\(Q\)值,因此是一种greedy策略,而不是\(\epsilon\)-greedy策略(完全没有随机性)。同时在更新Q值的时候,也使用了\(\epsilon\)-greedy策略决定下一步的动作。这种使用了不同策略的方法,叫做异策略方法(Off-policy)

现在讨论另外一种方法:SARSA方法(State-Action-Reward-State-Action)。其与Q-learning非常类似。在SARSA中,Q值的计算方法与Q-learning相同,只不过其中的\(q_{new}^{max}\),在Q-learning是下一步最大的可能性的动作。但是在SARSA方法中,如果使用\(\epsilon\)-greedy策略,那么\(q_{new}^{max}\)对应的动作选择,还是通过\(\epsilon\)-greedy策略来确定。因此在SARSA方法中,一直使用的都是\(\epsilon\)-greedy策略。这种使用相同策略的方法,叫做同策略方法(On-policy)

回头来看,什么是强化学习,在本文讨论的这个非常基础的案例上可以看出,强化学习就是让计算机自身去迭代,自己去寻找出最优路线的过程。这个迭代的过程即为学习。然而在目前这个阶段,完全没有涉及到神经网络。确实,Q-learning过程并不需要神经网络。然而我们可以在Q-learning的基础上,附加神经网络来处理更加复杂的情况。

最后,Q-learning算法通过Q值来决定最优的路线。还有一类方法是依据策略来进行最优路线的选取,在这种方法中不需要计算Q值。这将在其他章节介绍。

Deep Q-learning

Deep Q-learning (DQN)也被称之为深度Q网络。在上文讨论的原生Q-learning算法中,输入是一个状态,智能体会从Q表中查找出来最优的动作去执行。如果对于一个非常复杂的状态(比如一个10000\(\times\)10000的网格),以及很多可能性的动作(比如100个动作),这个表格将是非常巨大的(10000\(\times\)10000\(\times\)100)。另外,如果状态是连续的变化,Q表也不太行得通。深度Q网络就是把传统的Q表格,通过神经网络来进行替换。其输入一个复杂的状态,会输出一个最优的动作。只不过不是查表来进行,而是通过神经网络来进行。类似其他深度学习技术,最早的深度Q网络也被用在了玩游戏上,参考这个链接

待更新…