多精度 simulator 中的 RL：一篇 14 年 ICRA 的古早论文

全文快读

• 论文题目：Reinforcement learning with multi-fidelity simulators，是 14 年的 ICRA 会议的论文。师兄说是 robotics 顶会，但中稿率蛮高的。
• 链接：https://ieeexplore.ieee.org/document/6907423
• main contribution：把 multi-fidelity optimization 拓展到 sequential decision 场景。
• 主要内容：
  • 目标：real-world sample 数量最少。
  • 定义 optimistic multi-fidelity simulator chain：一大串 multi-fidelity 的 simulator。
  • KWIK 技术：很 naive 的技术，就是，如果我们看到过足够多这种情况，就根据经验给出 reward / transition 估计，否则，给出最大 reward 作为估计（鼓励 exploration）。
  • MF-bandit 算法：
    • 假设 state 不变，我们要找到最优 action；
    • 目前在尝试 a* = argmax Reward（最大化 reward 估计值）这个动作，在 level d 的 fidelity 尝试了这个动作，得到其 reward，用这个 reward 更新 reward 估计值。
      • reward 估计值的更新：如果在最 low-fidelity 的 simulator，估计值 = R_max；否则，用 fidelity 低一层的 reward 估计值，作为当前 fidelity reward 估计的 heuristic，估计 = R_{d-1} + β。
    • 然后，我们继续做 a* = argmax R，因为 reward 估计值变了嘛，所以这个 a* 很可能跟上一轮的 a* 不是同一个。
      • 如果是同一个，那我们就认为 policy 在 level d 的 fidelity 收敛了，去 level d+1 继续做 MF-bandit。
      • 如果不是同一个：如果这个 a* 在 level d-1 上并没有估计值，即，我们没法拿 d-1 的 reward 估计做 d 层 reward 估计的 heuristic 了，那么回退到 d-1 层，先把 d-1 层 reward 估计算出来。
  • MFRL 算法：跟 MF-bandit 基本一样。
    • 我们需要估计的有：1. reward，2. env transition。
    • 要通过 argmax Q function 取 action。
    • 每次 1. reward，2. env transition 有所更新（根据 KWIK，即出现 (s,a,r,s') 次数足够多），就重新计算 Q function。并且，如果 1 2 有所更新，把数据同步到所有更 low-fidelity 的 KWIK learner。
• 局限性：我还没太想好，如果用 DRL 来做，具体该怎么做。

0 abstract

• 提出一个 RL 框架：在有多个保真度（fidelity）不断降低的 simulator 的情况下。
• 我们的框架允许 agent 选择仍能提供信息的最 low-fidelity 的 simulator，来限制 high-fidelity simulator 的样本数量。
• 该方法基于 know-what-it-knows 技术，将 low-fidelity 的 Q function 作为 high-fidelity RL 的 heuristic。与迁移学习（transfer learning）或无模拟器学习相比，real-world sample 数量更少。
• 给出了关于 sample conplexity 的理论证明，并在一辆有 multi-fidelity simulator 的遥控汽车上做实验。

1 intro

• 迁移学习：将策略从 simulator 转移到 real-world。

• 多保真 RL（MFRL）：

  • 结合多保真优化 [6] 和 model-based RL，"面对不确定性的乐观主义 "启发式方法，RL [7] 的 "知道它知道什么"（know what it knows，KWIK）model-learning framework。
  • 1 在 coarse model 里探索，2 用 fine model 更新 coarse model。

• 与只向现实世界的 agent 传递一次 heuristics 的单向方法不同[5]，MFRL 框架还规定了 agent 何时应该向上移动到高保真模拟器，以及在更昂贵的模拟中进行过度探索之前，向下移动保真度的规则。有理论上的收敛、采样效率的保证。

• 具体来说，该框架

  • （1）不会在高水平上运行已被证明为次优的行动，
  • （2）（在一定条件下）将最高 fidelity 的样本数量降到最低，
  • （3）限制 sample 总数。
  • 此外，可以证明 MFRL without resets 在最高 fidelity 的 simulator 上的样本数（最坏情况）不比“单向传输”方法多。

• main contributions：

  • （1）介绍 MFRL framework；
  • （2）对该框架的 sample complexity 进行了理论分析；
  • （3）实验。

2 related work

• RL：1 在 simulator 里学，然后直接在 real-world 跑，2 一直在 real-world 里跑，但用 low-fidelty simulator 算 policy gradient。

• 已经有监督学习的 multi-fidelty 工作了。

• 使用 low-fidelty model 生成的东西，作为指导 exploration 的 heuristic。

  • 不是 用上一个环境训出来的 policy 指导当前环境学习的迁移学习（transfer learning，TL）。
  • 不是 在 action space 不同的环境间的 TL [10]，因为 env 的 dynamics 和 rewards 也不一样。

• 类似的方法是 transferred delayed Q-learning（TDQL）[5]。可以证明我们的方法在 highest-fidelity env 上的 sample 数量 ≤ TDQL。

• 我们的工作将多保真优化（MFO）[6] 扩展到顺序决策（sequential decision-making）问题，借鉴 MFO 的经验，用 high-fidelity 数据更新模型，并根据 low-fidelity 结果作为 RL exploration 的 constraint。

3 背景 & 假设

3.1 RL & KWIK（know what it knows）的背景

• KWIK：是一种 standardize RL sample complexity 的 framework。sample complexity 就是次优步骤的数量。
• 如果 agent 对 (s,a) 的预测 (s', r) 有把握，即 || prediction - ground truth || ≤ ε，则使用预测值 (s', r)，否则 agent 给出⊥，表示它不知道 (s,a) 会发生什么。
• KWIK-Rmax RL：于是，使用预测的 s' 和 real env 的 reward 建立近似 MDP。如果 agent 给出了⊥，则乐观的将 reward 设成 (1-γ)R_max。
• 它保证了多项式的 sample complexity。
• （并没有听懂）

3.2 问题定义

• 用 Σ 表示 MDP simulator。
• 貌似，假设 low-fidelity 是 high-fidelity 的一种状态集结，用 |Q(s, a) - Q(ρ[s], a)| 来定义 fidelity f(Σi, Σj, β)，其中 ρ 是 Si → Sj 的 state mapping，Σi 的 fidelity＜Σj。（见公式）
  • 所以，Σi 对 Σj 的 fidelity 与它们最优 Q function 的误差成（负的）正比，前提是 low-fidelity Σi 对 Q function 的低估（还是高估）不超过 β，否则就是负无穷。
  • 合理性解释：在汽车模拟器中，low-fidelity Σi 假设行动会有完美的结果，然而在 higher-fidelity 中，这些乐观的 Q function 被更现实的 value function 所取代。
• Definition 1: optimistic multi-fidelity simulator chain：一系列 Σ1 .. ΣD，其中 ΣD 是 real world，并且对于一个特定的 ρi 和 βi，有 fidelity(Σi, Σ_{i+1}, βi) 不是负无穷。
• Assumption 1: 假设对于 low-fidelity Σi 和 high-fidelity Σ_{i+1}，在后者上模拟一步的 cost 是在前者上模拟多项式步（polynomial）的 cost。
• Assumption 2: 只能通过连续 trajectory 的方式使用模拟器，不能随机访问 (s,a) 或直接读参数。
• objectives：
  • 尽量减少 ΣD（real-world）的 sample 数量。
  • sample 数量是多项式的约束？
  • switch simulator 次数是多项式的约束。

4 Multi-Fidelity Bandit Optimization

考虑最简单的 setting：一个带有随机性的、只包含一个 state、k 个 action（称为 arm）的 MDP，使用 MF 优化寻找最优 arm。

4.1 MF 寻找最优 arm 的算法（MF-bandit）

变量与初始化：

• 首先维护一个 reward 集合 R_d(a)，用于存储尝试各种 action（arm）的经验。
  • 如果 reward 经验集合 R_d(a) 里关于某 action a 的经验超过 m 条，则取这些经验 reward 的平均值为 reward 估计值 U^_{d,a}；
  • 否则给出⊥即“我不知道”，并将 R_max 作为估计值（乐观估计）。
• 维护 bool 变量 closed_d，表示 Σ_d 的 action 是否收敛。
• 维护采取某 action 后的 reward 的 upper bound，U_{d,a}。
• 维护 bool 变量 con_{d,a}，表示 d 层的 action a 我是否了解透了。
• 维护 bool 变量 change_d，表示 d 层的 a* = argmax R_d(a) 是不是要变了。

算法：

• 首先取 a* = argmax U_{d,a}，即 reward 上界最大的 action。
• 更新 closed_d = con_{d,a*} 或者 a* 肯定是 near optimal，表示 Σ_d 的 action 收敛了。
• 如果 closed_d == false，即 Σ_d 中 action 的 reward 还没收敛，则执行 a*，得到 reward r，更新 reward 经验集合 R_d(a)。
  • 然后，更新 reward upper bound U_{d,a*} = min(U_{d,a*}}, U^_{d,a*})。
    • 最初的 U_{d,a} = U_{d-1,a} + β_{d-1} 是来自 low-fidelity 的 heuristic，是 low-fidelity simulator 的 heuristic 加上高估的极限 β。
  • 如果 R_d(a) 能够给出对于 a 的 reward 估计（即经验超过 m 条）了，则
    • con_{d,a*} = true，表示 a* 我了解透了；
    • change_d = true，表示 既然我获得了基于真实经验的 reward 估计值，可能 d 层的 a* = argmax R_d(a) 要换一换了。
