Skip to content

蒙特卡洛方法

模型无关的强化学习

  • 在现实问题中，通常没有明确给出状态转移和奖励函数

比如，我们只看到了一些 episodes（采样）：

  • Episode1: \(s_0^{(1)}\xrightarrow{a_0^{(1)},R(s_0)^{(1)}}s_1^{(1)}\xrightarrow{a_1^{(1)},R(s_1)^{(1)}}s_2^{(1)}\cdots s_T^{(1)}\)

  • Episode2: \(s_0^{(2)}\xrightarrow{a_0^{(2)},R(s_0)^{(2)}}s_1^{(2)}\xrightarrow{a_1^{(2)},R(s_1)^{(2)}}s_2^{(2)}\cdots s_T^{(2)}\)

  • 模型无关的强化学习直接从经验中学习值 value和策略 policy，无需构建 MDP。

  • 关键步骤

  • 估计值函数

  • 优化策略

值函数估计

  • 在基于模型的强化学习中，值函数通过动态规划计算获得。

\(V^\pi(s)=R(s)+\gamma\sum\limits_{s'\in S}p_{s\pi(s)}(s')V^{\pi}(s')\)

  • 在模型无关的强化学习中

  • 无法直接获得 \(P_{sa}\) 和 \(R\)

  • 但我们可以根据已有的经验来估计值函数

    • Episode1: \(s_0^{(1)}\xrightarrow{a_0^{(1)},R(s_0)^{(1)}}s_1^{(1)}\xrightarrow{a_1^{(1)},R(s_1)^{(1)}}s_2^{(1)}\cdots s_T^{(1)}\)

    • Episode2: \(s_0^{(2)}\xrightarrow{a_0^{(2)},R(s_0)^{(2)}}s_1^{(2)}\xrightarrow{a_1^{(2)},R(s_1)^{(2)}}s_2^{(2)}\cdots s_T^{(2)}\)

蒙特卡洛方法

Monte-Carlo methods 是一类广泛的计算算法

  • 依赖于重复随机抽样来获得数值结果

例子

  • 估算圆周率
  • 围棋对弈：AlphaGo

蒙特卡洛价值估计

  • 目标：从策略 \(\pi\) 下的经验片段学习 \(V^\pi\)

\(s_0^{(i)}\xrightarrow{a_0^{(i)},R(s_0)^{(i)}}s_1^{(i)}\xrightarrow{a_1^{(i)},R(s_1)^{(i)}}s_2^{(i)}\cdots s_T^{(i)}\sim\pi\)

  • 累积奖励（return）是总折扣奖励

\(G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots+\gamma^{T-1}R_T\)

  • 值函数（value function）是期望累计奖励

\(V^\pi(s)=\mathbb E[R(s_0)+\gamma R(s_1)+\cdots|s_0=s,\pi]\)

\(=\mathbb E[G_t|s_t=s,\pi]\)

\(\simeq\frac{1}{N}\sum_{i=1}^NG_t^{(i)}\)

  • 使用策略 \(\pi\) 从状态 \(s\) 采样 \(N\) 个片段

  • 计算平均累计奖励

  • 蒙特卡洛策略评估使用经验均值累计奖励而不是期望累计奖励

实现蒙特卡洛值估计

实现

  • 使用策略 \(\pi\) 采样片段

\(s_0^{(i)}\xrightarrow{a_0^{(i)},R(s_0)^{(i)}}s_1^{(i)}\xrightarrow{a_1^{(i)},R(s_1)^{(i)}}s_2^{(i)}\cdots s_T^{(i)}\sim\pi\)

  • 在一个片段中每个时间步长 t 的状态 s 都被访问

  • 增量计数器 \(N(s)\leftarrow N(s)+1\)

  • 增量总累计奖励 \(S(s)\leftarrow S(s)+G_t\)
  • 值被估计为累计奖励的均值 \(V(s)=\frac{S(s)}{N(s)}\)
  • 由大数定律得 \(V(s)\rightarrow V^\pi(s)\ as\ N(s)\rightarrow\infty\)

增量蒙特卡洛更新

  • 每个片段结束后逐步更新 \(V(s)\)

  • 对于每个状态 \(S_t\) 和对应累计奖励 \(G_t\)

\(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))\)

  • 对于非稳定问题（即环境会随时间发生变化），我们可以跟踪一个现阶段的平均值（即不考虑过久之前的片段）

