专栏首页ThoughtWorks强化学习入门——说到底研究的是如何学习

强化学习入门——说到底研究的是如何学习

自机器学习重新火起来,深度强化学习就一直是科研的一大热点,也是最有可能实现通用人工智能的一个分支。然而对于没有强化学习基础的同学们,如果直接去学习深度强化学习,想必会碰到很多问题。本文尝试普及一些最基础的强化学习算法,并以一个小例子来辅助大家理解。


问题定义

强化学习究竟研究的是一个什么样的问题,让其具有实现通用人工智能的潜力?

这个问题与我们认识世界的方式相关。我们都知道这个世界时刻在变化着,而每件事物的变化,势必是由其他一系列事物导致的。这就是我们所普遍认识的世界,一个由因果律定义的世界。由于因果律的存在,我们就有可能根据某个当前世界的状态,计算后一时刻世界的状态。

而我们人类,作为一个智能体,通过观察这个世界,并进行各种各样的自主行动,在这个世界中生存,并对其产生影响。通用人工智能的实现,就是期望能通过计算机模拟人类这样的智能体进行各种各样的行动决策。

为了简化问题,我们可以像下面这样建模这个世界和智能体。我们可以认为在某一个时刻整个世界处于状态S1,当智能体进行了某一个行动之后,这个世界的状态变化为了S2。智能体之所以能够做出这一行动,是因为其心中有一个目标,并且从这个世界中得到了一定的反馈。

举个例子。比如我们想要喝水(目标),身边有一个杯子和一个饮水机(状态S1),我们会观察杯子和饮水机的位置,再伸手去拿取杯子(行动),然后将杯子靠近(反馈)饮水机,到达饮水机出水位置之后(状态S2),饮水机开始出水,之后我们再将杯子举到嘴边就能喝到水了。这个简单的模型可以图示如下:

智能体(Agent)通过观察这个世界(Environment)的状态(State: s),经过智能决策,开展了一些行动(Actions: a),这些行动进而引起了这个世界的状态变化。智能体从这些变化的状态中获得关于之前行动的反馈(Reward: r),从而指导后续的行动决策。就这样,整个世界周而复始的一直循环下去。

从这个模型出发,由于因果律的存在,是不是知道了S1这个初始状态及智能体做出的行动A之后,我们就可以直接计算下一状态S2了呢?理论是可行的,但实际情况要更复杂一些,因为状态实在太多太多了,我们通常无法直接建模所有的状态。这时,我们可以用统计学的方式来解决这个问题。我们可以认为在我们做出某一行动之后,这个世界的状态只是有一定概率会转换为S2,同时也有一定的概率会转换为S2_1等等。这样就算我们建模的状态不全,也可以相对较好的描述这个系统。

引入统计学的思维,也就引入了不确定性,虽然如此,但是却带来了更合理的描述系统的方式和系统层面的确定性。

以上描述的这一模型,在强化学习的世界里,我们称作Markov决策过程,简称MDP(Markov Decision Process)。这里面的不确定性也就是Markov特性。

有了这个模型之后,我们就可以从数学上来研究这个问题了。强化学习研究的正是如何在这样的一个数学模型的基础上去实现一个有效的算法,进而实现智能决策。


一个小例子

我们可以设计一个简单的小游戏来辅助解决这个问题。

如上图,机器人(智能体)可以在这样的网格中移动:

  • 绿色格子代表机器人可以移动到的位置
  • 灰色格子表示有障碍物,机器人不能移动到那个位置
  • 红色格子表示一个陷阱,如果机器人移动到此,游戏失败
  • 黄色格子代表一个出口,如果机器人移动到此,游戏成功

这个游戏中的MDP,可以描述为如下:

  1. 系统状态:格子位置,机器人位置
  2. 机器人可执行的动作:向上下左右四个方向移动
  3. 状态转换概率:如果机器人向某个方向移动,它移动到对应方向的格子的概率假设为0.7(如果无法移动到对应方向的位置,则留在原格子的概率为0.7),移动到其他位置的概率为0.3/n,n为其他可转换到的状态的数量。

