- こちらの本の一部をまとめる。
- 以前記事にしたUCB方策では、期待値最大ではないアームの誤選択率を1/t程度に制御することがしたいこと。なので、真の期待値についての、信頼区間を計算ですることが本質とは言えない。
- よって、直接的にアームの誤選択率を制御しようとするのが、MED方策(Minimal Empirical Divergence方策)である。
- そのうち、最も直観的な理解が容易なのが、DMED方策(Deterministic Minimal Empirical Divergence方策)である。
- 現在引くべきリストと、次に引くべきリストを用意する。次に引くべきリストに追加する要件として、
とする。
- DMED方策は理論限界と近いが、KL-UCB方策より劣る(ことが知られているらしい)。よって、少し補正した、IMED方策(Indexed Minimum Empirical Divergence方策)という、
を最小化するアームを引く方法がある。
-
import mathimport randomimport numpy as np
def Gaussian_KL(mu1, mu2 ,sigma1, sigma2):#return math.log(sigma2/sigma1) + (sigma1**2 + (mu1 - mu2)**2)/(2* (sigma2**2)) - 0.5return 0.5 * math.log(sigma2/sigma1) + (sigma1 + (mu1 - mu2)**2)/(2* (sigma2)) - 0.5
def action(i):mean = [0, 0, 1, 1, 1.1, 1.2]variance = [1, 10, 1, 3, 5, 0.5]return normal(mean[i], variance[i])
def DMED(T):K = 6#T = 10000#memory of past action & past action numberaction_number = [0] * Kaction_mean = [0] * Kaction_2mean = [0] * Kfor t in range(K):action_number[t] += 1act = action(t)action_mean[t] = actaction_2mean[t] = act**2LC = [i for i in range(K)]LN =t = K+1while t <= T:for i in LC:next_action = iact = action(next_action)action_mean[i] = (action_mean[next_action] * action_number[next_action] + act)/(action_number[next_action] + 1)action_2mean[i] = (action_2mean[next_action] * action_number[next_action] + act**2)/(action_number[next_action] + 1)action_number[i] += 1t += 1optimal_action = action_mean.index(max(action_mean))if t <= 2* K :LN.append(i)continuefor j in range(K):if action_number[j] * Gaussian_KL(action_mean[j], action_mean[optimal_action], action_2mean[j]-action_mean[j]**2, action_2mean[optimal_action]-action_mean[optimal_action]**2) <= math.log(t):if j not in LN:LN.append(j)LC = LNLN =
reward = 0for i in range(K):reward += action_mean[i] * action_number[i]
return reward
from matplotlib import pyplot as plt
x = [i for i in range(100, 10000)]y = [DMED(i) for i in range(100,10000) ]
plt.plot(x,y) - ガウス分布として、サンプルから近似して(尤度最大となる平均値と分散を持たせて、近似したガウス分布同士のKL距離を求めた。ガウス分布のKLダイバージェンスについては、こちらの記事が良かった。
- 意外と上手く行ったように見えるが、回数が増えるにつれて、報酬のぶれが大きくなっている。このブレは回数とどのような関係かが気になった。
- 一旦、折れ線グラフではなく、散布図とする。
-
import matplotlib.pyplot as plt# figureを生成するfig = plt.figure()# axをfigureに設定するax = fig.add_subplot(1, 1, 1)# axesに散布図を設定するax.scatter(x, y, s=1, c='b')# 表示するplt.show()
-
- 少しわかりにくい。回数で割った報酬値でグラフを書いてみる。
-
fig2 = plt.figure()ax2 = fig2.add_subplot(1,1,1)z = [y[i-100]/i for i in range(100, 10000)]ax2.scatter(x,z, s=1, c='r')plt.show()
-
-
Bye-Bye!