美文网首页
强化学习和Q learning算法入门(含java实现的小例子)

强化学习和Q learning算法入门(含java实现的小例子)

作者: M_lear | 来源:发表于2020-01-14 21:01 被阅读0次

一、强化学习

强化学习和遗传算法优胜劣汰的思想类似,通过奖惩机制不断强化好的行为(action),弱化坏的行为。至于什么是好的行为,什么是坏的行为,跟你要解决的具体问题有关,比如路径规划问题,走距离目标点较近的路线就是好的行为,走距离目标点较远的路线就是坏的行为。

强化学习包含四要素:agent、环境状态、动作和奖励,目标是获得最多的累计奖励。

二、强化学习原理

2.1 贝尔曼方程

强化学习是基于贝尔曼方程构建的。
贝尔曼方程说的是:如果从最佳路径的开头截除一小部分,那么余下的路径仍然是最佳路径。
例如,你从香港乘车到北京,选择了最便宜的路线,此路线经过 10 个车站,第二站是深圳:香港 -> 深圳 -> …… -> 北京如果除去出发点香港站,那么由第二站深圳到最后的北京站:深圳 -> …… -> 北京仍然应该是最便宜的路线。

用数学语言表达就是:


贝尔曼方程

2.2 从机器学习的角度上,表述贝尔曼方程

根据经验,我们知道,机器学习中的最优值永远都不是一蹴而就,而是朝着最优值的方向一步一步的迭代更新而来。

Delta rule

这是在机器学习中经常出现的更新规则。假设我们有一个目标,我们现在要逐步调整当前状态,令它慢慢趋近这个目标。方法是:当前状态+=\alpha\cdot(目标-当前状态)其中 𝛼 叫学习速率,是一个 0 到 1 之间的小数。Delta(Δ) 指的是目标和现状的差异。显然,反复执行上式,当前状态就会逐步逼近目标。

应用了Delta rule和衰减因子的贝尔曼方程
更新方程

其中 𝛾 同样是一个 0 到 1 之间的小数,为什么会有这个衰减因子的存在呢?因为在实际中,有些情况需要重视长远的收益,而有些情况则需要更重视眼前的收益。


FlappyBird

例如我们玩这个游戏时,就应该把主要精力放在眼前的两个关卡上。

