Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
3
Help us understand the problem. What is going on with this article?
@kex5n

パックマンAIを作るまで(強化学習入門~多腕バンディット問題編)

More than 1 year has passed since last update.

経緯

以前、こんな内容の強化学習の勉強会に参加し、強化学習楽しそうだなと思っていたところ、
ちょうど新入社員向けにAIの紹介をする機会があり、ドヤれる&自分も勉強できる絶好の機会だと思いパックマンAIを作ることにした。

目標

kerasRLとOpenAI Gym(Atariのゲームとかをpythonで動かすやつ)を使って、人間より強いパックマンを作る。

この記事の主な内容

強化学習とはなんぞやみたいなことは書きません。(というかそんな偉そうなこと書けません)
なので、強化学習とは的なものは他の記事やサイトで学んでください。
この記事では、強化学習を学ぶにあたってよく分からなかったことを自分で調べてみた結果を共有していくつもりです。
それでははじめていきたいと思います。

まず調べてみた

エージェントを使って価値関数を更新して戦略を決めていく…みたいな流れは何となくわかった。
しかし価値関数が出てきたあたりからはてなが浮かび始め、マルコフ決定過程などが出てくるとさっぱり訳が分からん。SだのTだのどういうこっちゃ。

多腕バンディット問題

なんでこんなに複雑なのかというと、どうやらエージェントが行動すると状態遷移があるかららしい(スマブラだったら攻撃したら敵は反撃してくるし、待ってても敵は攻撃してくる。そんな感じ)。諸悪の根源の状態遷移がない強化学習の例として"多腕バンディット問題"というのがあるらしい。これは聞いたことがあったので、これから取り組んでみることにした。

多腕バンディット問題というのは、当たる可能性が異なるスロットがあるとき、利益が最大になるようにスロットを回していくにはどうすればいいかという問題。この問題の肝は、仮に「このスロットは当たりやすそう」と発見したとしても他のスロットはもっと当たるかもしれない。そうなったとき、同じスロットを回し続けるべきかほかのスロットを試すべきか。それが問題だという点。
ギャンブル界のシェイクスピアの誕生である。

ちなみにさっき言った通りこの多腕バンディット問題には状態遷移がない。演出もないし、当たりまくったからといって確率を変えてくる店でもなければ席を奪おうとしてくるおじさんもいない。状態(当たる確率など)は常に一定である。

活用と探索

このような前提があるとき、大切になってくるのが活用探索という概念らしい。
活用というのは過去の情報を利用することで、つまり現時点で一番当たると思われるスロットを回し続けること(最適化問題では貪欲法(greedy algorithm)という。線形計画問題とかで学んだなぁ)。
これに対して探索はたまに別のスロットを回してみること。

多腕バンディット問題の解法のひとつとしてε-greedy algorithmというものがあるらしい。
変なギリシャ文字が出てきてアレルギーを起こすかもしれないが、なんてことはない、ただある確率εでほかのスロットも回す貪欲法だよ~というだけ。

実装

スロットマシンの数とイプシロンの数を指定すると、各スロットマシンの当たる確率をランダム生成した後10~300エピソードを10刻みで行い、それぞれで何%当たったかを表すグラフを返す関数。
『Pythonで学ぶ強化学習』code3-1~3を参考にしました。)


import random
import numpy as np

class Slot_Machine():
    #Slot_Machineクラスでmax_episode_steoとslot_countを定義。
    def __init__(self, win_probs, max_episode_step=30):
        self.win_probs = win_probs
        self.max_episode_step = max_episode_step
        self.slot_count = 0

    def __len__(self):
        return len(self.win_probs)

    def reset(self):
        self.slot_count = 0

    #スロットを一回回す関数。actionには選ばれたマシンの番号が渡される。
    def step(self, action):
        final = self.max_episode_step - 1
        if self.slot_count > final:
            raise Exception("The step count exceeded maximum. \
                            Please reset env.")
        else:
            done = True if self.slot_count == final else False

        if action >= len(self.win_probs):
            raise Exception("The No.{} machine doesn't exist.".format(action))
        else:
            win_prob = self.win_probs[action]
            if random.random()<win_prob:
                reward = 1.0
            else:
                reward = 0.0
            self.slot_count += 1
            return reward, done

class EpsilonGreedyAgent():

    def __init__(self, epsilon):
        self.epsilon = epsilon
        self.V = [] #Vには各スロットでこれまでに当たった確率が格納されていく。

    #どのスロットを回すかを選ぶ関数
    def policy(self):
        machines = range(len(self.V))
        #一様分布がεより小さくなったときスロットを選びなおす、つまり確率εでスロットを選びなおす。
        if random.random() < self.epsilon:
            return random.choice(machines)
        #確率が一番大きいもの、つまり一番当たるスロットを選ぶ
        else:
            return np.argmax(self.V)

    def play(self, env):
        # Initialize estimation.
        N = [0] * len(env)
        self.V = [0] * len(env)

        env.reset()
        done = False
        rewards = []
        while not done:
            selected_machine = self.policy()
            reward, done = env.step(selected_machine)
            rewards.append(reward)

            n = N[selected_machine]
            win_average = self.V[selected_machine]
            new_average = (win_average * n + reward) / (n + 1)
            N[selected_machine] += 1
            self.V[selected_machine] = new_average

        return rewards

if __name__ == "__main__":
    import pandas as pd
    import matplotlib.pyplot as plt

    def main(machine_num,epsilon):
        #各マシンの当たる確率をランダム生成
        win_probs = np.random.rand(machine_num)
        win_probs = np.round(win_probs,decimals=1)
        env = Slot_Machine(win_probs)

        game_steps = list(range(10,310,10))
        result = {}
        agent = EpsilonGreedyAgent(epsilon)
        means = []
        #スロットを10回回した時、20回回した時、…の結果を調べるためにSlot_Machineに様々なmax_episode_stepsを渡す。
        for s in game_steps:
            env.max_episode_steps = s
            rewards = agent.play(env)
            means.append(np.mean(rewards))
        result["epsilon={}".format(epsilon)] = means
        result["machine slot count"] = game_steps
        result = pd.DataFrame(result)
        result.set_index("machine slot count", drop=True, inplace=True)
        result.plot.line(figsize=(10,5))
        plt.show()

main(10,0.1)

感想

下は参考書通りのコードを動かしたもので、異なるεで[0.1,0.5,0.1,0.9,0.1]の確率で表が出る5枚のコインでコイン投げを行った結果。
Figure_1.png

参考書によるとε=0.1,0.2は高い確率に収束していくようだが、何回コードを動かしてみても発散してしまった。
どこかコードがおかしいのだろうか…
それにしてもこのアルゴリズムは運によるところが大きいと思われるが、どれくらいの施工回数に対してハイパーパラメータεはどれくらいがよいのかというのを定量的に言うことはできるのだろうか。
また、非常にヒューリスティックなアルゴリズムだと思われるが、どのような根拠があればうまくいっているということが言えるのだろうか。非常に気になる。

実社会での利用シーン

ギャンブルじみた話に徹してしまったが、広告分野では割と使われるアルゴリズムらしい。
このあたりの記事も読んでいきたい。

『多腕バンディットによる表示コンテンツの最適化』
『Web広告配信における多腕バンディット問題、Mortal Multi-Armed Bandits Problemとアルゴリズム』

参考書籍

『Pythonで学ぶ強化学習』

3
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
kex5n

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
3
Help us understand the problem. What is going on with this article?