强化学习笔记(三): 无模型算法

1. 基本概念

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

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

MDP 问题有两种:prediction和control(见上一章)

prediction 问题(据一个策略和一套 MDP 环境得到一套价值函数)
- 蒙特卡洛算法(Monte-Carlo,MC)
- Temporal-Difference Learning(TD-learning)
control 问题(根据一套 MDP 环境得到最佳的价值函数及其对应的策略)
- 根据 MC and TD 得到的推广的Policy Iteration

2. Prediction 问题算法

2.1 蒙特卡洛算法

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

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

$\begin{aligned} \mu_t &= \frac{1}{t}\sum_{j=1}^tx_j\\ &=\frac{1}{t}(x_t+\sum_{j=1}^{t-1}x_j)\\ &=\frac{1}{t}[x_t+(t-1)\mu_{t-1}]\\ &=\mu_{t-1}+\frac{1}{t}(x_t-\mu_{t-1}) \end{aligned}$

作用到价值函数上即为

$\begin{aligned} N(S_t) &\leftarrow N(S_t) + 1\\ v(S_t) &\leftarrow v(S_t) + \frac{1}{N(S_t)}(G_t-v(S_t)) \end{aligned}$

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

$v(S_t) \leftarrow v(S_t) + \alpha (G_t-v(S_t))$

2.2 TD-Learning

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

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

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

其迭代价值函数的公式为

$\begin{aligned} v(S_t) \leftarrow v(S_t) + \alpha [R_{t+1}+\gamma b(S_{t+1})-v(S_t)] \end{aligned}$

$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 为无限大时,就变成了蒙特卡洛算法)

$\begin{aligned} &n=1 &G_T^{(1)}&=R_{t+1}+\gamma v(S_{t+1})\\ &n=2 &G_T^{(2)}&=R_{t+1}+\gamma R_{t+2} + \gamma^2 v(S_{t+2})\\ & &\vdots&&\\ &n=\infty &G_T^{(\infty)}&=R_{t+1}+\gamma R_{t+2} + \dots + \gamma^{T-t+1}R_T\\ \end{aligned}$

2.3 Prediction 算法对比

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

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

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

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

3. Control 问题算法

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

与普通的 Policy Iteration 一样,GPI 还是由policy evaluation和policy 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 Starts和epsilon-Greedy Exploration对于 TD-Learning 也是适用的,不再赘述

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

其算法如下:

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

3.3 Q-Learning 方法

Q-Learning 的迭代方法如下

$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha [R_{t+1}+\gamma Q(S_{t+1},A')-Q(S_t,A_t)]$

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

$\pi(S_{t+1})= argmax_{a'}Q(S_{t+1},a')$

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

$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha [R_{t+1}+\gamma \max_aQ(S_{t+1},a)-Q(S_t,A_t)]$

Q-Learning 的完整算法如下:

3.4 On-Policy Learning vs Off-Policy Learning

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

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

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