\(V(S_t)\leftarrow V(S_t)+\alpha(G_t-V(S_t))\)

实现值估计

思路：\(V^\pi(s)\simeq\frac{1}{N}\sum_{i=1}^NG_t^{(i)}\)

实现：\(V(S_t)\leftarrow V(S_t)+\alpha(G_t-V(S_t))\)

  • 直接从经验片段中学习

  • model-free，模型无关的：为止马尔可夫决策过程的状态转移/奖励

  • 从完整的片段中进行学习：没有使用 bootstrapping 方法

  • 最简单的思想：值 value = 平均累计奖励 mean return

  • 警告⚠：只能讲蒙特卡洛方法应用于可分片段的马尔可夫决策过程中！

即，所有的片段都有终止状态

模型无关控制方法

模型无关的控制应用场景

  • 一些能够被建模成马尔可夫决策过程的问题

电梯、平行泊车、船舶操纵、生物反应器、直升机、飞机物流、Atari和星际争霸、投资组合管理、围棋对弈……

  • 对于大部分真实世界的问题：

  • MDP 模型为未知，但能从经验中采样

  • MDP 模型为已知，但规模太大难以直接使用，只能通过采样

  • 模型无关的控制能解决上述问题

在线策略和离线策略学习

两类模型无关的强化学习

  1. 在线策略学习 On-Policy
  2. Learning on the job
  3. 利用策略 \(\pi\) 的经验采样不断学习改进策略 \(\pi\)
  4. 离线策略学习 Off-Policy
  5. Look over someone's shoulder
  6. 利用另一个策略 \(\mu\) 的经验采样不断学习改进策略 \(\pi\)

状态值和状态-动作值

\(G_t=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-1}R_T\)

  • 状态值

马尔可夫决策过程的状态值函数 \(V^\pi(s)\) 是指从状态 \(s\) 开始，执行策略 \(\pi\) 的期望累计奖励为

\(V^\pi(s)=\mathbb E_\pi[G_t|S_t=s]\)

  • 状态-动作值

马尔可夫决策过程的状态-动作值函数 \(Q^\pi(s,a)\) 是指从状态 \(s\) 开始，执行 \(a\) 动作之后，执行策略 \(\pi\) 的期望累计奖励

\(Q^\pi(s,a)=\mathbb E_\pi[G_t|S_t=s,A_t=a]\)

贝尔曼期望方程

  • 状态值函数 \(V^\pi(s)\) 可被分解为即时奖励加上后续状态的折扣值

\(V^\pi(s)=\mathbb E_\pi[R_{t+1}+\gamma V^\pi(S_{t+1})|S_t=s]\)

  • 状态-动作值函数 \(Q^\pi(s,a)\) 也能被分解为

