Bandit 演算法#

Bandit 演算法（Multi-Armed Bandit，多臂老虎機）解決的是 探索與利用（Exploration vs Exploitation） 問題。

在推薦系統中，它用於回答：「該繼續推薦用戶已知喜歡的內容，還是冒險試試新東西？」

Bandit 在推薦的三大典型場景：

  1. 冷啟動：新用戶或新物品還沒資料，用 Bandit 邊推邊學
  2. 多策略融合：首頁有多種推薦策略（熱門、CF、深度模型）競爭曝光
  3. 多素材選擇：同一個推薦位有多張圖 / 多個標題候選

問題背景#

多臂老虎機問題#

想像一排老虎機，每台的中獎機率未知。目標是在有限次嘗試中拿到最大累積收益。

策略 = 利用（選歷史表現最好的）+ 探索（試不確定的）

推薦場景的對應#

  • 每個 arm = 一個候選物品 / 策略 / 素材
  • 拉一次 = 推給用戶看一次
  • 收益 = 點擊、停留、購買

只利用不探索 ➡️ 陷入「資訊繭房」、永遠錯過更好的選項；只探索不利用 ➡️ 用戶體驗崩掉。Bandit 的核心是「隨經驗累積動態調整探索比例」。

探索與利用的核心直覺#

在挑演算法之前，先建立幾個會反覆用到的直覺——它們決定了「該探索多少」。

時間區間決定探索比例#

探索與利用的比例，本質上由剩餘時間決定：

  • 剛搬到一座城市（前面還有好幾年）➡️ 該多試新餐廳。
  • 下週就要搬走 ➡️ 回到已知最愛，別再冒險。

對推薦的啟示：新用戶生命週期長，應積極探索找出興趣；臨近流失的用戶，應專注已驗證的內容。所以「探索強度」不是固定常數，而該隨用戶所處的時間區間調整。

後悔：衡量探索的代價#

後悔（Regret） = 「事後諸葛、從頭就一直選最優 arm 的累積收益」減去「實際累積收益」。它把「探索犯的錯」量化成一個數字。

理論結果（Lai-Robbins）：最佳策略的後悔只以 對數速率 成長——意思是「前期犯的錯，比後期多得多」。後悔雖然永遠不會歸零，但好的策略讓每年新增的後悔越來越少。這解釋了為何所有好 Bandit（UCB、Thompson）前期都拚命試、後期才穩定下來。

未知的價值（Gittins 指數）#

一個完全沒試過（0 勝 0 敗）的選項，到底值多少？Gittins 指數給了量化答案：在標準設定下，全新選項的指數約為 0.70，比一個已知勝率 70% 的選項還高。

關鍵洞察是「探索紅利消退得很慢」：即使新選項第一次就失敗（0 勝 1 敗），它的指數通常仍高於 50%，值得再給一次機會。剩餘時間越長，未知選項越值錢——這與「時間區間」的直覺完全一致。

樂觀面對不確定性#

UCB 與 Thompson 共享同一種態度：對不確定的選項給予樂觀的估計，先假設它可能很好，直到資料證明相反。

決策依據 = 已知表現 + 不確定性帶來的「樂觀加分」
  • 樣本少 ➡️ 不確定性大 ➡️ 樂觀加分大 ➡️ 自然被選中去探索。
  • 樣本多 ➡️ 估計變穩 ➡️ 加分縮小 ➡️ 自動轉向利用。

這就是為何「樂觀」在長期反而是最小化後悔的理性策略：它保證每個選項都被充分試過，不會因為運氣差的前幾次就被永久埋沒。下面的 UCB 與 Thompson Sampling 正是這個直覺的兩種具體實作。

基礎 Bandit 演算法#

ε-Greedy#

最簡單的策略：

以機率 ε 隨機探索
以機率 1-ε 選擇當前最優
實作程式碼
import numpy as np

def epsilon_greedy(Q, epsilon=0.1):
    """
    Q: 每個 arm 的估計價值
    epsilon: 探索機率
    """
    if np.random.random() < epsilon:
        return np.random.randint(len(Q))
    else:
        return np.argmax(Q)

ε-Greedy 的探索是盲目的：對「明顯爛」與「不確定可能很好」的 arm 一視同仁。後面 UCB 與 Thompson Sampling 都在改進這點。

湯普森採樣（Thompson Sampling）#

利用貝葉斯思想，為每個 arm 維護一個機率分佈，每次決策時從分佈中採樣：

1. 為每個 arm 維護 Beta(α, β) 分佈
   - α：成功次數 + 1
   - β：失敗次數 + 1

2. 每次決策：
   - 從每個 arm 的分佈中採樣
   - 選採樣值最大的 arm

3. 觀察結果後更新分佈
實作程式碼
import numpy as np

class ThompsonSampling:
    def __init__(self, n_arms):
        self.alpha = np.ones(n_arms)
        self.beta = np.ones(n_arms)

    def select_arm(self):
        samples = np.random.beta(self.alpha, self.beta)
        return np.argmax(samples)

    def update(self, arm, reward):
        if reward == 1:
            self.alpha[arm] += 1
        else:
            self.beta[arm] += 1

Thompson Sampling 在實務上幾乎是首選：實作簡單、效果好、自帶機率語意。Microsoft、Yahoo 的廣告平台都重度使用。

UCB（Upper Confidence Bound）#

每次選擇「信賴上界」最大的 arm：

