前回
ε-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を出すアームが適当に4本並べました。
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)]
実験
ハイパーパラメータに関係ないことを示すため、300回引くシミュレーション*1000回を別々に3回行いプロット。
Arm0: ベルヌーイ
最終的にベストなアームに収束していますが、初めの方は報酬の少ないアームにも積極的に探索に行っていることがわかります。
Arm1: 適当に作った分布
次回
Contextual Banditです。
参考文献
アルゴリズムは Bandit Algorithms for Website Optimization: Developing, Deploying, and Debugging のコードを参考にしました。