【AlphaZeroを理解する】多腕バンディット問題編

概要

囲碁、将棋、チェスなどのボードゲームにおいてルール以外のドメイン知識を利用せずに対戦用AIとしてのState-of-the-art（SOTA）を達成したAlphaZeroを細かく分解しながら理解していこうというシリーズです。今回はモンテカルロ法の基礎となる多腕バンディット問題についてまとめていきます。

※同シリーズの記事

【AlphaZeroを理解する】モンテカルロ法編

モンテカルロ木探索のベースになっている技術

モンテカルロ木探索はゲームAIの分野でよく用いられる木探索に対してモンテカルロ法を適用することで、AlphaBeta法などで必要な盤面評価がなくても探索を行えるようにしたものです。

最も単純なモンテカルロ法の適用例である多腕バンディット問題から着想を得て原始モンテカルロ法による探索が発案され、探索の効率化を目指してモンテカルロ木探索になったという背景があるので

多腕バンディット問題→原始モンテカルロ法→モンテカルロ木探索の順番で3回に分けてまとめていきます。

多腕バンディット問題

当たりの出る確率が異なるスロットが3台あり、スロットを引ける回数が合計100回の時、当たりを引ける回数を最大化するためにはどのような戦略が最適であるか？（スロットの当たりが出る確率はプレイヤーからは分からないものとする）

という問題が多腕バンディット問題と呼ばれおり、強化学習にも登場する探索と利用のバランシング問題の基礎になっています。

この時、当たりを引く確率を最大化するために採れる戦略にはどのようなものがあるでしょうか？

例えば、各スロット最初は20回ずつ均等に引き、合計60回の試行の中で最も当たりの出た回数が多かったスロットに残りの40回を割り当てるという方法があります。これをPythonで実装してみると以下のようになります。

import numpy as np
import random

class Bandit:
    def __init__(self):
        # それぞれのスロットマシンの出る確率は[0.3, 0.5, 0.7]とする
        self.prob = [0.3, 0.5, 0.7]
        # スロットを引ける回数は100回とする
        self.n = 100
        # 各スロットの選ばれた回数
        self.select_counts = [0, 0, 0]
        # 各スロットの当たった回数
        self.hit_counts = [0, 0, 0]
        # 各スロットの報酬の合計
        self.rewards = [0, 0, 0]

    def play(self):
        # スロットを引く
        for i in range(self.n):
            # 最初の各スロットを20回ずつ選択する
            if i < 20:
                slot = 0
            elif i < 40:
                slot = 1
            elif i < 60:
                slot = 2
            else:
                # 当たりが出た回数が最も多いスロットを選択する
                slot = np.argmax(self.hit_counts)
            # スロットを引く
            reward = 1 if random.random() < self.prob[slot] else 0
            # 各スロットの選ばれた回数を更新
            self.select_counts[slot] += 1
            # 各スロットの当たった回数を更新
            self.hit_counts[slot] += reward
            # 各スロットの報酬の合計を更新
            self.rewards[slot] += reward

    def reset(self):
        # 各スロットの選ばれた回数
        self.select_counts = [0, 0, 0]
        # 各スロットの当たった回数
        self.hit_counts = [0, 0, 0]
        # 各スロットの報酬の合計
        self.rewards = [0, 0, 0]

    def show_result(self):
        # 各スロットの選ばれた回数を表示
        print('select_counts:', self.select_counts)
        # 各スロットの当たった回数を表示
        print('hit_counts:', self.hit_counts)
        # 各スロットの報酬の合計を表示
        print('rewards:', self.rewards)
        # 合計報酬を表示
        print('total reward:', sum(self.rewards))

if __name__ == '__main__':
    bandit = UCBBandit()
    # 1000回実行して平均報酬を計算
    total_rewards = []
    for i in range(1000):
        bandit.play()
        if i < 3:
            print("#",i + 1,'回目')
            bandit.show_result()
        total_rewards.append(sum(bandit.rewards))
        bandit.reset()
    print("#1000回の平均報酬")
    print('mean rewards:', np.mean(total_rewards))

上記コードを実行すると

# 1 回目
select_counts: [20, 20, 60]
hit_counts: [8, 7, 38]
rewards: [8, 7, 38]
total reward: 53
# 2 回目
select_counts: [20, 20, 60]
hit_counts: [7, 11, 38]
rewards: [7, 11, 38]
total reward: 56
# 3 回目
select_counts: [20, 60, 20]
hit_counts: [8, 36, 14]
rewards: [8, 36, 14]
total reward: 58
#1000回の平均報酬
mean rewards: 56.962

のように、必ずしも当たりの出る確率が最高のスロットを選べるようになるとは限らないことがわかります。

上記の方法には以下の２つの問題があります。

