Bandit 算法簡介

MAB的全稱是 Multi-armed bandit problem（多臂老虎機問題）。它的背景是當賭場中有一排老虎機叫榕，每一臺老虎機中獎的概率不同，有沒有一種最優(yōu)的策略來在各個老虎機之間分配自己的資金以實現(xiàn)收益的最大化姊舵。

我們可以把這個問題翻譯成一個典型的推薦問題晰绎，有若干個item，每個item的曝光點擊率不同括丁，有沒有一種最優(yōu)的策略來分配item的曝光荞下，從而讓總體點擊率最高。下面敘述中史飞，我會統(tǒng)一采用推薦問題的術語尖昏，而不在用老虎機的術語。

當我們面對沒有先驗知識的item時构资，只能每個都去嘗試一下抽诉，但很快我們就會遇到 Exploitation-Exploration(E&E) 兩難的問題：

只把流量花在歷史點擊率高的item上，會錯過其他可能會有更好的點擊率表現(xiàn)的item吐绵，這個方法推到極端就是 winner gets all迹淌；
把流量花在到處探索上，就難免有較高的機會成本己单，不能積累到可觀的收益唉窃，這個方法推到極端就是隨機推薦。

bandit 算法是一類解決Exploitation-Exploration 問題的方法荷鼠，根據(jù)是否考慮上下文特征，算法分為 context-free bandit 和 contextual bandit 兩大類榔幸。

本篇主要介紹 context-free bandit 算法允乐，這類算法可以認為是推薦系統(tǒng)中“千人一面”的算法，不考慮不同用戶的差異性削咆。

1牍疏、基本原理

（1）Epsilon-Greedy算法

首先，介紹一種最簡單的算法拨齐。

選一個(0,1)之間較小的數(shù)epsilon鳞陨，生成一個隨機數(shù)，如果小于epsilon，則在所有item中選一個推薦厦滤，如果大于epsilon援岩，則返回目前為止點擊率最高的item。

這里epsilon的值可以控制對exploit和explore的偏好程度掏导。

（2）Thompson sampling算法

想了解 Thompson sampling享怀，就繞不開beta分布。知乎帖子（https://www.zhihu.com/question/30269898）對beta分布有比較詳細的介紹趟咆，這里會參照它進行介紹添瓷。

用一句話來說，beta分布可以看作一個二項分布期望值的概率分布值纱。

舉一個簡單的例子鳞贷，是用一個棒球運動員擊中的球數(shù)除以擊球的總數(shù)，就是擊球率虐唠，我們一般認為0.266是正常水平的擊球率搀愧，而如果擊球率高達0.3就被認為是非常優(yōu)秀的。

如果有一個棒球運動員凿滤，他的過往歷史擊球率是0.27妈橄，新賽季的第一場比賽，他擊球10次翁脆，命中5次眷蚓，我們可以說他現(xiàn)在的擊球率是0.5嗎？好像不太合理反番，那么用過往的0.27呢沙热？好像也不太合理。

實際上罢缸，“他現(xiàn)在的擊球率”這個概率值篙贸，也服從某個概率分布，對于二項分布來說枫疆，這個概率值的概率分布就是beta分布爵川。

beta分布有 $\alpha$ 和 $\beta$ 兩個參數(shù)，可以表示成 $Beta(\alpha, \beta)$ 息楔，這兩個參數(shù)分別代表在歷史擊球中寝贡，成功次數(shù)和失敗次數(shù)。

$\frac{\alpha}{\alpha + \beta}=0.27$

我們可以取 $\alpha$ = 81, $\beta$ = 219值依，beta分布的概率密度圖是這樣的圃泡，可以看到期望為0.27

beta.png

這位球員在新賽季擊球10次中5次，那么我們就可以更新Beta分布的參數(shù)了 Beta(81+5, 219+10)愿险，期望變成了0.273颇蜡。

如果這位球員繼續(xù)延續(xù)高水平的表現(xiàn)，擊球200次中100次，那么他的擊球率的分布就變成了 Beta(81+100, 219+200)风秤，期望變成了0.303鳖目，并且我們可以從概率密度圖看到，新的擊球率分布變窄了唁情，這也和我們直觀上的感覺是一致的疑苔。

beta2.png

那么Thompson sampling算法的基本原理就是，每一個item的點擊率都服從一個Beta分布甸鸟，Beta(alpha, beta)惦费，這個 $\alpha$ 是點擊次數(shù)， $\beta$ 是曝光未點擊的次數(shù)抢韭。

每個item都根據(jù)自己的Beta分布生成一個隨機數(shù)薪贫，選擇隨機數(shù)最大的那個item。