我们知道,越是靠近目标状态的状态,其到目标状态之间最大奖励就越容易计算。例如天津到北京的最便宜路线,肯定比香港到北京的最便宜路线更容易计算。所以在强化学习的训练过程后续状态Q(s^{'})先收敛到最优值𝑄^∗ (𝑠^′ )
然后根据贝尔曼方程就可以把后续状态的最优值反馈给当前状态,这样不断的迭代下去,所有的状态都可以收敛到最优值。

三、Q learning

Q learning 最重要的数据结构为 Q 表,Q 是 quality 的缩写。算法最终就是要学习到一张好的 Q 表,这样我们就可以根据 Q 表对环境中的任何情况(状态)都能给出一个好的反应(动作)。具体的,就是每次都选择 Q 表中对应状态下具有最大 Q 值的动作。

动作可以看作是状态之间转换的桥梁。

Q表的作用 Q 表一般用二维数组表示,每一行表示一个状态,每一列表示一个动作。 例如上图所示的基于移动的二维游戏,每个状态(方块)有四个动作:左移、右移、上移、下移。 Q表

0 代表不能向对应方向移动的地形边缘。

算法流程图: 流程图 伪码描述: 伪码描述 后面我们会有一个和这个伪码描述完全一致的 java 实现,可以对比理解。
\epsilon-greedy 策略

伪码中说,按照一定的策略选择动作,那为什么不是每次按照 Q 表选择对应 Q 值最大的动作呢?

二维小游戏 如上图所示,在初始阶段,Q 表中的值都普遍比较小,当机器人第一次找到砖石后,如果不控制它的贪婪程度(是否每次依据 Q 表选择动作),那么它每次都会直奔那一个砖石而去,因为其他路径的 Q 值都比较小,没有机会被选择到,假如地图中还有第二个更大的砖石,则很有可能被忽略(即缺少对地图的完全搜索)。所以在训练过程中过于贪婪(greedy)的使用 Q 表选择动作,很容易陷入局部最优。

一般在训练时,通过 epsilon(\epsilon)参数控制 agent 的贪婪程度,例如 epsilon = 0.9,表示 90% 的时间使用 Q 表做决策,10% 的时间随机选择动作来探索未知的环境。

java 实现的小例子

问题:最短路径,寻找起始点A到目标点D的最短路径。


例子
package main;
import java.util.Arrays;
public class Qlearning {
    public static void main(String[] args) {
        double[][] Q = new double[][] {
            {-1,  0,  0, -1},
            {-1, -1, -1,  0},
            {-1, -1, -1,  0},
            {-1, -1, -1, -1}
        };
        
        int[][] graph = new int[][] {
            {0, 3, 2, 0},
            {0, 0, 0, 1},
            {0, 0, 0, 4},
            {0, 0, 0, 0}
        };
        
        double epsilon = 0.8;
        double alpha = 0.2;
        double gamma = 0.8;
        int MAX_EPISODES = 400; // 一般都通过设置最大迭代次数来控制训练轮数
        for(int episode = 0; episode < MAX_EPISODES; ++episode) {
            System.out.println("第"+episode+"轮训练...");
            int index = 0;
            while(index != 3) { // 到达目标状态,结束循环,进行下一轮训练
                int next;
                if(Math.random() < epsilon) next = max(Q[index]); // 通过 Q 表选择动作
                else next = randomNext(Q[index]); // 随机选择可行动作
                
                int reward =5 - graph[index][next]; // 奖励
                Q[index][next] = (1-alpha)*Q[index][next] + alpha*(reward+gamma*maxNextQ(Q[next]));
                index = next; // 更新状态
            }
        }
        System.out.println(Arrays.deepToString(Q));
    }

    private static int randomNext(double[] is) { // 蓄水池抽样,等概率选择流式数据
        int next = 0, n = 1;
        for(int i = 0; i < is.length; ++i) {
            if(is[i] >= 0 && Math.random() < 1.0/n++) next = i;
        }
        return next;
    }

    private static int max(double[] is) {
        int max = 0;
        for(int i = 1; i < is.length; ++i) {
            if(is[i] > is[max]) max = i;
        }
        return max;
    }
    
    private static double maxNextQ(double[] is) {
        double max = is[0];
        for(int i = 1; i < is.length; ++i) {
            if(is[i] > max) max = is[i];
        }
        return max;
    }

}

Q 表的更新过程:


Q表的更新

第三个 Q 表其实已经收敛。

Q(s,a)=(1-\alpha)Q(s,a)+\alpha(R+\gamma\cdot \max Q(s^{'}))

(1-0.2)*4.56 + 0.2*(2+0.8*3.2)=4.56
(1-0.2)*3.16 + 0.2*(3+0.8*0.2)=3.16
(1-0.2)*3.2 + 0.2*(4-0.8)=3.2
(1-0.2)*0.2 + 0.2*(1-0.8)=0.2

对照着公式,通过手工计算可以看到所有的 Q 值已经趋于稳定,继续迭代,Q 值也不会发生更新。

对比 Q 表的更新过程可以发现,刚开始时,还会选择 A->C 这条路径,因为短期从 A->C 能够获得更多的奖励,但是当接受到未来奖励的反馈后,开始逐渐倾向于 A->B,并最终选择 A-> B 路径,因为从 B->D 会获得比从 C->D 大得多的奖励。这也体现了强化学习延迟反馈的特征。

参数设置对模型的影响:

  • epsilon 过大,模型不容易收敛。
  • alpha 过小,模型不容易收敛。
  • gamma 改变最终的收敛结果也会改变。

代码中用到了蓄水池抽样技术,可以等概率的选择流式数据,如果对蓄水池抽样感兴趣可以看看这篇文章

文中部分图片非原创。
参考:
https://www.zhihu.com/question/41775291/answer/93276779

相关文章

  • 强化学习和Q learning算法入门(含java实现的小例子)

    一、强化学习 强化学习和遗传算法优胜劣汰的思想类似,通过奖惩机制不断强化好的行为(action),弱化坏的行为。至...

  • Win10环境下使用WSL安装OpenAI/gym +Tenso

    实现目标 我们的目标是在Windows 10系统上具体实现DeepMind论文中强化学习算法Q-learning ...

  • 2019-04-18派森学习第150天

    想要用强化学习改进派工算法。 强化学习在之前学习过一个Q-learning算法。 强化学习的基本写法和神经网络很相...

  • 强化学习——Q-learning

    一、什么是Q_learning Q_learning是强化学习中的一个决策算法,如果你还不知道什么是强化学习,可以...

  • 基于Policy的强化学习算法

    在文章基于Value的强化学习算法中,介绍了Q-learning和SARSA两种经典的强化学习算法。在本篇文章中,...

  • 用一个小游戏入门深度强化学习

    今天我们来用深度强化学习算法 deep Q-learning 玩 CartPole 游戏。 强化学习是机器学习的一...

  • 2018-04-21

    【入门必备】史上最全的深度学习资源汇总,速藏! 入门 | 通过 Q-learning 深入理解强化学习 学界 | ...

  • AI学习笔记——Sarsa算法

    上一篇文章介绍了强化学习中的Q-Learning算法,这篇文章介绍一个与Q-Learning十分类似的算法——Sa...

  • 入门

    常见的强化学习算法有三类 通过价值行为选择1. Q learning2. sarsa3. Deep Q netwo...

  • 强化学习之Sarsa

    在强化学习中,Sarsa和Q-Learning很类似,本次内容将会基于之前所讲的Q-Learning的内容。 目录...

网友评论

      本文标题:强化学习和Q learning算法入门(含java实现的小例子)

      本文链接:https://www.haomeiwen.com/subject/dwwaactx.html