CS285 课程笔记：探索与利用

前面学习的model-free 和 model-based 方法都是假设**环境可实时交互，且奖励函数 r(s,a) **已知、确定的，只是探讨如何用不同的数学工具去求解这个奖励最大化问题。

而当打破了这些理想的假设，引入了符合真实物理世界限制的特殊设定：

• **Exploration（探索）**解决“如果环境奖励极其稀疏，机器人碰不到奖励，该怎么主动搜集数据”的问题。
• Offline RL（离线强化学习）： 解决“如果在真实世界中完全不能和环境交互，只能在一堆历史静态数据集上进行学习”的离线数据范式问题。
• Inverse RL（逆向强化学习）： 解决“如果在真实世界中，人类根本无法给机器人写出一个合理的奖励函数 R(s,a)（比如倒茶、叠衣服），如何通过专家的演示反推出奖励函数”的问题

Exploration and exploitation

探索问题有两种潜在定义，一个是智能体如何找到持续时间较长的一系列复杂行为的高回报策略，而这些行为单独来看是没有任何奖励的；一个是智能体如何决定是否尝试新的行为来发现带来高回报的行为或者采取目前认为最优的行为。我们会发现这两个其实是同一个问题，所谓 exploitation 就是执行当前认知中带来最高回报的行为，而exploration 就是尝试之前没做过的并期望获得比认知中更高的回报。

regret

$\text{Reg}(T) = T \mathbb{E}[r(a^*)] - \sum_{t=1}^T r(a_t)$

遗憾值定义了智能体在 $T$ 个时间步内，理论上的完美总收益与实际总收益的差值。在设计探索算法时，我们的目标就是让 Regret 随着时间 $T$ 的增长越慢越好，最好是次线性的，比如对数增长 $\mathcal{O}(\log T)$，这样智能体很快就能找到最优动作。

optimistic exploration

如果只是单纯地 Exploitation $\text{pick a} = \text{arg max} \hat{\mu}_a$，那么我们很容易陷入局部最优。于是积极探索策略在后面加上了一个**$C \sigma_a$（某种不确定性的估计）** $a = \text{arg max} \hat{\mu}_a + C \sigma_a$，这样尽管某个动作的得分很低，一开始也会因为不确定性大而乐观地去选它，直到确信这个动作真的不行。

这也就是经典算法 UCB 的来源，UCB的公式 $a = \arg\max \left( \hat{\mu}_a + \sqrt{\frac{2 \ln T}{N(a)}} \right)$ 中将那个方差写为总时间步与该动作被选过次数的比值， 平衡了探索与利用。如果某个动作没怎么被选过，$N(a)$ 极小，这部分就会变得很大，让智能体去探索它。随着时间 $T$ 的增加，分子会以对数速度极其缓慢地增长，这样即使是一个早就被抛弃的动作也可能会被再次选择。理论上可以证明使用 UCB 公式去探索，regret 最多只会随着时间呈对数级（$\log T$）增长，

posterior sampling

有时也叫汤普森采样，意思是对模型参数维持一个 belief，对belief采样并假设这是正确的模型参数，在该模型下采取最优行动，然后根据观察的结果更新模型分布。这个方法在理论上很难分析，但在经验上非常有效。

information gain

给定行为 a 根据观测值 y 来估计对某个感兴趣的量 z 的信息增益 $\text{IG}(z, y) = \mathbb{E}_y[\mathcal{H}(\hat{p}(z)) - \mathcal{H}(\hat{p}(z)|y)]$，因为观察结果 $y$ 是由动作 $a$ 决定的，所以公式最终写为 $\text{IG}(z, y|a)$，这个 z 可以是已知状态密度或动力学模型参数等，体现对世界、环境理解的改变程度。

基于信息增益有 Russo & Van Roy 提出的 Information-Directed Sampling (IDS, 信息导向采样)。通过 $\text{choose } a \text{ according to } \arg\min_a \frac{\Delta(a)^2}{g(a)}$ 权衡探索与利用，$g(a) = \text{IG}(\theta_a, r_a|a)$ ，$\Delta(a) = \mathbb{E}[r(a^*) - r(a)]$ 是单步 regret 值的期望。这样 IDS 算法在每次选择动作时，不是单纯找 regret 小的，也不是单纯找未知的，而是倾向于选择那些代价 $\Delta(a)$ 不算太大，但能带来巨大的信息增益 $g(a)$ 的动作。

