多臂老虎機問題簡介

許多實際應用需要解決順序決策問題，其中代理必須在幾個替代方案中選擇最佳行動。這類應用的例子包括臨床試驗、推薦系統和異常檢測。在某些情況下，每個行動都會關聯到次要信息或情境（例如用戶檔案），而反饋或獎勵僅限於所選選項。例如，在臨床試驗中，情境是患者的病歷（例如健康狀況、家族史等），行動對應於比較的治療選項，獎勵代表建議治療的結果（例如成功或失敗）。在這種情況下，影響長期成功的一個重要方面是在探索（例如嘗試新治療）和利用（選擇目前已知的最佳治療）之間找到良好平衡。

這種探索與利用之間的固有權衡存在於許多順序決策問題中，傳統上被表述為老虎機問題，其呈現如下：給定K個可能行動或「臂」，每個臂都關聯到一個固定但未知的獎勵概率分佈，在每次迭代中，代理選擇一個臂來拉動，並獲得一個獎勵，該獎勵是從相應臂的概率分佈中獨立於先前行動抽樣得出的。代理的任務是學會選擇其行動，以便隨時間累積的獎勵最大化。

多臂老虎機問題表述

經典的多臂老虎機問題由K個臂定義，每個臂具有未知的獎勵分佈。在每個時間步t，代理選擇一個臂a_t ∈ {1, 2, ..., K}，並從所選臂的分佈中獲得一個抽樣獎勵r_t。目標是在T輪中最大化累積獎勵，或者等效地，最小化遺憾，即最優臂的累積獎勵與所選臂的累積獎勵之間的差異。

請注意，代理必須嘗試不同的臂以了解它們的獎勵（即探索收益），並且還使用這學到的信息來獲得最佳收益（利用學到的收益）。在探索和利用之間存在自然的權衡。例如，每個臂恰好嘗試一次，然後播放其中最好的。當臂的獎勵不確定時，這種方法通常很可能導致非常次優的解決方案。

針對這個問題已經提出了不同的解決方案，基於隨機表述和貝葉斯表述；然而，這些方法沒有考慮代理可用的情境或次要信息。

情境多臂老虎機

MAB的一個特別有用的版本是情境多臂老虎機，或簡稱情境老虎機，在每輪中，在選擇臂之前，代理觀察一個情境向量x_t，該向量可能影響臂的獎勵分佈。情境可以包括用戶特徵、環境變量或任何相關的側面信息。目標仍然是最大化累積獎勵，但現在策略可以依賴於觀察到的情境。

情境老虎機由於其在個性化推薦系統中的適用性而獲得了顯著關注，其中情境通常代表用戶特徵，臂對應於要推薦的不同項目或內容。獎勵可能是點擊、購買或任何其他形式的參與。

已經開發了幾種用於情境老虎機的算法，包括LinUCB，它假設情境與每個臂的期望獎勵之間存在線性關係，以及帶有線性模型的湯普森抽樣。這些算法在各種應用中顯示出強大的實證性能。

多臂老虎機的實際應用

臨床試驗

在臨床試驗中，多臂老虎機框架提供了一種倫理的治療分配方法。情境包括患者病歷、人口統計信息和遺傳標記。臂代表不同的治療選項，獎勵指示治療成功或失敗。老虎機算法可以動態地將更多患者分配到有希望的治療，同時仍然探索替代方案，可能導致更好的患者結果和更有效的試驗。

推薦系統

推薦系統是老虎機算法最成功的應用之一。主要平台使用情境老虎機來個性化內容、產品和廣告推薦。探索組件允許系統發現用戶對新項目的偏好，而利用則利用已知偏好來最大化用戶參與。這種方法解決了新項目的冷啟動問題，並適應隨時間變化的用戶興趣。

異常檢測

在異常檢測系統中，老虎機算法可以優化有限檢查資源的分配。情境可能包括系統指標、網絡流量模式或用戶行為特徵。臂代表不同的檢查策略或異常檢測模型，獎勵反映是否識別出真正的異常。這種方法能夠將資源自適應地分配到最有希望的檢測方法。

其他應用

其他應用包括金融中的投資組合優化、網頁開發中的A/B測試、雲計算中的資源分配以及教育技術中的自適應學習。老虎機框架的靈活性使其適用於任何在有限反饋和不確定性下需要順序決策的場景。

老虎機算法與方法

隨機老虎機

隨機老虎機假設每個臂的獎勵是從固定分佈中獨立抽取的。關鍵算法包括ε-greedy，它以概率1-ε選擇最佳臂，以概率ε隨機選擇一個臂；上置信界算法，基於對其潛力的樂觀估計選擇臂；和湯普森抽樣，使用貝葉斯後驗分佈來平衡探索和利用。

對抗性老虎機

對抗性老虎機不對獎勵生成做統計假設，將其視為可能由對手選擇的任意序列。Exp3算法及其變體專為此設置設計，使用指數加權方案來實現對任何獎勵序列的次線性遺憾。

貝葉斯老虎機

貝葉斯老虎機維護臂的可能獎勵分佈的概率分佈。湯普森抽樣是最突出的貝葉斯方法，它從每個臂的獎勵參數的後驗分佈中抽樣，並選擇具有最高抽樣值的臂。這根據當前的不確定性優雅地平衡了探索和利用。

情境老虎機算法

情境老虎機算法擴展了這些方法以納入情境信息。LinUCB假設線性獎勵函數並在參數估計周圍維護置信橢球。神經老虎機使用深度神經網絡來建模情境與獎勵之間的複雜關係。這些算法在具有高維情境的大規模應用中展示了強大的性能。

當前趨勢與未來展望

多臂老虎機領域正在經歷復興，除了經典老虎機問題外，還引入了由多樣實際應用激發的新問題參數和算法。重要的當前趨勢包括老虎機與深度學習的整合，導致能夠處理複雜高維情境的更強大的情境老虎機算法。

另一個重要趨勢是開發用於非平穩環境的老虎機算法，其中獎勵分佈隨時間變化。這對於許多實際應用至關重要，其中用戶偏好、市場條件或系統行為在演變。滑動窗口UCB和折扣技術等算法應對了這一挑戰。

對協作和分佈式老虎機的興趣日益增長，其中多個代理同時學習並可能共享信息。這與數據隱私重要的聯邦學習設置相關。此外，帶有約束和安全考慮的老虎機正在獲得關注，特別是在醫療保健和金融應用中，必須避免某些行動。

未來研究方向包括為非常大的行動空間開發更高效的算法，納入關於行動空間的結構信息，以及改進深度老虎機算法的理論理解。老虎機與因果推理的交叉代表了另一個有希望的方向，當干預可能具有長期效應時，能夠實現更好的決策。

結論

多臂老虎機提供了一個強大的框架，用於在有限反饋和不確定性下進行順序決策。基本的探索-利用權衡出現在無數實際應用中，從臨床試驗到推薦系統。情境老虎機擴展對於適應個體特徵的個性化系統已證明特別有價值。

本調查全面概述了多臂老虎機的主要發展，重點關注實際應用。我們檢查了問題表述、關鍵算法和多樣應用領域。該領域繼續快速演變，新算法應對諸如非平穩性、大行動空間和安全約束等挑戰。

隨著老虎機算法變得更加複雜並應用於日益複雜的問題，它們將繼續在優化各個領域的決策中發揮關鍵作用。該領域的持續研究有望在未來產生更有效的算法和更廣泛的應用。