たまたま確率の低いスロットで当たりが多く出てしまった場合、後半の40回の試行で損なスロットを引くことになってしまう
全てのスロットに均等に前半の試行を割り当てており、効率が悪い

これらの問題を解決するために導入されたのがUCB方策です。 UCB方策は各スロットの評価を以下の式で評価し、最も大きいUCB値を持つスロットを引きます。

$UCB = \displaystyle \overline{x_i} + \sqrt{\frac{2\ln{N}}{n_i}}$

$\overline{x_i}$ はi番目のスロットの平均得点、 $N$ は全スロットを引いた合計回数、 $n_i$ はi番目のスロットを引いた回数です。このUCB値はスロットを十分な回数引くと最終的に期待値が最大のスロットのUCB値が最大になることが数学的に保証されています。

UCB方策を用いたバンディットをPythonで実装したのが以下のコードです。

import numpy as np
import random

class UCBBandit:
    def __init__(self):
        # それぞれのスロットマシンの出る確率は[0.3, 0.5, 0.9]とする
        self.prob = [0.3, 0.5, 0.7]
        # スロットを引ける回数は100回とする
        self.n = 100
        # 各スロットの選ばれた回数
        self.select_counts = [0, 0, 0]
        # 各スロットの当たった回数
        self.hit_counts = [0, 0, 0]
        # 各スロットの報酬の合計
        self.rewards = [0, 0, 0]
        # 各スロットのUCB値
        self.ucb_values = [0, 0, 0]

    def caluculate_ucb_value(self, i):
        # 各スロットのUCB値を計算
        for j in range(3):
            if self.select_counts[j] == 0:
                # まだ一度も選ばれていないスロットがある場合はそのスロットを大きな値にする
                self.ucb_values[j] = 1e10
            else:
                # 各スロットのUCB値を計算
                self.ucb_values[j] = self.rewards[j] / self.select_counts[j] + np.sqrt(2 * np.log(i) / self.select_counts[j])

    def play(self):
        # スロットを引く
        for i in range(self.n):
            # UCB値が最も大きいスロットを選択する
            slot = np.argmax(self.ucb_values)
            # スロットを引く
            reward = 1 if random.random() < self.prob[slot] else 0
            # 各スロットの選ばれた回数を更新
            self.select_counts[slot] += 1
            # 各スロットの当たった回数を更新
            self.hit_counts[slot] += reward
            # 各スロットの報酬の合計を更新
            self.rewards[slot] += reward
            # 各スロットのUCB値を更新
            self.caluculate_ucb_value(i + 1)

    def reset(self):
        # 各スロットの選ばれた回数
        self.select_counts = [0, 0, 0]
        # 各スロットの当たった回数
        self.hit_counts = [0, 0, 0]
        # 各スロットの報酬の合計
        self.rewards = [0, 0, 0]
        # 各スロットのUCB値
        self.ucb_values = [0, 0, 0]

    def show_result(self):
        # 各スロットの選ばれた回数を表示
        print('select_counts:', self.select_counts)
        # 各スロットの当たった回数を表示
        print('hit_counts:', self.hit_counts)
        # 各スロットの報酬の合計を表示
        print('rewards:', self.rewards)
        # 合計報酬を表示
        print('total reward:', sum(self.rewards))

if __name__ == '__main__':
    bandit = UCBBandit()
    # 1000回実行して平均報酬を計算
    total_rewards = []
    for i in range(1000):
        bandit.play()
        if i < 3:
            print("#",i + 1,'回目')
            bandit.show_result()
        total_rewards.append(sum(bandit.rewards))
        bandit.reset()
    print("#1000回の平均報酬")
    print('mean rewards:', np.mean(total_rewards))

UCB方策を用いたバンディットの実行結果は以下のようになります。

# 1 回目
select_counts: [14, 25, 61]
hit_counts: [3, 11, 39]
rewards: [3, 11, 39]
total reward: 53
# 2 回目
select_counts: [13, 34, 53]
hit_counts: [4, 22, 39]
rewards: [4, 22, 39]
total reward: 65
# 3 回目
select_counts: [17, 17, 66]
hit_counts: [5, 5, 45]
rewards: [5, 5, 45]
total reward: 55
#1000回の平均報酬
mean rewards: 58.735

このようにUCB方策によるバンディットの方が報酬平均が高くなっていることがわかります。

このUCB方策をゲーム木探索に適用したものがUCTアルゴリズムで、モンテカルロ木探索の基礎になっています。

UnityとゲームAIと将棋

Unity、Pythonを中心にゲーム開発やゲームAI開発の技術メモ等、たまに将棋も

【AlphaZeroを理解する】多腕バンディット問題編

概要

モンテカルロ木探索のベースになっている技術

多腕バンディット問題