UCB_i = Q_i + c × √(ln(t) / N_i)
  • Q_i：arm i 的平均收益
  • t：總嘗試次數
  • N_i：arm i 被選中的次數
  • c：探索係數

直觀理解（樂觀面對不確定性）：

  • 嘗試次數越少 ➡️ 不確定性越大 ➡️ UCB 加項越大
  • 平均收益高的會被選 ➡️ 利用
  • 沒怎麼試過的也會被選（因為加項大）➡️ 探索
  • 兩者自動平衡，不需手動調 ε

Contextual Bandit#

動機#

基礎 Bandit 不看「現在面對的是誰」。但推薦顯然要看用戶特徵與場景：年輕女性與中年男性適合的內容差很多。

LinUCB#

假設收益與上下文線性相關：

r = x^T θ + ε

選擇策略：
arm* = argmax(x_a^T θ̂_a + α × √(x_a^T A_a^(-1) x_a))
  • x_a：arm a 在當前上下文下的特徵向量
  • θ̂_a：arm a 的參數估計
  • A_a：協方差矩陣（衡量不確定性）

LinUCB 是 Yahoo 新聞首頁推薦的經典方案（2010 WWW 論文）。線性假設雖簡單，但工程上易於部署、線上學習穩定。

LinUCB 更新規則
class LinUCB:
    def __init__(self, d, alpha=0.1):
        self.d = d
        self.alpha = alpha
        self.A = {}  # A = I + Σ x x^T
        self.b = {}  # b = Σ r × x

    def get_action(self, x, arms):
        best_arm, best_ucb = None, -float('inf')
        for a in arms:
            if a not in self.A:
                self.A[a] = np.eye(self.d)
                self.b[a] = np.zeros(self.d)

            A_inv = np.linalg.inv(self.A[a])
            theta = A_inv @ self.b[a]
            ucb = x @ theta + self.alpha * np.sqrt(x @ A_inv @ x)

            if ucb > best_ucb:
                best_arm, best_ucb = a, ucb
        return best_arm

    def update(self, arm, x, reward):
        self.A[arm] += np.outer(x, x)
        self.b[arm] += reward * x

Bandit + 協同過濾#

COFIBA#

把 CF 的「相似用戶分享資訊」與 Bandit 的「動態探索」結合：

  1. 用戶聚類：把相似用戶聚成群組
  2. 群組共享資訊：群內用戶共享探索結果
  3. 動態更新：根據回饋調整聚類
用戶相似度 → 動態聚類 → 群組級 LinUCB → 個人化推薦

COFIBA 緩解了單純 Bandit 對新用戶要從零開始學的問題：新用戶可借助同群其他用戶的探索經驗。

工程實踐#

場景選擇#

場景推薦演算法理由
新用戶 / 新物品Thompson Sampling快速學習、自動平衡
首頁多策略選擇LinUCB考慮用戶上下文
A/B 測試替代Bandit自動收斂到最優策略

Thompson Sampling vs UCB#

維度Thompson SamplingUCB
理論保證較弱較強
實務效果優秀良好
實作複雜度簡單簡單
計算開銷採樣矩陣運算
適用場景通用需嚴格理論保證時

延遲回饋處理#

推薦系統的回饋常有延遲（用戶看到推薦到實際購買可能差好幾天）：

策略 1：使用短期代理指標（如點擊）
策略 2：設置回饋等待窗口
策略 3：使用延遲感知的 Bandit 演算法

批次更新#

線上不會每個請求都更新模型，而是批次更新：

  • 收集一段時間的回饋
  • 定期批次更新參數
  • 平衡即時性與計算開銷

Bandit vs A/B 測試#

何時用 Bandit#

對比A/B 測試Bandit
流量分配固定（如 50/50）動態（依表現調整）
結論時點實驗結束才下結論邊跑邊收斂
對劣質策略全程承擔劣質曝光成本自動降低劣質策略曝光
結果解讀統計顯著、易於決策不易做嚴格因果推論
適用場景需要嚴謹結論的功能上線決策多素材 / 多策略動態擇優

Bandit 不能完全取代 A/B：A/B 適合「決定要不要上線一個功能」（重大決策、需要乾淨的對照組），Bandit 適合「在多個已上線方案中持續找最好」（運營優化、素材擇優）。

範例：用 Bandit 做策略選擇#

# 每個策略當作一個 arm
strategies = ['strategy_A', 'strategy_B', 'strategy_C']
bandit = ThompsonSampling(len(strategies))

def get_strategy(user):
    arm_idx = bandit.select_arm()
    return strategies[arm_idx]

def record_feedback(strategy, success):
    arm_idx = strategies.index(strategy)
    bandit.update(arm_idx, 1 if success else 0)

總結#

要點說明
核心問題探索與利用的平衡
時間區間剩餘時間越長，越該探索
後悔（Regret）探索代價的量化，最佳策略對數成長
Gittins 指數未知選項天生有價值，探索紅利消退慢
ε-Greedy簡單但盲目探索
Thompson Sampling貝葉斯採樣、實務首選
UCB樂觀面對不確定性、自動平衡 E&E
LinUCB加入上下文，個人化的 Bandit
COFIBABandit + CF，緩解新用戶冷啟動
應用場景冷啟動、多策略 / 多素材擇優、廣告
與 A/B 的差異A/B 重決策，Bandit 重持續優化

下一章：排序模型

Backward 矩陣分解 (Matrix Factorization) 排序模型 (Ranking Model) Forward