继续接着上一篇,这篇文章介绍强化学习中的一个经典算法——Q Learning.
在之前的文章中已经介绍过了,强化学习就是让机器人(Agent)在与环境的互动过程学习解决问题的最佳路径的过程。
强化学习通常包括这么几个重要概念:
- 状态(State (S))
- 动作(Action(A))
- 奖励(Reward(R))
下面以一个例子来解释这几个概念,并介绍一下Q Learning是什么:
![img_44df3cad2b7a122c192867d03b9e1a7a.png](https://yqfile.alicdn.com/img_44df3cad2b7a122c192867d03b9e1a7a.png?x-oss-process=image/resize,w_1400/format,webp)
上图红色方框就是我们的机器人,任务是要在4x4的迷宫中找到黄色圆圈的宝藏,并学习到达宝藏的最佳路径。如果以左上角的初始状态为S 0,那么整个迷宫一共有16个 状态(State)(从左到右从上到下分别是S 0到S 15)。机器人的 行动(Action)有四个: 分别是向左(A 1)向右(A 2)向上(A 3)和向下(A 4)移动。如果找到黄色圆圈(宝藏) 奖励(Reward)为1,掉入黑色陷阱奖励(Reward)为-1,其他地方为0。
1. Q表(Q table)
Q Learning 就是创造一个Q表,来指导机器人的行动,Q表对应Action的数值越大,机器人就越大概率地采取这个Action.
Q table (States\Actions) | left (A1) | right (A2) | up (A3) | down (A4) |
---|---|---|---|---|
S0 | -1 | 3 | -1 | 2 |
S1 | 1 | 2 | -1 | 1 |
... | ... | ... | ... | .. |
比如Q表在S0最大概率会向右移动,在S1最大概率还是向右移动,因为A2在两个状态的Q表数值都是最大的。
这个Q表是经过学习之后的结果,学习并不断更新这个表的过程就是Q Learning。
2. 探索-利用困境(Explore-Exploit dilemma)
Q Learning 是如何学习并更新Q表呢?正如多臂老虎机(Multi-armed bandit)问题一样,如果机器人仅仅按照表中最大概率指导行动的话,是学不到任何东西的,它还需要不停地在未知地图上进行探索,这就是是探索-利用困境(Explore-Exploit dilemma)。同样的,我们也可以用ε贪婪方法(ε -Greedy method)的方法来解决这个困境。
也就是设定一个ε(比如0.9),90%的几率按照Q表数值最大Action行动,10%随机行动。每行动一次就要更新一下Q表。
3. 如何更新Q表
Q learning的算法就是如何更新Q表的方法。还是以表下为例:
Q table (States\Actions) | left (A1) | right (A2) | up (A3) | down (A4) |
---|---|---|---|---|
S0 | -1 | 3 | -1 | 2 |
S1 | 1 | 2 | -1 | 1 |
当机器人处于S0的状态时,如果刚好选择了A2,那么下一个状态就是S1(注意有10%的概率会选择其他的Action, 而到达其他的状态)。行动之后,我们就需要更新Q(S0,A2)的数值, 先给结果吧:
Q(S0,A2) = Q(S0,A2) + α[R(S1) + γ*maxa Q(S1,a)-Q(S0,A2)]
解释一下
- R(S1)是机器人在S1能活的的奖励(Reward)(该游戏除了陷阱的地方为-1,宝藏的地方为1,其他地方均为0)。
- γ为衰减值。
- maxa Q(S1,a)是S1状态下Q表数值最大的一个(这里是2)。
- α是学习速率(Learning Rate)。
- R(S1) + γ*maxa Q(S1,a)是Q(S0,A2) 的目标数值。
那我们再把公式重写一遍就清楚了吧:
Q(S0,A2)新=Q(S0,A2) 旧 + α* [Q(S0,A2)目标 - Q(S0,A2)旧]
上面的公式像极了在线性回归中的梯度下降法(Gradient Descent)。只不过在线性回归我们更新权重W的方法,在这里我们更新Q表而已。
完整的公式如下:
![img_9755261b5d5c34d316f8b6bbdf6c3b23.png](https://yqfile.alicdn.com/img_9755261b5d5c34d316f8b6bbdf6c3b23.png?x-oss-process=image/resize,w_1400/format,webp)
4. 衰减值
这里再解释一下为什么要用衰减值 γ,从上面的公式可以看出,St 和 St+1是一个递归的关系。当机器人走到第n步的时候,会受到0到n-1每一步状态的影响。如果衰减值γ=1,那么每一步的影响都是一样的。γ在0到1之间,就可以让越靠近n的状态对第n步影响越大,之前的状态随着行动的增加,影响力会越来越小。
文章首发steemit.com 为了方便墙内阅读,搬运至此,欢迎留言或者访问我的Steemit主页