CS285 Assignment 笔记

CS 285 2023 Fall
homework 2023 fall

为什么要写笔记？这个问题在 2026 年的回答(2026.3.7)已经有了很大变化, 最开始的原因是我记忆力很差。大学阶段的笔记分为两类, 高数课上我手抄, pytorch 与 Qt 学习我上 Typora。自从大模型时代来临后一切都变了, 有了真理机器喂 prompt 吐笔记, 比我考虑的周全很多, 但如果你看到了这句话, 说明我还是把我的手工笔记发表到了网络上。
简单阐明两件事情: 一是我原先的网络笔记指望给素不相识的网友所阅读, 以此带来一些学习的帮助, 现在的我发表网络笔记不期盼这些；二是我对未来纯人工生成的文章的数量抱有悲观, 很快大模型生成的文字将会占领 99% 甚至 100% 的互联网(这篇笔记也会使用大模型, 但是这几段文字不是), 我还是抱有一些朴素的想法, 为后人带来一些方便, 解决一些后人的问题, 例如具体的代码背后的东西？一些带有抽象人类风味的解释(大模型也有对于抽象的理解, 不过应该不会跟我的完全拟合)。
你可能会问(如果你是人类的话), 既然你不期盼他人阅读笔记, 怎么为后人带来方便？我想的是, 这是我纯人工(半人工)生成的语料, 应该算是优质数据(好歹是人类的而不是大模型反刍出来的(存疑)), 后世的大模型也许能把我的笔记拉去机器学习。即使在未来网站毁灭了, 这些东西还能在一些模型深处的神经元里传承下去, 带着我的一点人类风味抽象, 也许这就足够了。

下面是 CS 285 2023 Fall 五个 Assignment 的理论作业解答与代码作业解答

Assignment 1 模仿学习

Analysis

考虑一个具有有限步长 \(T\) 的离散马尔可夫决策过程 (MDP) 中的模仿学习问题, 以及一个专家策略 \(\pi^*\)
我们从 \(\pi^*\) 收集专家演示, 并根据这些轨迹拟合一个模仿策略 \(\pi_\theta\), 使得: \[ \mathbb{E}_{s \sim p_{\pi^*}} \pi_\theta(a \neq \pi^*(s) \mid s) = \frac{1}{T} \sum_{t=1}^{T} \mathbb{E}_{p_{\pi^*}(s_t)} \pi_\theta(a_t \neq \pi^*(s_t) \mid s_t) \leq \epsilon \] 即: 在从随机专家轨迹中提取的训练状态分布 \(p_{\pi^*}\)下, 学到的策略 \(\pi_\theta\) 与专家 \(\pi^*\) 不一致的预期可能性至多为 \(\epsilon\)

为了方便起见, 符号 \(p_\pi(s_t)\) 表示在时间步 \(t\) 时策略 \(\pi\) 下的状态分布, 而 \(p(s)\) 表示除非另有说明, 否则 \(\pi\) 表示在所有时间步的状态边际分布

1. 证明: \(\sum_{s_t} |p_{\pi_\theta}(s_t) - p_{\pi^*}(s_t)| \leq 2T\epsilon\)​

证明有限 MDP 摘出来中间项的差距上界是随着 T 线性增长的？

符号注意: \(s \sim p_{\pi^*}\) 时, 它实际上是在描述一个两步走的采样过程, 先从时间范围 \(\{1, 2, \dots, T\}\) 中随机均匀地选一个时刻 \(t\), 再取出专家在那个时刻 \(t\) 所处的具体状态 \(s_t\)​

和 Lecture 2 笔记中的 \(\mathbf s \sim p_{\text{train}}(\mathbf s)\) 相关推导思路几乎一样, 但数学细节需要强调处理

我们设 \(M_t\) 为事件: "在第 \(t\) 步之前, 策略 \(\pi_\theta\) 至少发生了一次与专家策略 \(\pi^*\) 不同的动作选择"
然后改写 \(p_{\pi_\theta}\), 有 \[ p_{\pi_\theta}(s_t) = (1 - \Pr(M_t)) \cdot p_{\pi^*}(s_t) + \Pr(M_t) \cdot p_{\text{mistake}}(s_t) \] 于是重构 \(p_{\pi_\theta}(s_t) - p_{\pi^*}(s_t)\), 有 \[ p_{\pi_\theta}(s_t) - p_{\pi^*}(s_t) = \Pr(M_t) \cdot (p_{\text{mistake}}(s_t) - p_{\pi^*}(s_t)) \] 于是 \[ \begin{aligned} \sum_{s_t} |p_{\pi_\theta}(s_t) - p_{\pi^*}(s_t)| &= \sum_{s_t} \left| \Pr(M_t) \cdot (p_{\text{mistake}}(s_t) - p_{\pi^*}(s_t)) \right| \\ &= \Pr(M_t) \cdot \sum_{s_t} |p_{\text{mistake}}(s_t) - p_{\pi^*}(s_t)| \\ &= 2\Pr(M_t) \end{aligned} \] 接下来估计 \(\Pr(M_t)\), 即前 \(t-1\) 步至少犯错一次的概率的上限
设 \(E_i\) 为事件: "在专家分布的状态下, 第 \(i\) 步 \(\pi_\theta\) 选择的动作与 \(\pi^*\) 不同", 有 \[ \Pr(M_t) = \Pr\left(\bigcup_{i=1}^{t-1} E_i\right) \leq \sum_{i=1}^{t-1} \Pr(E_i) \] 我们已知 \(\Pr(E_i) = \mathbb{E}_{p_{\pi^*}(s_i)} [\pi_\theta(a \neq \pi^*(s_i) \mid s_i)]\), 又有 \(\sum_{i=1}^T \mathbb{E}_{p_{\pi^*}(s_i)} [\pi_\theta(a_i \neq \pi^*(s_i) \mid s_i)] \leq T\epsilon\)
故大放缩, 对于任意 \(t \leq T\), 有 \[ \Pr(M_t) \leq \sum_{i=1}^{t-1} \mathbb{E}_{p_{\pi^*}(s_i)}[\dots] \leq \sum_{i=1}^T \mathbb{E}_{p_{\pi^*}(s_i)}[\dots] \leq T\varepsilon \] 回代, 故 \(\sum_{s_t} |p_{\pi_\theta}(s_t) - p_{\pi^*}(s_t)| \leq 2T\epsilon\)

2. 考虑学习策略 \(\pi_\theta\) 对于状态相关奖励 \(r(s_t)\) 的期望回报, 其中我们假设奖励是有界的, 即 \(|r(s_t)| \leq R_{\text{max}}\):
   \[ J(\pi) = \sum_{t=1}^{T} \mathbb{E}_{p_\pi(s_t)}r(s_t) \]
   1. 证明当奖励仅取决于最后一个状态时 (即对于所有 \(t < T, r(s_t) = 0\)), \(J(\pi^*) - J(\pi_\theta) = \mathcal{O}(T\epsilon)\)
      
   2. 证明对于任意奖励, \(J(\pi^*) - J(\pi_\theta) = \mathcal{O}(T^2\epsilon)\)

其中 \(\epsilon\) 表示策略 \(\pi_\theta\) 与最优策略 \(\pi^*\) 在单步分布上的最大差异

1. 此时 \(J(\pi^*) - J(\pi_\theta) = \mathbb{E}_{p_{\pi^*}(s_T)}r(s_T) - \mathbb{E}_{p_{\pi_\theta}(s_T)}r(s_T)\)
   期望的分布不一样, 但我们得到了差距估计 \(\sum_{s_t} |p_{\pi_\theta}(s_t) - p_{\pi^*}(s_t)| \leq 2T\epsilon\)

于是 \(\mathbb{E}_{p_{\pi^*}(s_T)}r(s_T) - \mathbb{E}_{p_{\pi_\theta}(s_T)}r(s_T) = r(s_T) \displaystyle\sum_{s_T} (p_{\pi^*}(s_T) - p_{\pi_\theta}(s_T)) \leq R_\max \cdot 2T\epsilon = \mathcal{O}(T\epsilon)\)

2. 类似有 \[ \begin{aligned} J(\pi^*) - J(\pi_\theta) &= \sum_{t=1}^{T} \left( \mathbb{E}_{p_{\pi^*}(s_t)}r(s_t) - \mathbb{E}_{p_{\pi_\theta}(s_t)}r(s_t) \right) \\ &= \sum_{t=1}^{T} r(s_t) \sum_{s_t} (p_{\pi^*}(s_t) - p_{\pi_\theta}(s_t)) \\ &= R_\max \sum_{t=1}^{T} \sum_{s_t} (p_{\pi^*}(s_t) - p_{\pi_\theta}(s_t)) \\ &= R_\max T(T+1)\epsilon \\ &= \mathcal{O}(T^2\epsilon) \end{aligned} \]

Code

现在都用 Gymnasium 了, 而我们作业用的是 gym, 名字短一截啊
先看 run_hw1.py, 定义了一个 run_training_loop(params), 然后 main 函数把 params 弄好
在 gym 中, 重要的是环境 env = gym.make(params['env_name'], render_mode=None)

环境 Env 是比一坨 \(\mathcal{M} = \{ \mathcal{S}, \mathcal{A}, \mathcal{O}, \mathcal{T}, \mathcal{E}, r \}\) 更大的东西, 我们主要用 step() 方法在 MDP 上步进
在 run_hw1.py 里面, Agent 就是个 MLP, 有个 replay_buffer 是 off-policy 用的？我们主要写训练部分

第一次 (iter 0) 是做行为克隆(Behavior Cloning, BC), 后面是在做 DAGGER
在 Step 3, 要把人类对 \(\mathbf o_t\) 的标记 \(\mathbf a_t\) 替换掉原来的 paths[i]["actions"], 个人感觉就是下面这样的

for i in range(len(paths)):
    paths[i]["action"] = expert_policy.get_action(paths[i]["observation"])

在 Step 1, 我们要从 replay_buffer 中打包 ob_batch, ac_batch 去训练, 需要 random_shuffle 一下

size = params['train_batch_size']
shuffle_index = np.random.permutation(len(replay_buffer))[:size]
ob_batch = replay_buffer.obs[shuffle_index]
ac_batch = replay_buffer.acs[shuffle_index]

在 utils.py 里面, 我们需要具体完成 sample_trajectory函数, 把轨迹采样出来, 主要用 env.step(ac) 来步进

ac = policy.get_action(ob)
...
next_ob, rew, done, _ = env.step(ac)
...
rollout_done = done

我得说这个 ac 即 action 原来获取的方式太蠢了, 搞了半天这个 get_action 函数在基类 base_policy.py 里还没写, 这层抽象化在原作业中暗示你在 utils.py 写是错误的
action 怎么从 observation 得到？我们从 observation 可以得到对应的高斯分布, 从这个分布中采样出一个动作
数据格式的变化是 numpy(obs) -> tensor(dist) -> numpy(action), 还要注意 observation 的维度问题

def get_action(self, obs: np.ndarray) -> np.ndarray:
    if len(obs.shape) > 1: observation = obs
    else: observation = obs[None]
    obs_tensor = ptu.from_numpy(observation)
    dist = self.forward(obs_tensor) # 1. 拿到分布对象
    action_tensor = dist.sample() # 2. 从分布中采样出一个真正的 Tensor
    action = ptu.to_numpy(action_tensor) # 3. 将采样出来的 Tensor 转成 NumPy
    if len(obs.shape) == 1:
        return action.flatten() 
    return action

最后在 MLP_policy.py 里实现 forward 与 update

def forward(self, observation: torch.FloatTensor) -> Any:
    mean = self.mean_net(observation)
    std = torch.exp(self.logstd)
    dist = torch.distributions.Normal(mean, std)
    return dist
def update(self, observations, actions):
    self.optimizer.zero_grad() 
    observations = ptu.from_numpy(observations)
    actions = ptu.from_numpy(actions)
    dist = self.forward(observations) # 最大似然估计
    log_probs = dist.log_prob(actions) # 专家动作在当前高斯分布下的对数概率
    loss = -log_probs.sum(dim=-1).mean()
    loss.backward()            
    self.optimizer.step()
    return {
        'Training Loss': ptu.to_numpy(loss),
    }

按照要求跑 run_hw1.py, 在 tensorboard 看结果, 发现几乎不用训 10 个 epoch, 我一个 epoch 就够了
借助 AI 神力解释一下, 我们在这里的 loss 是负对数极大似然估计, \(\text{Loss} = \dfrac{(a_{\text{expert}} - \mu_\theta(s))^2}{2\sigma^2} + \log \sigma + \text{const}\), 而传统的简单 loss 一般就是 MSE, 算两个分布之间的距离 \(\| \mu_\theta(s) - a_{\text{expert}} \|^2\), 我们的方法收敛快, 不容易漂移, 但容易因为 \(\sigma\) 震荡, 因为其对于 \(\sigma\) 太敏感了

Extra

在课程中讨论过的 DAGGER 算法的缺点之一是, 它需要人类专家对机器人收集的状态标注最优动作。这可能有悖直觉, 因为人类通常是在不断获得环境反馈的情况下选择动作的

在本题中, 你将分析一种 DAGGER 算法的变体, 该变体在轨迹铺展 (rollouts) 期间的某些时刻将控制权交给人类专家, 从而允许他们提供交互式演示
我们考虑一个视界 (horizon) 为 \(T\) 的离散 MDP 和一个专家策略 \(\pi^{*}\), 在每次迭代 \(n=1,...,N\) 中, 我们都有一个策略 \(\pi^{n}\), 我们从该策略中 rollout 轨迹, 使得在每条轨迹中, 我们在某个随机时间步 \(X^{*}+1\) 将控制权转移给专家, 直到轨迹结束
我们将以一定概率交出控制权的 \(\pi^{n}\) 版本表示为 \(\tilde{\pi}^{n}\)

形式上, 定义 \(S^{X}(\pi_{1},\pi_{2})\) 为先执行策略 \(\pi_{1}\) 共 \(X\) 步, 然后从当前状态切换到执行策略 \(\pi_{2}\) 直到轨迹剩余步骤结束的策略, 我们如下定义我们的算法 SWITCHDAGGER。为了方便起见, 我们设定 \(\tilde{\pi}^{0}\leftarrow\pi^{*}\) 和 \(\pi^{0}\leftarrow\hat{\pi}^{1}\), 在每一步 \(n=1,...,N\) 中, 我们执行以下更新:

