ただのメモ

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

UCB方策

コードを書いて理解することと、日本語で説明して理解すること。この両方の理解が、相互に影響し合うことで、本質的な理解が得られる。

日本語だけだと、雰囲気はつかめても、実感がわかない。

コードだけだと、実感はあっても、概要はつかめない。

 

今回も、コードを書いていく

  • UCB方策。
  • UCBとは、信頼区間の上限(upper confidence bound)である。
  • これは、報酬の期待値が高そうに見える行動をしつつ、選択数が少ない行動もする。そのバランスをとり、理論限界を達成する方法。
  • UCBスコアの取り方は様々。
  • 今回は、ヘフディングの不等式に基づいた計算をする。
  • ヘフディングの不等式とは、i.i.d. 確率変数 X_i \in [0, 1]と任意の \Delta >0に対して、 \mathbb{P} [\hat{\mu_n} \leq \mu - \Delta ] \leq e^{-2n\Delta^2},  \mathbb{P} [\hat{\mu_n} \geq \mu + \Delta ] \leq e^{-2n\Delta^2}
  • 標本平均に補正項を乗せた形。 \bar{\mu_i}(t) = \hat{\mu_i}(t) + \sqrt{\frac{logt}{2N_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 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 UCB():
      K = 6
      T = 10000
      #memory of past action & past action number
      action_number = [0] * K
      action_mean = [0] * K
      for t in range(K):
        action_number[t] += 1
        action_mean[t] = action(t)

      for t in range(K, T):
        max_bar_mu = - 10 ** 8
        next_action = 10 ** 8
        for i in range(K):
          cand_max_bar_mu = action_mean[i] + math.sqrt(math.log(t)/(2 * action_number[i]))
          if max_bar_mu <= cand_max_bar_mu:
            max_bar_mu = cand_max_bar_mu
            next_action = i 
        #agent(next_action)
        action_mean[next_action] = (action_mean[next_action] * action_number[next_action] + action(next_action))/(action_number[next_action] + 1)
        action_number[next_action] += 1
        
      reward = 0
      for i in range(K):
        reward += action_mean[i] * action_number[i]

      return reward  
     
    UCB()
    11919.966940127577
  • UCBの方策が出来上がった。
  • ここで、Tの取り方によって、どのように学習が進んでいるかを知りたい。
  • なので、UCBをTの関数として、プロットしてみる。
  • from matplotlib import pyplot as plt

    x = [for i in range(100, 10000)]
    y = [UCB(i) for i in range(100,10000) ]

    plt.plot(x,y)
  • f:id:medical-science:20211016203303p:plainすると、このような(わりと)まっすぐなグラフが出来る。
  • Tが大きい程、最大報酬を得る回数が増えるので、Tの一次式となるのは頷ける。
  • もう少し複雑な状況を考えることも出来そうである。

バイバイ!