强化学习-概述

课程来自 Udacity-Reinforcement Learning（2017）- 1.Smoov & Curly’s Bogus Journey 的笔记整理

强化学习的”Hello-world”

规则

• 绿色是目标
• 红色是失败
• 黑色是墙
• start是开始点
• 你要找到一条从start到目标的路径

思考

1. 如果给定一个附加概率：按着想法走的0.8,不按想法走的0.2。如果我们假定正确序列是”UURRR”.则这个序列最终能到终点的概率是?

答：如果按照正确的指令 UURRR走是可达的：概率是0.85=0.32768.但如果错误 也有一种RRUUR可达，这种前4次是错误的，第五次正确。发生概率是0.14∗0.8=0.0008。总计0.0008+0.32768=0.32776

强化学习 - 概述

与机器学习中概念进相比

• 监督学习：给定多组(x,y),拟合出一个Loss 最低的 f(x)
• 无监督学习:给定多组 x,找到一组函数集可以联合描述 x的变化特性。
• 强化学习：与监督学习相似，给定多组(x,y),同时一个抉择向量 z。强化学习可以称之为监督学习的扩展，扩展了一套决策方案而并非单一的 GD

定义

特性

• 提供了关于Decision Making在机器上的实现方案
• 基于计算机尝试不按既定规则的权利
• 通过奖励函数来使看似随机的函数行为变得可控
• 通过 延迟奖励使得决策注重整体，而非局部最优
• 通过 回滚决策 对一系列决策进行判断，尝试寻找问题的所在

与传统监督学习的区别

• 延迟奖励：强化学习的驱动是每次按规则给每个状态丢到另一个状态。但具体这个决策好或者不好，只有在之后的特定条件时才会知道。比如下棋，当经过60步后你赢的了棋局。这时你才明白这60步的决策是好是坏。
• 得到奖励后回滚我所做的抉择，分析是那些决策导致我获得了一个好的或是坏的决策

核心-决策框架 - Markov Decision Processes （MDP）

过程

1. 状态 - 决策时可能经历的状态集，上面例子为4X3的区域（包括上面游戏中的墙）
2. 传递模型 - T(s′|s,a) s 为状态,a为动作，s' 为下一个状态。注意传递模型的下一个状态，只依赖于当前状态 s
3. 动作 - 所有被允许的决策动作
4. 奖励函数 - 通过过程或者最终结果对当前执行行为进行评定。比如上例，如果最后结果是 green 那么就+1分，如果结果是red 就-1分

结果

policy(规则)：一个函数，输入一个状态返回一个动作，一个

MDPtips

• MDP框架的核心是让程序关注我在哪里，该做什么，是否会得到的奖励,而并非去计划”我后面的15 20步子该怎么走”
• MDP的关键是奖励函数的设置，最终规则集合包含了一系列奖惩措施

关于奖励

概述

• 奖励是让学习算法衡量决策好坏的标准
• 当我们想让获得的决策尽量步数少时，可以将默认奖励值设置为一个不大的负数单位：走过步数的平均要小于且与终止``吸收态有一定的数值距离

影响奖励的几大因素

1. 默认奖励数值
2. 吸收态奖励数值
3. 剩余的时间步
4. 每一步的偏差发生率（不按规定执行的概率）

一个关于奖励区别的例子

• 这是一个关于默认奖励不同的情况的两个例子，上面的区块默认奖励为+2，下面的默认奖励为-2
• 对于上面的而言，奖励为正值。为了能获得到更多的奖励，我们不能让程序进入停止游戏区间，最好的办法就是撞墙（不断的停留原地所以获得奖励）
• 对于下面的区间，由于奖励为负值，我们需要尽快的离开游戏。右下角的方向为上的原因是，如果当前为其他方向，那么肯定会有至少一个-2出现在奖励序列里。所以最好的方法是：直接终止，取得那个-1的红色区间
• 通过这个例子可以看出，当奖励函数不同，强化学习最后得到的规则集合也是截然不同的。

偏向稳定性

定义

如果有两个时间序列 A:s0,s1.s2与B:s0,s′1,s′2，如果 A>B 则 AB 的去掉相同元素的子序列仍然满足s1,s2>s′1,s′2。我们称这种现象为偏向稳定性

偏向稳定性与奖励序列

强化学习中，奖励是一个序列性的问题，也就是状态序列。学习的目的是希望最后能得到的总奖励最高。但请一定要注意时序的长短问题,即时间长度是否无限。

