吃角子老虎機問題 (Bandit problem)

假想一個風險投資公司的目標為利益最大化,這時公司會面臨一個兩難問題:
- 何時去投資那些已經成功的公司,何時去投資那些還沒有成功但具有很大潛力的公司.
- 投資學告訴人們:收益總是伴隨著風險的.
- 一個成功的風投必須處理好這個勘探-開發兩難(exploration and exploitation tradeoff): 勘探過多意味著不能獲得較高的收益,而開發過多意味著可能錯過更高回報的機會.
在現實生活和商業中我們都會面對這種兩難,而且沒有正確的答案教你怎麼去做，可能的原因是我們對世界的認識不夠清楚. 但是在數學領域, 這個問題已經被研究過,被稱為多臂賭博機問題(multi-armed bandit problem),也稱為順序資源配置問題(sequential resource allocation problem). 它被廣泛應用於廣告推薦系統,源路由和棋類遊戲中.

問題描述

假設有 $K$ 個吃角子老虎機並排放在我們面前,我們首先給它們編號 $i=1,2,\cdots, K$ .
- 每一輪,我們可以選擇一個老虎機來按,同時記錄老虎機給出的獎勵.
- 假設各個老虎機不是完全相同的,經過多輪操作後,我們可以勘探出各個老虎機的部分統計資訊,然後選擇那個看起來獎勵最高的老虎機.
- 在多臂賭博機中,我們把老虎機稱為臂(arm).
這裡產生了兩個問題:
- 獎勵以什麼方式產生?
  - 隨機式(stochastic bandit): 臂 $i$ 的獎勵服從某種固定的概率分佈 $D_i$ .
  - 對抗式(adversarial bandit): 賭場老闆使壞,會動態調整臂的獎勵,比如讓你選的臂的獎勵很低,但是其它未選的臂獎勵變高.注意這裡賭場老闆不能也不會使全部臂的獎勵變為0,因為這樣會使我們無法得到獎勵,這時我們體驗到的是任何策略都是無差別的.
  - 馬可夫式(Markovian bandit): 臂獎勵由馬可夫鏈定義.
- 如何測量策略的好壞?
  - 簡單的以總獎勵作為測量策略好壞的標準是不切實際的. 所以我們定義遺憾(regret)作為策略好壞的指標,指的是我們可以達到的最理想總獎勵與實際得到的總獎勵.

隨機式(stochastic bandit)

本節中只討論隨機式多臂賭博機問題及UCB策略集,並假定各臂給出的獎勵 $X_i$ 是歸一化到 $[0,1]$ 之間的隨機變數,其期望值用 $\mu_i$ 表示. 在第 $t$ 輪的獎勵用 $X_{i,t}$ 表示.
- 假設 $X_i$ 與 $X_j$ 獨立，且 $X_{i,t}$ 與 $X_{i,s}$ 獨立
定義隨機式多臂賭博機
- 已知參數: 臂數(老虎機數) $K$ ,遊戲輪數 $T \geq K$ /
- 未知參數: 在 $[0,1]$ 區間上的各臂分佈 $D_i$
- 過程: 每輪遊戲(1)從 $1, \cdots, K$ 任意選擇一個臂 $i_t$ . (2)該臂獨立地給出服從 $D_i$ 的獎勵
- 同時我們需要定義策略的好壞指標: 累積遺憾(cumulative regret):
  - 定義: 給定一個策略 $A$ 和一個動作集 $1,\cdots i, \cdots ,K$ , 在 $T$ 時間後 $A$ 的累積遺憾是最佳臂的期望獎勵與 $A$ 的期望獎勵之差.
  - 由此定義在上述隨機變數 $X_i$ 中,我們總可以找到一個期望獎勵最大的臂,使得: $\mu_i^{*} = \max_{1 \leq i \leq K} \mu_i$ .
  - 而最佳的策略(選老虎機的順序)為 $i^* = \sigma(1,\cdots, i, \cdots, K)$ , 其中 $\sigma(\cdot)$ $為一排列組合.
  - 一個選擇策略 $A$ 在 $T$ 輪遊戲後獲得的獎勵定義為 $G_A(T) = \sum_{t=1}^T X_{i_t, t}$ .
  - 因此策略 $A$ 的累積遺憾 $R_A(T) = G_{i^*}(T) - G_A(T)$ , 其中 $G_{i^*}(T)$ 為理想策略所獲得的收益,該策略表示我們已知那個期望最大的臂並總選擇那個臂.
  - 所以一个好的策略應該最小化累積遺憾期望值 $\min E(R_A(T)) = \min \lbrace E(G_{i^*}(T)) - E(G_A(T)) = \mu^* T - E(G_A(T)) \rbrace$ .

UCB1 algorithm

UCB1演算法是常見的bandit策略,該演算法的精神被認為是樂觀地面對不確定性.
- 我們首先猜測各臂可能給出的獎勵,然後選擇那個最高臂,如果實際的獎勵較少,我們會儘快地降低對該臂的猜測.反之,我們就儘量多選擇這個臂.
- 這裡面的猜測,其實就是對各臂的獎勵建立了一個分數,通過動態調整這個分數,我們最終將確定那個期望獎勵最高的臂.
假設遊戲次數 $T$ 大於老虎機數 $K$ ，在前 $K$ 輪時，每臂均選擇一次(每個臂必須選過後才知道獎勵)，而在 $t=K+1, K+2, \cdots$ 時：
- 選擇分數 $I_i$ 最大的臂。 $I_i = \bar{x}_i + \sqrt{2 \frac{\log{t}}{n_i}}$ . $\bar{x}_i$ 是均值， $n_i$ 是臂 $i$ 目前累積被選擇的次數。
- 記錄獲得的獎勵，更新 $\bar{x}_i, n_i$ .

UCB1累積遺憾上界

當UCB1演算法被執行時,我們可以確定如下定理,其中 $\Delta_i = \mu^* - \mu_i$ .
- UCB1累積遺憾的期望不會超過 $8 \sum_{i: \mu_i \le \mu^*} \frac{\log T}{\Delta_i} + (1+\pi^2/3) \left( \sum_{j=1}^K \Delta_j \right)$ .
我們發現UCB1演算法的累積遺憾期望是 $O(\log{T})$ ,這是不是就足夠了呢? 當然不是,如果最壞情況下的累積遺憾過高,該演算法其實是沒有意義的.

吃角子老虎機問題(Bandit problem)

吃角子老虎機問題 (Bandit problem)

問題描述

隨機式(stochastic bandit)

UCB1 algorithm

UCB1累積遺憾上界

UCB1 worse case

參考資料

results matching ""

No results matching ""