• \(\hat{\pi}^{n}\leftarrow\) 对来自 \(s\sim p_{\tilde{\pi}^{n-1}}\) 的专家动作 \(\pi^{*}(s)\) 进行拟合
• \(\tilde{\pi}^{n}\leftarrow S^{X_{n}}(\hat{\pi}^{n},\tilde{\pi}^{n-1})\), 其中 \(X_{n}+1\sim \text{Geom}(1-\alpha)\)
• \(\pi^{n}\leftarrow S^{X_{n}}(\hat{\pi}^{n},\pi^{n-1})\), 或等价于对 \(X^{*}=\sum_{i=1}^{n}X_{i}\) 使用 \(S^{X^{*}}(\tilde{\pi}^{n},\pi^{0})\)

其中我们假设 \(\hat{\pi}^{n}\) 在 \(\tilde{\pi}^{n-1}\) 的状态边缘分布上进行拟合, 使得: \[ \mathbb{E}_{s\sim p_{\tilde{\pi}^{n-1}}}Pr[\hat{\pi}^{n}(s)\ne\pi^{*}(s)]\le\epsilon \] 我们将代价 (cost) 定义为一个策略所犯错误的期望数量: \[ C(\pi)=\sum_{t=1}^{T}\mathbb{E}_{s_{t}\sim p_{\pi}}Pr[\pi(s_{t})\ne\pi^{*}(s_{t})] \] 我们的目标是最小化 SWITCHDAGGER 产生的不使用专家的最终策略 \(\pi^{N}\) 的代价
在下面的部分中, 你将证明, 对于适当的 \(N\) 和 \(\alpha\) 的选择, 我们可以将该策略的代价 \(C(\pi^{N})\) 限界为 \(\mathcal{O}(T\epsilon~log(1/\epsilon))\)

上面是题目背景翻译, 我在这说点能听懂的

\(\tilde{\pi}^{n-1}\) 训练了 \(\hat{\pi}^{n}\), 使其在 \(\tilde{\pi}^{n-1}\) 的分布下, 与专家动作不一致的概率小于 \(\epsilon\)
\(\hat{\pi}^{n}\) 被我们嵌入了 \(\pi^n\) 中, 我们实际上训练了 \(\{\hat{\pi}^1, \hat{\pi}^2, \dots, \hat{\pi}^n\}\), 然后拼接成了 \(\pi^n\), 随着概率 \(\alpha\) 切换为 "下级" 策略

1. 证明 \(C(\tilde{\pi}^{n})\le A(T,n)\), 其中 \(A(t,n)\) 由以下条件定义:
   \(A(0,n)=0, A(t,0)=0, A(t,n)=\alpha\epsilon t+\alpha(1-\epsilon)A(t-1,n)+(1-\alpha)A(t,n-1)\)

我们可以展开 \(\tilde\pi\) 来看一眼, \(\tilde{\pi}^{2} = S^{X_{2}}(\hat{\pi}^{2}, \tilde{\pi}^{1}) = S^{X_{2}}(\hat{\pi}^{2}, S^{X_{1}}(\hat{\pi}^{1}, \pi^{*}))\), 有 \[ \tilde{\pi}^{n} = \underbrace{\hat{\pi}^{n} \to \hat{\pi}^{n-1} \to \dots \to \hat{\pi}^{1}}_{\text{运行总步数 } X^{*}} \to \underbrace{\pi^{*}}_{\text{专家接管}} \] 其中总步数 \(X^{*} = \sum\limits_{i=1}^{n} X_{i}\), 并且 \(X_n + 1 \sim \text{Geom}(1-\alpha)\)
证明这个概率就是从 \(\pi^*\) 开始倒推, 一一对应, 首先专家是不会出错的, \(C(\pi^*) = A(0,n) = 0\)
从 \(\tilde{\pi}^{n}\) 到 \(\tilde{\pi}^{n-1}\) 的概率为 \(1-\alpha\), 剩余 \(t\) 步的期望错误上限为 \(A(t, n-1)\)
以 \(\alpha\) 的概率, 我们会继续执行 \(\hat{\pi}^n\), 在这个单步中, \(\hat{\pi}^n\) 犯错的概率最高为 \(\epsilon\), 全错了的概率为 \(\alpha\epsilon t\)
如果不犯错, 剩余 \(t-1\) 步由 \(\tilde{\pi}^n\) 控制, 代价为 \(A(t-1,n)\)
组合一下, 总期望为 \(A(t,n)=\alpha\epsilon t+\alpha(1-\epsilon)A(t-1,n)+(1-\alpha)A(t,n-1)\)

2. 证明 \(C(\tilde{\pi}^{n})\le Tn\alpha\epsilon\)

归纳法解决, 略

3. 证明当 \(n\ge T\) 且 \(\alpha\le1/T\) 时, \(C(\pi^{n})\le C(\tilde{\pi}^{n})+Te^{\frac{-n}{(1-\alpha)T}}\)

\(\pi^n\) 和 \(\tilde{\pi}^n\) 行为的唯一区别在于当时间步超过 \(X^* = \sum_{i=1}^n X_i\) 时, \(\tilde{\pi}^n\) 切换为专家 \(\pi^*\) (后续无错误), 而 \(\pi^n\) 切换为初始策略 \(\pi^0\) (然后后面全错了)
当 \(X^* \ge T\) 时无区别, 当 \(X^* < T\) 时, 作业给出了 Chernoff 界 \(\Pr[X^{*} \le T] \le e^{\frac{-n}{(1-\alpha)T}}\)​, 那不就证完了吗

4. 证明 \(C(\pi^{N})=\mathcal{O}(T\epsilon~log(1/\epsilon))\)

我们有 \(C(\pi^N) \le T n \alpha \epsilon + Te^{\frac{-n}{(1-\alpha)T}}\), 选择 \(\alpha = 1/T\), 有 \(C(\pi^N) \le n \epsilon + Te^{\frac{-n}{T-1}}\)
我们希望两项差不多, 令 \(T \cdot e^{\frac{-n}{T-1}} = T\epsilon\), 则 \(n = \Theta(T \log(1/\epsilon))\), 则总项为 \(\mathcal{O}(T\epsilon~log(1/\epsilon))\)

Assignment 2 策略梯度

大概要学完 Lecture 6 才能写, 推荐一下 Zhangkuns 的实验报告

Review

下文我的笔记有 1-index 与 0-index 混用, 要不还是去看作业原文吧

策略梯度 \(\nabla_{\theta} J(\theta) = E_{\tau \sim p_{\theta}(\tau)} [\nabla_{\theta} \log p_{\theta}(\tau) r(\tau)]\)​

策略梯度的近似 \(\nabla_\theta J(\theta) \approx \dfrac{1}{N} \sum\limits_{i=1}^N \left[ \left( \sum\limits_{t=1}^T \nabla_\theta \log \pi_\theta(\mathbf a_{i,t}|\mathbf s_{i,t}) \right) \left( \sum\limits_{t=1}^T r(\mathbf{s}_{i,t}, \mathbf{a}_{i,t}) \right) \right]\)

课程介绍的降低方差的方式有 因果假设(reward to go)、基线(baseline)、折扣因子(discounting) 三种