• 大部分探索策略包括以上三种都需要估计不确定性，即使是简单的方法如UCB（估计状态访问频率）。通常假设获取信息具有某种价值，因为由此产生的算法可以证明最优性，在后面更复杂的领域中则无法证明这一点。我们可以以这些策略为基础推导出更实用的算法并将他们应用于更复杂的MDP，同时那些保证也不再成立。

Optimistic Exploration in deep RL

在 RL 中使用积极探索策略可以直接简单地对奖励函数加上一个基于计数的 exploration bonus，比如计数值的平方分之一，不过这个bonus的权重可能需要不断调整。基于计数的探索策略面临的一个问题是，在大型强化学习问题中我们几乎不会看见两次完全相同的 state，这就使得计数失去了意义。即使我们永远不会访问两个完全相同的状态，但这些状态总有很多相似之处。所以我们不妨拟合一个概率密度模型 $p_\theta(s)$，它不会告诉我们访问某个状态的真实次数，而是让这个模型拟合到数据集中目前为止看到的所有状态，告诉我们访问该状态的概率密度。然后把新状态放入数据集训练得到一个更新后的新模型 $p_{\theta'}(s)$，对比旧模型和新模型对这个画面给出的概率，倒推出一个伪计数 $\hat{N}(\mathbf{s})$。

$$p_\theta(\mathbf{s}_i) = \frac{\hat{N}(\mathbf{s}_i)}{\hat{n}}$$ $$p_{\theta'}(\mathbf{s}_i) = \frac{\hat{N}(\mathbf{s}_i) + 1}{\hat{n} + 1}$$

在这个方程组里，等号左边的概率 $p_\theta$ 和 $p_{\theta'}$ 是用神经网络算出来的已知数，等号右边的 $\hat{N}$ 和 $\hat{n}$ 是的未知数，可解得 $\hat{N}(\mathbf{s}_i) = \hat{n} p_\theta(\mathbf{s}_i)$，其中 $\hat{n} = \frac{1 - p_{\theta'}(\mathbf{s}_i)}{p_{\theta'}(\mathbf{s}_i) - p_\theta(\mathbf{s}_i)} p_\theta(\mathbf{s}_i)$。

关于密度模型的选择，可以使用任何想要的密度模型，只要它能生成良好的概率分数而无需关心它是否能生成高质量的样本。

一些新颖的探索策略

• 使用哈希值进行计数：这里仍然使用常规计数而不是伪计数，但采用不同的表示方法。它会获取状态，计算压缩后状态的哈希，所以是一种有损哈希，使得不同的状态有不同的哈希值而非常相似的状态有可能映射到相同的哈希值。

• 通过分类器来获得密度分数从而避免密度建模：它明确将新状态与过去状态进行比较，直觉上我们希望如果分类器能够轻松区分当前状态是新状态那么给出低密度，如果和过去状态看起来无法区分，则给出高密度。那么密度公式就可以写为 $p_\theta(\mathbf{s}) = \frac{1 - D_{\mathbf{s}}(\mathbf{s})}{D_{\mathbf{s}}(\mathbf{s})}$。 $D_{\mathbf{s}}(\mathbf{s})$ 是一个Classifier输出的概率值，在数学上严格等于 $\frac{P_{\text{正样本}}(x)}{P_{\text{正样本}}(x) + P_{\text{负样本}}(x)}$（通常经过 Sigmoid 函数，介于 0 到 1 之间），完美符合我们分类器越容易识别 = 状态越新颖 = 密度越低的直觉。

• 通过误差启发式估计次数：它用神经网络的预测误差来代替计数，构建两个神经网络一个参数固定的目标网络（ $f^*$），一个用 Buffer $\mathcal{D}$ 中 $(s_i, a_i)$ 拟合的预测网络（ $\hat{f}_\theta$）。计算它们的均方误差（MSE）$\text{Loss} = \mathcal{E}(\mathbf{s}, \mathbf{a}) = ||\hat{f}_\theta(\mathbf{s}, \mathbf{a}) - f^*(\mathbf{s}, \mathbf{a})||^2$，然后通过梯度下降，更新预测网络 $\hat{f}_\theta$ 的参数，让它尽量逼近目标网络。把这个误差 $\mathcal{E}$ 代替计数作为探索奖励（Bonus），误差越大，代表 $(s_i, a_i)$ 对预测网络越未知，奖励越高。目标网络 $f^*$ 的常见选择是预测下一个状态 $s'$的前向动力学模型，或使用一个随机初始化的固定网络即 RND（随机网络蒸馏） 算法。在这里不需要 $f^*$ 有多么重要的意义，只需要他能够作为目标，并在动作空间中随状态变化即可，所以使用一个随机网络效果也相当不错。

Posterior sampling in deep RL

从Q函数的分布中采样一个Q function，然后根据这个Q函数行动整个回合，接着更新Q函数的分布，重复这一过程。为了获得函数的分布，我们使用一个数据集有放回地随机采样多份，每份训练一个模型，近似组成函数的分布。 但是训练多个完整网络就太贵了，我们可以前面大部分参数共享只有最后的head不同。这种探索策略的好处是可以在整个回合中保持一种探索的一致性，而不会像 epsilon-greedy 一样来回震荡，并且不需要修改奖励函数，缺点是相比之下设计一个好的 exploration bonus 有时会做得更好。

information theoretic quantities in RL

example of mutual information: empowerment $I(st+1;at)=H(st+1)−H(st+1∣at)$

第一项表示下一状态有多少种可能，第二项表示基于某一动作，下一状态还有多少可能，empowerment 可以视为以信息论方式对控制能力的一种量化。如果说信息增益是更好地了解世界，那么empowerment就是更大程度地决定世界走向。

learn without a reward function

如果没有目标就自己产生多样的目标来探索整个状态空间，先随机采 latent $z_g∼p(z)$，再通过 encoder $x_g∼p_θ(x_g∣z_g)$，让VAE生成一个想象中的目标图像。机器人使用 $a_t∼π(a_t∣x_t,x_g)$ 尝试到达目标，最后实际可能只到 $\bar{x}$ ，用这些轨迹继续训练 goal-conditioned policy $π(a∣x,x_g)$ 让它越来越向目标走。最后用实际访问到的状态 $\bar{x}$ 重新训练 VAE $p_θ(x_g∣z_g),q_ϕ(z_g∣x_g)$ 然后重新生成下一批目标。

但是这里VAE 更新时不使用普通 MLE，而使用 weighted MLE: $θ,ϕ←arg_{θ,ϕ}maxE[w(\bar{x})logpθ(\bar{x})]$ 其中$w(\bar{x})=p_θ(\bar{x})α$ 并取 α∈[−1,0)，使得越罕见的状态，训练权重越大。VAE 就会生成更多以前很少访问的目标，然后 policy 被迫去探索这些地方，通过最大化 goal distribution entropy 得到更多样目标覆盖更多状态空间。

why state entropy a good objective

最大化状态访问熵并不是普适的最优探索原则，而是在与目标无关或不知道以后会给什么目标，并希望对最坏目标也有保障，那么最大状态熵是robust的。当我们不知道未来 goal时，假设运行时选择最坏目标 $g^-= \arg\min_g\rho_\pi(g)$ ，于是 worst-case regret：$R_{\rm worst} = \frac1{\min_g\rho_\pi(g)}$ 目标因此变成 $\min_\rho \frac1{\min_g\rho(g)}$ 等价于$\max_\rho \min_g\rho(g)$ 但又必须满足 $\sum_g\rho(g)=1$。为了让最小的那一项尽可能大唯一合理答案就是每个 goal 一样多 $\rho(g)=\frac1{|G|}$。因此在 goal-reaching learning procedures 中，uniform terminal-state marginal 是最低 worst-case regret 的选择。但是如果未来 goal distribution $p(g)$ 已知，平均 regret 是 $R(\pi) = \sum_g p(g) \frac1{\rho_\pi(g)}$，此时最优解其实不是简单的$\rho=p$ 而是 $\rho_\pi^*(g) \propto \sqrt{p(g)}$。