大家好，我是毛毛。
今天是Day 20
那麼就來開始看UCB吧 ヽ(✿ﾟ▽ﾟ)ノ

Reinforcement learning-based QoS/QoE-aware service function chaining in software-driven 5G slices

這篇是2018年七月刊登在Trans. Emerg. Telecommun. Technol.上的論文。

昨天講過了Softmax，今天就來搞懂Upper Confidence Bound（UCB）啦~

Upper Confidence Bound

• 
  • 這是2002年Peter Auer在他的論文《Finite-time Analysis of the Multiarmed Bandit Problem》提出的一個簡單、被廣泛使用的UCB1的policy。
  • 這個policy就是要在所有的機器中，選擇紅框處的值最大的機器
  • xi：觀察到的第j個機器的平均回報
  • nj：目前為止選到第j個機器的次數
  • n：目前為止有選過任一個機器的次數

藉由上面UCB1，作者將其套用在他的環境中：

• 
  • 上面的xi就是的Q-value值
  • countj：目前為止有使用過VNFj的次數
  • count：目前為止所有已經處理完成的SFC需求數量

這邊就來實際的看看UCB怎麼運作的，以MAB的問題來做：
在一開始，我們先假設每個老虎機的期望值是相同的，如下圖：

• 

  • 上圖中的虛線代表著期望值，縱軸表示老虎機可能帶來的收益，實線則分別代表每台老虎機的實際平均值，但實線我們並不曉得，所以我們就是要不斷的嘗試去估算出每個老虎機的期望值。
  • 灰色方框則是置信區間（Confidence Bound）
  • 接下來，每一輪我們要做的事就是選擇區間上界最大（也就是灰色區間的頂）的老虎機，然後給他按下去 σ ﾟ∀ ﾟ) ﾟ∀ﾟ)σ

• 

  • 一開始因為每一台的區間上界都一樣，所以我們就隨便選一台，假設我們選了中間這台按下去，會看到它的區間的灰色方框下降，這是因為按完之後，我們發現這台老虎機很坑，它給的獎勵有夠爛，低於一開始的期望值，於是在重新計算所有的期望值後會發現中間這台的期望值就下降了。
  • 除了區間上界下降以外，它的置信區間也會變小，因為比起上一輪，觀察的次數增加了，也就是信心升高，所以這個置信區間長度就變小了。

• 

  • 可以看到在Step1，除了中間那台以外，其他的區間上界都一樣，所以這邊我們也隨便選一個，假設我們選右邊數來第二個（手指指的），那它的平均獎勵是高於我們虛線的，因此它的區間上界會上升，但置信區間會變小。

• 

  • 在Step2時，左邊兩台和最右邊那台老虎機的區間上界是一樣，那這邊假設我們隨機選，選擇最左邊這台，按了下去，其實老虎機給獎勵是一個隨機的事件，也就是有可能好也有可能壞，最左邊這台老虎機雖然它實際的平均值是不高的，但假設現在運氣很好，剛好出現了機率很低的大獎，那這台的區間上界就會變高，置信區間變小。

• 

  • 接著在Step3從左二跟右一的老虎機選一個，假設選左二，那它的區間上界會下降，置信區間變小。

• 

  • 接著按下了右一這台，結果得到了一個很好的觀察值，所以區間上界上升，置信區間縮小。
  • 而右一其實實際上是最佳的老虎機，所以即便置信區間縮小了，它的區間上限還是高於其他幾台。

• 

  • 接續Step5，選擇的老虎機還是右一，因為在Step5右一的老虎機的區間上界還是最高的。
  • 但是由於對右一的信心愈來愈高，它的置信區間也會愈來愈小，可能就會導致它的區間上界不是最高的。

• 

  • 在Step6有說到，它的區間上界有可能不是最高的，但這也不是壞事，這樣可以給其他的老虎機一點機會，看看其他台的區間上界會不會變高。
  • 以這個圖為例，雖然在Step7~StepN之間可能右一的區間上界會有不是最高的時候，但是選擇到右一這台的次數還是會有很多次，所以它的置信區間會愈來愈小，直到結束。

以上就是UCB如何運作的~ (´◓Д◔`)
大家明天見