因果假设: \(\nabla_\theta J(\theta) \approx \dfrac{1}{N} \sum\limits_{i=1}^N \left[ \left( \sum\limits_{t=1}^T \nabla_\theta \log \pi_\theta(\mathbf a_{i,t}|\mathbf s_{i,t}) \right) \left( \sum\limits_{t'=t}^T r(\mathbf{s}_{i,t'}, \mathbf{a}_{i,t'}) \right) \right]\)

基线: \(\nabla_\theta J(\theta) \approx \dfrac{1}{N} \sum\limits_{i=1}^N \nabla_\theta \log p_\theta(\tau) \left[r(\tau)-b \right]\)

折扣因子: \(\nabla_\theta J(\theta) \approx \dfrac{1}{N} \sum\limits_{i=1}^N \left[ \left( \sum\limits_{t=1}^T \nabla_\theta \log \pi_\theta(\mathbf a_{i,t}|\mathbf s_{i,t}) \right) \left( \sum\limits_{t=1}^T \gamma^{t-1} r(\mathbf{s}_{i,t}, \mathbf{a}_{i,t}) \right) \right]\)

因果假设 + 折扣因子: \(\nabla_\theta J(\theta) \approx \dfrac{1}{N} \sum\limits_{i=1}^N \left[ \left( \sum\limits_{t=1}^T \nabla_\theta \log \pi_\theta(\mathbf a_{i,t}|\mathbf s_{i,t}) \right) \left( \sum\limits_{t'=t}^T \gamma^{t'-t} r(\mathbf{s}_{i,t}, \mathbf{a}_{i,t}) \right) \right]\)

在本次作业中, 我们会实现状态价值函数 \(V_\phi^\pi\) 作为一个依赖状态的基线(baseline), 训练它去拟合未来奖励之和, 有 \[ V_\phi^\pi(\mathbf s_t) \approx \sum_{t'=t}^T \mathbb E_{\pi_\theta} [r(\mathbf s_{t'}, \mathbf a_{t'})|\mathbf s_t] \] 总的策略梯度为: \(\nabla_\theta J(\theta) \approx \dfrac{1}{N} \sum\limits_{i=1}^N \sum\limits_{t=1}^T \nabla_\theta \log \pi_\theta(\mathbf a_{i,t}|\mathbf s_{i,t}) \left( \left( \sum\limits_{t'=t}^T \gamma^{t'-t} r(\mathbf{s}_{i,t}, \mathbf{a}_{i,t}) \right) - V_\phi^\pi(\mathbf s_{i,t}) \right)\)

前一个策略梯度表达式中的量 \(\left(\sum_{t'=t}^{T} \gamma^{t'-t}r(\mathbf s_{t'}, \mathbf a_{t'})\right) - V^{\pi, \phi}(\mathbf s_t)\) 可以被解释为优势函数的估计值

\[ A^\pi(\mathbf s_t, \mathbf a_t) = Q^\pi(\mathbf s_t, \mathbf a_t) - V^\pi(\mathbf s_t) \] 其中 \(Q^\pi(\mathbf s_t, \mathbf a_t)\) 使用蒙特卡洛回报进行估计, 而 \(V^\pi(\mathbf s_t)\) 使用学习到的价值函数 \(V_\phi^{\pi}\) 进行估计
我们可以通过进一步使用 \(V_\phi^{\pi}\) 来替代蒙特卡洛回报以估计优势函数, 从而进一步降低方差 \[ A^\pi(\mathbf s_t, \mathbf a_t) \approx \delta_t = r(\mathbf s_t, \mathbf a_t) + \gamma V_\phi^{\pi}(\mathbf s_{t+1}) - V_\phi^{\pi}(\mathbf s_t) \] 其中边界情况为 \(\delta_{T} = r(\mathbf s_{T}, \mathbf a_{T}) - V_\phi^{\pi}(\mathbf s_{T})\)
然而, 由于 \(V_\phi^{\pi}\) 中的建模误差, 这会给我们策略梯度的估计引入偏差 (bias)
我们可以转而使用 \(n\) 步蒙特卡洛回报与 \(V_\phi^{\pi}\) 的组合来估计优势函数： \[ A_n^{\pi}(\mathbf s_t, \mathbf a_t) = \sum_{t'=t}^{t+n} \gamma^{t'-t}r(\mathbf s_{t'}, \mathbf a_{t'}) + \gamma^n V_\phi^{\pi}(\mathbf s_{t+n+1}) - V_\phi^{\pi}(\mathbf s_t) \] 增大 \(n\) 会在优势估计中更多地纳入蒙特卡洛回报, 这会降低偏差但增加方差, 而减小 \(n\) 则效果相反
注意，当 \(n = T - t - 1\) 时, 恢复为最初使用的无偏但方差较高的蒙特卡洛优势估计
而当 \(n = 0\) 时, 则恢复为方差较低但偏差较高的优势估计 \(\delta_t\)

我们可以将多个 \(n\) 步优势估计组合为指数加权和, 这被称为广义优势估计器 (GAE)
设 \(\lambda \in [0, 1]\), 那么我们定义 (0-index): \[ A_\text{GAE}^{\pi}(\mathbf s_t, \mathbf a_t) = \frac{1-\lambda^{T-t-1}}{1-\lambda} \sum_{n=1}^{T-t-1} \lambda^{n-1} A_n^{\pi}(\mathbf s_t, \mathbf a_t) \] 其中 \(\dfrac{1-\lambda^{T-t-1}}{1-\lambda}\) 是一个归一化常数
注意, 较高的 \(\lambda\) 会强调具有较大 \(n\) 值的优势估计, 而较低的 \(\lambda\) 则相反
因此, \(\lambda\) 充当了偏差 - 方差权衡 (bias-variance tradeoff) 的控制参数: 增加 \(\lambda\) 会减少偏差但增加方差

在无限时间范围 (inftyite horizon) 的情况下 (\(T = \infty\)), 我们可以证明: \[ \begin{aligned} A_\text{GAE}^{\pi}(\mathbf s_t, \mathbf a_t) &= \frac{1}{1-\lambda} \sum_{n=1}^{\infty} \lambda^{n-1} A_n^{\pi}(\mathbf s_t, \mathbf a_t) \\ &= \sum_{t'=t}^{\infty} (\gamma\lambda)^{t'-t} \delta_{t'} \end{aligned} \] 出于简洁考虑, 我们省略了推导过程 (详细信息请参阅 GAE 论文）

在有限时间范围 (finite horizon) 的情况下, 我们可以写为:

\[ A_\text{GAE}^{\pi}(\mathbf s_t, \mathbf a_t) = \sum_{t'=t}^{T-1} (\gamma\lambda)^{t'-t} \delta_{t'} \] 这提供了一种高效实现广义优势估计器的方法, 因为我们可以递归地计算:

\[ A_\text{GAE}^{\pi}(\mathbf s_t, \mathbf a_t) = \delta_t + \gamma\lambda A_\text{GAE}^{\pi}(\mathbf s_{t+1}, \mathbf a_{t+1}) \]

Review Analysis

这里引入了一些神奇妙妙符号, 我们解释一下
\(\delta_t\) 被称为时序差分误差 (TD Error), \(V_{\phi}^{\pi}(\mathbf s_{t})\) 是行动前对当前状态能拿多少分的旧预测,
而 \(r(\mathbf s_{t},\mathbf a_{t}) + \gamma V_{\phi}^{\pi}(\mathbf s_{t+1})\) 是你实际走了一步后, 拿到的真实奖励加上对未来的新预测
因为 \(Q^{\pi}(\mathbf s_t, \mathbf a_t) = \mathbb{E}_{\mathbf s_{t+1}}[r(\mathbf s_t, \mathbf a_t) + \gamma V^{\pi}(\mathbf s_{t+1})]\), 不求期望, 做单步采样就是上面的式子 \(A^\pi(\mathbf s_t, \mathbf a_t) \approx \delta_t = \dots\)

我们可以转向做 \(n\) 步的估计, 多一点采样步数, 少一点预测步数, 就是下面的式子 \[ A_{n}^{\pi}(s_{t},a_{t})=\underbrace{\sum_{t^{\prime}=t}^{t+n}\gamma^{t^{\prime}-t}r(s_{t^{\prime}},a_{t^{\prime}})}_{\text{1.真实的多步体验}} + \underbrace{\gamma^{n}V_{\phi}^{\pi}(s_{t+n+1})}_{\text{2.对远期未来的预测}} - \underbrace{V_{\phi}^{\pi}(s_{t})}_{\text{3.最初的期望基线}} \] 那问题变成了, \(n\) 为多少的时候效果最好？GAE 的解决方法是: 把所有可能的 \(n\) 步优势估计 \(A_n^{\pi}(\mathbf s_t, \mathbf a_t)\) 全都算出来, 然后给它们做一个加权平均 \[ A_{GAE}^{\pi}(\mathbf s_t, \mathbf a_t) = \underbrace{\frac{1-\lambda^{T-t-1}}{1-\lambda}}_{\text{1.归一化常数}} \sum_{n=1}^{T-t-1} \underbrace{\lambda^{n-1}}_{\text{2.指数衰减}} \underbrace{A_n^{\pi}(\mathbf s_t, \mathbf a_t)}_{\text{3.各个 n 步的优势估计}} \] 用 \(\delta_t\) 重写这个优势函数, 就是 \(A_\text{GAE}^{\pi}(\mathbf s_t, \mathbf a_t) = \delta_t + \gamma\lambda A_\text{GAE}^{\pi}(\mathbf s_{t+1}, \mathbf a_{t+1})\)

Code

先看 pg_agent.py, 这部分内容照着我们上面的 Review 和 Analysis 可以完成, GAE 可能难一点

batch_size = obs.shape[0]
values = np.append(values, [0])
advantages = np.zeros(batch_size + 1)
for i in reversed(range(batch_size)):
    advantages[i] = rewards[i] + (1-terminals[i])*self.gamma*values[i+1] - values[i] # A^\pi = \gamma_t
    advantages[i] += self.gamma * self.gae_lambda * advantages[i+1] # A_{GAE}^\pi
advantages = advantages[:-1] # remove dummy advantage

再之后还能用 advantage normalisation 方法, 直接变成 \(\mathcal N(0,1)\) 上的优势函数

if self.normalize_advantages:
    return (advantages - advantages.mean()) / (advantages.std() + 1e-8)

在 critics.py 中, 我们要训练 \(V_\phi^{\pi}\), forward 方法就是直接 self.network(obs) 了, 问题是怎么 update
我们一般使用 TD 误差(时序差分误差), 在 lecture 6 中有 \(\mathcal L(\phi) = \dfrac{1}{2} \sum\limits_i \| \hat V_{\phi}^\pi - y_i \|^2\), 这里的 \(y_i\) 就是 Q 函数的单步采样, 即 \(y_{i,t} \approx r(\mathbf s_{i,t}, \mathbf a_{i,t}) + \gamma \hat V_{\phi}^\pi (\mathbf s_{i,t+1})\)​, 不过代码好像直接给了 q_values？
于是有代码

def update(self, obs: np.ndarray, q_values: np.ndarray) -> dict:
    obs = ptu.from_numpy(obs)
    q_values = ptu.from_numpy(q_values)
    self.optimizer.zero_grad() 
    logits = self.forward(obs)
    # TODO: update the critic using the observations and q_values
    loss = F.mse_loss(logits, q_values)
    loss.backward()            
    self.optimizer.step()
    return {
        "Baseline Loss": ptu.to_numpy(loss),
    }

然后想要启动 run_hw2.py, 发现 utils.py 中 sample_trajectory 还没写, utils.py 进去一看发现 policies.py 中的 MLPPolicy 类也没写

在离散动作空间里, self.logits_net 输出每个动作的相对概率 logits,
在连续动作空间里, 还是 Assignment 1 中的 self.mean_net
在 MLPPolicyPG 类里的 update 是 actor-critic 中的 update, 使用 \(\nabla_\theta J(\theta) \approx \sum_i \ \nabla_\theta \log \pi_\theta \left(\mathbf a_i|\mathbf s_i \right) \hat A^\pi(\mathbf s_i, \mathbf a_i)\)

self.optimizer.zero_grad() 
dist = self.forward(obs)
log_probs = dist.log_prob(actions) # 专家动作在当前高斯分布下的对数概率
if not self.discrete:
    log_probs = log_probs.sum(dim=-1)
    # 连续情况下, log_probs 维度是 (Batch, Action_Dim), 需要对 Action_Dim 求和
loss = -(log_probs * advantages).mean()
loss.backward()            
self.optimizer.step()

回到 utils.py, 发现和 Assignment 1 中的一样, 略
回到 run_hw2.py, 一行 utils.sample_trajectories(env, agent, args.batch_size, max_ep_len) 就行了
下面 agent.update 调用一下 trajs_dict 的内容, 记得 obs 和 acs 要做 np.concatenate()

然后我们会在不同的 batch-size, reward-to-go, advantage normalization 设置下跑八次代码,
下面是 blacefeather 的结论

tensorboard 上的图表有很多, 我们主要关心 Average Return
我这边最好的结果来自 大 batch + advantage normalization, 稳得很, 否则会抖

在 HalfCheetah-v4 任务上, 增加 baseline 后会变好很多, 但是仍然很抽象
这个任务是控制一个二维机器人向右奔跑, 即使训练了 100 轮还是只能抽抽着走一两步

在 LunarLander-v2 任务上, 我们要应用 GAE, 做一个飞船降落的问题, 300 轮在我的 CPU pytorch 上跑死了, 这部分主要是教你调整 GAE 的 \(\lambda\) 以获得偏差与方差的权衡, 这个任务震荡的非常厉害, 设置 \(\lambda = 0.99\) 比较好

我们略过调超参的问题, 直接看最后一个问题, 在 Humanoid-v4 任务上训练能走的人类, 1000 轮, batch_size = 50000, 我一轮在 GPU 上训 70s 左右, 寄, 应该把一些 list 改成 tensor, 更聪明点就自己写并行, 作业建议 vectorize

我能给后来人的建议是, 200 轮左右就收敛的差不多了, 训 4h 左右应该就行?

Analysis

考虑下面这个无限视界 MDP \[ \mathbf a_1 \circlearrowright \mathbf s_1 \stackrel{\mathbf a_2}{\longrightarrow} \mathbf s_F \] 在每一步, agent 如果选择动作 \(\mathbf a_1\) 会停留在 \(\mathbf s_1\) 并获得 1 点奖励, 否则会获得 0 奖励并且终止
我们可以把策略写成这样, \(\theta\) 表示概率: \[ \pi_\theta(\mathbf a_1|\mathbf s_1) = \theta, \pi_\theta(\mathbf a_2|\mathbf s_1) = 1-\theta \]

1. 使用 policy gradient

​ a. 使用 policy gradient 计算奖励 \(R(\tau)\) 的期望的梯度(\(\nabla_\theta J(\theta)\)) , 不考虑折扣因子 \(\gamma\)

套公式 \(\nabla_\theta J(\theta) = E_{\tau \sim p_\theta(\tau)} \left[ \left( \sum\limits_{t=1}^T \nabla_\theta \log \pi_\theta(\mathbf a_t|\mathbf o_t) \right) \left( r(\tau) \right) \right]\), 然后思考, \(\tau\) 是啥, \(\nabla_\theta \log \pi_\theta(\mathbf a_t|\mathbf o_t)\) 是啥？
设 \(\tau_i\) 代表它选择了 \(i\) 次动作 \(\mathbf a_1\), 然后选择了一次 \(\mathbf a_2\), 故 \(r(\tau_i) = i\)
思考 \(\nabla_\theta \log \pi_\theta(\mathbf a_t|\mathbf o_t)\), 要么是 \(\nabla_\theta \log \theta\) 要么是 \(\nabla_\theta \log (1-\theta)\), 求和, 对于 \(\tau_i\), 其为 \(\dfrac{i}{\theta}+ \dfrac{-1}{1-\theta}\)
对于 \(\tau_i\), 其出现的概率为 \(\theta^i(1-\theta)\)
于是 \(\nabla_\theta J(\theta) = \sum\limits_{i=0}^{\infty} \theta^i(1-\theta)[(\dfrac{i}{\theta}+ \dfrac{-1}{1-\theta})i] = \sum\limits_{i=0}^{\infty} (\theta^{i-1} i^2 -\theta^i i^2 -\theta^{i} i)\)
我们在高数课上牢记过 \(\sum\limits_{i=0}^{\infty} \theta^i = 1 + \theta + \theta^2 + \theta^3 + \dots = \dfrac{1}{1 - \theta}\), 这个式子两边对 \(\theta\) 求任意次导再乘(或不乘) \(\theta\) 可以获得 \(\sum\limits_{i=0}^{\infty} i\theta^{i-1}, \sum\limits_{i=0}^{\infty} i\theta^{i}, \sum\limits_{i=0}^{\infty} i^2\theta^{i}\) 等的值, 最后可以推出 \(\nabla_\theta J(\theta) = \dfrac{1}{(1-\theta)^2}\)

​ b. 直接通过对 \(J(\theta)\) 求导来计算 \(\nabla_\theta J(\theta)\)

\(J(\theta) = E_{\tau \sim p_{\theta}(\tau)} [r(\tau)] = \sum\limits_{i=0}^{\infty} \theta^i(1-\theta)i = \dfrac{\theta}{1-\theta}\), 求导可得 \(\nabla_\theta J(\theta) = \dfrac{1}{(1-\theta)^2}\)

2. 计算策略梯度的方差 \(\text{Var}(\nabla_\theta J(\theta))\), 当 \(\theta\)​ 为何值时方差最小? 最大?

套公式, 我们在概率论课上记过, \(\text{Var}(\nabla_\theta J(\theta)) = E[(\nabla_\theta J(\theta))^2] - (E[\nabla_\theta J(\theta)])^2\)
其中 \(E[\nabla_\theta J(\theta)] = \nabla_\theta J(\theta)\), 但是 \(E[(\nabla_\theta J(\theta))^2]\) 就不好弄了, 这是个二阶矩, 有 \[ \begin{aligned} E[(\nabla_\theta J(\theta))^2] &= \sum_{i=0}^\infty \theta^i(1-\theta) [(\dfrac{i-1}{\theta}+ \dfrac{-1}{1-\theta})i]^2 \\ &= \sum_{i=0}^\infty \theta^i(1-\theta) \left[ \frac{i^2(1-\theta) - i}{\theta(1-\theta)} \right]^2 \\ &= \frac{1}{\theta^2(1-\theta)} \sum_{i=0}^\infty \theta^i \left[ i^4(1-\theta)^2 - 2i^3(1-\theta) + i^2 \right] \\ &= \frac{\mathbb{E}[T^4]}{\theta^2} - \frac{2\mathbb{E}[T^3]}{\theta(1-\theta)} + \frac{\mathbb{E}[T^2]}{(1-\theta)^2} \quad 带入 2-4 阶原点矩\\ &= \frac{1 + 9\theta + 4\theta^2}{\theta(1-\theta)^4} \end{aligned} \] 于是 \(\text{Var}(\nabla_\theta J(\theta)) = E[(\nabla_\theta J(\theta))^2] - (E[\nabla_\theta J(\theta)])^2 = \dfrac{1 + 9\theta + 4\theta^2}{\theta(1-\theta)^4} - \dfrac{1}{(1-\theta)^4} = \dfrac{1 + 8\theta + 4\theta^2}{\theta(1-\theta)^4}\)
当 \(\theta \to 0\) 或 \(\theta \to 1\) 时, \(\text{Var} \to +\infty\), 当 \(\theta \approx 0.1099\) 时, \(\text{Var}_\min \approx 27.9411\)

3. 应用因果假设(reward to go)技巧

​ a. 应用因果假设(reward to go)技巧下计算 \(\nabla_\theta J(\theta)\)

此时 \(\nabla_\theta J(\theta) = E_{\tau \sim p_\theta(\tau)} \left[ \left( \sum\limits_{t=1}^T \nabla_\theta \log \pi_\theta(\mathbf a_t|\mathbf o_t) \right) \left( \sum\limits_{t'=t}^T r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \right) \right]\), 主要是 \(r\) 不好算了, 我们令 \(r_{i,t}\) 表示第 \(i+1\) 步走到 \(\mathbf s_F\), 从 \(t\) 步开始的总奖励, 有 \(r_{i,t} = i-t+1\)
对于 \(\tau_i\), 其梯度为 \(\sum\limits_{t=0}^i \dfrac{1}{\theta}(i-t+1)\), 在 \(i+1\) 步的终结不贡献梯度
于是 \(\nabla_\theta J(\theta) = \sum\limits_{i=0}^{\infty} \theta^i(1-\theta)[\sum\limits_{t=1}^i \dfrac{1}{\theta}(i-t+1)] = \dfrac{1}{(1-\theta)^2}\), 和之前一样

​ b. 应用因果假设(reward to go)技巧下计算方差, 并与 1.b 一起在 \(\theta - \text{Var}\)​ 坐标系上绘图

单个轨迹的样本梯度 \(g(\tau_i) = \sum\limits_{t=1}^i \dfrac{1}{\theta}(i-t+1) = \dfrac{i(i+1)}{2\theta}\), 故有 \[ \begin{aligned} E[(\nabla_\theta J(\theta))^2] &= \sum_{i=0}^{\infty} \theta^i(1-\theta) \left[ \frac{i(i+1)}{2\theta} \right]^2 \\ (E[\nabla_\theta J(\theta)])^2 &= \left( \sum_{i=0}^{\infty} \theta^i(1-\theta) \left[ \frac{i(i+1)}{2\theta} \right] \right)^2 \\ \text{Var}(\nabla_\theta J(\theta)) &= E[(\nabla_\theta J(\theta))^2] - (E[\nabla_\theta J(\theta)])^2 \\ &= \dfrac{\theta^2 + 3\theta + 1}{\theta(1-\theta)^4} \end{aligned} \]

绘图, 有

应用 reward-to-go 将方差极值从 B(约 27.94) 点降低到了 C 点(约 18.79)

4. 考虑下图这个 H 步的 MDP

​ 如果到达 \(\mathbf s_H\), 有奖励 \(R_{\max}=1\), 否则如果到达 \(\mathbf s_F\) 获得 0 奖励并且终止

​ a. 通过重要性采样方法列出 policy-gradient​

除非整条轨迹都是 \(\mathbf a_1\)​, 奖励为 1, 否则奖励为 0, 可以抽象为两条轨迹, 故 \[ \nabla_\theta J(\theta) = \theta^H \cdot \frac{H}{\theta} = H\theta^{H-1} \] 啊, 但这不叫作重要性采样, 我们得从 \(\theta'\) 上采集样本, 此时 \(\nabla_\theta J(\theta) = \mathbb E_{\tau \sim \pi_{\theta'}} \left[ R(\tau)\dfrac{p_{\theta}(\tau)}{p_{\theta'}(\tau)} \nabla_{\theta} \log p_{\theta}(\tau) \right]\)
因为只有一条轨迹有奖励, 有 \[ \begin{aligned} \nabla_\theta J(\theta) &= (\theta')^H \cdot 1 \cdot \frac{(\theta)^H}{(\theta')^H} \cdot \frac{H}{\theta} = H\theta^{H-1} \end{aligned} \] ​ b. 通过重要性采样方法计算其方差

还是 \(\text{Var}(X) = \mathbb E[X^2] - (\mathbb E[X])^2\) 老一套, 但是我们的样本梯度 \(\hat{g}(\tau) = R(\tau)\dfrac{p_{\theta}(\tau)}{p_{\theta'}(\tau)} \nabla_{\theta} \log p_{\theta}(\tau)\)
第二项很好算, \((\mathbb E_{\tau \sim \pi_{\theta'}}[\hat{g}(\tau)])^2 = (H\theta^{H-1})^2 = H^2\theta^{2H-2}\)
我们算第一项, 有 \[ \begin{aligned} \mathbb E_{\tau \sim \pi_{\theta'}}[\hat{g}(\tau)^2] &= p_{\theta'}(\tau_{succ}) \left( 1 \cdot \frac{p_{\theta}(\tau_{succ})}{p_{\theta'}(\tau_{succ})} \nabla_{\theta} \log p_{\theta}(\tau_{succ}) \right)^2 \\ &= (\theta')^H \cdot \left( \frac{\theta^H}{(\theta')^H} \cdot \frac{H}{\theta} \right)^2 \\ &= \frac{H^2\theta^{2H-2}}{(\theta')^H} \end{aligned} \] 故 ${{'}}[()] = H²{2H-2} ( - 1 ) $

Assignment 3 Q-learning 与 Actor-Critic 算法

Questionnaire

考虑 Lecture 8 中的 n 步奖励 Q-learning, 我们通过以下步骤学习 \(Q_{\phi_{k+1}}\) \[ y_{j,t}\leftarrow(\sum_{t^{\prime}=t}^{t+N-1}\gamma^{t^{\prime}-t}r_{j,t^{\prime}})+\gamma^{N} \max_{\mathbf a_{j,t+N}}Q_{\phi_{k}}(\mathbf s_{j,t+N},\mathbf a_{j,t+N}) \quad (1) \\ \phi_{k+1}\leftarrow \arg \min_{\phi\in\Phi}\sum_{j,t}(y_{j,t}-Q_{\phi}(\mathbf s_{j,t},\mathbf a_{j,t}))^{2} \quad (2) \] 在这些等式中, \(j\) 表示轨迹回放缓冲区 \(\mathcal D_{k}\) 中的索引
我们首先使用策略 rollout 一批包含 B 个轨迹的数据, 以更新 \(\mathcal{D}_{k}\) 并计算等式 (1) 中的目标值, 然后我们使用等式 (2) 将 \(Q_{\phi_{k+1}}\) 拟合到这些目标值上
在估计出 \(Q_{\phi_{k+1}}\)​ 之后, 我们可以通过 argmax 更新策略 \[ \pi_{k+1}(\mathbf a_{t}|\mathbf s_{t})\leftarrow \begin{cases} 1 \text{ if } \mathbf a_{t} = \arg \max_{\mathbf a_{t}}Q_{\phi_{k+1}}(\mathbf s_{t},\mathbf a_{t})\\ 0~\text{otherwise}. \end{cases} \quad (3) \] 我们将等式 (1) 到 (3) 中的步骤重复 K 次以改进策略。在这个问题中, 你将分析下文算法 1 的一些性质

Q1-1 TD-Learning Bias
我们说使用从过程 \(P\) 采样的数据 \(\mathcal D\) 构建的 \(f\) 的估计器 \(f_{\mathcal{D}}\) 是无偏的, 当且仅当在每个 \(x\) 处 \(\mathbb{E}_{\mathcal{D}\sim P}[f_{\mathcal{D}}(x)- f(x)]=0\)
假设 \(\hat{Q}\) 是对 \(Q\) 的一个带噪声 (但无偏) 的估计, 贝尔曼备份 \(\mathcal{B}\hat{Q}=r(\mathbf s,\mathbf a)+\gamma\max_{\mathbf a^{\prime}}\hat{Q}(\mathbf s^{\prime},\mathbf a^{\prime})\) 是否是 \(\mathcal BQ\) 的无偏估计？

显然不对, \(\mathbb{E}[\hat{Q}(\mathbf s,\mathbf a)] = Q(\mathbf s,\mathbf a)\), \(\mathbb{E}[\max \hat{Q}(\mathbf s,\mathbf a)] \geq \max Q(\mathbf s, \mathbf a)\),
因为对于凸函数 \(f\), 有 \(\mathbb{E}[f(X)] \geq f(\mathbb{E}[X])\), 而 \(\max\) 是凸函数

Q1-2 Tabular Learning
在上述算法每次经过等式 (2) 的更新后, \(Q_{\phi_{k}}\) 可以被看作是对真实最优 \(Q^{*}\) 的估计, 考虑以下陈述

i. \(Q_{\phi_{k+1}}\) 是上一策略的 Q 函数 \(Q^{\pi_{k}}\) 的无偏估计
ii. 当 \(k \to \infty\), 对于某个固定的 B, \(Q_{\phi_{k}}\) 是 \(Q^{*}\) 的无偏估计, 即 \(\lim_{k\rightarrow\infty}\mathbb{E}[Q_{\phi_{k}}(s,a)-Q^{*}(s,a)]=0\)
iii. 在无限次迭代和无限数据的极限情况下, 我们能恢复出最优的 \(Q^{*}\), 即 \(\lim_{k,B\rightarrow\infty}\mathbb{E}[\|Q_{\phi_{k}}-Q^{*}\|_{\infty}]=0\)

我们做出以下额外假设:
状态和动作空间是有限的; 每个批次至少包含在每个状态下采取的每种动作的一次经验; 在表格型设置中, \(Q_{\phi_{k}}\) 可以表达任何函数, 即 \(\{Q_{\phi_{k}}:\phi\in\Phi\}=\mathbb{R}^{S\times A}\)​

当在算法 1 的第 3 行使用 B 条新轨迹更新缓冲区 \(\mathcal{D}_{k}\) 时, 我们说:
当进行 on-policy 学习时, \(\mathcal{D}_{k}\) 被设置为仅包含 \(\pi_{k}\) 的 B 个新 rollout (因此 \(|\mathcal{D}_{k}|=B\)), 因此, 我们只在当前策略的 rollout 上进行训练
当进行 off-policy 学习时, 我们使用来自另一个策略 \(\pi^{\prime}\) 的 B 条轨迹构成的固定数据集 \(\mathcal{D}_{k}=\mathcal{D}\)

指出在以下情况下哪些陈述 i-iii 始终成立, 下表每个格子填写三个 T/F, 表示是否遵守陈述 i-iii, 例: T T F

	on-policy	off-policy
\(N=1\)	F F T	F F T
\(N>1\)	F F T	F F F
\(N\rightarrow\infty\) 且无自举	T F T	F F F

解释一下, i 到 iii 的假设是逐渐减弱的, 我们用表格表示而不是神经网络来拟合 Q 函数, 这使无偏变得可能
首先, ii 不可能成立, 因为 \(\max\) 必然引入高估的误差
然后, \(N>1\) 时 off-policy 的策略会被 \(\sum r\) 污染, 不可能还原最优解而满足 iii, 其他情况不被污染能满足 iii
最后, 无偏估计 \(Q^{\pi_{k}}\) 就不能引入自举, 否则 \(\max\) 有偏差, 所以仅 \(N\rightarrow\infty\) 且无自举且 on-policy 下成立

Q1-3 Variance of Q Estimate
在无限次迭代的极限情况下, 对于固定的数据集大小 B, 您预计这三种情况 (\(N=1\)、\(N>1\)、\(N\rightarrow\infty\)​) 中哪一种对 Q 的估计方差最高？哪一种方差最低

\(N\rightarrow\infty\) 方差最高, \(N=1\) 方差最低, 因为 \(N\)​ 越大累加的随机变量越多

Q1-4 Function Approximation
现在假设我们希望通过函数逼近而不是表格型表示来表示 \(Q\), 假设对于任何确定性策略 (包括最优策略 \(\pi^{*}\)), 函数逼近都能准确无误地表示真实的 \(Q^{\pi}\), 以下哪些陈述是正确的？

1. 当 \(N=1\) 时, \(Q_{\phi_{k+1}}\) 是上一策略的 Q 函数 \(Q^{\pi_{k}}\) 的无偏估计
   
2. 当 \(N=1\) 且在 \(B\rightarrow\infty\)、\(k\rightarrow\infty\) 的极限下, \(Q_{\phi_{k}}\) 收敛到 \(Q^{*}\)
   
3. 当 \(N>1\) (但有限) 且在 \(B\rightarrow\infty\)、\(k\rightarrow\infty\) 的极限下, \(Q_{\phi_{k}}\) 收敛到 \(Q^{*}\)
   
4. 当 \(N\rightarrow\infty\) 且在 \(B\rightarrow\infty\)、\(k\rightarrow\infty\) 的极限下, \(Q_{\phi_{k}}\) 收敛到 \(Q^*\)

这里应该默认是 on-policy 的, 我们使用函数逼近时, 比 tabular 引入了自举的互相影响, 所以仅有 iiii 成立, 即使函数能准确无误地表示真实的 \(Q^\pi\)

Q1-5 Multistep Importance Sampling
我们可以使用重要性采样(Importance Sampling) 使 N 步更新在 off-policy 的情况下利用从任意策略抽样的轨迹工作
重写等式 (1) 以正确逼近一个 \(Q_{\phi_{K}}\), 使得当它在包含其他策略 \(\pi^{\prime}(\mathbf a_{t}|\mathbf s_{t})\) 的 B 个 rollout 的数据 \(\mathcal D\) 上进行训练时, 能够带来改进
当 \(N=1\) 时我们需要改变等式 (1) 吗？当 \(N\rightarrow\infty\) 时呢？你可以假设 \(\pi^{\prime}\) 始终为每个动作分配正的概率质量
[提示: 使用来自当前策略和 \(\pi^{\prime}\) 的似然比 (ratio of likelihoods) 对总和中的每一项进行重新加权]

原来是 \[ y_{j,t}\leftarrow(\sum_{t^{\prime}=t}^{t+N-1}\gamma^{t^{\prime}-t}r_{j,t^{\prime}})+\gamma^{N} \max_{\mathbf a_{j,t+N}}Q_{\phi_{k}}(\mathbf s_{j,t+N},\mathbf a_{j,t+N}) \quad (1) \]

模仿 Lecture 4 与 Lecture 9 的方法, 令 \(\rho_t = \dfrac{\pi'(\mathbf{a}_t | \mathbf{s}_t)}{\pi(\mathbf{a}_t | \mathbf{s}_t)}\), 更改后即 \[ y_{j,t} \leftarrow r_{j,t} + \left(\sum_{t'=t+1}^{t+N-1}\gamma^{t^{\prime}-t} \left( \prod_{t''=t+1}^{t'} \rho_{t''} \right) r_{j,t^{\prime}} \right)+\gamma^{N} \left( \prod_{t'=t+1}^{t+N-1} \rho_{t'} \right) \max_{\mathbf a_{j,t+N}}Q_{\phi_{k}}(\mathbf s_{j,t+N},\mathbf a_{j,t+N}) \] 我们修正的是错误的动作, 其中第一个动作是正确的, 不修正, 最后一个动作(t+N)是自举的, 不修正
当 \(N=1\) 时不需要重要性采样, 当 \(N \to \infty\) 时仍然需要修正 \(r\)

Code

先来读代码, 为了假装我们努力过了, 我们不直接把 dqn_agent.py 与 run_hw3_dqn.py 扔进 ai 里面让它填完所有的 TODO, 相反, 我们先看完 dqn_basic_config.py 与 dqn_atari_config.py, 当然, 不会的地方还得问 ai

在 dqn_basic_config.py 中
def basic_dqn_config() 接收了一系列 DQN 训练必需的超参数, 例如 clip_grad_norm 对梯度 clip, use_double_q 决定是否使用 DDQN, discount 就是折扣因子 \(\gamma\)​, target_update_period 是目标网络同步参数的频率
def make_critic() 构建了 Q 网络, 用一个 MLP 作为 Q 拟合器
def make_optimizer() 与 def make_lr_schedule() 定义如何更新网络, 注意 exploration_schedule

exploration_schedule = PiecewiseSchedule(
    [
        (0, 1),
        (total_steps * 0.1, 0.02),
    ],
    outside_value=0.02,
)

这里用 \(\epsilon\)​-greedy, 第一步 100% 随机, 在总进度的 10% 时, 随机探索率直线下降到 2%, 之后一直不变
def make_env() 里面使用了 RecordEpisodeStatistics() Wrapper, Wrapper 可以看成一种更高级的装饰器, 可以无限套娃, 在这里它的作用是自动帮你记录每个 Episode 的总奖励和耗时步数

在 dqn_atari_config.py 中:
我们的 Q 网络用上了 CNN, 而且有 PreprocessAtari() 把 uint8 归一化到 [0,1] 浮点数
wrap_deepmind 是一个 Wrapper 大礼包 ! (from gemini pro 3.1), 其中包含: 灰度化与缩放, 跳帧, 帧堆叠(把连续的 4 张处理后的画面叠在一起, 就可以知道速度, 方向, 加速度)
做 Atari 游戏的 RL 可比做 cartpole 困难多了, 这里可以看到 total_steps 更大, make_lr_schedule 更复杂, exploration_schedule 时间更长

在 replay_buffer.py 中:
class ReplayBuffer 适用于状态是一维向量的情况,
insert(obs, act, rew, next_obs, done): 将单步交互产生的 \((\mathbf s, \mathbf a, \mathbf s', r, d)\) 五元组存入对应数组的指定位置, 并将 self.size 加 1, 这里的 d 是完成标记位
sample(batch_size): 组装好的一个 Batch 的数据, 供神经网络进行梯度下降
class MemoryEfficientReplayBuffer 用于 Atari 游戏等以图像作为状态输入的环境

在 atari_wrappers.py 中:
class FireResetEnv 帮忙按 "开始", 跳过无意义的"等待开局"阶段
class ClipRewardEnv 统一奖励尺度
def wrap_deepmind() 就是大礼包 !, 记录 reward, AtariPreprocessing, FrameStack

我们先来完成 dqn_agent.py, 先写 get_action, 使用 \(\epsilon\)- greedy, 记得用 tensor

def get_action(self, observation: np.ndarray, epsilon: float = 0.02) -> int:
    observation = ptu.from_numpy(np.asarray(observation))[None]
    if np.random.random() < epsilon:
        action = torch.tensor(np.random.randint(self.num_actions)).to(ptu.device)
    else:
        with torch.no_grad(): 
            q_values = self.critic(observation) # [1, num_actions]
        action = torch.argmax(q_values, dim=-1)
        # 找到最后一个维度中最大值的索引, 并转换为 Python int
    return ptu.to_numpy(action).squeeze(0).item()

然后 update_critic, 先写 target 网络, 不管 DDQN, 其实这里的 next_action 没用

with torch.no_grad():
    next_qa_values = self.target_critic(next_obs)
    if self.use_double_q:
        raise NotImplementedError # DDQN 先不管
    else:
        next_action = next_qa_values.argmax(dim=-1)   
    next_q_values = torch.max(next_qa_values, dim=-1)[0]
    target_values = reward + self.discount*next_q_values*(~done)

在考虑 DDQN 时代码是这样

with torch.no_grad():
    next_qa_values = self.target_critic(next_obs)
    if self.use_double_q:
        main_next_qa_values = self.critic(next_obs)
        next_action = main_next_qa_values.argmax(dim=-1)    
        next_q_values = torch.gather(next_qa_values, dim=1, 
                                     index=next_action.unsqueeze(1)).squeeze(-1)
    else: 
        next_q_values = torch.max(next_qa_values, dim=-1)[0]
    target_values = reward + self.discount*next_q_values*(~done)

然后 MSE 算 loss

qa_values = self.critic(obs)
q_values = torch.gather(qa_values, dim=1, index=action.unsqueeze(1)).squeeze(1)
loss = self.critic_loss(q_values, target_values)

最后 update 就很好写了

critic_stats = self.update_critic(obs, action, reward, next_obs, done)
if(step % self.target_update_period == 0):
	self.update_target_critic()

继续完成 run_hw3_dqn.py, 和之前的很像,

action = agent.get_action(observation,epsilon)
next_observation, reward, done, info = env.step(action)

replay_buffer insert 分辨一下是普通的还是 Memory 的

if isinstance(replay_buffer, MemoryEfficientReplayBuffer):
    replay_buffer.insert(action=action, 
                     reward=reward, 
                     next_observation=next_observation[-1], 
                     done=done)
else:
    replay_buffer.insert(observation=observation, 
                     action=action, 
                     reward=reward, 
                     next_observation=next_observation, 
                     done=done)

之后直接从 buffer 里面 sample batch, 然后调用 agent.update, 其实还算简单

完成这些之后可以跑跑 cartpole 与 LunarLander 任务, 有一些结论:
DQN 不稳定: \(Q\) 值发散、目标不平稳、高估偏置, 把 lr 调高会爆炸(Q 与 Critic loss)
DDQN 还可以, 效果比 DQN 好一些

我们在 LunarLander 上跑个 300k step, 上图红线是 DDQN, 黄线是 DQN, 好的比较有限, 可能因为 \(\phi, \phi'\) 相关性太大了, 应该从头训两套网络
有点怪, eval return 在 0 左右, 我们第二次作业做 policy gradient 的 eval return 在 100 左右震荡
好像是还没收敛, DQN 就是慢啊, 得等到 500k 步左右才有 200+ reward
之后再试一下 mspacman 任务

MsPacman 是一个假人在一个固定的环境中尽量躲避敌人并得分的游戏, 每次被敌人碰到就会丧失一次机会,一共有三次机会, 没有时间限制, 目的是尽可能的获得高的分数.
MsPacman 的动作空间维度是 9, 是从数字 0 到 8 的离散空间, gym 游戏中给出的 reward 空间为[0, 10, 50]

当然, Wrapper 包裹之后, RL 接受的输入就是 4 帧一次的 resize 的模糊灰度图

这个作业其实只关心最后的 eval_return, 我们跑 1M step(约 4h), reward 能有 1600 左右

其中黄线是 eval return, 绿线是 train return

接下来我们进入连续动作的部分
在连续动作时, 我们还要训练一个 policy \(\pi\) 去最大化 \(\mathbb E_{\mathbf a \sim \pi(\mathbf a|\mathbf s)}Q(\mathbf s, \mathbf a)\)​

run_hw3_sac.py 的逻辑与 run_hw3_dqn.py 相同, 故略去, 我们主要看怎么写 soft_actor_critic.py
这里的花活很多, 除了 DDQN, 还有 min, mean, REDQ 方法, actor 也可以用 reinforce 或 reparametrize(重参数化)

对于不同类型的 q_strategy, 就是对一堆 critic 网络进行简单操作

if self.target_critic_backup_type == "doubleq":
    next_qs=next_qs[[1,0]]
elif self.target_critic_backup_type == "min":
    next_qs=torch.min(next_qs, dim=0)[0]
elif self.target_critic_backup_type == "mean":
    next_qs=torch.mean(next_qs, dim=0)
else: pass

考虑 update_critic 怎么写, 其他部分同上, argmax 变 sample 额外提一下

next_action_distribution: torch.distributions.Distribution = self.actor(obs)
next_action = next_action_distribution.sample()

在连续空间中, 为了产生类似于 \(\epsilon\)-greedy 中的探索噪声, 我们要给予熵惩罚, 以鼓励 actor 具有高熵(更随机), 我们用温度系数 \(\beta\) 来缩放熵并慢慢退火, 此时总 loss 大致为 \[ \mathcal{L}_{\pi}=Q(\mathbf s,\mu_{\theta}(\mathbf s)+\sigma_{\theta}(\mathbf s)\epsilon)+\beta\mathcal{H}(\pi(\mathbf a|\mathbf s)) \] 这里的 \(\mu_{\theta}(\mathbf s)+\sigma_{\theta}(\mathbf s)\epsilon\) 利用了重参数化技巧, 以此传递梯度
其中熵定义为 \(\mathcal{H}(\pi(\mathbf a|\mathbf s))=\mathbb{E}_{\mathbf a\sim\pi}[-\log~\pi(\mathbf a|\mathbf s)]\), 为确保熵也被纳入 Q 函数中, 我们还应该在目标值中考虑它 \[ y\leftarrow r_{t}+\gamma(1-d_{t})[Q_{\phi}(\mathbf s_{t+1},\mathbf a_{t+1})+\beta\mathcal{H}(\pi(\mathbf a_{t+1}|\mathbf s_{t+1}))] \] 由于 torch.distributions.Distribution 自带了很好的 rsample() 与 log_prob() 方法, 我们直接用

def update_critic(...):
    ...
    with torch.no_grad():
        if self.use_entropy_bonus and self.backup_entropy:
            next_action_entropy = self.entropy(next_action_distribution)
            next_qs += self.temperature * next_action_entropy
	...
def entropy(self, action_distribution: torch.distributions.Distribution):
    return -action_distribution.log_prob(action_distribution.rsample())

软更新与硬更新很好写, 因为软更新的方法已经帮你写好了, 你就是调个接口而已

if self.soft_target_update_rate is None:
    if(step % self.target_update_period == 0):
        self.update_target_critic()
else:
    self.soft_update_target_critic(self.soft_target_update_rate)

我们不希望我们的目标 \(\mathbf y\) 一直移动, 所以我们有时也不希望 actor 一直动, 有

for i in range(self.num_critic_updates):
    stats = self.update_critic(observations, actions, rewards, next_observations, dones)
    critic_infos.append(stats)
actor_info = self.update_actor(observations)

即 critic 更新 self.num_critic_updates 后再更新 actor, 这个数字叫做 UTD(Update-To-Data Ratio, UTD)
在传统的 SAC 中, UTD = 1, 这是因为我们只有 1 或 2 个 critic, UTD 太大容易过拟合, 同时 actor 会高估
我们其实还没有实现 REDQ 方法, REDQ 有 10 个 Critic, 每次计算目标值时, 它从 10 个目标网络里随机抽 2 个并取最小值, 把 Q 值的爆炸压住了

elif self.target_critic_backup_type == "redq":
    random_indices = torch.randperm(next_qs.size(0))[:2]
    next_qs = torch.min(next_qs[random_indices[0]], next_qs[random_indices[1]])

我们在 hopper 任务中比较 DQN, DDQN, clipped-DQN, REDQ(critic=10, UTD=20) 方法

从 eval_return 来看, clipped-DQN>DDQN>REDQ>DQN

从最终估计的 Q 值来看, clipped-DQN 明显较小
AI 说因为 Hopper 是容易失败的任务, 所以最悲观的 clipped-DQN 表现最好
但是我看网上也有 DDQN>clipped-DQN 的情节, 如果我 REDQ 的代码没写错的话, 我更倾向与种子在 RL 中还是太重要了

actor_loss_reinforce() 方法要求随机采样 num_actor_samples 个后算 loss

def actor_loss_reinforce(self, obs: torch.Tensor):
    batch_size = obs.shape[0]
    action_distribution: torch.distributions.Distribution = self.actor(obs)
    with torch.no_grad():
        action = action_distribution.sample((self.num_actor_samples,))
        obs_expand = obs.unsqueeze(0).expand(self.num_actor_samples, -1, -1)
        q_values = self.critic(obs_expand, action)
        q_values = torch.mean(q_values, axis=0)
        advantage = q_values
    log_probs = action_distribution.log_prob(action)
    loss = torch.mean(-log_probs * advantage)
    return loss, torch.mean(self.entropy(action_distribution))

而 REPARAMETRIZE 方法只需要一个样本就可以了, 我们在正态分布 \(\mathcal N\) 上采样, 方差自然小, 还能传梯度

def actor_loss_reparametrize(self, obs: torch.Tensor):
    batch_size = obs.shape[0]
    action_distribution: torch.distributions.Distribution = self.actor(obs)
    action = action_distribution.rsample() # rsample 直接重参数化
    q_values = self.critic(obs, action)
    loss = -torch.mean(q_values)
    return loss, torch.mean(self.entropy(action_distribution))

我们在 halfcheetah 任务上测试 单样本REINFORCE, 十样本REINFORCE, 以及 REPARAMETRIZE方法

发现 REPARAMETRIZE 方法遥遥领先, 把"随机性"和"网络参数"剥离就是好用啊
最后其实还要测试一个 5M 步的 Humanoid, 但是因为在我电脑上要跑 30h 作罢了

Assignment 4 Model-Based RL

Model-Based RL 主要包含两个部分, 一是学习一个动力学函数来模拟观察到的状态转换, 二是以某种方式利用该模型的预测结果来决定下一步该做什么

我们先过一些采样效率的理论部分(see lecture 17), 再完成代码

Analysis

有一个带折扣的表格型 MDP \(M=(\mathcal{S},\mathcal{A},P,r,\gamma)\), 其中 \(\mathcal S, \mathcal A\) 是有限的状态和动作集合,
\(P\) 是动力学模型 (\(P(\cdot\vert{}s,a)\) 是状态上的概率分布), \(r\) 是奖励函数(在 \([0, 1]\) 之间), \(\gamma\in(0,1)\) 是折扣因子

考虑最朴素的基于模型的算法, 假设我们可以访问环境的模拟器, 并且在每个状态-动作对 \((s, a)\) 处, 我们调用模拟器 \(N\) 次来获取样本 \(s^{\prime}\sim P(\cdot\vert{}s,a)\)​, 然后, 我们简单地按如下方式构建环境的动力学模型 \[ \widehat{P}(s^{\prime}\vert{}s,a)=\frac{\text{count}(s,a,s^{\prime})}{N} \] 其中 \(\text{count}(s, a, s')\) 是我们观察到 \((s, a)\) 转移到 \(s^{\prime}\) 的次数
对于表格型 MDP \(M\), 我们可以将 \(\widehat{P}\) 视为一个大小为 \(\vert{}\mathcal{S}\vert{}\vert{}\mathcal{A}\vert{}\times\vert{}\mathcal{S}\vert{}\) 的矩阵

\(\widehat{M}\) 为一个与 M 完全相同的 MDP, 唯一的区别是真实的动力学 \(P\) 被替换为了模型 \(\widehat{P}\)
令 \(\widehat{V}^{\pi}\)、\(\widehat{Q}^{\pi}\)、\(\widehat{V}^{*}\) 和 \(\widehat{Q}^{*}\) 分别表示在 \(\widehat {M}\)​ 中的价值函数、状态-动作价值函数, 以及最优价值函数和最优状态-动作价值函数

Q1. 在第 17 讲中, 我们看到了一个被称为 "模拟引理" (Simulation Lemma) 的证明, 该引理指出对于任意策略 \(\pi\): \[ Q^{\pi}-\widehat{Q}^{\pi}=\gamma(I-\gamma\widehat{P}^{\pi})^{-1}(P-\widehat{P})V^{\pi} \] 证明以下类似的引理, 我们将其称为 "替代模拟引理" (Alternative Simulation Lemma):
对于任意策略, 我们有 \[ Q^{\pi}-\widehat Q^{\pi}=\gamma(I-\gamma P^{\pi})^{-1}(P-\widehat P)\widehat V^{\pi} \]

Proof. 看一眼 lec 17 的笔记回忆一下 \(Q^{\pi}-\widehat{Q}^{\pi}=\gamma(I-\gamma\widehat{P}^{\pi})^{-1}(P-\widehat{P})V^{\pi}\)​ 是怎么推导的

然后猜一猜, 之前是展开 \(\widehat{Q}^{\pi}\), 现在展开 \(Q^\pi\) 能不能凑出来对应的项, 我试试 \[ \begin{aligned} Q^{\pi}-\widehat Q^{\pi} &= (I - \gamma P^\pi)^{-1}r - \widehat Q^{\pi} \\ &= (I - \gamma P^\pi)^{-1}r - (I - \gamma P^\pi)^{-1}(I - \gamma P^\pi)\widehat Q^{\pi} \\ &= (I - \gamma P^\pi)^{-1}(I - \gamma\widehat{P}^{\pi})\widehat Q^{\pi} - (I - \gamma P^\pi)^{-1}(I - \gamma P^\pi)\widehat Q^{\pi} \\ &= \gamma(I - \gamma P^\pi)^{-1}(P^\pi - \widehat P^{\pi})\widehat Q^{\pi} \\ &= \gamma(I - \gamma P^\pi)^{-1}(P - \widehat P)\Pi\widehat Q^{\pi} \\ &= \gamma(I-\gamma P^{\pi})^{-1}(P-\widehat P)\widehat V^{\pi} \end{aligned} \] 啊哈哈, 终于有会做的题了

Q2. 在第 17 讲中, 我们了解了如何使用模拟引理和标准的集中度论证(concentration arguments)来对 \(\vert{}\vert{}Q^{\pi}-\hat{Q}^{\pi}\vert{}\vert{}_{\infty}\) 进行有界分析, 我们将尝试使用在问题 2.1 中推导出的 "替代模拟引理" 来做同样的事情
以下哪些陈述 (可能是多个) 是正确的

A. 对于任意策略和 \(\delta>0\), 以下情况以至少 \(1-\delta\)​ 的概率成立 \[ \begin{aligned} \vert{}\vert{}(P-\widehat{P})\widehat{V}^{\pi}\vert{}\vert{}_{\infty} &\le \max_{s,a}\vert{}\vert{}P(\cdot\vert{}s,a)-\widehat{P}(\cdot\vert{}s,a)\vert{}\vert{}_{1}\vert{}\vert{}\widehat{V}^{\pi}\vert{}\vert{}_{\infty} \\ &\le\frac{1}{1-\gamma}\sqrt{\frac{4\vert{}\mathcal{S}\vert{}\log(\vert{}\mathcal{S}\vert{}\vert{}\mathcal{A}\vert{}/\delta)}{N}} \end{aligned} \] B. 对于任意策略和 \(\delta>0\), 以下情况以至少 \(1-\delta\) 的概率成立 \[ \vert{}\vert{}(P-\widehat{P})\widehat{V}^{\pi}\vert{}\vert{}_{\infty}\le\frac{1}{1-\gamma}\sqrt{\frac{2~\log(2\vert{}\mathcal{S}\vert{}\vert{}\mathcal{A}\vert{}/\delta)}{N}} \] C. 对于 \(\delta>0\), 以下情况以至少 \(1-\delta\)​ 的概率成立 \[ \vert{}\vert{}(P-\widehat{P})V^{*}\vert{}\vert{}_{\infty}\le\frac{1}{1-\gamma}\sqrt{\frac{2~\log(2\vert{}\mathcal{S}\vert{}\vert{}\mathcal{A}\vert{}/\delta)}{N}} \] D. 对于 \(\delta>0\), 以下情况以至少 \(1-\delta\)​ 的概率成立 \[ \vert{}\vert{}(P-\widehat{P})\widehat{V}^{*}\vert{}\vert{}_{\infty}\le\frac{1}{1-\gamma}\sqrt{\frac{2~\log(2\vert{}\mathcal{S}\vert{}\vert{}\mathcal{A}\vert{}/\delta)}{N}} \]

[!TIP]

使用霍夫丁不等式

如果所引用的不等式被正确应用, 并且在应用它们之前其假设成立, 则该陈述是正确的

对于从 \((s, a)\) 到 \(s^{\prime}\) 的每一次观测转移, 你可以定义一个随机变量 \(X=\mathbb{I}_{s^{\prime}}\cdot V\), 它是 \(s^{\prime}\) 处的指示向量 \(\mathbb{I}_{s^{\prime}}\in\mathbb{R}^{\vert{}\mathcal{S}\vert{}}\) 与向量 \(V\in\mathbb{R}^{\vert{}\mathcal{S}\vert{}}\) 之间的点积, 其期望值为 \(\mathbb{E}[X]=P(\cdot\vert{}s,a)\cdot V\)
当以此方式将霍夫丁不等式应用于从 \((s, a)\) 观测到的所有 \(N\) 次转移时, 它是什么样的？
霍夫丁不等式可以应用于任何向量 \(V\)​ 吗？

对于 A 选项, \(\| ab \|_{\infty} \leq \max \| a \|_1 \| b \|_{\infty}\) 放一放就出来了, 是对的

对于 BCD, 这里不用 \(\| ab \|_{\infty} \leq \max \| a \|_1 \| b \|_{\infty}\) 这样的技巧, 而是直接构造一个随机变量
如果直接用 \(\Pr\left(\Vert{}\hat{q} - \vec{q}\Vert{}_1 \ge \sqrt{d}(1/\sqrt{N} + \epsilon)\right) \le e^{-N\epsilon^2}\) 式子的话, 不可避免会引入状态数, 在这里是 \(\sqrt {\mathcal S}\), 究其原因是 \(\Vert{}\hat{q} - \vec{q}\Vert{}_1 \le \sqrt{d} \Vert{}\hat{q} - \vec{q}\Vert{}_2\) 放缩太糙了, 只在 \(\hat{q} - \vec{q} = \mathbf 1\) 上是紧的

如果我们直接处理 \((\widehat{P} - P) \cdot V\), 对于从 \((s, a)\) 到 \(s^{\prime}\) 的每一次观测转移 \(i\), 我们定义随机变量 \(X_{i}=\mathbb{I}_{s^{\prime}}\cdot V\), 它是 \(s^{\prime}\) 处的指示向量 \(\mathbb{I}_{s^{\prime}}\in\mathbb{R}^{\vert{}\mathcal{S}\vert{}}\) 与向量 \(V\) 的点积, \(X_i\) 就是一个标量, 其范围在 \([-\Vert V\Vert_\infty, \Vert V\Vert_\infty]\)​ 内

于是有 \(\mathbb{E}[X_{i}]=P(\cdot\vert s,a)\cdot V,\; \bar X = \widehat P(\cdot\vert s,a)\cdot V\)
于是根据 \(P(\bar{X} - \mathbb{E}[X] \ge \epsilon) \le \exp \left( {-\dfrac{2N\epsilon^2}{4\| V\|_\infty^2}} \right)\), 令 \(\delta = \exp \left( {-\dfrac{N\epsilon^2}{2\| V\|_\infty^2}} \right)\), 则 \(\epsilon = \sqrt{\dfrac{2\Vert V\Vert_\infty^2 \ln(1/\delta)}{N}}\)

于是有 \(1-\delta\) 的概率, \((P(\cdot\vert{}s,a)-\widehat{P}(\cdot\vert{}s,a))\cdot V\le \sqrt{\dfrac{2\Vert V\Vert_\infty^2 \ln(1/\delta)}{N}} = \dfrac{1}{1-\gamma} \sqrt{\dfrac{2 \log(1/\delta)}{N}}\)

于是你在想, ABCD 难道都是对的？
但这么做有个前提, \(V\in\mathbb{R}^{\vert{}\mathcal{S}\vert{}}\) 是不依赖于观测到的转移 \(\widehat P\) 的, 所有的 \(X_{i}\) 都是独立的, 不然霍夫丁不等式用不了

于是这题选择 AC, 我也不用继续于是于是了

想用 \(L_1\) 拆分解耦法: 通杀所有价值向量(管你带不带帽), 但代价是误差界包含 \(\sqrt{\vert\mathcal{S}\vert}\), 状态一多就爆炸
想用标量期望 Trick 法: 误差界极小, 去掉了 \(\sqrt{\vert\mathcal{S}\vert}\)​, 但条件苛刻, 向量必须是真实的、不依赖经验数据的

Overview

我们要完成神经网络动力学模型 \(f_{\theta}\): \(\hat{\Delta}_{t+1}=f_{\theta}(\mathbf s_{t},\mathbf a_{t})\)
它在给定当前状态和动作的情况下预测状态的变化
给定预测值 \(\hat{\Delta}_{t+1}\), 你可以通过 \(\hat{\mathbf s}_{t+1}=\mathbf s_{t}+\hat{\Delta}_{t+1}\) 生成下一个状态的预测

根据 NN Dynamics for MBDRL with Model-Free Fine-Tuning 文章, 预测下一个状态的变化而不是预测下一个状态的原因如下:
相邻状态过于相似 动作对输出结果产生的影响难以体现
当两个状态之间的时间间隔 \(\Delta t\)​​ 变小时, 学习困难会变得更加明显

我们在标准的监督学习设置中训练 \(f_{\theta}\)​, 对以下目标函数执行梯度下降 \[ \begin{aligned} \mathcal{L}(\theta) &=\sum_{(\mathbf s_{t},\mathbf a_{t},\mathbf s_{t+1})\in\mathcal{D}}\vert{}\vert{}(\mathbf s_{t+1}-\mathbf s_{t})-f_{\theta}(\mathbf s_{t},\mathbf a_{t})\vert{}\vert{}_{2}^{2} \\ &=\sum_{(\mathbf s_{t},\mathbf a_{t},\mathbf s_{t+1})\in\mathcal{D}}\vert{}\vert{}\Delta_{t+1}-\hat{\Delta}_{t+1}\vert{}\vert{}_{2}^{2} \end{aligned} \] 在实践中, 进行对神经网络的目标值进行归一化很有用, 我们预测状态变化的归一化版本 \[ \mathcal{L}(\theta)=\sum_{(\mathbf s_{t},\mathbf a_{t},\mathbf s_{t+1})\in\mathcal{D}}\vert{}\vert{}\text{Normalize}(\mathbf s_{t+1}-\mathbf s_{t})-f_{\theta}(\mathbf s_{t},\mathbf a_{t})\vert{}\vert{}_{2}^{2} \] 由于 \(f_{\theta}\) 是被训练来预测归一化的状态差值, 通过下式生成下一个预测状态 \[ \hat{\mathbf s}_{t+1}=\mathbf s_{t}+\text{Unnormalize}(f_{\theta}(\mathbf s_{t},\mathbf a_{t})) \]

---

动作选择

给定学到的动力学模型, 我们现在希望选择并执行能够最小化已知成本函数(或最大化已知奖励函数)的动作
理想情况下, 你可以通过求解以下优化问题来计算这些动作 \[ \mathbf a_{t}^{z}=\arg\min_{\mathbf a_{t:\infty}}\sum_{t^{\prime}=t}^{\infty}c(\hat{\mathbf s}_{t^{\prime}},\mathbf a_{t^{\prime}}), 其中\; \hat{\mathbf s}_{t^{\prime}+1}=\hat{\mathbf s}_{t^{\prime}}+f_{\theta}(\hat{\mathbf s}_{t^{\prime}},\mathbf a_{t^{\prime}}) \] 求解上式是不切实际的
1). 对无限长度的动作序列进行规划是不可能的
2). 学到的动力学模型是不完美的, 以这种开环方式进行规划会导致误差随时间累积, 规划将变得非常不准确

一种替代方法是求解以下无梯度的优化问题 \[ \mathbf A^{*}=\arg \min_{\{\mathbf A^{(0)},...,\mathbf A^{(K-1)}\}}\sum_{t^{\prime}=t}^{t+H-1}c(\hat{\mathbf s}_{t^{\prime}},\mathbf a_{t^{\prime}}) \\ \text{s.t.} \quad \hat{\mathbf s}_{t^{\prime}+1}=\hat{\mathbf s}_{t^{\prime}}+f_{\theta}(\hat{\mathbf s}_{t^{\prime}},\mathbf a_{t^{\prime}}) \] 其中, 每个 \(\mathbf A^{(k)}=(a_{t}^{(k)},...,a_{t+H-1}^{(k)})\) 都是长度为 \(H\) 的随机动作序列
上式的含义是: 考虑 \(K\) 个长度为 \(H\) 的随机动作序列, 使用学到的动力学模型 \(f_{\theta}\) 预测采取每个动作序列的结果 (即未来状态), 评估与每个候选动作序列相关的成本/奖励, 然后选择最佳的动作序列

这种方法仅规划未来 \(H\) 步, 防止误差累积但不适应 long-horizon 任务

更好的替代方案是交叉熵方法(CEM), 我们会学习一个动作的高斯分布 \(p(\mathbf A)\)
随机挑选可以认为从均匀分布中选择动作
而我们可以设一个高斯分布, 从其中选择 \(N\) 个动作, 并选择 \(M<N\) 个表现最好的精英样本(elites), 使用这 \(M\) 个样本重新拟合(做最大似然拟合)概率分布 \(p(\mathbf A)\)

由于我们的模型并不完美, 并且事情永远不会完全按计划进行, 我们采用了模型预测控制 (MPC) 方法
即在每个时间步, 我们执行随机打靶或 CEM 以选择最佳的 \(H\)​ 步动作序列, 但随后我们仅执行该序列中的第一个动作, 然后在使用更新后的状态信息在下一个时间步重新进行规划

---

On-Policy 数据收集

尽管 MBRL 理论上是 off-policy 的, 这意味着它可以从任何数据中学习
但在实践中, 如果没有 on-policy 数据, 它的表现会很差

---

模型集成 (Ensembles)

训练 \(N\) 个独立初始化的网络 \(\{f_{\theta_{n}}\}_{n=1}^{N}\)
在测试时, 对于每个候选动作序列, 我们将生成 \(N\)​ 个独立的 rollouts, 并对这些轨迹的奖励求平均, 以此来选择最佳的动作序列

Code

Problem 1 要求收集数据并训练 \(f\), 然后自己在 halfcheetah 任务上调整超参
对于 MBA 中的 update 方法编写, 注意 Normalize 就行

delta_scale = ((next_obs-obs)-self.obs_delta_mean)/(self.obs_delta_std+1e-8)
criterion = nn.MSELoss()
obs_acs = (torch.cat([obs,acs], dim=-1)-self.obs_acs_mean)/(self.obs_acs_std+1e-8)
pred = self.dynamics_models[i](obs_acs)
loss = criterion(delta_scale, pred)

update_statistics 方法就是 torch.cat, torch.mean 和 torch.std

编写 run_training_loop 时要注意模型集成的问题

for i in range(mb_agent.ensemble_size):
    batch = replay_buffer.sample(config["train_batch_size"])
    step_losses.append(mb_agent.update(i, batch["observations"], batch["actions"], batch["next_observations"],))
all_losses.append(np.mean(step_losses))

至于调超参, 我已经抛弃传统方法, 让 gpt 5.6 调去了……也许 AI 比较理解 RL……

我在这里放调整前后的图像对比一下(l1_32_lr1e-3 与 l3_256_lr1e-3)

Problem 2 评估使用随机采样候选序列进行优化的 MPC 动作选择效果

要求完成 get_dynamics_predictions 和 evaluate_action_sequences
前者还是之前 Normalize 的套路, Unnormalize 就是 x*std + mean
后者记得把 shape 对好了, 时刻牢记在处理模型集合

def evaluate_action_sequences(self, obs: np.ndarray, action_sequences: np.ndarray):
    """
    Evaluate a batch of action sequences using the ensemble of dynamics models.
    Args:
        obs: starting observation, shape (ob_dim,)
        action_sequences: shape (mpc_num_action_sequences, horizon, ac_dim)
    Returns:
        sum_of_rewards: shape (mpc_num_action_sequences,)
    """
    sum_of_rewards = np.zeros(
        (self.ensemble_size, self.mpc_num_action_sequences), dtype=np.float32
    )
    obs = np.tile(obs, (self.ensemble_size, self.mpc_num_action_sequences, 1))
    # for [seq, ac_dim] in [horizon, seq, ac_dim]
    for acs in action_sequences.transpose(1, 0, 2): 
        next_obs_list = []
        for i in range(self.ensemble_size):
            next_obs_list.append(self.get_dynamics_predictions(i,obs[i],acs))
        next_obs = np.stack(next_obs_list, axis=0)
        rewards = []
        for i in range(self.ensemble_size):
            reward, _ = self.env.get_reward(next_obs[i], acs)
            rewards.append(reward)
        rewards = np.stack(rewards, axis=0)
        sum_of_rewards += rewards
        obs = next_obs
    return sum_of_rewards.mean(axis=0)

最终 MPC 的 Average eval return 在 -29.3250 左右

Problem 3-4 就是开训, 调超参, 这部分都让 AI 干

AI 训练比较聪明的一点是会主动优化程序, 例如它看到了每个模型预测都把数据在 NumPy 与 GPU 之间来回转换, 就考虑优化, 不过没有用, 它又给撤回了

Problem 3 如下

Obstacles 环境中的动力学模型或 MPC 规划对数据分布和随机采样较为敏感, 寄寄了, 其他都不错啊

Problem 4 就是调超参的 trade-off
经验是在 reacher 任务上用三个模型集成就足够了, num_action_sequences=1000 就足够了以及 horizon = 10 是最好的, 不过这些数据都是 problem specific 的

Problem 5 是实现 CEM 方法

elif self.mpc_strategy == "cem":
    elite_mean, elite_std = None, None
    for i in range(self.cem_num_iters):
        if i!=0: 
            action_sequences = np.random.normal(elite_mean, elite_std, size=(self.mpc_num_action_sequences, self.mpc_horizon, self.ac_dim))
            action_sequences = np.clip(action_sequences, self.env.action_space.low, self.env.action_space.high)
        rewards = self.evaluate_action_sequences(obs, action_sequences)
        elite_indices = np.argsort(rewards)[-self.cem_num_elites:]
        elite_actions = action_sequences[elite_indices] 
        # shape [cem_num_elites, mpc_horizon, ac_dim]
        new_mean = elite_actions.mean(axis=0)
        new_std = elite_actions.std(axis=0)
        if i==0: elite_mean, elite_std = new_mean, new_std
        else:
            elite_mean = self.cem_alpha*new_mean + (1-self.cem_alpha)*elite_mean
            elite_std = self.cem_alpha*new_std + (1-self.cem_alpha)*elite_std
    return elite_mean[0]

这里的细节是区分 i=0 与 i ≠ 0, 使用 numpy 的 argsort 以及使用 self.cem_alpha 滑动更新 elite

CEM 训练是真慢啊,
每一个真实 step 对应 4 次 CEM 迭代 × 15 步规划长度 × 3 个 dynamics models × 1000 条候选动作序列
规划 15 步只取一步, 我要是有个 actor 神经网络一下子就走出来了
不过 model-based RL 中的 model 训练飞快, 这可能也是一种 trade-off

5 次 iteration 就已经把之前的 HalfCheetah 的 400 pts 打爆了
avg return 变化为 \(241 \to 577 \to 797 \to 888 \to 943\), 看来动力学是完全拟合上了
另一方面来说, 5 次 iteration 花了我 2.5h, 这是肯定不能实时用的

Problem 6 是实现 MBPO 的 rollout, 额, 动态控制部分几乎没有, 只是单纯 short rollout 罢了
我们保留 Actor 网络了！真实的数据和 model 的虚拟数据一齐训 SAC, 让 SAC 选 action
我们比较 model-free SAC, Dyna-style(rollout_length = 1) 与 MBPO(rollout_length = 10) 的区别

在 run_hw4.py 中编写 collect_mbpo_rollout 时还是注意模型集成的问题, 最后的 next_ob 求了平均

ac = sac_agent.get_action(ob)
ac_batch, ob_batch = ac[None], ob[None]
next_ob = []
for i in range(mb_agent.ensemble_size):
    next_ob.append(mb_agent.get_dynamics_predictions(i,ob_batch,ac_batch))
next_ob = np.mean(next_ob, axis=0)[0]
rew, _ = env.get_reward(next_ob, ac)

最后的实验结果你肯定能猜到, MBPO > Dyna-style > model-free SAC, 多步预测真是力大砖飞啊

Assignment 5 Exploration 与 Offline RL

Analysis

回忆一下 Soft Actor-Critic, 它大概是 DDPG + doubleQ + noise + MaxEntropy
我们优化下面的奖励, \(b(\mathbf s,\mathbf a)=-\log\pi(\mathbf a\mid \mathbf s)\) 负责为策略施加最大熵正则化, 在下文直接加入奖励了 \[ \begin{aligned} \mathbb{E}_{\mathbf s,\mathbf a\sim p_\pi}\bigl[r(\mathbf s,\mathbf a)+\lambda b(\mathbf s,\mathbf a)\bigr] &=\frac{1}{H}J(\pi)-\lambda\, \mathbb{E}_{\mathbf s\sim p_\pi}\mathbb{E}_{\pi(\mathbf a\mid \mathbf s)}\log\pi(\mathbf a\mid \mathbf s)\\ &=\frac{1}{H}J(\pi)+\lambda\, \mathbb{E}_{\mathbf s\sim p_\pi}\mathcal{H}\!\left[\pi(\mathbf a\mid \mathbf s)\right] \end{aligned} \]

---

现在我们希望从离线数据 \(\mathcal{D}\) 中学习一个 \(Q\) 函数和策略 \(\pi\), 同时满足约束 \(D(\pi,\pi_\beta)\leq\varepsilon\)
采用如下更新 \[ Q(\mathbf s,\mathbf a)\leftarrow r(\mathbf s,\mathbf a)+\mathbb{E}_{\mathbf a'\sim\pi}\left[Q(\mathbf s',\mathbf a')\right] \\ \text{其中}\; \pi=\operatorname*{arg\,max\;}_{\pi}\mathbb{E}_{\mathbf s,\mathbf a\sim p_\pi}[Q(\mathbf s,\mathbf a)]\quad \text{满足}\; D(\pi,\pi_\beta)\leq\varepsilon \] 像 Lec 16 中的那样, 把约束通过拉格朗日方式隐式施加在奖励中, \(\bar r(\mathbf s,\mathbf a)=r(\mathbf s,\mathbf a)+\lambda b(\mathbf s,\mathbf a)\), 即 \[ Q(\mathbf s,\mathbf a)\leftarrow \bar r(\mathbf s,\mathbf a)+\mathbb{E}_{\mathbf a'\sim\pi}\left[Q(\mathbf s',\mathbf a')\right] \\ \text{其中}\; \pi=\operatorname*{arg\,max\;}_{\pi}\mathbb{E}_{\mathbf s,\mathbf a\sim p_\pi}[Q(\mathbf s,\mathbf a)] \] 假设已经适当地选择了 \(\lambda>0\), 并且假设能够获得分布 \(\pi(\mathbf a\mid \mathbf s)\) 和 \(\pi_\beta(\mathbf a\mid \mathbf s)\)

Q1. 假设我们希望在 KL 散度约束下学习策略 \(\pi\)​, 即 \[ D(\pi,\pi_\beta)= \mathbb{E}_{\mathbf s\sim p_\pi}D_{\mathrm{KL}}\left[\pi(\mathbf a\mid \mathbf s)\,\|\,\pi_\beta(\mathbf a\mid \mathbf s)\right] \] 如何通过向奖励 \(\bar r(\mathbf s,\mathbf a)=r(\mathbf s,\mathbf a)+\lambda b(\mathbf s,\mathbf a)\) 中加入 \(\lambda b(\mathbf s,\mathbf a)\) 来施加约束? 将答案写成 \(b(\mathbf s, \mathbf a)\)​ 的表达式

Sol.
我猜是数据凑凑
\(D_{\text{KL}}(\pi \| \pi_\beta) = \mathbb E_{\pi} [\log \pi(\mathbf a|\mathbf s) - \log \pi_\beta(\mathbf a|\mathbf s)]\), 故 \(D(\pi,\pi_\beta) = \mathbb E_{\mathbf s\sim p_\pi} \mathbb E_{\mathbf a\sim\pi(\cdot\mid \mathbf s)} \left[ \log\dfrac{\pi(\mathbf a\mid \mathbf s)}{\pi_\beta(\mathbf a\mid \mathbf s)} \right]\)
一个小细节是这一堆期望套不套, 我们设 \(b(\mathbf s, \mathbf a) = - \log\dfrac{\pi(\mathbf a\mid \mathbf s)}{\pi_\beta(\mathbf a\mid \mathbf s)}\)
要对 \(\mathbb{E}_{\mathbf s,\mathbf a\sim p_\pi}[Q(\mathbf s,\mathbf a)]\) 求 arg max, 这样设 \(b(\mathbf s, \mathbf a)\) 后套期望后正好是优化 \(\mathbb E_{\mathbf s,\mathbf a\sim p_\pi}[Q(\mathbf s,\mathbf a)] -\lambda D(\pi,\pi_\beta)\)

Q2. \(f\)-散度是 KL 散度的一种推广, 对于分布 \(P\) 和 \(Q\)​, 它可以定义为 \[ D_f[P\|Q]=\int Q(x)\,f\!\left(\frac{P(x)}{Q(x)}\right)\,\mathrm{d}x \] 其中 \(f\) 是一个凸函数, 并且在 1 处取值为零, 我们可以将一个 \(f\)-散度策略约束写成 \[ D(\pi,\pi_\beta)=\mathbb{E}_{\mathbf s\sim p_\pi}D_f \left[\pi(\mathbf a\mid \mathbf s)\,\|\,\pi_\beta(\mathbf a\mid \mathbf s)\right] \] 也即 \[ D(\pi,\pi_\beta)=\mathbb{E}_{\mathbf s\sim p_\pi}\mathbb{E}_{\pi_\beta(\mathbf a\mid \mathbf s)} f\!\left(\frac{\pi(\mathbf a\mid \mathbf s)}{\pi_\beta(\mathbf a\mid \mathbf s)}\right) \] 通过 \(f\)-散度约束, 我们可以指定许多其他形式的约束, 以限制 \(\pi\) 与 \(\pi_\beta\) 之间的散度
例如, 当取 \(f(x)=\dfrac{1}{2}|x-1|\) 时, \(f\)-散度等价于总变差距离(Total Variation Distance, TVD)
当取 \(f(x) = -(x+1)\log\!\left(\dfrac{x+1}{2}\right) +x\log x\) 时, \(f\)-散度等价于 Jensen–Shannon 散度
当取 \(f(x) = x \log x\) 时, 我们就恢复了标准的 KL 散度
如何扩展在 Q1. 中的答案, 使其能够处理任意的 \(f\)-散度? 答案应当使用 \(f\) 给出更加一般化的 \(b(\mathbf s, \mathbf a)\)​ 表达式

Sol.
寄寄, \(\pi_\beta\) 不是 \(\pi\), 能不能做类似重要性采样的东西把分布换掉？
我们能不能说
\[ D_f[P\|Q]=\displaystyle\int Q(x)\,f\!\left(\dfrac{P(x)}{Q(x)}\right)\,\mathrm{d}x = \displaystyle\int P(x) \dfrac{Q(x)}{P(x)}\,f\!\left(\dfrac{P(x)}{Q(x)}\right)\,\mathrm{d}x = \mathbb{E}_{P(x)} \dfrac{Q(x)}{P(x)} f\!\left(\frac{P(x)}{Q(x)}\right) \] 于是可以说 \[ D(\pi,\pi_\beta) = \mathbb{E}_{\mathbf s\sim p_\pi}\mathbb{E}_{\pi(\mathbf a\mid \mathbf s)} \dfrac{\pi_\beta(\mathbf a\mid \mathbf s)}{\pi(\mathbf a\mid \mathbf s)} f\!\left(\dfrac{\pi(\mathbf a\mid \mathbf s)}{\pi_\beta(\mathbf a\mid \mathbf s)}\right) \] 于是 \(b(\mathbf s, \mathbf a) = -\dfrac{\pi_\beta(\mathbf a\mid \mathbf s)}{\pi(\mathbf a\mid \mathbf s)} f\!\left(\dfrac{\pi(\mathbf a\mid \mathbf s)}{\pi_\beta(\mathbf a\mid \mathbf s)}\right)\)

Q3. 假设 MDP 的时域长度为 \(H\), 我们继续约束策略 \(\pi\) 与 \(\pi_\beta\) 所产生的状态轨迹分布之间的散度
对于轨迹 \(\tau=(s_1,s_2,\ldots,s_H)\), 状态轨迹分布之间的 KL 散度可以表示为 \[ D(\pi,\pi_\beta)= D_{\mathrm{KL}}\left[p_\pi(\tau)\,\|\,p_{\pi_\beta}(\tau)\right] \] 应当使用怎样的 \(b(\mathbf s, \mathbf a)\) 表达式来施加这一约束？可以假设能够获得环境动力学 \(p(\mathbf s'|\mathbf s, \mathbf a)\)

[!TIP]

对动作进行边缘化, 得到一个依赖于 \(\mathbf s'\) 的加成 \(b(\mathbf s,\mathbf a,\mathbf s')\)
怎样才能将其转换为能够与 \(r(\mathbf s,\mathbf a)\) 一起使用的加成 \(b(\mathbf s,\mathbf a)\)?

Sol.
啊, 从单个 \((\mathbf s, \mathbf a)\) 变成 \(\tau\) 了, 需要写出 transition
考虑策略 \(\pi\) 诱导的状态转移概率, 下面假设动作空间连续, 离散同理 \[ p_\pi(\mathbf s'| \mathbf s)=\int_{\mathcal A}\pi(\mathbf a| \mathbf s)p(\mathbf s'| \mathbf s,\mathbf a)\,\mathrm d\mathbf a \] 故 \(p_\pi(\tau) = g(\mathbf s_1) \prod_{t=1}^{H-1} p_\pi(\mathbf s_{t+1}\mid \mathbf s_t)\), 这里的 \(g(\mathbf s_1)\) 代表初始状态分布, 其实无所谓, 肯定能消掉, 于是 \[ \begin{aligned} D(\pi, \pi_\beta) &= D_{\text{KL}} [p_\pi(\tau) \| p_{\pi_\beta}(\tau)] \\ &= \mathbb E_{\tau \sim p_\pi} [\log \frac{p_\pi(\tau)}{p_{\pi_\beta}(\tau)}] \\ &= \mathbb E_{\tau \sim p_\pi} [\log \frac{g(\mathbf s_1) \prod_{t=1}^{H-1} p_\pi(\mathbf s_{t+1}\mid \mathbf s_t)}{g(\mathbf s_1) \prod_{t=1}^{H-1} p_{\pi_\beta}(\mathbf s_{t+1}\mid \mathbf s_t)}] \\ &= \mathbb E_{\tau \sim p_\pi} [\log \frac{\prod_{t=1}^{H-1} p_\pi(\mathbf s_{t+1}\mid \mathbf s_t)}{\prod_{t=1}^{H-1} p_{\pi_\beta}(\mathbf s_{t+1}\mid \mathbf s_t)}] \end{aligned} \] 故 \(b(\mathbf s, \mathbf a, \mathbf s') = - \log \dfrac{ p_\pi(\mathbf s'\mid \mathbf s)}{ p_{\pi_\beta}(\mathbf s'\mid \mathbf s)}\), 于是 \(b(\mathbf s, \mathbf a) = \mathbb E_{\mathbf s' \sim p(\cdot|\mathbf s, \mathbf a)} [-\log \dfrac{ p_\pi(\mathbf s'\mid \mathbf s)}{ p_{\pi_\beta}(\mathbf s'\mid \mathbf s)}]\)
这其实告诉我们抽象的 \(\tau\)​ 想不出来还是往细了想更好

Review

首先实现 RND 的探索方法, 并使用该探索过程收集数据
然后把 CQL, AWAC, IQL 轮着来一遍

随机网络蒸馏(Random Network Distillation, RND)算法
常见的探索方法是访问某个量的预测误差较大的状态, 这个量可以是 TD 误差, 甚至可以是一个随机函数
形式化地, 令 \(f_{\theta^*}(\mathbf s')\) 表示一个随机选择的由神经网络表示的向量值函数
RND 会训练另一个神经网络 \(\hat f_\phi(\mathbf s')\), 使其在缓冲区数据点的分布上匹配 \(f_{\theta^*}(\mathbf s')\) 的预测 \[ \phi^*=\operatorname*{arg\,min}_{\phi}\mathbb E_{\mathbf s,\mathbf a,\mathbf s'\sim\mathcal D} \left[\underbrace{\left\|\hat f_\phi(\mathbf s')-f_{\theta^*}(\mathbf s')\right\|}_{\mathcal E_\phi(\mathbf s')}\right] \] 如果某个状态转移 \((\mathbf s,\mathbf a,\mathbf s')\) 位于数据缓冲区的数据分布之中, 那么其预测误差 \(\mathcal E_\phi(\mathbf s')\) 应该较小

为了把这一预测误差用作探索的奖励加成, RND 会训练两个 Critic:

• 利用评论家(exploitation critic) \(Q_R(\mathbf s,\mathbf a)\), 用于估计策略在真实奖励函数下的回报
• 探索评论家(exploration critic) \(Q_E(\mathbf s,\mathbf a)\), 用于估计策略在奖励加成下的回报

在实践中, 我们会先对误差进行归一化, 再将其传入探索评论家, 这是因为预测误差在不同状态下的数值大小可能相差很大, 从而导致较差的优化动态

保守 Q 学习(Conservative Q-learning, CQL)算法
额外降低 Q 值来学习一个保守的、作为下界的 Q 函数, 在训练 Q 函数时, CQL 会加入一个正则项, 其会最小化 Q 值的软最大值以及最大化数据集中实际出现的状态—动作对的 Q 值, 完整的 CQL 目标为 \[ \alpha\frac{1}{N}\sum_{i=1}^{N} \left(\log\left(\sum_{\mathbf a}\exp(Q(\mathbf s_i,\mathbf a))\right)-Q(\mathbf s_i,\mathbf a_i)\right) \] 优势加权演员—评论家(Advantage-Weighted Actor-Critic, AWAC)算法
AWAC 使用下面的 Actor 更新来改进策略训练 \[ \theta\leftarrow\operatorname*{arg\,max}_{\theta}\; \mathbb E_{\mathbf s,\mathbf a\sim\mathcal B} \left[\log\pi_\theta(\mathbf a\mid \mathbf s)\exp\left(\frac{1}{\lambda}A^{\pi_k}(\mathbf s,\mathbf a)\right)\right] \] 这一更新类似于加权行为克隆。当 Q 函数退化时, 该方法就会化为加权行为克隆
在上述更新中, 智能体会用较大的权重拟合高优势动作, 而几乎忽略低优势动作
Q 函数通过时序差分损失(TD Loss)学习, 其目标如下 \[ \mathbb E_{\mathcal D} \left[\left(Q(\mathbf s,\mathbf a)-r(\mathbf s,\mathbf a)+\gamma\mathbb E_{\mathbf a'\sim\pi}\left[Q_{\phi_{k-1}}(\mathbf s',\mathbf a')\right]\right)^2\right] \] 下一步动作 \(\mathbf a'\) 是从学得的策略 \(\pi\) 中采样的
这意味着, 如果 \(\pi\) 能够很好地拟合经过加权的行为策略, 就不会采样到 OOD 动作

隐式 Q 学习(Implicit Q-learning, IQL)算法
它通过学习 Q 值的期望分位数(expectile)来将 Critic 的学习与 Actor 学习解耦
期望分位数是一种与分位数类似的统计量, 可以视为某个分布所能达到的最大值的一种软版本

对于随机变量 \(X\), 其期望分位数 \(m_\tau(X)\) 可以通过以下优化问题得到 \[ \operatorname*{arg\,min}_{m_\tau}\;\mathbb E_{x\sim X}\left[L_2^\tau(x-m_\tau)\right], \\ 其中\; L_2^\tau(\mu)=\left|\tau-\mathbf 1\{\mu\leq 0\}\right|\mu^2 \] 当样本 \(X\) 高于预测值 \(m\) 时, 权重为 \(\tau\), 当样本 \(X\) 低于预测值 \(m\) 时, 权重为 \(1-\tau\)
这一备份会对数据集中已经采取过的动作保持乐观

为了避免对状态转移也持乐观估计, 我们需要学习一个独立的价值函数 \(V(\mathbf s)\), ,由它执行这种乐观估计
随后, 使用普通的均方误差损失回归, \(Q(\mathbf s,\mathbf a)\leftarrow r+\gamma V(\mathbf s')\)​, 综合起来, 两个目标函数为 \[ L_V(\phi)=\mathbb E_{(\mathbf s,\mathbf a)\sim\mathcal D}\left[L_2^\tau\left(Q_\theta(\mathbf s,\mathbf a)-V_\phi(\mathbf s)\right)\right], \\ L_Q(\theta)=\mathbb E_{(\mathbf s,\mathbf a,\mathbf s')\sim\mathcal D}\left[\left(r(\mathbf s,\mathbf a)+\gamma V_\phi(\mathbf s')-Q_\theta(\mathbf s,\mathbf a)\right)^2\right] \] Critic 的学习过程具有两个很好的性质
首先, 它从不查询 OOD 动作, 完全避免了对 OOD 动作的过高估计问题
然后, Critic 的学习可以在不更新 Actor 的情况下完成, 如果你愿意, 可以先训练 Critic, 最后再单独训练 Actor

Code

总的基础还是 hw3 的 dqn_agent.py

在 Random exploration 下, 可怜的小点根本跑不到 target

先写 rnd_agent.py
rnd_net 和 rnd_target_net 都给你了, 核心操作就四行

redictions = self.rnd_net(observations) #[B, rnd_dim]
targets = self.rnd_target_net(observations) #[B, rnd_dim]
rnd_error = torch.norm(predictions - targets, dim=-1) #[B]
rnd_loss = nn.MSELoss()(prediction, target) #[1]

然后探索稍微变好了一点, 10k step 是这样的

CQL 只用实现一个 loss, 我们改掉 dqn_agent.py 让它输出 qa_value 和 q_value 的 variable, 然后在这里后处理一下就行

def compute_critic_loss(...) -> Tuple[torch.Tensor, dict, dict]:
        loss, metrics, variables = super().compute_critic_loss(obs, action, reward, next_obs, done)
        qa_values = variables["qa_values"]
        q_values = variables["q_values"]
        cql_loss = (self.cql_temperature*torch.logsumexp(qa_values/self.cql_temperature, dim=1) - q_values).mean()
        loss = loss + self.cql_alpha * cql_loss
        metrics["cql_loss"] = cql_loss.item()
        metrics["critic_loss"] = loss.item()
        return loss, metrics, variables

这里使用了 cql_temperature 来控制 logsumexp, 有 \(T\log\sum_{\mathbf a} \exp(Q_{\mathbf a}/T)\)
因为 \(\dfrac{\partial}{\partial Q_{\mathbf a}} \left[ T\log\sum_j e^{Q_j/T} \right] = \operatorname{softmax}(Q/T)_{\mathbf a}\), 所以 T 较小时梯度集中在最大 Q 动作, 较大时梯度更均匀

metrics 中保存 .item() 得到的 Python 数值, 脱离计算图, 只能用于记录

然后看一下 CQL 与 DQN 在 pointmass_easy 下的 100k eval return, 这不是没区别吗？(｀皿´＃)

在 pointmass_medium 下确实是 CQL 更好, 不过都是一坨, Pointmass 使用稀疏奖励, 普通步 -1, 到达终点 0
现在都是 -60 ~ -40 之间

然后先写 AWAC 再写 IQL, 本质上 IQL 只比 AWAC 多训了一个 \(V(\mathbf s')\) 来代替 \(\mathbb E_{\mathbf a' \sim \pi_{new}}[Q(\mathbf s', \mathbf a')]\), 其中 \(V\) 用了 expectile loss

我们深入一点 DQN / AWAC / IQL 的细微区别 \[ y_{\mathrm{DQN}}=r+\gamma(1-d)\max_{a'}Q_{\text{target}}(\mathbf s',\mathbf a') \\ y_{\mathrm{AWAC}}=r+\gamma(1-d)\mathbb E_{a'\sim\pi(\cdot|s')}[Q_{\text{target}}(\mathbf s',\mathbf a')] \\ y_{\mathrm{IQL}}=r+\gamma(1-d)V_{\text{target}}(\mathbf s') \] 于是 AWAC 需要乘以 prob 来算 advantage

def compute_advantage(self, observations: torch.Tensor, actions: torch.Tensor, action_dist: Optional[torch.distributions.Categorical] = None):
    qa_values = self.critic(observations)
    q_values = torch.gather(qa_values, dim=1, index=actions.unsqueeze(1)).squeeze(1)
    action_probs = action_dist.probs # [B, A]
    values = torch.sum(action_probs*qa_values, dim=1)
    advantages = q_values - values
    return advantages

在 AWAC update actor 时需要 weighted 加权, 在 Lec 16 中有 \[ \mathbf{\theta}_{\mathrm{new}}= \arg\max_{\mathbf{\theta}}\mathbb{E}_{(\mathbf{s},\mathbf{a})\sim\mathcal D} \left[\underbrace{\frac{1}{Z(\mathbf{s})}\exp\left(\frac{A^{\pi_{\mathrm{old}}}(\mathbf{s},\mathbf{a})}{\lambda}\right)}_{w(\mathbf{s},\mathbf{a})} \log\pi_{\mathbf{\theta}}(\mathbf{a}|\mathbf{s}) \right] \] 真实代码实现把归一化的 \(\dfrac{1}{Z(\mathbf s)}\) 毙掉了, 加入了 temperature

def update_actor(self, observations: torch.Tensor, actions: torch.Tensor):
    action_dist = self.actor(observations)
    with torch.no_grad():
        advantages = self.compute_advantage(observations, actions, action_dist)
        weights = torch.exp(advantages / self.temperature) # exp(A/λ)
    log_probs = action_dist.log_prob(actions.long())
    loss = -(weights * log_probs).mean()
    self.actor_optimizer.zero_grad()
    loss.backward()
    self.actor_optimizer.step()
    return loss.item()

IQL 真的十分类似, 我就单列个 expectile_loss 的代码吧

def iql_expectile_loss(expectile: float, vs: torch.Tensor, target_qs: torch.Tensor
) -> torch.Tensor:
    diff = target_qs-vs
    weight = torch.where(diff>0, expectile, 1.0-expectile)
    return (weight*diff.pow(2)).mean()

由于时间原因, 就不调超参了, 直接用 RND 收集 50k pointmass_hard 数据然后比较一下 DQN/CQL/AWAC/IQL 吧

感觉至少 20k 的数据还是必要的, 不然数据集里面根本没几个探索到终点的, offline 也没得学, 但是看效果 DQN>CQL>AWAC=IQL, 估计是我代码的问题, 还是说一定要 online 微调, 唉唉, 也许上面列出的代码都是错的

接下来完成 offline to online, 还是在 CQL 上 tuning 吧, 用 100k 离线数据与 100k 在线数据
按照代码难度, run_hw5_finetune.py 是最大的, 原因是代码内部除了 TODO 外也少了一些组件, 例如离线的 RND 数据收集后我还要手动 replay_buffer.insert(...), update info 要注意 use reward
一个最后才更改的小问题是评估会改变正在采样的环境, 评估开始时会 env.reset(), 但是返回训练脚本时，observation 不变, 环境内部却停在评估结束时的状态。gpt 6 sol high 的改法是创建一个 eval_env, 我不知道有没有用, 听起来挺有道理, 可能这也是上面 AWAC 和 IQL 代码跑不起来的原因？应该是个小问题, 因为 10k step 才 eval 一次, 而错配的 state 100 step 内迟早也要 reset 的

代码可以弄一些 epsilon 退火或者 alpha 退火的花活, 但感觉没啥用, 重要是 alpha = 0.1 量级而不是 alpha = 1/5/10, 不然太保守了训不出来

finetune 了一下, 发现在线数据在 hard 环境非常有用, 100k 在线完全没有收敛, 作业的要求 reward 为 -20 代表最多 20 次动作走到目标点, 这就要求几乎不能有多余动作了, 试一下 100k 离线与 400k 在线, 即使这样, 我的 reward 也只会收敛在 -35 左右

我在网络上查了一些别人的实现, 也问了 AI, 但看来就是这样了, 这里倍感抱歉