不基于模型的控制

背景

本章内容

前一章内容讲解了个体在不依赖模型的情况下如何进行预测，也就是求解在给定策略下的状态价值或行为价值函数
本章则主要讲解在不基于模型的条件下如何通过个体的学习优化价值函数，同时改善自身行为的策略以最大化获得累积奖励的过程，这一过程也称作不基于模型的控制

问题举例

生活中有很多关于优化控制的问题，比如控制一个大厦内的多个电梯使得效率最高;
控制直升机的特技飞行
机器人足球世界杯上控制机器人球员，围棋游戏等等
两类问题：
- 所有的这些问题要么我们对其环境动力学的特点无法掌握，但是我们可以去经历、去尝试构建理解环境的模型;
- 要么虽然问题的环境动力学特征是已知的，但由问题的规模太大以至于计算机根据一般算法无法高效的求解，除非使用采样的办法。
- 无论问题是属于两种情况中的哪一个，强化学习都能较好的解决

算法的整体关系

从已知模型的、基于全宽度采样的动态规划学习转至模型未知的、基于采样的蒙特卡洛或时序差分学习进行控制是朝着高效解决中等规模实际问题的一个突破
基于这些思想产生了一些经典的理论和算法:
- 如不完全贪婪搜索策略、现时蒙特卡洛控制，现时时序差分学习
- 属于借鉴学习算法的 Q 学习等

行为价值函数的重要性

生活学习哲学到强化学习
- 生活中有些人喜欢做事但不善于总结，这类人一般要比那些勤于总结的人进步得慢，从策略迭代的角度看，
  - 这类人策略更新迭代的周期较长
  - 有些人在总结经验上过于勤快，甚至在一件事情还没有完全定论时就急于总结并推理过程之间的关系，这种总结得到的经验有可能是错误的
- 强化学习中的个体也是如此，为了让个体的尽早地找到最优策略，可以适当加快策略迭代的速度:
  - 但是从一个不完整的状态序列学习则要注意不能过多地依赖状态序列中相邻状态行为对的关系。
  - 由于基于蒙特卡洛的学习利用的是完整的状态序列，为了加快学习速度可以在只经历一个完整状态序列后就进行策略迭代
  - 而在进行基于时序差分的学习时，虽然学习速度可以更快，但要注意减少对事件估计的偏差

ε− 贪婪策略

背景

