多精度 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。

真抽象。