強化学習?でジャンケンの出す手に偏りがあるAさんに高確率で勝つ方法を探す

強化学習に入門したいのですが、入門にちょうどいい難易度の本とか記事とか見当たらなかったんで、簡単そうな問題を考えてそれに強化学習に当てはめて解いてみようと思いました。

あ、Python3.5.2でやってます。

ジャンケンの出す手に偏りがある人に、高確率で勝つ選択を見つける問題なんかめっちゃシンプルでちょうどいいじゃないかなーと思いついたのでやってみようと思います。

色々検索して見たところ、多腕バンディット問題というのがかなり近い性質のものであることがわかった。

ここでは詳しくは書きませんが、情報はたくさんあるみたいなのでそちらを参照くだしあ。

http://yamaimo.hatenablog.jp/entry/2015/08/20/200000 http://qiita.com/ta-ka/items/90f0580fd15293c35881

強化学習そのものについてこのあたりを読んだ。今回の問題には直接関係ないけど。

http://qiita.com/Hironsan/items/56f6c0b2f4cfd28dd906

前提

まず、Aさんという人がいて、Bさんは今からこの人と2,000回ジャンケンしたいと思っています(2,000回とかやりたくねえ)。

Aさんはちょっと天然さんでして、どうも出す手が偏っていて、やたらパーばかり出す人です。出す手は確率は以下だとしましょう。ただしジャンケン相手であるエージェントのBさんはこのことを知りません。

  • グー(G): 0.3
  • チョキ(C): 0.1
  • パー(P): 0.6

すると、バンディット問題におけるアームと確率は以下のようになります。要するにBさんが手を出したときに勝てる確率ですね。

  • グー(G): 0.1
  • チョキ(C): 0.6
  • パー(P): 0.3

この前提がある場合、Bさんはひたすらチョキを出すことが最適解なわけですね。それを機械で求めてみましょう。

実装

ソースコードはほぼこちらのコピペです。

https://iridge.jp/blog/201412/5508/

使う定数を定義する。

import numpy as np
import matplotlib.pyplot as plt

TRIAL_NUMBER = 2000
# 出す手ごとの勝てる確率
OBVERSE_PROP = np.array([0.1, 0.6, 0.3])
# 勝負したときの勝敗 { 0 or 1 }
RESULT_DATA = np.array(
    [np.random.binomial(1, p, TRIAL_NUMBER)for p in OBVERSE_PROP])

COINS = range(3)

Greedyアルゴリズムを実装。今回時間がなかったので中身はよく読んでいない。強化学習のアルゴリズムだと思う。

class Greedy(object):
    def __init__(self):
        self.rewards = dict()
        self.cnt = 0
        self.result = np.zeros(TRIAL_NUMBER)
        self.choiced_coins = np.array([])

    def get_reward(self, coin):
        return RESULT_DATA[coin][self.cnt]

    def estimate_q(self, coin):
        """説明を省きたいので、漸進的ではない方法で実装"""
        reward = self.rewards.get(coin)
        q = sum(reward) / float(len(reward)) if reward else 0
        return q

    def choice_coin(self):
        choiced_coin = np.argmax(
            [self.estimate_q(coin) for coin in COINS])
        return choiced_coin

    def first_throw(self):
        choiced_coin = np.random.choice(
            list(set(COINS) - set(self.rewards.keys())))
        self.rewards[choiced_coin] = [self.get_reward(choiced_coin)]
        self.cnt += 1

    def throw(self):
        choiced_coin = self.choice_coin()
        self.choiced_coins = np.append(self.choiced_coins, choiced_coin)
        reward = self.get_reward(choiced_coin)
        self.rewards[choiced_coin].append(reward)
        self.result[self.cnt] = reward
        self.cnt += 1

    def execute(self):
        print('execute')
        [self.first_throw() if i < len(COINS) else self. throw()
         for i in range(TRIAL_NUMBER)]

実はGreedyアルゴリズムは、最初の方に出した手の結果に大きく依存されてしまうため、うまく振る舞えないことがある。実際にやってみたら、勝率0.1であるグーを出し続ける選択をしてしまった。

そこでGreedyアルゴリズムを拡張したε-Greedyアルゴリズムを実装。超ざっくりいうと、εの割合で探索を続けるというものですが、詳しい説明は割愛。

class EpsilonGreedy(Greedy):
    def __init__(self, epsilon):
        self.epsilon = epsilon
        super(EpsilonGreedy, self).__init__()

    def choice_coin(self):
        is_random = np.random.choice(
            2, 1, p=[1 - self.epsilon, self.epsilon])[0]
        choiced_coin = (np.random.choice(COINS) if is_random else
                        np.argmax([self.estimate_q(coin) for coin in COINS]))
        return choiced_coin

プロットする関数と、アルゴリズムの実行。

def verification(alg, title):
    print('choiced_coins: %s' % alg.choiced_coins)
    print('グーを出した回数: %s' % alg.choiced_coins[alg.choiced_coins==0].size)
    print('チョキを出した回数: %s' % alg.choiced_coins[alg.choiced_coins==1].size)
    print('パーを出した回数: %s' % alg.choiced_coins[alg.choiced_coins==2].size)

    plt.plot(np.cumsum(alg.result) / np.arange(1, TRIAL_NUMBER+1),label=title)
    plt.legend(loc='lower right')
    plt.axhline(y=0.7, color='gray')
    plt.xlabel('play count')
    plt.ylabel('rate')
    plt.ylim(0, 0.8)
    plt.show


epsilons = [0, 0.1, 0.2, 0.3, 0.4]
epsilon_greedy_list = [EpsilonGreedy(epsilon) for epsilon in epsilons]
[eg.execute() for eg in epsilon_greedy_list]
[verification(eg, 'epsilon='+str(eg.epsilon)) for eg in epsilon_greedy_list]

アウトプット。

choiced_coins: [ 1.  1.  1. ...,  1.  1.  1.]
グーを出した回数: 0
チョキを出した回数: 1997
パーを出した回数: 0
choiced_coins: [ 1.  1.  1. ...,  1.  1.  2.]
グーを出した回数: 71
チョキを出した回数: 1845
パーを出した回数: 81
choiced_coins: [ 1.  1.  1. ...,  1.  1.  1.]
グーを出した回数: 122
チョキを出した回数: 1741
パーを出した回数: 134
choiced_coins: [ 0.  1.  1. ...,  0.  1.  0.]
グーを出した回数: 189
チョキを出した回数: 1611
パーを出した回数: 197
choiced_coins: [ 1.  1.  1. ...,  1.  0.  1.]
グーを出した回数: 260
チョキを出した回数: 1475
パーを出した回数: 262

ε = 0でたまたま出したチョキが勝ったからひたすらチョキを出し続けて探索していないのがもっとも良い結果になってしまったが、まあこのように複数のεを指定して探索して、最適な結果を見つけるというものですかね。

まとめ

強化学習についてはそれほど理解は進まなかったけれども、調べたり試したりしているうちに概要が少しだけわかった気がしないでもない。

今日はこれにて。



mofmof inc.では、一緒に仕事をしてくださるエンジニアを募集しております。
募集要項については以下をご確認ください。
興味を持っていただけましたら、ぜひ一度ゆっくりお話出来れば嬉しいです。

募集一覧(wantedly)
https://www.wantedly.com/companies/mof-mof/projects

mofmofは何をしたいのか
https://www.mof-mof.co.jp/recruit/want-to-do

mofmof入社ガイド
http://everyday.mof-mof.co.jp/entry/2017/01/25/141201