跳至內容

多臂賭博機

維基百科,自由的百科全書

概率論機器學習中,多臂賭博機問題(英語:multi-armed bandit problem[1]有時稱為K-N-臂賭博機問題(英語:K-or N-armed bandit problem[2],是一個必須在競爭(替代)之間分配一組固定的有限資源的問題。當每個選擇的屬性在分配時僅部分已知時,以最大化其預期收益的方式進行選擇,並且隨着時間的推移或通過向該選擇分配資源可能會更好地被理解。這是一個經典的強化學習問題,體現了探索-利用權衡困境[3][4]。這個名字來源於想像一個賭徒坐在一排賭博機(或稱角子機、老虎機)前(有時被稱為「單臂賭博機」),他必須決定玩哪台機器,每台機器玩多少次以及玩的順序[5],並且是否繼續使用當前機器或嘗試不同的機器。多臂賭博機問題也屬於隨機調度的廣義範疇。

在該問題中,每台機器根據該機器特定的概率分佈提供隨機獎勵,該獎勵是先驗未知的。賭徒的目標是最大化通過一系列槓桿拉動所獲得的獎勵總和[4]。賭徒在每次試驗中面臨的關鍵權衡是在「利用」具有最高預期收益的機器和「探索」以獲得有關其他機器的預期收益的更多信息之間[3]。機器學習也面臨着探索和利用之間的權衡。在實踐中,多臂賭博機已用於對諸如管理大型組織(如科學基金會製藥公司)中的研究項目等問題進行建模[3][4]。在問題的早期版本中,賭徒一開始對機器一無所知。

赫伯特·羅賓斯於1952年認識到該問題的重要性,在「實驗序貫設計的某些方面」中構建了收斂種群選擇策略[6]約翰·C·吉廷斯首次發表的吉廷斯指數定理給出了最大化預期折扣獎勵的最優策略[7]

參考資料

[編輯]
  1. ^ Auer, P.; Cesa-Bianchi, N.; Fischer, P. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning. 2002, 47 (2/3): 235–256. doi:10.1023/A:1013689704352可免費查閱. 
  2. ^ Katehakis, M. N.; Veinott, A. F. The Multi-Armed Bandit Problem: Decomposition and Computation. Mathematics of Operations Research. 1987, 12 (2): 262–268. S2CID 656323. doi:10.1287/moor.12.2.262. 
  3. ^ 3.0 3.1 3.2 引用錯誤:沒有為名為Gittins89的參考文獻提供內容
  4. ^ 4.0 4.1 4.2 引用錯誤:沒有為名為BF的參考文獻提供內容
  5. ^ Weber, Richard, On the Gittins index for multiarmed bandits, Annals of Applied Probability, 1992, 2 (4): 1024–1033, JSTOR 2959678, doi:10.1214/aoap/1177005588可免費查閱 
  6. ^ Robbins, H. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society. 1952, 58 (5): 527–535. doi:10.1090/S0002-9904-1952-09620-8可免費查閱. 
  7. ^ J. C. Gittins. Bandit Processes and Dynamic Allocation Indices. Journal of the Royal Statistical Society. Series B (Methodological). 1979, 41 (2): 148–177. JSTOR 2985029. S2CID 17724147. doi:10.1111/j.2517-6161.1979.tb01068.x. 

延伸閱讀

[編輯]

外部連結

[編輯]