Multi-Armed Bandit: UCB (Upper Bound Confidence)

01-30

上一講主要內容回顧

假設我們開了一家叫Surprise Me的飯館

客人來了不用點餐，由演算法從N道菜中選擇一道菜推薦給客人
每道菜都有一定的失敗概率：以1-p的概率不好吃，以p的概率做得好吃
演算法的目標是讓滿意的客人越多越好。

解決方法：

$epsilon － greedy$ 演算法：

以 $epsilon$ 的概率從N道菜中隨機選擇(概率為 $frac{epsilon}{N}$ )一個讓客人試吃
以 $1-epsilon$ 的概率選擇N道菜中選擇好吃的概率最高的菜推薦給客

充分利用歷史信息進行選擇

$epsilon － greedy$ 生硬的將選擇過程分成探索階段 (Exploration) 和利用階段(Exploitation)，在探索時對所有物品進行以同樣的概率 (概率為 $frac{epsilon}{N}$ ) 進行探索，並不會利用任何歷史信息，包括（1）某道菜被探索的次數，（2）某道菜獲得好吃反饋的比例。

讓我們忘記探索階段和利用階段，仔細想想如何充分利用歷史信息，找到最值得被推薦的菜：

觀測 1: 如果一道菜已經推薦了k遍（獲取了k次反饋），我們就可以算出菜做的好吃的概率：

$tilde{p} = frac{sum{reward_i}}{k}$

當k趨近正無窮時， $tilde{p}$ 會趨近於真實的菜做的好吃的概率 $p$

觀測 2: 現實當中一道菜被試吃的次數k不可能無窮大，因此估計出的好吃的概率 $tilde{p}$ 和真實的好吃的概率 $p$ 總會存在一個差值 $Delta$ ，即 $tilde{p} - Delta le p le tilde{p} + Delta$

基於上面兩個觀測，我們可以定義一個新的策略：每次推薦時，總是樂觀地認為每道菜能夠獲得的回報是 $tilde{p} + Delta$ ，這便是著名的Upper Confidence Bound (UCB) 演算法，代碼如下所示。

def UCB(t, N):n upper_bound_probs = [avg_rewards[item] + calculate_delta(t, item) for item in range(N)]n item = np.argmax(upper_bound_probs)n reward = np.random.binomial(n=1, p=true_rewards[item])n return item, rewardnnfor t in range(1, T): # T個客人依次進入餐館n # 從N道菜中推薦一個，reward = 1 表示客人接受，reward = 0 表示客人拒絕並離開n item, reward = UCB(t, N)n total_reward += reward # 一共有多少客人接受了推薦n

真實的概率和估計的概率之間的差值 $Delta$

最後只需解決一個問題，真實的概率和估計的概率之間的差值 $Delta$ 到底怎麼計算呢？

在進入公式之前，讓我們直觀的理解影響 $Delta$ 的因素：

對於被選中的菜，多獲得一次反饋會使 $Delta$ 變小，最終會小於其他沒有被選中的菜
對於沒被選中的菜， $Delta$ 會隨著輪數的增大而增大，最終會大於其他被選中的菜

下面我們正式介紹如何計算 $Delta$ ，首先介紹Chernoff-Hoeffding Bound：

[Chernoff-Hoeffding Bound] 假設 $reward_1, ..., reward_n$ 是在[0, 1]之間取值的獨立同分布隨機變數，用 $tilde{p}=frac{sum_i {reward_i}}{n}$ 表示樣本均值，用 $p$ 表示分布的均值，那麼有
$P{|tilde{p} - p| leq delta} geq 1 - 2e^{-2n{delta}^2}$

當 $delta$ 取值為 $sqrt{2 ln {T} /n }$ 時 (其中T表示有T個客人，n表示菜被吃過的次數)，可以得到

$P{|tilde{p} - p| leq sqrt{2 ln {T} /n } } geq 1 - frac{2}{T^4}$

也就是說 $tilde{p} - sqrt{2 ln {T} / n} le p le tilde{p} + sqrt{2 ln {T} / n}$ 是以 $1 - frac{2}{T^4}$ 的概率成立的：

當T=2時，成立的概率為0.875
當T=3時，成立的概率為0.975
當T=4時，成立的概率為0.992

可以看出 $Delta = sqrt{2 ln {T} / n}$ 是一個不錯的選擇。

最後，我們附上完整的代碼，跟第一講不一樣的地方已經重點加粗標註。

import numpy as npnnT = 1000 # T個客人nN = 10 # N道菜nntrue_rewards = np.random.uniform(low=0, high=1, size=N) # 每道菜好吃的概率nestimated_rewards = np.zeros(N) # 每道菜好吃的估計概率nchosen_count = np.zeros(N) #各個菜被選中的次數ntotal_reward = 0 nndef calculate_delta(T, item):n if chosen_count[item] == 0:n return 1n else:n return np.sqrt(2 * np.log(T) / chosen_count[item])nndef UCB(t, N):n upper_bound_probs = [estimated_rewards[item] + calculate_delta(t, item) for item in range(N)]n item = np.argmax(upper_bound_probs)n reward = np.random.binomial(n=1, p=true_rewards[item])n return item, rewardnnfor t in range(1, T): # T個客人依次進入餐館n # 從N道菜中推薦一個，reward = 1 表示客人接受，reward = 0 表示客人拒絕並離開n item, reward = UCB(t, N)n total_reward += reward # 一共有多少客人接受了推薦n n # 更新菜的平均成功概率n estimated_rewards[item] = ((t - 1) * estimated_rewards[item] + reward) / tn chosen_count[item] += 1n

歡迎訂閱微信公眾號 "零基礎機器學習"，搜索微信號：ml-explained