\(Q^\pi(s,a)=\mathbb E_\pi[R_{t+1}+\gamma Q^\pi(S_{t+1},A_{t+1})|S_t=s,A_t=a]\)

  • 因此

  • \(V^\pi(s)=\sum_{a\in A}Q^\pi(s,a)\)

  • \(Q^\pi(s,a)=R(s,a)+\gamma \sum_{s'\in S}P_{sa}(s')V^\pi(s')\)

模型无关的策略迭代

  • 给定状态值函数 \(V(s)\) 和状态-动作值函数 \(Q(s,a)\)，模型无关的策略迭代应使用状态-动作值函数

  • 基于状态值函数 \(V(s)\) 的贪心策略改进需要建立马尔可夫决策过程的模型

\(\pi^{new}(s)=\arg\max_{a\in A}\{R(s,a)+\gamma\sum_{s'\in S}P_{sa}(s')V^\pi(s')\}\)

  • 我们不知道状态转移概率 \(P_{sa}(s')\)

  • 基于状态-动作值函数 \(Q(s,a)\) 的贪心策略改进是模型无关的

\(\pi^{new}(s)=\arg\max_{a\in A}Q(s,a)\)

使用状态-动作值函数的广义策略迭代

  • 策略评估：蒙特卡洛策略估计 \(Q=Q^\pi\)
  • 策略改进：贪心策略改进

ε-greedy 策略探索

  • 确保持续探索最简单的想法

  • 所有 m 个动作都以非零概率进行尝试

  • 以 1-ε 的概率，选择贪心动作

  • 以 ε 的概率，随机选择一个动作

\(\pi(a|s)=\frac{\epsilon}{m}+1-\epsilon\) 当 \(a^*=argmax_{a\in A}Q(s,a)\)

\(\pi(a|s)=\frac{\epsilon}{m}\) otherwise

ε-greedy 策略改进

定理：

  • 对于任意 ε-greedy 的策略 \(\pi\)，关于 \(Q^\pi\) 的 ε-greedy 策略 \(\pi'\) 是 \(\pi\) 的一个改进，即 \(V^{\pi'}(s)\ge V^\pi(s)\)

\(V^{\pi'}(s)=Q^\pi(s,\pi'(s))=\sum_{a\in A}\pi'(a|s)Q^\pi(s,a)\)

\(=\frac{\epsilon}{m}\sum_{a\in A}Q^\pi(s,a)+(1-\epsilon)\max_{a\in A}Q^\pi(s,a)\)

\(\ge\frac{\epsilon}{m}\sum_{a\in A}Q^\pi(s,a)+(1-\epsilon)\sum_{a\in A}\frac{\pi(a|s)-\frac{\epsilon}{m}}{1-\epsilon}Q^\pi(s,a)\)

\(=\sum_{a\in A}\pi(a|s)Q^\pi(s,a)=V^\pi(s)\)

蒙特卡洛控制

对于每个片段 episode

  • 策略评估：蒙特卡洛策略估计 \(Q≈Q^\pi\)
  • 策略改进：ε-greedy 策略改进

蒙特卡洛控制 vs. 时序差分控制

  • 时序差分（TD）学习相比蒙特卡洛（MC）有许多优点
  • 更低的方差
  • 在线策略
  • 基于不完整的序列
  • 自然的想法：在控制中，使用时序差分代替蒙特卡洛
  • 使用时序差分来更细状态-动作值函数
  • 使用 ε-greedy 策略改进
  • 每个时间步长更新状态-动作值函数

重要性采样

  • 估计一个不同分布的期望

\(\mathbb E_{x\sim p}[f(x)]=\int_xp(x)f(x)dx\)

\(=\int_xq(x)\frac{p(x)}{q(x)}f(x)dx\)

\(=\mathbb E_{x\sim q}[\frac{p(x)}{q(x)}f(x)]\)

  • 将每个实例的权重重新分配为 \(\beta(x)=\frac{p(x)}{q(x)}\)

使用重要性采样的离线策略蒙特卡洛

  • 使用策略 \(\mu\) 产生的累计奖励评估策略 \(\pi\)

  • 根据两个策略之间的重要性比率（importance ratio）对累计奖励 \(G_t\) 加权

  • 每个片段乘以重要性比率

\(\{s_1,a_1,r_2,s_2,a_2,\cdots,s_T\}\sim\mu\)

\(G_t^{\pi/\mu}=\frac{\pi(a_t|s_t)\pi(a_{t+1}|s_{t+1})}{\mu(a_t|s_t)\mu(a_{t+1}|s_{t+1})}\cdots\frac{\pi(a_T|s_T)}{\mu(a_T|s_T)}G_t\)

  • 更新值函数以逼近修正的累计奖励值

\(V(s_t)\leftarrow V(s_t)+\alpha(G_t^{\pi/\mu}-V(s_t))\)

  • 无法在 \(\pi\) 非零而 \(\mu\) 为 0 时使用
  • 重要性采样将显著增大方差（variance）

使用重要性采样的离线策略时序差分

  • 使用策略 \(\mu\) 产生的时序差分目标评估策略 \(\pi\)

  • 根据重要性采样对时序差分目标 \(r+\gamma V(s')\) 加权

  • 仅需要一步来进行重要性采样验证

\(V(s_t)\leftarrow V(s_t)+\alpha(\frac{\pi(a_t|s_t)}{\mu(a_t|s_t)}(r_{t+1}+\gamma V(s_{t+1}))-V(s_t))\)

  • 重要性采样修正：\(\frac{\pi(a_t|s_t)}{\mu(a_t|s_t)}\)
  • 时序差分目标：\(r_{t+1}+\gamma V(s_{t+1})\)

时序差分学习

时序差分学习

\(G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots=R_{t+1}+\gamma V(S_{t+1})\)

\(V(S_t)\leftarrow V(S_t)+\alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t))\)

观测值 \(R_{t+1}\)，对未来的猜测 \(\gamma V(S_{t+1})\)

  • 时序差分方法直接从经验片段中进行学习
  • 时序差分是模型无关的
  • 不需要预先获取 MDP 的状态转移/奖励
  • 通过自举法（bootstrapping），时序差分从不完整的片段中学习
  • 时序差分更新当前预测值使之接近估计累计奖励（非真实值）

蒙特卡洛 MC VS 时序差分 TD

相同的目标：从策略 \(\pi\) 下的经验片段学习 \(V^\pi\)

  • 增量地进行每次蒙特卡洛过程

  • 更新值函数 \(V(S_t)\) 使之接近准确累计奖励 \(G_t\)

    \(V(S_t)\leftarrow V(S_t)+\alpha(G_t-V(S_t))\)

  • 最简单的时序差分学习算法：

  • 更新 \(V(S_t)\) 使之接近估计累计奖励 \(R_{t+1}+\gamma V(S_{t+1})\)

    \(V(S_t)\leftarrow V(S_t)+\alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t))\)

  • 时序差分目标： \(R_{t+1}+\gamma V(S_{t+1})\)

  • 时序差分误差：\(\delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)\)

蒙特卡洛和时序差分的优缺点

时序差分能够在知道最后结果之前进行学习

  • 能够在每一步之后进行学习
  • 蒙特卡洛必须等待片段结束，直到累计奖励已知

时序差分能够无需最后结果而进行学习

  • 时序差分能够从不完整序列中学习，而蒙特卡洛只能从完整序列中学习
  • 时序差分在连续（无终止的）环境下工作
  • 蒙特卡洛只能在片段化（有终止）环境下工作

蒙特卡洛 MC

蒙特卡洛具有高方差，无偏差 \(V(S_t)\leftarrow V(S_t)+\alpha(G_t-V(S_t))\)

  • 良好的收敛性质
  • 使用函数近似时依然如此
  • 对初始值不敏感
  • 易于理解和使用

时序差分 TD

时序差分具有低方差，有偏差 \(V(S_t)\leftarrow V(S_t)+\alpha(R_{t+1}+\gamma V(S_{t+1})-V(S_t))\)

  • 通常比蒙特卡洛更高效
  • 时序差分最终收敛到 \(V^\pi(S_t)\)
  • 但使用函数近似时并不总是如此
  • 比蒙特卡洛对初始值更加敏感

偏差 Bias 和方差 Variance 的权衡

  • 累计奖励 \(G_t=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-1}R_T\) 是 \(V^\pi(S_t)\) 的无偏估计
  • 时序差分真实目标 \(R_{t+1}+\gamma V^\pi(S_{t+1})\) 是 \(V^\pi(S_t)\) 的无偏估计

  • 时序差分目标 \(R_{t+1}+\gamma V(S_{t+1})\) 是 \(V^\pi(S_t)\) 的有偏估计

  • 时序差分目标具有比累计奖励更低的方差

  • 累计奖励——取决于多步随机动作，多步状态转移和多步奖励
  • 时序差分目标——取决于单步随机动作，单步状态转移和单步奖励

多步时序差分学习

  • 对于有时间约束的情况，我们可以跳过 n 步预测的部分，直接进入模型无关的控制

  • 定义 n 步累计奖励

\(G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1}R_{(t+n)}+\gamma^nV(S_{t+n})\)

  • n 步时序差分学习

\(V(S_t)\leftarrow V(S_t)+\alpha(G_t^{(n)}-V(S_t))\)