前回

ε-Greedy+softmaxについてやった。

UCB(Upper Confidence Bound)

UCBの説明

これまでのアルゴリズムはアームの期待報酬から引くかどうかを定めていたけれども、アームを引いた回数（どれくらいそのアームについて知識があるか）が考慮されていなかった。それを踏まえた上で、”ボーナス”という変数を追加してより知識が少ないアームを積極的に探索するようにした手法。 アームの期待値＋ボーナス の値に基づいてアームを決定する。

理論的な説明

海外のPh.Dの方のブログより。

UCBのアルゴリズム

n_armsがアームの数です。math.sqrt((2 * math.log(total_counts)) / float(self.counts[arm]))がこれまでの探索回数に基づいたボーナスと4バレル部分で、探索が少ないアームほど大きくなります。他のアルゴリズムよりも有利な点はハイパーパラメータがないところ。

class UCB():
    ....
    def select_arm(self):
        # とりあえず全てのアームを一回引く
        n_arms = len(self.counts)
        if sum(self.counts) < n_arms:
            return sum(self.counts)
        else:
            # UCBを計算して
            ucb = list(np.zeros(n_arms))
            total_counts = sum(self.counts)
            for arm in range(n_arms):
                bonus = math.sqrt((2 * math.log(total_counts)) / float(self.counts[arm]))
                ucb[arm] = self.values[arm] + bonus

            # max(UCB)のアームを選択する
            return ind_max(ucb_values)

アームの定義

前回に引き続き2つのアームを使用。

Arm0: ベルヌーイ

pの確率で0か1を出すアーム。 p = 0.1 ~ 0.9を適当に10本並べます。

class Arm0():
    def __init__(self, p):
        self.p = p

    def draw(self):
        if random.random() > self.p:
            return 0.0
        else:
            return 1.0

arms = [Arm0(p) for p in np.linspace(0.1, 0.9, 10)]

Arm1: 適当に作った分布

p,qに従って 0, 0.5, 1を出すアームが適当に４本並べました。

class Arm1():
    def __init__(self, p, q):
        self.p = p
        self.q = q

    def draw(self):
        rnd = random.random()
        if self.p > rnd:
            return 0.0
        elif self.q > rnd > self.p:
            return 0.5
        else:
            return 1.0

arms = [Arm1(0.0, 0.5), Arm1(0.1, 0.5), Arm1(0.2, 0.5),  Arm1(0.3, 0.5)]