Bandit 演算法#
Bandit 演算法解決的是探索與利用 (Exploration vs Exploitation) 問題，在推薦系統中用於平衡推薦已知好的內容和嘗試新內容。
問題背景#
多臂老虎機問題#
想像一排老虎機，每台的中獎概率未知。目標是在有限次嘗試中獲得最大收益。
策略 = 利用（選擇歷史表現最好的）+ 探索（嘗試不確定的）推薦場景#
- 用戶喜歡什麼類型的內容？
- 新物品的質量如何？
- 應該推薦已知喜歡的還是嘗試新的？
如果只利用不探索，會陷入「資訊繭房」；如果只探索不利用，用戶體驗會很差。
基礎 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) # 選擇最優Thompson Sampling#
利用貝葉斯思想，維護每個選項的概率分佈：
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) # 成功次數 + 1
self.beta = np.ones(n_arms) # 失敗次數 + 1
def select_arm(self):
# 從每個 arm 的 Beta 分佈採樣
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] += 1Thompson Sampling 在實踐中效果優異，被廣泛應用於推薦系統。
UCB (Upper Confidence Bound)#
選擇置信上界最大的選項：
UCB_i = Q_i + c × √(ln(t) / N_i)
其中：
- Q_i：arm i 的平均收益
- t：總嘗試次數
- N_i：arm i 被選中的次數
- c：探索係數直觀理解：
- 選擇次數越少的 arm，不確定性越大
- 不確定性越大，置信上界越高
- 傾向於嘗試「可能很好但不確定」的選項
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 更新規則
class LinUCB:
def __init__(self, d, alpha=0.1):
self.d = d # 特徵維度
self.alpha = alpha
# 每個 arm 的參數
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 * xBandit + 協同過濾#
COFIBA#
結合協同過濾和 Bandit 的思想：
- 用戶聚類：將相似用戶聚成群組
- 群組共享資訊：群組內用戶共享探索結果
- 動態更新：根據反饋調整聚類
用戶相似度 → 動態聚類 → 群組級 LinUCB → 個性化推薦COFIBA 解決了冷啟動問題：新用戶可以借助相似用戶的探索經驗。
工程實踐#
場景選擇#
| 場景 | 推薦演算法 | 理由 |
|---|---|---|
| 新用戶/新物品 | Thompson Sampling | 快速學習，自動平衡 |
| 首頁推薦位 | LinUCB | 考慮上下文，個性化 |
| A/B 測試替代 | Bandit | 自動收斂到最優策略 |
Thompson Sampling vs UCB#
| 維度 | Thompson Sampling | UCB |
|---|---|---|
| 理論保證 | 較弱 | 較強 |
| 實踐效果 | 優秀 | 良好 |
| 實現複雜度 | 簡單 | 簡單 |
| 計算開銷 | 採樣 | 矩陣運算 |
| 適用場景 | 通用 | 需要理論保證 |
延遲反饋處理#
推薦系統中，用戶反饋可能有延遲：
策略 1：使用短期代理指標（如點擊）
策略 2：設置反饋等待窗口
策略 3：使用延遲感知的 Bandit 演算法批量更新#
實踐中不是每個請求都更新模型，而是批量更新：
- 收集一段時間的反饋
- 定期批量更新參數
- 平衡實時性和計算開銷
Bandit 在實驗平台的應用#
替代傳統 A/B 測試#
傳統 A/B 測試：
- 固定流量分配
- 實驗結束才能得出結論
- 「失敗」的策略消耗大量流量
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)總結#
| 要點 | 說明 |
|---|---|
| 核心問題 | 探索與利用的平衡 |
| ε-Greedy | 簡單直接，以固定概率探索 |
| Thompson Sampling | 基於貝葉斯採樣，實踐效果好 |
| UCB | 樂觀面對不確定性 |
| LinUCB | 考慮上下文的 Bandit |
| COFIBA | 結合協同過濾，解決冷啟動 |
| 應用場景 | 冷啟動、實驗平台、動態優化 |