无模型算法

1. 基本概念

前面讲的 MDP 的解法都假设知道状态的固有奖励和转移函数,也就是有环境的模型.
从而找到一个”后门”,用与模型交互代替与环境交互.

但是真实情况下我们很少有环境模型,或者模型太过复杂无法使用
为此我们需要无模型的算法,通过与真实环境交互,得到奖励并转换状态,从中获取经验

MDP 问题有两种:predictioncontrol(见上一章)

  1. prediction 问题(据一个策略和一套 MDP 环境得到一套价值函数)

    • 蒙特卡洛算法(Monte-Carlo,MC)
    • Temporal-Difference Learning(TD-learning)
  2. control 问题(根据一套 MDP 环境得到最佳的价值函数及其对应的策略)

    • 根据 MC and TD 得到的推广的Policy Iteration

2. Prediction 问题算法

2.1 蒙特卡洛算法

简单来说,就是从一个状态出发,进行大量模拟,得到大量轨迹(episode),计算每条轨迹的 Return 值,取其平均值作为出发状态的 value function

更进一步,可以使用Incremental Mean(增量平均)代替普通的平均值,使得算法可以不断使用新的数据

作用到价值函数上即为

再进一步,可以把上述公式的系数固定,使得算法在使用新数据的时候可以不断遗忘过去的数据

2.2 TD-Learning

蒙特卡洛算法从一个点出发,模拟路径到路径尽头,而 TD-Learning 仅仅模拟有限步数,有bootstrap的感觉(可以翻译成拔靴自助)

[BootStrap 的由来与内涵 | 海上泊舟 | 知乎]

简而言之,源自<<蒙乔森男爵的冒险故事>>(吹牛大王历险记)
“男爵掉到湖里沉到湖底,在他绝望的时候,他用自己靴子上的带子把自己拉了上来”
表示不借助外力,凭借自身进步与成功

其迭代价值函数的公式为

$R_{t+1}+\gamma b(S_{t+1})$ 叫做 TD target
$\delta_t=R_{t+1}+\gamma b(S_{t+1})-v(S_t)$ 叫做 TD error
$\gamma$ 和 $\alpha$ 是 TD-Learning 的两个超参数

从公式中可以看到,与蒙特卡洛算法不同,TD-Learning 每次向前模拟一步(也可能是多步)都会学习一些东西

更进一步,TD-Learning 可以增大每次模拟的步数,进化为n-step TD-Learning(当 n 为无限大时,就变成了蒙特卡洛算法)

2.3 Prediction 算法对比

DP(动态规划):每次考虑所有的可能性,但是对于每个可能性都不深入探索

MC(蒙特卡洛算法):每次只考虑一个可能性,但是把这个可能性探索到尽头

TD(TD-learning):每次考虑一个可能性,探索有限个步数

还有一个组合:探索所有的可能并极尽到头,这就成了便利了

3. Control 问题算法

无模型 Control 问题通常用 Generalize Policy Iteration(GPI)方法解

与普通的 Policy Iteration 一样,GPI 还是由policy evaluationpolicy improvement两部分组成
policy evaluation中,求解价值函数被 generalize 为求解 Q 函数
policy evaluation则被替代为 MC 或者 TD-Learning

同时还有一种类似 value iteration 的方法:Q-Learning(其实感觉应该叫 Q Iteration)

Q-Learning 对 Q 函数不断进行迭代,最后抽取出最佳策略

3.1 蒙特卡洛方法

为了使得所有的状态都能得到足够次数的更新,蒙特卡洛方法可以随机选择起始状态和行动,这种方法叫做Exploring Starts
这样可以使得所有状态和行动被更新的概率都大于 0

上述方法可以看作是在exploration(探索)exploitation(利用)trade-off(权衡)中完全偏向 exploration 了
再进一步的改进可以以 $\epsilon$ 的概率选择随机选择状态和行动(探索),以 $1-\epsilon$ 的概率在选择行动的时候选择表现最好的行动(利用)
这种方法叫做epsilon-Greedy Exploration

算法如下(不想再手打算法了…):

3.2 TD-Learning 方法

首先 MC 中的Exploring Startsepsilon-Greedy Exploration对于 TD-Learning 也是适用的,不再赘述

TD-Learning 方法结合 Policy Iteration 方法,即得到了Sarsa算法
Sarsa 的意思是:连续执行两次epsilon-greedy算法,选择两次动作 a

其算法如下:

再进一步,n-step TDPolicy Iteration结合,即得到了n-step Sarsa(截图公式真不错,再也不手打了哈哈哈哈)

3.3 Q-Learning 方法

Q-Learning 的迭代方法如下

更新 Q 函数后,直接通过贪心算法即可得到最佳策略 $\pi$

综合上述两个公式,即可得到 Q-Learning 的核心迭代公式
需要注意的是,$\max_aQ(S_{t+1},a)$ 中的 a 取自多个 $\pi$ 策略,在一次迭代中只取一个
而 Q()函数本身来自多个 $\mu$ 策略,所以这个 max 是作用于 Q 上而非 a 上面
利用 $\mu$ 策略的激进性和 max 操作的保守性,可以很好地平衡探索与利用两个矛盾(应该是这样吧)

Q-Learning 的完整算法如下:

3.4 On-Policy Learning vs Off-Policy Learning

知乎上关于这个有很好的回答: 强化学习中 on-policy 与 off-policy 有什么区别? - LinLin 的回答 - 知乎

其中对这两个方法形象的描述:

古时候,优秀的皇帝都秉持着“水能载舟 亦能覆舟”的思想,希望能多了解民间百姓的生活。
皇帝可以选择通过微服出巡,亲自下凡了解百姓生活(On-policy),虽然眼见为实,但毕竟皇帝本人分身乏术,掌握情况不全;
因此也可以派多个官员去了解情况,而皇帝本人则躺在酒池肉林里收听百官情报即可(Off-policy)。
(坏皇帝则派出“锦衣卫”_(´ཀ`」 ∠)_)

On-Policy Learning

在学习的过程中,把得到的经验直接汇入维护的唯一策略中
在探索的过程中,策略会故意表现得不完美,以此增加探索性,增加探索到未知方法的概率
(当然了,在实际使用的时候肯定会尽力表现得最好)

Off-Policy Learning

在学习的过程中,维护两个策略

  • target policy $\pi$ : 即主策略,学习的策略
  • behavior policy $\mu$ : 行动策略,产生轨迹的策略

4. Summary

最后补一个总结