首先，我們以一種非常概括的方式來談論Multi-Armed Bandits問題。

困境：在信息不完全的情況下，如何找到最佳的勘探策略?

一般假設：每個手臂/動作的獎勵是固定的。換句話說，獎勵的分配不會隨著時間而改變。這個假設在實踐中並不需要，但我們認為它是真實的，至少在短時間內是如此。

其次，我們將逐步討論3種主流算法，這些算法分為以下兩類：

• 隨機探索。
• 智能探索優先考慮不確定性。

隨機探索：ε-Greedy

想法：我們分配一定比例的帶寬僅用於勘探。

策略：我們採取一個小概率ε 的隨機行動，但除此之外，我們選擇迄今為止所學的最佳行動。

缺點：

- 低效的探索。由於這種隨機性，我們最終可能會發現一個我們過去已經證實的不好的行為。

- 長期的浪費探索。由於固定的勘探速度，即使我們已經有信心並且可以選擇利用最有名的行動，我們也會繼續探索。

- 次優開採。由於我們只使用樣本均值來選擇最佳的行為，因此較低的不確定性的回報優先於較低的不確定性回報。

智能探索：置信區間上界（UCB）

想法：為了解決上述第一個缺點，我們不考慮隨機探索，而是考慮每個行為的不確定性。基於我們已經知道的，我們可以估計每個行動在歷史均值周圍的一些邊界內具有高概率的獎勵。邊界的寬度由其不確定性決定，這基本上是由試驗次數決定的。如果我們樂觀並且追求具有強大潛力的行動，我們總會選擇置信區間上界（UCB）的行動。通過這種方式，避免了第二和第三個缺點。

策略：我們總是選擇UCB最高的行動。

如何估算UCB？

- Hoeffding的不平等

- 我們嘗試了更多的特殊行動，UCB就會越來越緊密。

- 我們需要先選擇概率P，關於UCB大於其真實平均值的置信水平。換句話說，我們需要確定我們有多低估其潛力。我們通常希望這個數字相當小，比如5％。我們低估的可能性越小，UCB就會越廣泛，這又會導致勘探效率低下。

進一步優化：

- UCB1：隨著時間的推移降低概率P，所以當我們有更多的試驗時，我們將能夠擴展UCB並獲得更多的信心覆蓋。

- 貝葉斯UCB：Hoeffding的不等式不會假設獎勵的分配。由於它適用於任何發行版，因此它必須保守，並且不會針對特定問題達到最佳效果。如果我們知道獎勵的前期分配（例如，正態分佈），我們可以在相同的置信水平下獲得更緊密的UCB。

缺點：

- 信息利用不足。雖然獎勵的上限已經被用來選擇最優的行動，但是具有更豐富信息的分配沒有被充分利用。

智慧探索：Thompson Sampling

想法：為了解決上述缺點，我們不是以確定性的方式計算分佈的置信上限，而是從概率上對分佈進行抽樣。

策略：在每個時間步驟，我們隨機從每個行動的分佈中挑選一個樣本，然後通過評估這些樣本選擇最佳行動。本質上，我們根據相應動作是最優的概率來選擇動作，並以觀察歷史為條件。

分發如何更新？

- 在每個時間步後，我們需要更新我們之前的後驗和觀察到的真實獎勵。

- 與ε-Greedy和UCB不同，我們只需更新樣本均值，我們需要更新分佈。

- 使用貝葉斯推理。

- 實際上，貝葉斯推斷可能是計算上難以處理的。我們可以通過使用像吉布斯採樣（Gibbs sampling），拉普拉斯近似和bootstraps這樣的方法來近似它。

最後，讓我們談談這些算法使用的兩個基本策略，即概率匹配策略和效用最大化策略。

本質上，Thompson Sampling應用概率匹配策略，而所有貪婪算法（包括UCB）都在應用效用最大化策略。那麼，每種策略的基本假設是什麼？我們應該在什麼時候應用？

效用最大化策略是針對某些問題的

有兩個盒子，兩個人要麼吃一塊糖果，要麼什麼都不吃。

你的目標是選擇其中的一個超過1000輪，你想要有儘可能多的糖果。

你知道，在一個時間段內，A盒子裡有糖果60%的時間B盒子裡有40%的時間。

理性策略顯然總是選擇A。

概率匹配是針對不確定的問題。

與上面的例子相同的設置，不同之處在於，您知道盒子A在過去10次中有6次糖果，盒子B在過去10次中有過4次。

直覺告訴我們，以前的策略並不是最優的，因為由於運氣不佳，很可能B表現不佳。因此，我們應該給B至少一些機會。

或者，不是隻知道最近10次，而是最近10000次。那麼之前的策略非常接近最優。

我們如何以數學的方式表達我們的直覺？概率匹配策略告訴我們，基於方框A和方框B的分佈，我們可以計算方框A將擊敗方框B的概率。然後我們可以擲骰子以這個概率選擇A.

概率匹配策略本質上是一種混合策略。