（3）UCB算法

UCB是 Upper Confidence Bound 的簡稱刻恭。對于每個item的點擊率p來說瞧省，假設歷史觀測的點擊率是p’，那么我們可以認為鳍贾，p實際是在p‘的鄰域內(nèi)的鞍匾，我們可以假設

$p' - \Delta <= p <= p' + \Delta$

UCB算法就是使用真實值的上界 p‘+ $\Delta$ 來進行樂觀預估。

我們會有一些觀察：

如果曝光的次數(shù)越多骑科， $\Delta$ 應該越小橡淑，p'會越趨向于真實值p
如果一個item在多次曝光中總是不被選中，那么它的delta應該逐漸增大咆爽，以保證它后面有機會曝光

UCB算法中選擇

$\Delta = \sqrt{\frac{2log(T)}{n}}$

其中梁棠，T是總實驗次數(shù)，n是選中該item的次數(shù)斗埂。這么選擇的數(shù)學原理可以參考這篇知乎帖子（https://zhuanlan.zhihu.com/p/32356077）符糊，這里直接略過。

2呛凶、代碼

代碼結構：

 - item.py
 - mab_algo.py
 - mab_simulator.py

首先男娄，我們抽象一個Item的類，它代表了推薦問題中的一個item漾稀，它會有一個自己真實的點擊率（click_rate）模闲，會記錄在實驗中自己的曝光次數(shù)和點擊次數(shù)，以及實驗中觀測到的點擊率县好。

# item.py

import random

'''
定義被曝光的item
item有一個屬性是點擊率
每次被調(diào)用exposure函數(shù)時围橡，都會隨機返回1和0暖混，返回1的概率是點擊率
'''
class Item(object):
  def __init__(self, click_rate):
    self.click_rate = click_rate
    self.click_cnt = 0
    self.exposure_cnt = 0

  def exposure(self):
    rnd = random.random()
    self.exposure_cnt = self.exposure_cnt + 1
    if rnd <= self.click_rate:
      self.click_cnt = self.click_cnt + 1
      return 1
    else:
      return 0
  
  def get_ctr(self):
    if self.exposure_cnt == 0:
      return 0.0
    else:
      return self.click_cnt / self.exposure_cnt


if __name__ == "__main__":
  item = Item(0.1)
  exposure_cnt = 10000
  click_cnt = 0
  for i in range(exposure_cnt):
    item.exposure()
  print('exposure: %d click: %d click_rate: %4.2f' 
        %(item.exposure_cnt, item.click_cnt, 1.0*item.click_cnt/item.exposure_cnt) )

然后缕贡，我們根據(jù)上面的介紹，分別實現(xiàn)三種 bandit 算法，并實現(xiàn)了一個隨機算法作為對比：

# mab_algo.py
import random
import numpy as np

# UCB算法
# p = p' + np.sqrt(2*np.log(T) / N)
# T是總實驗次數(shù)晾咪，n是選中該item的次數(shù)
def ucb_algo(item_list):
  total_exposure_cnt = 0
  for item in item_list:
    total_exposure_cnt = total_exposure_cnt + item.exposure_cnt
  upper_bound_probs = [item.get_ctr() + np.sqrt(2*np.log(1+total_exposure_cnt) / max(1, item.exposure_cnt)) \
                      for item in item_list]
  return np.argmax(upper_bound_probs)

# Thompson sampling算法
def thompson_sampling_algo(item_list):
  max_item_idx = 0
  max_rand = -1
  for idx, item in enumerate(item_list):
    # beta(a, b), a should be larger than 0
    rand = np.random.beta(1+item.click_cnt, 1+item.exposure_cnt - item.click_cnt)
    if rand > max_rand:
      max_item_idx = idx
      max_rand = rand
  return max_item_idx

# epsilon的概率是隨機返回
# 1-epsilon的概率是選擇當前效果最好的一個
def epsilon_greedy_algo(item_list):
  epsilon = 0.2
  rnd = random.random()
  if rnd < epsilon:
    # explore
    return random.randint(0, len(item_list) - 1)
  else:
    # exploit
    max_item_idx = 0
    max_ctr = -1
    for idx, item in enumerate(item_list):
      if item.get_ctr() > max_ctr:
        max_ctr = item.get_ctr()
        max_item_idx = idx
    return max_item_idx

# 隨機返回
def random_algo(item_list):
  return random.randint(0, len(item_list) - 1)

最后收擦，我們寫一個模擬器，來看一下不同算法的實際分配曝光的表現(xiàn)情況谍倦。

# mab_simulator.py
import random
from item import Item
from mab_algo import *

