ただのメモ

他の人に見せても良い方のメモ

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(musigma):
      return np.random.normal(mu, sigma)
      #return 1/(math.sqrt(2 * math.pi) * sigma) * math.exp(- (x - mu)**2 / (sigma ** 2))

    def Gaussian_KL(mu1mu2 ,sigma1sigma2):
      #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 = [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 = [for i in range(100, 10000)]
    y = [DMED(i) for i in range(100,10000) ]

    plt.plot(x,y)
  • ガウス分布として、サンプルから近似して(尤度最大となる平均値と分散を持たせて、近似したガウス分布同士のKL距離を求めた。ガウス分布のKLダイバージェンスについては、こちらの記事が良かった。
  • f:id:medical-science:20211022225342p:plain
  • 意外と上手く行ったように見えるが、回数が増えるにつれて、報酬のぶれが大きくなっている。このブレは回数とどのような関係かが気になった。
  • 一旦、折れ線グラフではなく、散布図とする。
  • 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()
  • f:id:medical-science:20211022230802p:plain

  • 少しわかりにくい。回数で割った報酬値でグラフを書いてみる。
  • 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()
  • f:id:medical-science:20211022231024p:plain

  •  

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

Bye-Bye!