强化学习笔记(三)- 蒙特卡罗方法

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言,谢谢

引言

  本文开始介绍无模型的方法,无模型的方法需要在没有环境的数学描述下,只依靠经验学习出给定策略的价值函数和最优策略。根据价值函数的更新时机,强化学习又可以分为回合更新算法和时序差分更新算法。本文讨论的事回合更新算法,它只能用于回合制任务,它在每个回合结束更新价值函数,主要利用了蒙特卡洛方法(Monte Carlo Methods)。

  状态价值和动作价值分别是在给定状态和状态动作对下回报的期望值,回合更新策略评估的基本思路就是用 MC 方法来估计这个期望值。这其中又包括同策回合更新算法和异策回合更新算法。

同策(on-policy)回合更新

同策回合更新策略评估

  因为在无模型的情况下,状态价值和动作价值不能互相表示,所以无模型的策略评估算法有评估状态价值函数和评估动作价值函数两种版本。
  因为对于无模型的情况,\(p\) 未知,我们不能用状态价值表示动作价值,我们只能借助于策略 \(\pi\),用动作价值函数来表示状态价值函数。除此之外,由于策略改进可以仅有动作价值函数确定,因此在学习问题中,动作价值函数往往更加重要。
  在同一个回合中,多个步骤可能会到达同一个状态或状态动作对,对于不同次的访问,计算得到的回报样本值很可能不相同。

  • 如果采样回合内全部的回报样本值更新价值函数,则称为每次访问回合更新(every visit Monte Carlo update)
  • 如果只采样回合内第一次访问的回报样本值更新价值函数,则称为首次访问回合更新(first visit Monte Carlo update)

  每次访问和首次访问在学习过程中的中间值并不相同,但是它们都能收敛到真实的价值函数。首次访问回合更新评估策略的状态价值的伪代码如下:

  其中求平均的方法我们可以采用增量法,即 \(\overline{g}_c=\overline{g}_{c-1}+\frac{1}{c}(\overline{g}_c-\overline{g}_{c-1})\),抽象一下 \(q_k = q_{k-1} + a_k(g_k-g_{k-1})\)\(a_k\) 可以定义为学习率,它的设置需要满足 Robbins-Monro 条件,Robbins-Monro 条件需要让 \(a_k\) 同时满足下列三个条件:

  • \(a_k \ge 0\)
  • \(\sum_k^\infty a_k = \infty\),不受起始点限制而可以达到任意收敛点的条件
  • \(\sum_k^\infty a_k^2 \lt \infty\),不受噪声限制最终可以收敛的条件

  如果同时满足了这三个条件,那么则有 \(q_k \to q, k \to \infty\),即收敛。当 \(a_k = \frac{1}{k}\) 时就是增量法了。
  拿首次访问回合更新评估策略的状态价值举例,我们每次更新 \(v(S_t)\) 以减少 \([G-v(S_t)]^2\)(如\(c(S_t) = c(S_t) + 1, v(S_t)=v(S_t) + \frac{1}{c(S_t)}[G-v(S_t)]\))。如果用学习率替代的话,就可以写为\(v(S_t)=v(S_t) + a[G-v(S_t)]\)。为什么每次更新要减少 \([G-v(S_t)]^2\),这是为了求解梯度时较为方便,并且梯度 \(-2[G-v(S_t)]\) 正是迭代的关键。但是总这样做是行不通的,因为例如总是让 \(v(S_t) \to G\) 就不行,这相当于让 \(a=1\),使得学习率不满足 Robbins-Monro 条件,无法收敛。
  首次访问回合更新评估策略的动作价值,每次访问回合更新评估策略的状态价值,每次访问回合更新评估策略的动作价值的算法类似,这里就不赘述了。

带起始探索的同策回合更新

  在更新价值估计后,进行策略改进,那么就会得到新的策略,不断更新,不断得到更优策略,这就是同策回合更新的基本思想。但是如果只是简单地将回合更新策略评估的算法移植为同策回合更新算法,这经常会陷入局部最优解而得到全局最优策略,这是因为算法可能从一个并不好的策略出发,只经过那些很差的状态,然后只为那些很差的状态更新价值。
  起始探索(exploring start)可以缓解这一问题,它让所有可能的状态动作都成为可能的回合起点,这样就不会遗漏任何状态动作对,但是理论上,目前并不能确定带起始探索的同策回合更新算法是否能收敛到最优策略。
  它的伪代码如下图所示:

基于柔性策略的同策回合更新

  起始探索也有着缺点,它需要任意一个状态都可以被指定为回合的起始状态,这实际上是很难的做到的,例如迷宫游戏它通常都有着固定的起点。
  柔性策略(soft policy)可以缓解这个问题,所谓的柔性策略指的是任意 \(\pi(a|s) \gt 0\)\(\varepsilon\) 柔性策略(\(\varepsilon\)-soft policy)指的是任意 \(\pi(a | s) \geq \frac{\varepsilon}{|\mathcal{A}(s)|}\)
  对于给定的环境上的某个确定性策略,在所有的 \(\varepsilon\) 中有一个策略最接近这个确定策略,这个策略就称为 \(\varepsilon\) 贪心策略(\(\varepsilon\)-greedy policy),举个例子:

