多腕バンディット入門：3つのアルゴリズムをpythonで実装する
概要
本記事では多腕バンディット問題の概説と、多腕バンディット問題に対する以下の3つの代表的なアルゴリズムをpythonによる実装とともに紹介します。
-
\epsilon - Upper Confidence Bound
- Thompson Sampling
最後にそれぞれのアルゴリズムの簡単な比較実験を行います。
※この記事はこちらに加筆修正を加えたものです。元記事は非公開にしてます。
多腕バンディット問題
いくつかのアーム（スロット）があります。
アームを引くと確率的に報酬がもらえます。ここでは各アーム
3つのアルゴリズムとpythonによる実装例
Armクラス
まず最初に共通で使うArmクラスを用意します。
from numpy.random import binomial
# p: 成功確率
class Arm:
def __init__(self, p):
self._p = p
self.success = 0
self.fail = 0
def play(self):
result = binomial(n=1, p=self._p)
if result == 1:
self.success += 1
else:
self.fail += 1
return result
Armクラスはコンストラクタで成功確率
\epsilon
まずは
探索
探索では過去の成功／失敗の情報は全く参照せず、全アームから一様ランダムにアームを選択します。「良さげなアームはおらんかーグヘヘ」と適当にアームを引くわけです。
活用
活用では今までの成功／失敗の情報をもとに、最も成功割合の高いアームを選択します。
例えばアームが3個あったとします(A, B, Cとします)。Aの成功割合が20%、Bが30%、Cが50%だとしたら、活用ではCを選択します。
アルゴリズム
ここまでの内容をアルゴリズムとしてまとめましょう。
- ハイパーパラメータ
\epsilon - 確率
\epsilon - 表が出た場合、探索を行う。すなわち、全アームから一様ランダムにアームを選択し、選択したームを引く。
- 裏が出た場合、活用を行う。すなわち、今までで最も成功割合の高いアームを選択し、選択したアームを引く。
- 2～5を
T
コード
from numpy.random import binomial, randint
from Arm import Arm
def calc_success_ratio(arm):
if arm.success + arm.fail == 0:
return 0
return arm.success / (arm.success + arm.fail)
def epsilon_greedy(arms, T, epsilon):
reward = 0
for i in range(T):
if binomial(n=1, p=epsilon) == 1:
# 探索ステップ : アームを一様ランダムに選ぶ
index = randint(0, 99)
else:
# 活用ステップ : 今までで一番成功確率の高いアームを選ぶ
avgs = [ calc_success_ratio(arm) for arm in arms]
index = avgs.index(max(avgs))
reward += arms[index].play()
return reward
Upper Confidence Bound
UCBでは確率は使わず、各アームに対してスコアを計算し、スコアが一番大きいアームを引きます。
スコアは成功割合の項とボーナス項の和で算出されます。ボーナス項はアームが選択された回数が多ければ多いほど小さくなります。
逆に、あまり選択されていないアームには多くのボーナスが与えられ、選択されやすくなります。スコアの詳細については次で説明します。
スコア
右辺の第2項がボーナス項です。アーム
・・・ちょっと記号がごちゃごちゃ出てきて分かりにくいですね。具体例を使って整理しましょう。
| アーム | 選択された回数 | 成功回数 |
|---|---|---|
| A | 5 | |
| B | 10 | |
| C | 20 |
この結果をもとにスコアを計算します。のちの観察のため、スコアを成功割合の項ととボーナス項に分解しておきます。
| アーム | 成功割合 |
ボーナス項 |
スコア全体 |
|---|---|---|---|
| A | |||
| B | |||
| C |
次にアームを引くときは最もスコアが高いAが選択されます。Aは成功割合だけで見ると最も小さいですが、選択された回数が少ないため、ボーナス項が効いてスコアが高くなっています。逆に最も成功割合が高いCは選択された回数も多いため、スコアが小さくなっています。
コード
from Arm import Arm
import math
def __init(arms):
for arm in arms:
arm.success = 1
return arms
def __get_score(arm, t):
ucb = math.sqrt(2*math.log(t) / (arm.success + arm.fail))
return arm.success / (arm.success + arm.fail) + ucb
def UCB(arms, T):
__init(arms)
reward = 0
for i in range(1, T+1):
scores = [__get_score(arm, i) for arm in arms]
max_score_index = scores.index(max(scores))
reward += arms[max_score_index].play()
return reward
Thompson sampling
Thompson samplingではベイズ統計を使います。
これまでのアームを引いた結果から、アームごとに成功確率
その事後確率分布に従う乱数をアームごとに生成し、乱数値が最も大きいアームを引きます。
前2つのアルゴリズムは「期待値」に注目していましたが、このアルゴリズムでは成功確率
p
ここでは
コード
from numpy.random import beta
from Arm import Arm
def thompson_sampling(arms, T):
reward = 0
for i in range(T):
# 事後分布から乱数を生成。これをpの推定値として扱う
rand_gened_params = [ beta(a=arm.success+1, b=arm.fail+1) for arm in arms ]
# 推定値が一番高いアームを選択
max_index = rand_gened_params.index(max(rand_gened_params))
reward += arms[max_index].play()
return reward
比較実験
紹介した3つのアルゴリズムの簡単な比較実験を行います。
成功確率が0.3のアームを4本、成功確率が0.5のアームを1本の計5本のアームに対して、1000回アームを引くシミュレーションを100回行います。
最も期待報酬が大きくなるのは成功確率0.5のアームを引き続けたときで、500前後になります。
なので各アルゴリズムで得られる累積報酬はだいたい400前後くらいかな、という予想のもと実験を行います。
実験結果
| アルゴリズム | 平均 | 標準偏差 | 最大 | 最小 |
|---|---|---|---|---|
|
|
436.46 | 20.40 | 480 | 375 |
|
|
414.29 | 15.90 | 441 | 379 |
|
|
382.96 | 16.30 | 433 | 347 |
| UCB | 409.08 | 21.39 | 457 | 346 |
| Thompson sampling | 466.38 | 22.69 | 519 | 393 |
考察
今回の実験では
まとめ
本記事では多腕バンディット問題に対する3つのアルゴリズムとpythonによる実装を紹介しました。また、3つのアルゴリズムに対して、簡単な比較実験を行いました。thompson samplingが最も良い結果になりましたが、様々なシチュエーションで比較する必要がありそうです。
今回の記事を書くにあたって参考にさせていただいたサイトです。
ALBERT Official Bolog, バンディットアルゴリズム 基本編
Slide Share, バンディットアルゴリズム入門と実践
コードは以下に置いてあります。
Discussion