DMED方策とKL距離 - ただのメモ

こちらの本の一部をまとめる。
以前記事にしたUCB方策では、期待値最大ではないアームの誤選択率を1/t程度に制御することがしたいこと。なので、真の期待値についての、信頼区間を計算ですることが本質とは言えない。
よって、直接的にアームの誤選択率を制御しようとするのが、MED方策（Minimal Empirical Divergence方策）である。
そのうち、最も直観的な理解が容易なのが、DMED方策（Deterministic Minimal Empirical Divergence方策）である。
現在引くべきリストと、次に引くべきリストを用意する。次に引くべきリストに追加する要件として、 $N_j(t) d(\hat{\mu}_j(t) , \hat{\mu}^{*}(t) ) \leq log(t)$ とする。
DMED方策は理論限界と近いが、KL-UCB方策より劣る（ことが知られているらしい）。よって、少し補正した、IMED方策（Indexed Minimum Empirical Divergence方策）という、 $I_i(t) = N_i(t) d(\hat{\mu}_j(t) , \hat{\mu}^{*}(t) ) + log(N_i(t))$ を最小化するアームを引く方法がある。
import math

import random

import numpy as np

def normal(mu, sigma):

  return np.random.normal(mu, sigma)

  #return 1/(math.sqrt(2 * math.pi) * sigma) * math.exp(- (x - mu)**2 / (sigma ** 2))

def Gaussian_KL(mu1, mu2 ,sigma1, sigma2):

  #return math.log(sigma2/sigma1) + (sigma1**2 + (mu1 - mu2)**2)/(2* (sigma2**2)) - 0.5

  return 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 number

  action_number = [0] * K

  action_mean = [0] * K

  action_2mean = [0] * K

  for t in range(K):

    action_number[t] += 1

    act = action(t)

    action_mean[t] = act

    action_2mean[t] = act**2

  LC = [i for i in range(K)]

  LN =

  t = K+1

  while t <= T:

    for i in LC:

      next_action = i

      act = 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] += 1

      t += 1

      optimal_action = action_mean.index(max(action_mean))

      if t <= 2* K :

        LN.append(i)

        continue

      for 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 = LN

    LN =

  reward = 0

  for 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()
回数が少ないところでは、最大期待値報酬の1.2よりぶれるけれど、回数が大きくなるにつれて、1.2に集まっていくことがわかる。しかし、相変わらず1付近に集まっている傾向があるので、DMED方策も改善の余地がある。

Bye-Bye！