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(mu, sigma):

  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 = [i for i in range(100, 10000)]

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

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

バイバイ！