状态转换概率举例如下(假设我们对格子进行编码,编码方式与excel表格的编码方式一致,从A1到E3):

  1. 假设机器人在位置A2,如果其向上移动,有70%的概率会移动到A1,分别有15%的概率会移动到A2(留在原位)和A3
  2. 假设机器人在位置A2,如果其向左或向右移动,有70%的的概率会留在原位A2,分别有15%的概率会移动到A1和A3

我们的算法要解决的问题是,在任意绿色格子里面放置一个机器人,算法可以指导机器人一步一步到达位置E1(成功完成游戏)。


方案与算法

为了实现一个智能算法解决上述机器人走格子问题,我们可以考虑给每个格子定义一个价值。这个价值表示到达这个格子后有多大可能性能成功完成游戏。

观察这个游戏可以发现,D1的价值应该高于C1,C1的价值应该高于B1。

如果可以计算出每个格子的价值,我们是不是就解决了这个问题了呢?因为,无论机器人处于哪个位置,它只需要往价值比当前格子更高的格子方向走即可。

现在问题转化为如何定义和计算这个价值。

我们先将目标数值化。由于到达出口格子即成功,如果机器人能到达此处,我们就给智能体反馈奖励1。同理,如果到达陷进格子,反馈奖励-1,到达绿色格子则奖励0。

这个时候我们来看格子D1。如果机器人在此处,它可以往四个方向移动。如果右移,有70%的概率可以到达出口,获得奖励1。如果往其他三个方向走,则分别有10%的概率会到达出口,获得奖励1。

经过以上的分析可以发现,我们其实可以将概率与奖励相乘来代表某个移动方向的价值。得到如下的价值数值:

  • 向右移动:0.7 * 1 = 0.7
  • 向上/下/左移动:0.1 * 1 = 0.1

这里的数值我们可以定义为动作价值。有了这个动作价值,要计算某个格子的价值,我们其实可以直接用最大的动作价值来表示,即:max([0.7, 0.1, 0.1, 0.1]) = 0.7。

如果要计算格子C1的价值呢?这时,虽然达到格子D1的奖励为0,但是我们可以利用刚计算好的D1的价值。还是按照前面的方式进行计算:

  • 向右移动:0.7 * (0 + 0.7) = 0.49
  • 向上/下/左移动:0.1 * (0 + 0.7) = 0.07
  • 格子价值:max([0.49, 0.07, 0.07, 0.07]) = 0.49

到这里,一个简单的算法呼之欲出。我们只需要找到所有有奖励的位置,然后从那里开始去计算其他所有位置的奖励,好像这个问题就解决了。

实际情况会稍微复杂一些。因为我们可能有很多个位置都存在奖励,而且这些奖励的多少可能由于任务定义而不一样。这里更实际一些的算法是利用多次迭代来实现。

为了不失一般性,我们可以定义公式:

(表示每个动作的价值,其中:s表示当前状态;a表示动作;s'表示下一个状态;T(s, a, s')表示在状态s,执行动作a转换到状态s'的概率;R(s, a, s')表示表示在状态s,执行动作a转换到状态s'得到的奖励)

(表示每个格子的价值,其中:s表示当前状态,a表示动作)

一般而言,我们会引入一个额外的γ参数,对下一个状态的价值打一定的折扣,这是因为当前获得的奖励一般会优于下一个状态的价值的,毕竟下一个状态的价值只是一个估计值。这时,上述第一个公式变为:

于是,我们的算法就可以描述为:* 对每一个状态,初始化 V := 0 * 循环,直到V收敛:* 对每一个状态,

这里为判断V是否收敛,我们可以检查当前这次迭代是否会更新V的值。用javascript代码实现,主要代码如下:

MDPVISolver.solve = function () {
  var values = m.zeroArray([this.states.length]);
  var valuesNew = values;
  var iterations = 0;
  do {
    var qValuesAll = [];
    values = valuesNew;
    valuesNew = [];
    for (var i = 0; i < this.states.length; i++) {
      var state = this.states[i];
      var qValues = this.qValues(values, state);
      qValuesAll.push(qValues);
      var value = this.value(qValues);
      valuesNew.push(value);
      }
    console.log('finished iteration ' + (++iterations));
    // console.log('values: ', values);
  } while(!this.converged(values, valuesNew));   
  ...
}