• 如果 closed_d == true，即 Σ_d 中 action 的 reward 收敛了，则 d += 1。
  • 同时更新 heuristic U_{d+1,a} = U_{d,a} + β_d，changed_{d+1} = false。
• 如果 con_{d-1,a*} == false（目前给出的 a* 还没了解透）&& change_d == true（上一轮得到了一个 action 的真实 reward 估计，所以这一轮换 argmax action 了），则代表 a* = argmax R 换了个 action，但这个 action 在 low-fidelity 中还没理解透（也就是所谓的 low-fidelity 给出的最佳 action 在 high-fidelity 表现不好），要回溯到 low-fidelity simulator，d -= 1。
  • 更新 changed_{d-1} = false。
  • for 所有的 action a：如果 con_{d,a} == true（表示 action a 在 simulator d 研究透了），then
    • 把 high-fidelity 的经验 R_{d} 拷贝到 low-fidelity 经验集合 R_{d-1}，
    • 设置 con_{d-1,a} == true（既然上层研究透了，下层也不用做研究了），
    • change_{d-1} = true。

真抽象。😥

4.2 一个例子 4.3 理论证明

不愿多看。

5 Multi-Fidelity RL

5.1 MFRL algorithm

变量与初始化：

• ρ 是 simulator 之间的 state mapping。
• m_known 是去往更高 fidelity 的采样次数。
• Q function 初始化为 R_max / (1-γ)，乐观的估计。
• 如果模型参数发生变化，change_d = true，重新计算 Q 值。
• 关键技术和前面的 MF-bandit 很像：如果在当前 fidelity 上，刚刚模型学到了更多 (s,a) 的值（change == true），导致 Q function 重新计算，a* = argmax Q 的 a* 变化了；然而，变化后的 a* 在上一 fidelity（d-1 层）仍然存在不确定性，那么就回溯到 d-1 层。

