Multi-Armed Bandits 簡介

在 TensorFlow.org 上檢視 在 Google Colab 中執行 在 GitHub 上檢視原始碼 下載筆記本

簡介

Multi-Armed Bandit (MAB) 是一種機器學習架構，其中代理程式必須選擇動作 (臂桿) 才能在長期內最大化其累積獎勵。在每一輪中，代理程式都會收到有關目前狀態 (情境) 的一些資訊，然後根據此資訊和先前幾輪中收集的經驗選擇一個動作。在每一輪結束時，代理程式都會收到與所選動作相關聯的獎勵。

也許最純粹的範例是為 MAB 命名的問題：想像一下，我們面對 k 台吃角子老虎 (獨臂強盜)，我們需要找出哪一台的賠率最好，同時又不會損失太多錢。

Multi-Armed Bandits

嘗試每台機器一次，然後選擇賠率最高的機器並不是一個好策略：代理程式可能會選擇一台一開始運氣好，但總體而言並非最佳的機器。相反地，代理程式應該重複回來選擇看起來不太好的機器，以便收集更多關於它們的資訊。這是 Multi-Armed Bandits 的主要挑戰：代理程式必須在利用先前的知識和探索之間找到適當的平衡，以避免忽略最佳動作。

MAB 更實際的例子包括學習者每次做出決策時都會收到一則附帶資訊。我們將此附帶資訊稱為「情境」或「觀察」。

Multi-Armed Bandits 和強化學習

為什麼 TF-Agents 程式庫中會有 MAB 套件？RL 和 MAB 之間有什麼關聯？Multi-Armed Bandits 可以被認為是強化學習的特例。引用強化學習簡介

在每個時間步驟，代理程式會根據其政策 \(\pi(a_t|s_t)\) 對環境採取動作，其中 \(s_t\) 是來自環境的目前觀察，並從環境中接收獎勵 \(r_{t+1}\) 和下一個觀察 \(s_{t+1}\)。目標是改進政策，以最大化獎勵總和 (報酬)。

在一般 RL 案例中，下一個觀察 \(s_{t+1}\) 取決於先前的狀態 \(s_t\) 和政策採取的動作 \(a_t\)。最後一部分是 MAB 與 RL 的區別：在 MAB 中，下一個狀態 (即觀察) 不取決於代理程式選擇的動作。

這種相似性讓我們能夠重複使用 TF-Agents 中存在的所有概念。

  • 環境輸出觀察結果，並以獎勵回應動作。
  • 政策根據觀察結果輸出動作，以及
  • 代理程式根據先前的觀察-動作-獎勵元組重複更新政策。

蘑菇環境

為了說明目的，我們使用一個名為「蘑菇環境」的玩具範例。蘑菇資料集 (Schlimmer，1981) 包含可食用和有毒蘑菇的標記範例。特徵包括蘑菇不同部位的形狀、顏色、大小，以及氣味等等。

mushroom

蘑菇資料集就像所有監督式學習資料集一樣，可以轉化為情境式 MAB 問題。我們使用的方法也由 Riquelme 等人 (2018) 使用。在此轉換中，代理程式接收蘑菇的特徵，決定是否食用。食用可食用蘑菇會產生 +5 的獎勵，而食用有毒蘑菇則有相等的機率給予 +5 或 -35。不食用蘑菇會產生 0 獎勵，與蘑菇的類型無關。下表總結了獎勵分配

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

LinUCB 代理程式

在情境式 bandit 環境中表現良好需要對每個動作的獎勵函數進行良好的估計 (給定觀察結果)。一種可能性是使用線性函數估計獎勵函數。也就是說，對於每個動作 \(i\)，我們都試圖找到參數 \(\theta_i\in\mathbb R^d\)，以使估計值

\(r_{t, i} \sim \langle v_t, \theta_i\rangle\)

盡可能接近現實。此處 \(v_t\in\mathbb R^d\) 是在時間步 \(t\) 接收的情境。然後，如果代理程式對其估計值非常有信心，它可以選擇 \(\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle\) 以獲得最高的預期獎勵。

如上所述，僅僅選擇具有最佳估計獎勵的臂桿並不能帶來好的策略。在線性估計器代理程式中混合利用和探索有很多不同的方法，其中最著名的方法之一是線性上限信賴區間 (LinUCB) 演算法 (例如，請參閱 Li 等人，2010)。LinUCB 有兩個主要建構區塊 (省略了一些細節)

  1. 它使用線性最小平方法維護每個臂桿的參數估計值：\(\hat\theta_i\sim X^+_i r_i\)，其中 \(X_i\) 和 \(r_i\) 是臂桿 \(i\) 被選中時的堆疊情境和獎勵，而 \(()^+\) 是偽逆。
  2. 它維護由上述估計值的逆共變異數 \(X_i^\top X_i\) 定義的信賴橢球。

LinUCB 的主要思想是「面對不確定性的樂觀態度」。代理程式透過將估計值提高一個對應於這些估計值的變異數的量來整合探索。這就是信賴橢球發揮作用的地方：對於每個臂桿，樂觀估計值為 \(\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle\)，其中 \(E_i\) 是 \(\hat\theta_i\) 周圍的橢球。代理程式選擇看起來最好的臂桿 \(\arg\max_i\hat r_i\)。

當然，上述描述只是對 LinUCB 功能的直觀但膚淺的總結。實作可以在我們的程式碼庫 這裡 找到

下一步？

如果您想獲得有關我們的 Bandits 程式庫的更詳細教學課程，請查看我們的 Bandits 教學課程。相反地，如果您想立即開始探索我們的程式庫，您可以在 這裡 找到它。如果您更渴望開始訓練，請查看我們的一些端對端範例 這裡，包括上面描述的帶有 LinUCB 的蘑菇環境 這裡。