这里我已经实现了上述的游戏的一个Demo,见这里(http://brightliao.com/examples/mdp/grid-world.html),完整代码见这里(https://github.com/gmlove/gmlove.github.io/blob/source/source/examples/mdp/grid-world.js)865行到890行。

上述算法就是强化学习里面的经典算法 价值迭代 算法了。而我们上面定义V的迭代形式的公式就是著名的 Bellman 公式了,其最初由 Richard Bellman 提出。


另一个思路

上述算法存在一个问题,我们最后得到的是一系列状态价值(每个格子的价值),为了得到我们想要的行动,我们还需要根据根据状态价值,计算行动价值,即上述Q(s, a)。使用上有所不便。

那么有没有办法改进呢?再来思考一下这个问题的目标,实际上我们想要找到一种指导机器人行动的策略。这里的策略可以表示为:在任意一个位置,算法可以给出一个恰当的行动。

我们能不能直接去衡量某一个策略的价值呢?因为一旦有了这个策略的价值,我们就可以考虑直接去优化这个策略,而不是去对所有的状态计算价值。

对于某一策略,由于其可以基于当前状态指导我们作出行动,我们可以定义它为一个 输入为状态 输出为行动 的函数,即π: a = π(s)

既然这样,参考价值迭代算法中的状态价值(格子价值)定义,我们可以定义策略价值函数为:

(策略π的价值,其中:s表示当前状态;a = π(s)表示动作;s'表示下一个状态;T(s, π(s), s')表示在状态s,执行动作a=π(s)转换到状态s'的概率;R(s, π(s), s')表示在状态s,执行动作a=π(s)转换到状态s'得到的奖励)

上面的公式是一个迭代形式的定义,既然如此,我们可以参考之前的状态价值迭代算法,迭代计算这个策略的价值,最后这个价值可能会收敛到某个具体的值。

然而就算可以计算策略的价值,我们如何得到一个有效的策略呢?如果没有策略,其实也无从计算其价值。

能不能随机初始化一个策略?在这基础上计算其价值,进而得到更好的策略。

对于以上解决问题的思路,我第一次看到的时候,也不禁暗暗赞叹。事实上,这就是我这里想要给大家介绍的另一个强化学习经典算法:策略迭代 算法。

如何根据一个策略寻找更优策略?可以这样做:

  • 计算在当前策略下,哪一个行动能得到最大价值
  • 选择价值最大的行动作为新策略的行动

用公式表述如下:

(下一个(第i+1个)更优策略π(i+1),其中:s表示当前状态;a = π(s)表示动作;s'表示下一个状态;T(s, a, s')表示在状态s,执行动作a转换到状态s'的概率;R(s, a, s')表示在状态s,执行动作a转换到状态s'得到的奖励)

到这里,这个 策略迭代 算法就差不多完成了。用JavaScript代码实现,主要代码如下:

MDPPISolver.solve = function () {
  var policy = this.randomPolicy();
  var policyNew = policy;
  do {
    policy = policyNew;
    values = this.solveForPolicy(policy);
    policyNew = this.improvePolicy(values, policy);
  } while (!this.converged(policy, policyNew));
  ...
}