算法：

• 首先取 a* = argmax Q_d(s,a)，即估计的 Q function 上界最大的 action。
• 如果 d＞1 && change_d == true && \(T_{d-1}[ρ_{d-1}^{-1}(s),a]\) == ⊥ 或者 \(R[ρ_{d-1}^{-1}(s),a]\) == ⊥，则回溯到 low-fidelity simulator，d -= 1。
  • \(Q_{d-1}[s,a] = P(\hat\Sigma_{d-1}, Q_{d-2} + \beta_{d-2})\)。
  • m_k = 0。
• else，执行 action a*，观测 r 和 s'。
  • 如果 \(R_d[s,a^*]\) == ⊥ 或者 \(T_d[s,a^*]\) == ⊥，那么 m_k = 0，更新 R_d 和 T_d。
    • else，m_k += 1。
  • 如果 \(R_d[s,a^*]\) 和 \(T_d[s,a^*]\) 从 ⊥ 变成 known，那么
    • \(Q_d[s,a^*] = P(\langle S_d,A,R_d,T_d,\gamma\rangle, Q_{d-1} + \beta_{d-1})\) 。
    • 对于所有 d' ≤ d，根据 \(R_d[s,a^*]\) 和 \(T_d[s,a^*]\) 的新值，来更新 \(\langle R,T\rangle_{d'}(ρ_{d-1}^{-1}(s),a^*)\)。
      • 把 high-fidelity 的数据传递给【所有】更低的 fidelity。
    • 并且 change_d' 都 = true。
• 如果 d＜D && m_k == m_{known}，那么增加 fidelity，去 d+1 层，d += 1。
  • \(Q_{d+1}(s,a) = P(\hat\Sigma_{d+1},Q_d+\beta_d)\) 。
  • m_k = 0，change_d == false。

5.2 一个例子 5.3 理论证明

不愿多看。

6 实验：RC car results

自己开 Google 翻译看就好啦。

看起来实验 setting 蛮 naive 的。

7 extensions & conclusions

• 虽然这项工作是 tabular transition model & tabular reward，但 NN 近似当然可以。
• 生成一些样本（？）第二段没看懂。
• MFRL：
  • sequential decision 的 multi-fidelity optimization，用 low-fidelity 作为 heuristic 来指导 high-fidelity 探索。
  • 与 transfer learning 不同，我们还可以从 high-fidelity transfer 到 low-fidelity。
  • 有一堆理论证明。
  • 在遥控汽车上做实验。