如上在动态规划策略迭代中，可看见：贪婪搜索策略在基于模型的动态规划算法中能收敛至最优策略(价值)，但这在不基于模型、基于采样的蒙特卡罗或时序差分学习中却通常不能收敛至最优策略
因为后两者则仅能考虑到有限次数的、已经采样经历过的状态，那些事实存在但还没经历过的状态对于后两者算法来说都是未探索的不被考虑的状态
- 有些状态虽然经历过，但由于经历次数不多对其价值的估计也不一定准确。
- 如果存在一些价值更高的未被探索的状态使用贪婪算法将式中无法探索到这些状态，而已经经历过但价值较低的状态也很难再次被经历，如此将无法得到最优策略
总体来说，使用贪婪策略，在MC,TD中，因为是采样，会导致有些状态不能经历或者经历的次数不够，造成无法得到最优策略
贪婪策略产生问题的根源是无法保证持续的探索，为了解决这个问题，一种不完全的贪婪 (ε-greedy 搜索策略被提出，其基本思想就是保证能做到持续的探索，具体通过设置一个较小的 ε 值，使用 1 − ε 的概率贪婪地选择目前认为是最大行为价值的行为，而用 ε 的概率随机的从所有m 个可选行为中选择行为，即:

现时策略蒙特卡罗控制

定义

现时策略蒙特卡罗控制通过 ε-贪婪策略采样一个或多个完整的状态序列后，平均得出某一状态行为对的价值，并持续进行策略的评估和改善。通常可以在仅得到一个完整状态序列后就进行一次策略迭代以加速迭代过程

GLIE

背景
使用 ε-贪婪策略进行现时蒙特卡罗控制仍然只能得到基于该策略的近似行为价值函数，这是因为该策略一直在进行探索，没有一个终止条件。因此我们必须关注以下两个方面:
- 一方面我们不想丢掉任何更好信息和状态
- 另一方面随着我们策略的改善我们最终希望能终止于某一个最优策略
为此引入了另一个理论概念:GLIE(greedy in the Limit with Infinite Exploration)
含义
- 一是所有的状态行为对会被无限次探索
- 二是另外随着采样趋向无穷多，策略收敛至一个贪婪策略:
- 定理：GLIE 蒙特卡洛控制能收敛至最优的状态行为价值函数

GLIE应用

如果在使用 ε-贪婪策略时，能令 ε 随采样次数的无限增加而趋向于 0 就符合 GLIE。这样基于 GLIE 的蒙特卡洛控制流程如下:

基于给定策略 π，采样第 k 个完整的状态序列:${S_1, A_1, R_2, · · · , S_T}$
对于该状态序列里出现的每一状态行为对$(S_t, A_t)$，更新其计数N 和行为价值函数Q:
基于新的行为价值函数 Q 以如下方式改善策略
- 在实际应用中，ε 的取值可不局限于取 1/k，只要符合 GLIE 特性的设计均可以收敛至最优策略(价值)

现时策略时序差分控制

前言介绍

预测问题上TD比MC有点多
我们体会到时序差分 (TD) 学习相比蒙特卡罗 (MC) 学习有很多优点:低变异性，可以在线实时学习，可以学习不完整状态序列等
控制问题上任很多优点,会介绍一些算法
在控制问题上使用TD学习同样具备上述的一些优点。
- 本节的现时策略TD学习中，我们将介绍Sarsa算法和Sarsa(λ)算法
- 在下一节的借鉴策略TD学习中将详细介绍Q学习算法

Sarsa 算法

算法理解
Sarsa 的名称来源于下图所示的序列描述:针对一个状态 S，个体通过行为策略产生一个行为 A，执行该行为进而产生一个状态行为对 (S,A)，环境收到个体的行为后会告诉个体即时奖励 R 以及后续进入的状态 S’;个体在状态 S’ 时遵循当前的行为策略产生一个新行为 A’，个体此时并不执行该行为，而是通过行为价值函数得到后一个状态行为对 (S’,A’) 的价值，利用这个新的价值和即时奖励 R 来更新前一个状态行为对 (S,A) 的价值与 MC 算法不同的是，Sarsa 算法在单个状态序列内的每一个时间步，在状态 S 下采取一个行为 A 到达状态 S’ 后都要更新状态行为对 (S,A) 的价值 Q(S,A)。这一过程同样使用 ε-贪婪策略进行策略迭代:
算法伪代码
Sarsa 算法将收敛至最优策略和最优价值函数条件
- 在更新行为价值时，参数 α 是学习速率参数，γ 是衰减因子。当行为策略满足前文所述的 GLIE 特性同时学习速率参数 α 满足
举例：有风格子
- 为了使用计算机程序解决这个问题，我们首先将这个问题用强化学习的语言再描述一遍。这是一个不基于模型的控制问题，也就是要在不掌握马尔科夫决策过程的情况下寻找最优策略。环境世界中每一个格子可以用水平和垂直坐标来描述，如此构成拥有 70 个状态的状态空间 S。行为空间 A 具有四个基本行为。环境的的动力学特征不被个体掌握，但个体每执行一个行为，会进入一个新的状态，该状态由环境告知个体，但环境不会直接告诉个体该状态的坐标位置。即时奖励是根据任务目标来设定，现要求尽快从起始位置移动到目标位置，我们可以设定每移动一步只要不是进入目标位置都给予一个 -1 的惩罚，直至进入目标位置后获得奖励 0 同时永久停留在该位置
- 这里先给出最优策略为依次采取如下的行为序列:
  右、右、右、右、右、右、右、右、右、下、下、下、下、左、左
  个体找到该最优策略的进度以及最优策略下个体从起始状态到目标状态的行为轨迹如图 5.3 所示。
- 可以看出个体在一开始的几百甚至上千步都在尝试各种操作而没有完成一次从起始位置到目标位置的经历。不过一旦个体找到一次目标位置后，它的学习过程将明显加速，最终找到了一条只需要 15 步的最短路径。由于世界的构造以及其内部风的影响，个体两次利用风的影响，先向右并北漂到达最右上角后折返南下再左移才找到这条最短路径。其它路径均比该路径所花费
  的步数要多

Sarsa(λ)算法

可以结合TD(λ)对比理解,这里不做详细介绍

在前一章，我们学习了 n-步收获，这里类似的引出一个 n-步 Sarsa 的概念。观察下面一些列的式子

借鉴策略Q学习算法

背景

现时策略学习的特点就是产生实际行为的策略与更新价值 (评价) 所使用的策略是同一个策略，而借鉴策略学习 (off-policy learning) 中产生指导自身行为的策略 μ(a|s) 与评价策略 π(a|s) 是不同的策略

具体地说，个体通过策略 μ(a|s)生成行为与环境发生实际交互，但是在更新这个状态行为对的价值时使用的是目标策略 π(a|s)
目标策略 π(a|s) 多数是已经具备一定能力的策略，例如人类已有的经验或其他个体学习到的经验

借鉴策略学习相当于站在目标策略 π(a|s)的“肩膀”上学习。

借鉴策略学习根据是否经历完整的状态序列可以将其分为基于蒙特卡洛的和基于 TD 的。
- 基于蒙特卡洛的借鉴策略学习目前认为仅有理论上的研究价值，在实际中用处不大。
- 这里主要讲解常用借鉴策略 TD 学习

借鉴学习TD学习任务

借鉴学习 TD 学习任务就是使用 TD 方法在目标策略 π(a|s) 的基础上更新行为价值，进而优化行为策略
我们可以这样理解:个体处在状态 $S_t$ 中，基于行为策略 μ 产生了一个行为 $A_t$，执行该行为后进入新的状态 $S_{t+1}$，借鉴策略学习要做的事情就是，比较借鉴策略和行为策略在状态 $S_t$ 下产生同样的行为 $A_t$ 的概率的比值(其实就是看此次对该状态价值的更新支持程度):
- 如果这个比值接近 1，说明两个策略在状态 $S_t$ 下采取的行为 $A_t$ 的概率差不多，此次对于状态 $S_t$ 价值的更新同时得到两个策略的支持
- 如果这一概率比值很小，则表明借鉴策略 π 在状态 $S_t$ 下选择 $A_t$ 的机会要小一些，此时为了从借鉴策略学习，我们认为这一步状态价值的更新不是很符合借鉴策略，因而在更新时打些折扣。
- 如果这个概率比值大于 1，说明按照借鉴策略，选择行为 $A_t$ 的几率要大于当前行为策略产生 $A_t$的概率，此时应该对该状态的价值更新就可以大胆些

Q学习

借鉴学习TD学习任务的典型分支
- 行为策略 μ 是基于行为价值函数 Q(s, a) ε-贪婪策略
- 借鉴策略 π 则是基于 Q(s, a) 的完全贪婪策略
这种学习方法称为 Q 学习 (Q learning)
Q学习的目标
Q 学习的目标是得到最优价值 Q(s,a)
策略μ
t 时刻的与环境进行实际交互的行为$A_t$由策略μ产生:$A_t ∼ μ(·|S_t)$,其中策略 μ 是一个 ε-贪婪策略
策略π
t + 1 时刻用来更新 Q 值的行为 $A’{t+1}$ 由下式产生:$ A’{t+1} ∼ π(·|S_{t+1}) $。其中策略 π 是一个完全贪婪策略
$Q(S_t, A_t)$ 的按下式更新
- 其中红色部分的 TD 目标是基于借鉴策略 π 产生的行为 A’ 得到的 Q 值。
- 根据这种价值更新的方式
  - 状态 $S_t$ 依据 ε-贪婪策略得到的行为 $A_t$ 的价值将朝着 $S_{t+1}$ 状态下贪婪策略确定的最大行为价值的方向做一定比例的更新
  - 这种算法能够使个体的行为策略策略 μ 更加接近贪婪策略，同时保证保证个体能持续探索并经历足够丰富的新状态。
并最终收敛至最优策略和最优行为价值
- 下图是 Q 学习具体的行为价值更新公式
  - 注意和上式比较max部分就是基于贪婪策略得到
伪代码

Q学习和Sarsa比较

这里通过悬崖行走的例子 (图) 简要讲解 Sarsa 算法与 Q 学习算法在学习过程中的差别。任务要求个体从悬崖的一端以尽可能快的速度行走到悬崖的另一端，每多走一步给以 -1 的奖励。图中悬崖用灰色的长方形表示，在其两端一个是起点，一个是目标终点。个体如果坠入悬崖将得到一个非常大的负向奖励 (-100) 回到起点。可以看出最优路线是贴着悬崖上方行走。Q 学习算法可以较快的学习到这个最优策略，但是 Sarsa 算法学到的是与悬崖保持一定的距离安全路线。在两种学习算法中，由于生成行为的策略依然是 ε 贪婪的，因此都会偶尔发生坠入悬崖的情况，如果 ε 贪婪策略中的 ε 随经历的增加而逐渐趋于 0，则两种算法都将最后收敛至最优策略

背景