🌟

多腕バンディット入門:3つのアルゴリズムをpythonで実装する

2020/09/26に公開

概要

本記事では多腕バンディット問題の概説と、多腕バンディット問題に対する以下の3つの代表的なアルゴリズムをpythonによる実装とともに紹介します。

  • \epsilon-greedy
  • Upper Confidence Bound
  • Thompson Sampling

最後にそれぞれのアルゴリズムの簡単な比較実験を行います。

※この記事はこちらに加筆修正を加えたものです。元記事は非公開にしてます。

多腕バンディット問題

いくつかのアーム(スロット)があります。

アームを引くと確率的に報酬がもらえます。ここでは各アームiを引くと確率p_iで1の報酬がもらえ、1-p_iで報酬がもらえないものとします。p_iはアーム毎に異なります。アームを引く人はp_iを知りません。T回アームを引くとき、なるべく多くの報酬をもらいたい、というのが問題設定です。p_iが大きいアームをいかに早く見つけるか、が鍵になりそうですね。

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クラスはコンストラクタで成功確率pを渡します。これは本来はアームを引く人はわからない情報です。また、Armクラスは「アームを引く」ことに対応するメソッドplayを持ちます。これは確率的に報酬を返すメソッドで、確率pで報酬1がもらえますが、1-pでハズレ(報酬0)になります。各Armは成功した回数、失敗した回数を覚えておきます。この成功/失敗した回数はアームを引く人も参照できます。この情報をどう使うかが各アルゴリズムの大きな違いになります。それでは次章からアルゴリズムの紹介に入ります。お付き合いください!

\epsilon-greedy

まずは\epsilon-greedyアルゴリズムから紹介します。考え方は非常に単純です。このアルゴリズムでは、アームを引く際のポリシーとして「<b>探索</b>」と「<b>活用</b>」の2種類を使い分けます。アームを引く際、確率\epsilonで探索を、1-\epsilonで活用を選びます。\epsilonはハイパーパラメータであり、何かしらの知見をもとに人が事前に設定しておく必要があります。では、探索と活用はどのようなものなのでしょうか。次節でその説明を行いたいと思います!

探索

探索では過去の成功/失敗の情報は全く参照せず、全アームから一様ランダムにアームを選択します。「良さげなアームはおらんかーグヘヘ」と適当にアームを引くわけです。

活用

活用では今までの成功/失敗の情報をもとに、最も成功割合の高いアームを選択します。
例えばアームが3個あったとします(A, B, Cとします)。Aの成功割合が20%、Bが30%、Cが50%だとしたら、活用ではCを選択します。

アルゴリズム

ここまでの内容をアルゴリズムとしてまとめましょう。
\epsilon-greedyは以下の手順に従います。

  1. ハイパーパラメータ\epsilonに適当な値(0.3とか0.8とか)をセットする。
  2. 確率\epsilonで表のでるコインを1回投げる。
  3. 表が出た場合、探索を行う。すなわち、全アームから一様ランダムにアームを選択し、選択したームを引く。
  4. 裏が出た場合、活用を行う。すなわち、今までで最も成功割合の高いアームを選択し、選択したアームを引く。
  5. 2~5をT回繰り返す

\epsilonが小さいと活用ばかりになってしまい、情報が十分にないままアームを引き続けることになってしまいます。逆に、\epsilonが大きいと探索ばかりになってしまい、せっかく探索で得た情報をうまく活用できないままになってしまいます。\epsilon-greedyでは\epsilonをどう決めるかが鍵になります。

コード

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

\epsilon-greedyの探索では、過去の情報は全く参照せず全てのアームから一様ランダムにアームを選んでいました。
Tが十分に大きければ全アームまんべんなく探索ができますが、さすがに単純すぎるというか、もう少しうまくやれそうな気がしませんか?この点を改善したのがUpper Confidence Bound(以下、UCB)になります。
UCBでは確率は使わず、各アームに対してスコアを計算し、スコアが一番大きいアームを引きます。
スコアは成功割合の項とボーナス項の和で算出されます。ボーナス項はアームが選択された回数が多ければ多いほど小さくなります。
逆に、あまり選択されていないアームには多くのボーナスが与えられ、選択されやすくなります。スコアの詳細については次で説明します。

スコア

