筆記-強化式學習演算法簡介：ε - greedy、UCB1

前言

在閱讀《強化式學習：打造最強 AlphaZero 通用演算法》一書時，對一些沒有聽過的演算法感到陌生，基於打基礎或是增廣見聞的念頭下，上網或問ChatGPT，搜尋了一些資料，整理並紀錄而成這篇文章。

正文

下面說的兩種選擇策略方法用來解決類似多臂拉霸機(Multi-Armed Bandit)的問題。多臂拉霸機是說有一台拉霸機，上面有多支拉桿，拉每支拉桿會掉出來的代幣的機率都不同但是固定，問題是我們在不知道各拉桿掉出代幣的機率的情況下，如何在有限的次數中獲得最多的代幣。

• ε - greedy(Epsilon - Greedy Algorithm)：

使用 1-ε 的機率選擇拉目前知道的價值最高的拉桿，ε 的機率去探索其他不知道價值的拉桿(ε 的數值介於 0 和 1)。當某支拉桿被拉了，會更新該拉桿(只有該拉桿)的價值：

V_t = (n-1)/n * V_t-1 + 1/n * R_t

V_t：所選拉桿本次的價值

n：所選拉桿的試驗次數

V_t-1：所選拉桿最近一次算出來的價值

R_t：所選拉桿本次獲得的回饋值

乍看這公式有點不好分析，但我想到用遞迴的方式解它(就是把V_t-1用它以V_t-2組成的公式帶入，一層層帶入直到V₁)。

• UCB1(Upper Confidence Bound, version 1)：

一開始會把所有拉桿拉過一遍後，更新所有拉桿的價值，然後下一次選擇價值最大的拉桿，再更新所有拉桿價值，反覆下去。更新拉桿價值公式如下：

w/n + (2*ln(t)/n)^1/2

n：所選拉桿的試驗次數

w：所選拉桿的成功次數

t：所有拉桿的試驗次數總和

可以看到公式加號左邊 w/n 是成功率，右邊隨著 n​ 的增長而減少，鼓勵對未充分探索的選項進行更多嘗試。而UCB1策略的遺憾值是有上限的，推導如多臂老虎机UCB1算法推导一文，很複雜在這裡就不細說了。

以上兩種策略方法可以應用在廣告推薦，例如一部分時間展示點擊率高的廣告，一部分時間展示新廣告。

參考

• 《強化式學習：打造最強 AlphaZero 通用演算法》
• 多臂老虎机UCB1算法推导
• ChatGPT

小結

因為工作以及開始閱讀另一本書的原因，還有就是懶惰(XD)，積了一些題目還沒細查並紀錄成文章，之後會慢慢補上來的。繼續趕路，繼續留腳印(XD)，週末愉快！