多臂賭博機

在概率論和機器學習中，多臂賭博機問題（英語：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]。