\[ \pi\left(a | S_{t}\right) =\left\{\begin{array}{ll} {1} & {\text { if } a=A^{*}} \\ {0} & {\text { if } a \neq A^{*}} \end{array}\right. \]

  它转换为 \(\varepsilon\) 贪心策略即为:

\[ \pi\left(a | S_{t}\right) =\left\{\begin{array}{ll} {1-\varepsilon+\varepsilon /\left|\mathcal{A}\left(S_{t}\right)\right|} & {\text { if } a=A^{*}} \\ {\varepsilon /\left|\mathcal{A}\left(S_{t}\right)\right|} & {\text { if } a \neq A^{*}} \end{array}\right. \]

  它的伪代码如下:

异策(off-policy)回合更新

  所谓的异策算法指的是生成轨迹的策略和正在被评估或被优化的策略可以不是同一个策略,这就需要用到重要性采样。

重要性采样(importance sampling)

  在统计学上,重要性采样是一种用一个分布生成的样本来估计另一个分布的统计量的方法。在异策学习中,我们将要学习的策略 \(\pi\) 称为目标策略(target policy),将用来生成行为的另一策略 \(b\) 称为行为策略(behavior policy)。
  我们考虑一段轨迹,计算策略 \(\pi\) 生成它的概率:

\[ \begin{array}{l} {\operatorname{Pr}\left\{A_{t}, S_{t+1}, A_{t+1}, \ldots, S_{T} | S_{t}, A_{t: T-1} \sim \pi\right\}} \\ {\quad=\pi\left(A_{t} | S_{t}\right) p\left(S_{t+1} | S_{t}, A_{t}\right) \pi\left(A_{t+1} | S_{t+1}\right) \cdots p\left(S_{T} | S_{T-1}, A_{T-1}\right)} \\ {=\prod_{k=t}^{T-1} \pi\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)} \end{array} \]

  策略 \(b\) 生成它的概率也类似,于是我们可以得到重要性采样比率(importance sampling ratio):

\[ \rho_{t: T-1} \doteq \frac{\prod_{k=t}^{T-1} \pi\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)}{\prod_{k=t}^{T-1} b\left(A_{k} | S_{k}\right) p\left(S_{k+1} | S_{k}, A_{k}\right)}=\prod_{k=t}^{T-1} \frac{\pi\left(A_{k} | S_{k}\right)}{b\left(A_{k} | S_{k}\right)} \]

  回合更新使用 MC 来估计价值函数的值,它通过得到 \(c\) 个回报 \(g_1,g_2,...,g_c\) 后计算它们的平均值来更新价值函数的值,这样的方法实际上是默认这个 \(c\) 个回报是等概率出现的。类似的异策回合更新用 \(b\) 得到 \(c\) 个回报,这些回报值对于 \(b\) 是等概率出现的,但是对于 \(\pi\) 不是等概率出现的,对于 \(\pi\) 来说,它们出现的概率正是各个轨迹的重要性采样比率。这样我们就可以通过加权平均来完成 MC 估计,有两种加权法:

  • 加权重要性采样(weighted importance sampling):\(\frac{\sum_{i=1}^c \rho_i g_i}{\sum_{i=1}^c \rho_i}\)
  • 普通重要性采样(ordinary importance sampling):\(\frac{1}{c} \sum_{i=1}^c \rho_i g_i\)

  可以看出主要是分母不同,并且影响 \(\rho_i=0\)\(g_i\),前者不会让 0 参与平均,并不影响整体的平均值,后者会让 0 参与平均,使得平均值变小。这两种加权方法同样可以使用增量法,不同的是加权重要性采样需要将计数值替换为权重的和,即:

\[ c \leftarrow c + \rho \\ v \leftarrow v + \frac{\rho}{c}(g-v) \]

异策回合更新策略评估

  知道重要性采样后,异策回合更新策略评估就很简单了,伪代码如下:

  伪代码里加入一个检查机制,即 \(W=0\) 时终止循环,因为一开始权重值从 1 开始,会越来越小,如果某次权重值变为 0,通常是由于 \(\pi(A_t|S_t)=0\) 导致的,那么以后的权重值都会变成 0,再循环下去也没有意义了。

异策回合更新最优策略求解

  和其它最优策略求解算法一样,都是在策略估计算法上加上策略改进得到的,伪代码如下:

  其中 \(\pi\) 是一个确定性策略,在回合更新的过程中,任选一个柔性策略 \(b\) 都满足 \(\pi \ll b\)。由于采用了确定性策略 \(\pi\),即:

\[ \pi\left(a | S_{t}\right) =\left\{\begin{array}{ll} {1} & {\text { if } a=A^{*}} \\ {0} & {\text { if } a \neq A^{*}} \end{array}\right. \]

  根据这一性质,我们可以简化更新权重并判断权重是否为 0,\(\pi(A_t|S_t)=0s\) 意味着权重为 0,以此来退出循环。

总结

  MC 方法可用于无模型的回合更新方法中,回合更新任务只能用于回合制任务中,它需要在每个回合结束后更新价值估计

Refer

相关内容


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 同策(on-policy)回合更新
    1. 2.1. 同策回合更新策略评估
    2. 2.2. 带起始探索的同策回合更新
    3. 2.3. 基于柔性策略的同策回合更新
  3. 3. 异策(off-policy)回合更新
    1. 3.1. 重要性采样(importance sampling)
    2. 3.2. 异策回合更新策略评估
    3. 3.3. 异策回合更新最优策略求解
  4. 4. 总结
  5. 5. Refer
  6. 6. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 670.5k 字啦

载入天数...载入时分秒...