完整代码见这里(https://github.com/gmlove/gmlove.github.io/blob/source/source/examples/mdp/grid-world.js)932行到1024行。


扩展

状态空间降维

虽然我们可以用上述两个经典算法解决这个问题,但是它们的效率是很低的,算法复杂度用大O计算法可以表示为O(ass)。对于这个非常简单的问题,计算速度尚能接受,但是如果我们考虑一些更复杂的问题,就会发现这里的状态s的取值空间可能会非常大。

比如对于下面这个吃豆子的游戏,这里的状态数量为:

状态数量 = 格子数量 * N (N为每个格子的可能状态:比如是否有吃豆人、是否有豆子、是否有敌人及敌人的类型等等)

过大的状态空间就导致上述经典算法实际无法执行,也就无法满足实际需求。

一个可能的优化手段是人为的设计一些特征来表示某个状态s,这样就实现了对s进行降维的操作。比如对于上面吃豆子的游戏,我们可以建模这样几个特征:

  • 离最近的豆子的方向和距离
  • 离每个敌人的方向和距离
  • 敌人的移动速度和方向

有了这样的很小的状态空间,上述算法就可以执行了。

深度强化学习DQN

有了上述状态空间降维的办法,我们可以考虑是不是可以用一个深度神经网络来替代人工特征的过程呢?当然是可以的,这就是前几年 Deep Mind 轰动学界和产业界的关于 深度强化学习 的论文中的内容了。

DQN的全称是Deep Q-Network,它的核心是一个Q值迭代的算法。Q值迭代公式就是我们 价值迭代 公式中的关于行动价值的公式的一个迭代形式。算法也是不断迭代直到收敛。

我在另一篇文章中有关于DQN的更多内容。详情见这里(http://brightliao.com/2016/12/05/let-machine-play-games/)。

更多的问题

考虑一个更实际的问题,上述经典算法假设我们知道了状态转移函数T。但实际上当前世界可能对于我们是全新的,T对于我们而言当然也是未知的。这个时候有什么办法呢?一个简单的思路是我们可以通过不断在这个世界中进行探索,去了解这个世界的运作方式,也就是不断的弄清了这个T函数。在强化学习的研究中,抽象一下这个过程,即通过不断采样来近似估计T函数。

另一个实际的问题是,有时候我们可能无法执行这么多次探索,或者每次探索的成本太高以至于负担不起。这时,一个有效的思路是,我们可以从别人的经验中学习,或者通过看电影读书进行学习。当前的强化学习方法也在这个方向上进行了很多探索。

对于如何高效的进行学习,还有一个思路,那就是我们能否模仿某个已有的不错的行动策略呢?比如,假设我们希望训练机器人做家务,那么是不是可以通过演示一遍给机器人看,然后机器人通过模仿进行学习呢?这就是模仿学习思路去解决这个问题。

关于这个领域,我们还可以想出更多的问题,比如,如何让机器人自己去探索解决问题的方法?如何处理连续的动作(文章开始时提到的喝水的例子,这里移动双手的过程其实就是连续动作决策的过程)?如何自动设置奖励甚至不设置奖励?很多越来越难问题被一个一个提出,同时又正在被不断提出的新思路一个一个攻克。


总结

总结起来,强化学习其实就是关于如何学习的研究。这个领域发展至今能解决的问题还比较有限,我们离最终的通用人工智能的路还很长。同时,很多新的有挑战性的问题不断被提出来,被大家研究,很多创新的解决问题的思路也不断被发掘出来。正是我们对这个领域充满热情,才推动了这个领域如此蓬勃的发展。相信终有一天这个问题能被我们人类攻克。

本文分享自微信公众号 - ThoughtWorks洞见(TW-Insights),作者:廖光明

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 强化学习是如何解决问题的?

    什么是强化学习算法呢?要回答这个问题,必须先回答强化学习可以解决什么问题,强化学习如何解决这些问题。

    博文视点Broadview
  • 我是如何入门机器学习的呢

    机器学习在很多眼里就是香饽饽,因为机器学习相关的岗位在当前市场待遇不错,但同时机器学习在很多人面前又是一座大山,因为发现它太难学了。在这里我分享下我个人入门机器...

    abs_zero
  • 学习JVM是如何从入门到放弃的?(修订版)

    JVM在准备面试的时候就有看了,一直没时间写笔记。现在到了一家公司实习,闲的时候就写写,刷刷JVM博客,刷刷电子书。

    程序员小强
  • 人人能上手:OpenAI发射初学者友好的强化学习教程 | 代码简约易懂

    他们刚刚发射了一套强化学习 (RL) 入门教程,叫做Spinning Up。真诚友好,无微不至。

    量子位
  • 强化学习如何入门?看这篇文章就够了

    对于大脑的工作原理,我们知之甚少,但是我们知道大脑能通过反复尝试来学习知识。我们做出合适选择时会得到奖励,做出不切当选择时会受到惩罚,这也是我们来适应环境的方式...

    量子位
  • 这里是强化学习入门,的入门 | 绝对新手友好

    强化学习是机器学习里面非常重要的一个派别。智能体 (agent) 会不断执行一些操作,通过结果来学习,在不同的环境中分别应该采取怎样的行动。

    量子位
  • 专访 | 英特尔AIPG数据科学主任 Yinyin Liu:英特尔更注重构建整体性端到端平台

    机器之心原创 作者:邱陆陆 2016 年起,英特尔在人工智能领域接连的大手笔收购引起了业界广泛关注。从 Nervana 到 Movidius 和 Mobiley...

    机器之心
  • 微软张若非:搜索引擎和广告系统,那些你所不知的AI落地技术

    这两年,被誉为“皇冠上的明珠”的自然语言处理领域发展愈发火热,成为了业内新宠,而搜索和广告这两大老牌技术领域似乎已被大家遗忘。其实,这两大接地气的工程领域仍是各...

    AI科技大本营
  • 入门 | GPU是如何优化运行机器学习算法的?

    机器之心
  • 当强化学习遇见泛函分析

    随着 DeepMind 公司的崛起,深度学习和强化学习已经成为了人工智能领域的热门研究方向。除了众所周知的 AlphaGo 之外,DeepMind 已经与著名的...

    张戎
  • 【论文复现】一步步详解用TD3算法通关BipedalWalkerHardcore-v2环境

    熟悉强化学习Gym环境的小伙伴应该对 (BWH-v2环境) BipedalWalkerHardcore-v2(如图1)并不陌生。在这个环境里,这个Agent需...

    深度强化学习实验室
  • B程序员:讲述三年计算机学习辛酸史

    近年来,有些读者会问我一些形形色色的问题,让我很难去回答,甚至给不出建设性的意见。

    Guide哥
  • 吴恩达说“将引领下一波机器学习技术”的迁移学习到底好在哪?

    【导读】两年前,吴恩达在 NIPS 2016 的 Tutorial 上曾说“在监督学习之后,迁移学习将引领下一波机器学习技术商业化浪潮。”现实中不断有新场景的出...

    AI科技大本营
  • 吴恩达亲自采访百度林元庆和谷歌 Ian Goodfellow,他们对AI入门者有何忠告?

    AI 科技评论按:随着吴恩达公开 Deeplearning.ai 系列深度学习课程,他也出人意料地放出了一系列主题为“The Heros in Deep Lea...

    AI科技评论
  • 腾讯AI足球队夺冠Kaggle竞赛,绝悟强化学习方案迁移至足球队

    12月30日,腾讯宣布其人工智能球队摘得首届谷歌足球Kaggle竞赛冠军。该冠军球队来自腾讯AI Lab研发的绝悟WeKick版本,凭借1785.8的总分在与全...

    AI科技大本营
  • 诺亚方舟实验室李航:深度学习还局限在复杂的模式识别上

    用户1737318
  • 张潼:独家起底腾讯 AI Lab军力,对标世界一流实验室 | 新智元峰会演讲

    【新智元导读】腾讯在3月23日宣布,张潼担任腾讯AI Lab(腾讯人工智能实验室)主任、杰出科学家,作为部门第一负责人带领团队做AI领域的基础研究和应用探索。3...

    新智元
  • DeepMind高赞课程:24小时看完深度强化学习最新进展(视频)

    今天,DeepMind 官推贴出一则告示,将 DeepMind 研究人员今年在 UCL 教授的深度强化学习课程“Advanced Deep Learning a...

    新智元
  • 当AI开始“踢脏球”,你还敢信任强化学习吗?

    足球机器人排成一排向球门发起射击,但守门员却并没有准备防守,而是一屁股倒在地上开始胡乱摆动起了双腿。然后,前锋跳了一段十分令人困惑的舞蹈,跺跺脚,挥挥手,啪叽一...

    脑极体

扫码关注云+社区

领取腾讯云代金券