• 看上面的例子，如果问当上面情况一直重复时，哪个会更好？
• 答案是：两者都一样

• 看似下面的奖励要比上面多，因为有部分+2出现。但当时间无限时，上面得到的奖励:
  

  limn→+∞n=∞
  同样下边序列
  
  14(3limn→+∞n+limn→+∞2n)=∞
  
  上下相等

• 显然在无限时间内,讨论不受控制的没有负奖励的两个奖励序列的区别是无意义的

• 但是如上文单独讨论的一个序列的奖励大小也是无意义的。因为无穷大不是一个数。
• 这时我们就需要对无限增长的正奖励一个界定空间，即折扣期望

折扣期望

由来及描述

对上面的序列

加以扩展

这里 0≤γ<1
此时当 t 达到一定数量时，上式的值会停留在一个Rmax数值上,这里上式实际等价于

没错这就是一个等比数列前 n 项和的表达式

意义

• 让获得的奖励具有边界。这里实际是将Rmax值直接类比为无穷大
  
  • 折扣期望级数加和序列退化为等比序列
  • 等比数列又允许我们使用无穷多的数字跟在奖励值后做乘积，但结果的是一个又穷的数字
  • 允许我们在有穷的时间接触到无穷大
• 使之前的无穷时域具有了有穷性。

决策

最优决策与特定决策效用

我们定义最优决策：

这里E[]为整体的期望，表示我们希望找到一种可以最大化长期期望奖励的决策。
但上式我们无法知道从哪点开始。
同时定义特定策略的效用：

决策的效用意味着当程序遵循了一种决策后，从指定点S0开始最后将得到的奖励期望

s 点效用奖励 U（s）与瞬时决策奖励 R（s）的区别

• R(s)是当在s 点状态时，将得到的瞬时奖励
• U(s)是在 s 点起遵循一种决策后，将得到的长期奖励的期望。也就是从s 点开始将获得所有奖励的和
• 举个例子
  
  • “我给你200元，你去打校长一顿”，这里的200元就是瞬时决策奖励R(s)。本例中虽然R(s)大但是U(s)低
  • “你花费一些钱去读本科，最后你工作的起薪将会是6000元/月，这里的6000元/月就是决策效用奖励U(s). 本例中虽然R(s)为负，但长远的U(s)却很高

效用的意义

效用恰恰映射了强化学习中延迟奖励的意义。

通过效用定义最优决策

上式的含义是：通过传递函数 T得到当前状态的所有下一状态，并据其得到根据当前策略的效用期望U(s′) 。从中选择期望最大的作为当前的下一步。
此时的 U(s′)可以展开为：

也就是当前 s 状态的奖励R(s)加上 s’ 状态的折扣效用值。
上面的U(s)被称之为贝尔曼（Bellman）方程,该方程是求解 MDP 与强化学习的关键方程，它定义了某个状态中的真实价值

策略迭代

步骤

1. 从一个随机的规则π0开始
2. 给定πt计算Ut=Uπt 作为规则的评价
3. 提升规则：πt+1=argmaxa∑T(s,a,s′)Ut(s′)

表达式

意义

使用效用最优决策，使得在迭代中，每个效用 U(s')中的真实效用R(s)不断被扩散。最终使得整体效用不断逼近真实效用。

计算 Ut 的方法

- 评估时假定当前为最优决策，所以s 的状态就直接由最优决策决定
- 这里我们有 n 个未知数，n 个方程。所以有唯一解

Bellman 函数与强化学习

关联

我们将贝尔曼公式进行简单的变换得到：

我们称该式为value层面的 BellmanFunction
我们将 max 中的内容看做一个整体，经过变换可得到

我们称该式为Quality 层面的BellmanFunction，在强化学习中这是重要的函数

为何要区分出V Q U 函数

对于强化学习而言，QBellman函数更加有效。因为我们只需要使用已有的经验值就可以得到 Q函数的期望值。我们不需要在 Q 函数中直接访问奖励函数。
通过 V 函数作为媒介，V 值的迭代是由传递函数和奖励函数共同决定的

CBellman函数

站在持续性的角度考虑问题，重心放在奖励函数上

C V Q 函数间的相互转换

扩展内容

• 信用赋值问题：在决策时间序列里你的哪个动作决定了最后奖励结果的好坏，寻找这个结果的问题被称之为时间信用赋值问题