K回アームを引いたとき、アームiを引いた回数をN_{K,i}とします。また、\mu_{K,i}K回アームを引いたときの、アームiの成功割合とします。つまり\mu_{K,i} = \frac{成功回数}{N_{K,i}}となります。このとき、アームiのスコアs_is_i = \mu_{K,i} + \sqrt{\frac{2\log{K}}{N_{K,i}}}となります。
右辺の第2項がボーナス項です。アームiがあまり選択されないままでいると\sqrt{\log{K}}が支配的になり、多くのボーナスを獲得できることになります。逆に、iがたくさん選択されると\log{K}よりもN_{K,i}が支配的になり、ボーナス項が小さくなっていきます。
・・・ちょっと記号がごちゃごちゃ出てきて分かりにくいですね。具体例を使って整理しましょう。
\epsilon-greedyのときと同様に、アームは3個(A, B, C)とします。全部で100回アームを引いたとしましょう。結果は以下のようになったとします。

アーム 選択された回数 成功回数
A N_{100,A}=20 5
B N_{100,B}=30 10
C N_{100,C}=50 20

この結果をもとにスコアを計算します。のちの観察のため、スコアを成功割合の項ととボーナス項に分解しておきます。

アーム 成功割合\mu_{K,i} ボーナス項\sqrt{\frac{2\log{K}}{N_{K,i}}} スコア全体
A 5/20=0.25 \sqrt{2\log{100}/20} \sim 0.68 s_A \sim 0.93
B 10/30=0.33... \sqrt{2\log{100}/30} \sim 0.55 s_A \sim 0.89
C 20/50=0.4 \sqrt{2\log{100}/50} \sim 0.43 s_A \sim 0.83

次にアームを引くときは最もスコアが高いAが選択されます。Aは成功割合だけで見ると最も小さいですが、選択された回数が少ないため、ボーナス項が効いてスコアが高くなっています。逆に最も成功割合が高いCは選択された回数も多いため、スコアが小さくなっています。\epsilon-greedyと違い、UCBでは探索/活用という明確な区別はなく、最初は探索気味にアームを選択し、アームを引く回数が増えるにつれて徐々に活用の比重を高くしていくようなアルゴリズムになります。

コード

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ではベイズ統計を使います。
これまでのアームを引いた結果から、アームごとに成功確率pの事後確率分布を計算します。
その事後確率分布に従う乱数をアームごとに生成し、乱数値が最も大きいアームを引きます。
前2つのアルゴリズムは「期待値」に注目していましたが、このアルゴリズムでは成功確率pそのものに注目しているのが面白いところです。

pの事前分布と事後分布

ここではpの事前分布はベータ分布と仮定します。pはベルヌーイ分布のパラメータなので、事前分布をベータ分布とすると事後分布もベータ分布となります。詳しくは自然共役事前分布で調べてください。プログラムの開始時は、pBeta(1,1)に従うと仮定します。これは(0,1]上の一様分布と同じものになります。事後分布はBeta(成功回数+1, 失敗回数+1)になります。計算がとっても簡単ですよね!

コード

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回行います。\epsilon-greedyについては\epsilon=0.3, 0.5, 0.7の3パターンでシミュレートします。
最も期待報酬が大きくなるのは成功確率0.5のアームを引き続けたときで、500前後になります。
なので各アルゴリズムで得られる累積報酬はだいたい400前後くらいかな、という予想のもと実験を行います。

実験結果

アルゴリズム 平均 標準偏差 最大 最小
\epsilon-greedy(\epsilon=0.3) 436.46 20.40 480 375
\epsilon-greedy(\epsilon=0.5) 414.29 15.90 441 379
\epsilon-greedy(\epsilon=0.7) 382.96 16.30 433 347
UCB 409.08 21.39 457 346
Thompson sampling 466.38 22.69 519 393

考察

今回の実験では\epsilonが大きくなると性能が悪くなっていますが、成功確率によって変わりそうでもありますね。UCBはもっと性能いいのかと思っていましたが、そうでもないんだな、というのが率直な感想でした。UCBは最初は探索重視でアームを引くので、アームを引く回数が1000回程度だとうまく活用できないのかもしれません。今回の実験ではThompson samplingが一番性能が良いようです。たまたまでしょうが、一番良い結果で累積報酬が500を超えています。ただ、標準偏差もThompson samplingが一番大きいため、安定しないとも言えそうです。

まとめ

本記事では多腕バンディット問題に対する3つのアルゴリズムとpythonによる実装を紹介しました。また、3つのアルゴリズムに対して、簡単な比較実験を行いました。thompson samplingが最も良い結果になりましたが、様々なシチュエーションで比較する必要がありそうです。

今回の記事を書くにあたって参考にさせていただいたサイトです。
ALBERT Official Bolog, バンディットアルゴリズム 基本編
Slide Share, バンディットアルゴリズム入門と実践

コードは以下に置いてあります。
https://github.com/g0nta/multi_arm_bandit

Discussion