研究生课程：高级人工智能-第14讲 强化学习

《高级人工智能》课程笔记：第14讲 强化学习

第14讲 强化学习

强化学习

目标：学习从环境状态到行为的映射（即策略），智能体选择能够获得环境最大奖赏的行为，使得外部环境对学习系统在某种意义下的评价为最佳。

区别于监督学习：监督学习是从标注中学习；强化学习是从交互中学习

两种反馈

评价性反馈

• 当智能体采取某个行为时，对该行为给出一个评价，但并不知道哪个行为是最好的
• 强化学习经常面临的是评价性反馈

指导性反馈

• 直接给出某个状态下的正确或最好行为
• 独立于智能体当前采取的行为
• 监督学习使用的是指导性反馈

强化学习的两大特性

试错搜索和延迟奖励，用于判断某一问题是否适用于强化学习求解。

强化学习需要应对的挑战

利用和探索之间的矛盾

强化学习的要素

主体：智能体和环境-状态、行为和奖励

要素：

• 策略：状态到行为的映射，包括确定策略和随机策略两种
• 奖励：关于状态和行为的函数，通常具有一定的不确定性
• 价值：累积奖励或长期目标
• 环境模型：刻画环境对行为的反馈

强化学习发展历程

• 1911年，Thorndike 提出效果律（Law of effect），从心理学的角度探讨了强化思想：动物感到舒服的行为会被强化，动物感到不舒服的行为会被弱化
• 1954年，马文 · 明斯基（Marvin Minsky）在其博士论文中实现了计算上的试错学习
• 1957年，Bellman提出求解最优控制问题的动态规划方法，并提出了最优控制问题的随机离散版本，即著名的马尔科夫决策过程
• 1960年，Howard提出马尔科夫决策过程的策略迭代方法
• 1961年，明斯基在其论文“Steps toward artificial intelligence”中首次使用“Reinforcement learning”一词
• 1989年，Watkins提出了Q-learning，将动态规划、时序差分、蒙特卡洛模拟三条线结合在了一起
• 1992年，Tesauro 将强化学习成功应用到西洋双陆棋
• 2015年，强化学习和深度学习结合： AlphaGo
• 2017年，AlphaGo Zero

多臂赌博机

一台赌博机有多个摇臂 ，每个摇臂摇出的奖励（reward）大小不确定 ，玩家希望摇固定次数的臂所获得的期望累积奖励最大

问题形式化

行为：摇哪个臂

奖励：每次摇臂获得的奖金

表示第轮的行为，表示第轮获得的奖励

第轮采取行为的期望奖励为：

假如摇臂次， 那么按照什么策略摇臂，才能使期望累积奖励最大呢？

当已知时， 每次都选择最大的（贪心策略）

但是一般情况下，对于玩家而言是未知的或具有不确定性，玩家在第轮时只能依赖于当时对的估值进行选择，此时，贪心策略是在第轮 选择最大的

利用和探索

利用：

• 按照贪心策略进行选择，即选择最大的行为
• 优点：最大化即时奖励
• 缺点：由于只是对的估计，估计的不确定性导致按照贪心策略选择的行为不一定是最大的行为

探索：

• 选择贪心策略之外的行为
• 缺点：短期奖励会比较低
• 优点：长期奖励会比较高 ，通过探索可以找出奖励更大的行为，供后续选择

每步选择在“利用”和“探索”中二选一

如何平衡“利用”和“探索” 是关键

贪心策略形式化地表示为：，当有多个行为的同时为最大时，随机选择一个

贪心策略：

• 以概率按照贪心策略进行行为选择（Exploitation）
• 以概率在所有行为中随机选择一个（Exploration）
• 的取值取决于的方差，方差越大取值应越大

行为估值方法

根据历史观测样本的均值对进行估计

约定：

• 当分母等于0时，
• 当分母趋于无穷大时，收敛到

行为估值时，一个行为被选择了次后的估值记为，该估值方式需要记录个奖励值

乐观初值法

行为的初始估值

• 前述贪心策略中，每个行为的初始估值为0
• 每个行为的初始估值可以帮助我们引入先验知识
• 初始估值还可以帮助我们平衡exploitation 和 exploration

乐观初值法：Optimistic Initial Values

• 为每个行为赋一个高的初始估值
• 好处：初期每个行为都有较大机会被explore

小结

• 多臂赌博机是强化学习的一个简化场景，行为和状态之间没有关联关系
• 扩展情形
  • 有上下文的多臂赌博机
    • 存在多个多臂赌博机，状态表示赌博机
    • 学习状态到行为的映射
    • 但行为不改变状态
• 更一般的情形
  • 马尔科夫决策过程

马尔科夫决策过程

• 常用于建模序列化决策过程
• 行为不仅获得即时奖励，还能改变状态，从而影响长期奖励
• 学习状态到行为的映射-策略
  • 多臂赌博机学习
  • MDP学习或

奖励设置

• 设置奖励是希望智能体能达到我们期望的目标
  • 下围棋
    • 目标：赢棋
    • 奖励需要是能够实现赢棋这一目标才合适
      • 吃子多少？占领棋盘的中心？
  • 迷宫
    • 目标：尽快走出去
    • 奖励：每走一步，奖励为-1（相当于惩罚）
  • 垃圾回收机器人
    • 目标：在尽可能少的人工干预的情况下回收尽可能多的垃圾
    • 奖励：回收一个垃圾奖励+1 （等待和主动寻找获得奖励的概率不同），人工干预一次奖励-3

贝尔曼方程的作用

贝尔曼方程定义了状态估值函数的依赖关系

• 给定策略下，每个状态的估值视为一个变量
• 所有状态（假如有个）的估值根据贝尔曼方程形成了一个具有个方程和个变量的线性方程组
• 求解该方程组即可得到该策略下每个状态的估值

寻找最优策略

• 基于状态估值函数的贝尔曼最优性方程
  • 第一步：求解状态估值函数的贝尔曼最优性方程得到最优策略对应的状态估值函数
  • 第二步：根据状态估值函数的贝尔曼最优性方程，进行一步搜索找到每个状态下的最优行为
    • 注意：最优策略可以存在多个
    • 贝尔曼最优性方程的优势，可以采用贪心局部搜索即可得到全局最优解
• 基于行为估值函数的贝尔曼最优性方程
  • 直接得到最优策略

寻找最优策略小结

求解贝尔曼最优性方程寻找最优策略的局限性

• 需要知道环境模型
• 需要高昂的计算代价和内存（存放估值函数）
• 依赖于马尔科夫性