2020-04-23 (Thu.)
\(\def\eps{\epsilon}\)
\(N\) 本の腕 \(\{0, 1, \ldots, N-1\}\) がある. 時刻 \(t\) に対して腕 \(i\) には報酬の確率分布 \(\mu^i_t : \mathbb R^+\) が決まっているが, この分布を直接観測することは出来ない.
時刻 \(t\) に依らずにこの分布が一定の場合を定常 (stationary) 多腕バンディットという. 逆に時刻で変化するような問題を非定常 (non-stationary) - という.
各時刻 \(t=0,1,2,\ldots\) にあなたは腕を一本選ぶことができる. 腕 \(i\) を選ぶと報酬 \(X^i_t \sim \mu^i_t\) が与えられる. 適切に腕を選ぶことで報酬の和 \[R = \sum_t X^i_t\] を最大化したい.
まずはじめは何もわからないので, すべての腕を一回ずつ引いて様子を見る. 報酬 \(X\) を蓄積して \(mu\) の平均を腕ごとに集計して, それが高いものを選ぶ. ただし集計が少ないと過小評価している可能性もあるので, そこを上手く頑張る.
素朴であるが定常多腕バンディットにはそれなりに利く手法.
パラメータ定数 \(\eps \in (0, 1)\) をはじめに設定する.
この 2. を探索, 3. を活用という.
形式的に疑似コードで記述すると次の通り.
N: int # 腕の本数
X_sum: List[int] = [0] * N # 各腕の報酬和
N_arm: List[int] = [0] * N # 各腕を試した回数
for t in 0..:
if t < N:
yield t
elif random.uniform() < eps:
yield random.uniform(0..N)
else:
yield argmax(X_sum[i] / N_arm[i] for i in 0..N)Epsilon-Greedy の改良. 探索の際に一様乱数にしているのが勿体なくて, そこでも報酬の集計を使いたい. softmax サンプリングを用いる.
活用時点での各腕の報酬の平均を \(\overline{X_i}\) とするとき, 腕 \(i\) を確率 \[p_i = \frac{\exp(X_i/T)}{\sum_j \exp(X_j/T)}\] で選ぶことにする.
ここで \(T\) は温度などと呼ばれるパラメータで, 時刻に従って \(T \colon T_0 \to T_1\) (\(T_0 > T_1 > 0\)) と変化させていく. この温度は十分大きいとき \(X_i/T\) の差が減ってくために活用はほとんど一様ランダムに近くなる. 一方で十分ゼロに小さいときは差が極端になるために活用はほとんど greedy に近くなる.
さらに Epsilon-Greedy の何がイケてないかを考えると, 単に平均だけを取って使ってることである. サンプリング数が少ないとき正しく分布の平均は取れない（大数の法則の逆）. その試行回数から信頼区間を見積もることはできる. その区間の上限を使うことで, 平均が小さくても試行回数が少ない腕を楽観的に使うようになる.
この手法では活用と探索を両方兼ねて区別していない.
ここで \(\overline{X_i}\) は今までに得た腕ごとの報酬の平均. \(c(i)\) は信頼区間の幅で, 次で計算される.
\[c(i) = \sqrt{\frac{2 \log t}{N_i}}\]
またここで分母の \(N_i\) は今までに腕 \(i\) を選んだ回数. \(t\) は時刻であるが, これは今までに腕を選んだ回数.
UCB1 と一緒に提案されてる別バージョンのアルゴリズム.
信頼区間を改良したもの. ただしこの改良は理論的なものというよりは経験的に書き換えたものに過ぎない.
\(c(i)\) を次に書き換える.
\[c(i) = \sqrt{\frac{\log t}{N_i} \min\{1/4, V_i\} }\] where \[V_i = \sigma_i^2 + \sqrt{\frac{2 \log t}{N_i}}\] \(\sigma_i^2\) は今まで得た報酬から見積もる標準偏差.