def get_exposure_item_idx(item_list, algo):
  return algo(item_list)

def demo():
  algo_list = [random_algo, epsilon_greedy_algo, thompson_sampling_algo, ucb_algo]
  click_rate_list = [0.05, 0.06, 0.1, 0.12, 0.2]
  
  exposure_cnt = 100000
  for algo in algo_list:
    print(algo)
    item_list = []
    for click_rate in click_rate_list:
      item = Item(click_rate)
      item_list.append(item)

    for i in range(exposure_cnt):
      idx = get_exposure_item_idx(item_list, algo)
      item_list[idx].exposure()

    for i in range(len(item_list)):
      print('item #%d click_rate=%4.2f%%\texpo=%d click=%d real_click_rate=%4.2f%%'
        %(I, 
          100*item_list[i].click_rate, 
          item_list[i].exposure_cnt, 
          item_list[i].click_cnt, 
          100.0*item_list[i].click_cnt/item_list[i].exposure_cnt))

if __name__ == "__main__":
  demo()

3塞赂、實驗

（1）實驗設置

我們設定5個item，#0到#4昼蛀，它們的真實點擊率分別是5%宴猾、6%、10%叼旋、12%和20%仇哆。

共進行10萬次實驗（也就是10萬次曝光機會），記錄在不同算法下夫植，每個item的曝光次數(shù)讹剔。

（2）實驗結果

先看隨機算法的結果，不出意外详民，每個item的曝光次數(shù)差不多延欠。

item #0 click_rate=5.00%    expo=20041 click=980 real_click_rate=4.89%
item #1 click_rate=6.00%    expo=19813 click=1231 real_click_rate=6.21%
item #2 click_rate=10.00%   expo=19946 click=1988 real_click_rate=9.97%
item #3 click_rate=12.00%   expo=20193 click=2358 real_click_rate=11.68%
item #4 click_rate=20.00%   expo=20007 click=3924 real_click_rate=19.61%

epsilon_greedy算法，實驗中設置epsilon=0.2沈跨，也就是會有20%的曝光（2萬次）會作為探索分配到各個item由捎，實驗結果也符合預期。

item #0 click_rate=5.00%    expo=3995 click=180 real_click_rate=4.51%
item #1 click_rate=6.00%    expo=3984 click=240 real_click_rate=6.02%
item #2 click_rate=10.00%   expo=3995 click=396 real_click_rate=9.91%
item #3 click_rate=12.00%   expo=3889 click=455 real_click_rate=11.70%
item #4 click_rate=20.00%   expo=84137 click=16898 real_click_rate=20.08%

thompson_sampling算法將幾乎全部的曝光機會都給了點擊率最高的 item #4谒出。這是因為實驗設置的item之間的點擊率差異還是很大的隅俘，在beta分布中體現(xiàn)了很明顯的差距。

item #0 click_rate=5.00%    expo=81 click=4 real_click_rate=4.94%
item #1 click_rate=6.00%    expo=167 click=16 real_click_rate=9.58%
item #2 click_rate=10.00%   expo=202 click=21 real_click_rate=10.40%
item #3 click_rate=12.00%   expo=313 click=40 real_click_rate=12.78%
item #4 click_rate=20.00%   expo=99237 click=19934 real_click_rate=20.09%

UCB算法也將大部分的曝光都給了 item #4笤喳，但沒有thompson_sampling算法那么極端为居。

item #0 click_rate=5.00%    expo=730 click=29 real_click_rate=3.97%
item #1 click_rate=6.00%    expo=918 click=54 real_click_rate=5.88%
item #2 click_rate=10.00%   expo=1773 click=183 real_click_rate=10.32%
item #3 click_rate=12.00%   expo=1946 click=211 real_click_rate=10.84%
item #4 click_rate=20.00%   expo=94633 click=19115 real_click_rate=20.20%

4、總結

context-free bandit 算法是一類非常簡單的算法杀狡，它可以有效解決E&E問題蒙畴，并且計算過程非常簡單，在實際應用中呜象，因為它天生應對冷啟動膳凝，容易做到實時反饋的特點，在很多場景中依然是很有用的工具恭陡。

為了解決 context-free 無法做到千人千面的問題蹬音，有很多可以結合上下文的 bandit 算法，其中LinUCB休玩，就是比較有代表性的一種著淆，它來自于雅虎的新聞推薦算法：https://arxiv.org/pdf/1003.0146.pdf劫狠。

參考

簡書：http://www.reibang.com/p/e7825a9596ef
知乎：https://www.zhihu.com/question/30269898
知乎：https://zhuanlan.zhihu.com/p/32356077