強化学習っぽいことをしてみた

#はじめに
強化学習の手法の一つQ学習を用いて後出しじゃんけんをしたら絶対勝てるように学習するプログラムを書いてみました。if文を使えば後出しじゃんけんをしたら絶対勝てるプログラムは書けますが、後出しじゃんけんという簡単な題材で強化学習の勉強のために書いてみました。
※実装はpythonです。
※強化学習初心者が書いてるので間違いや、意味不明なところがあるかもしれません。

#強化学習
強化学習とは学習するプログラムが経験を通して適切な行動を学習していく機械学習の手法の一つです。

#Q学習
Ｑ学習とは強化学習の手法の一つで、ある状態ｓの下で、次の行動ａを選択する適切な評価値Ｑ（ｓ，ａ）を学習する手法のことです。今回の学習するプログラムは先手が出した手に対して勝てる手を出せるように学習していきます。なので、先手が出した手が状態ｓとなり、学習するプログラムはその状態を判断し、勝てる手を出すように行動ａを選択します。
すなわち後出しじゃんけんの学習プログラムではグー(Rock)、パー(Paper)、チョキ(Scissors)の三つの状態があります。そして、それぞれの状態で選択できる行動もグー、パー、チョキの三つです。
たとえば、後出しじゃんけんを使った適切な評価値Ｑ（ｓ，ａ）の学習方法は以下のような感じになります。
1.　まず先手がグー、パー、チョキのいずれかを出す。たとえばグーを出したとすると、状態は$s_{Rock}$となる。
2.　学習プログラムは状態$s_{Rock}$において、$a_{Rock}, a_{Paper}, a_{Scissors}$のうちいずれか一つを実行する。ここでは、状態が$s_{Rock}$なので$a_{Paper}$を選択するのが正解ですが、実際は評価値Ｑ（ｓ，ａ）の中から最大値を探し出して次の行動を選択します。たとえば、$Q(s_{Rock}, a_{Rock})$が最大値だと学習プログラムはグーを実行します。
3.　選択した行動に対して報酬ｒが得ることができる。得た報酬に基づいて適切なＱ（ｓ，ａ）を学習する。
１～３を繰り返していくことにより適切な評価値Ｑ（ｓ，ａ）を学習していきます。

#Q学習のアルゴリズム
今回使うQ学習のアルゴリズムはまとめると以下のようになります。
1.　Q値を乱数を用いて初期化する。
2.　先手がグー、パー、チョキのいずれかの手を出し状態ｓにセットする。
3.　Q値より行動ａを選択し報酬ｒを得る。
4.　報酬に基づきQ値を更新する。
5.　決められた学習回数なら終了、そうでなければ2.に戻る。

#プログラム
アルゴリズムに基づいてプログラムを書いていきます。

##Q値の初期化

num_action = 3
num_state = 3
Q = [[random.random() for _ in range(num_action)] \
                      for _ in range(num_state)]

ランダムモジュールのrandom関数を用いてQ値を初期化する。
num_actionは行動の数。
num_stateは状態の数。

##状態ｓの設定

actions = ["ROCK", "PAPER", "SCISSORS"]
hand = random.choice(actions) #先手
state = actions.index(hand)   #状態ｓ

先手の手をランダムに選び状態にセットします。

##行動する
次に状態ｓの下で取るべき行動ａを評価値Ｑ（ｓ，ａ）より決定します。

def choice_action(s):
    return random_action() if random.random() < epsilon else max_action(s)

def max_action(s):
    return Q[s].index(max(Q[s]))

def random_action():
    random_value = random.random()
    if random_value < 0.33:
        return 0
    elif random_value < 0.66:
        return 1
    return 2

action = choice_action(state)

今回はεグリーディ法を使って行動を決定しています。εグリーディ法とはある確率で行動をランダムに決定し、それ以外はQ値の最大値を探し出して行動を決定します。なぜεグリーディ法を使うかというと、毎回Q値の最大値から行動を選択していたら必ずしも適切な学習ができるとは限らないからです。どういうことかというと、例えば次のような状態グーのQ値があったとします。
0.429 0.506 0.953
左からグー、パー、チョキとなっています。仮に毎回Q値の最大値から行動を選択するとなると、この例では毎回チョキを選択することになります。学習回数が多ければやがてパーの値がチョキよりも大きくなります。しかし、少なければ決められた学習回数が終了する前に、正しく学習することができません。
そのためにεグリーディ法を使いランダムに行動を選択できるようにし、さまざまな行動を決定することにより、適切に学習を進めることができます。

※εグリーディ法を使わなくても後出しじゃんけんに絶対勝てるように学習することはできます。なぜ今回使ったかというと、使う必要がないと気づいたのがこの記事を書いているときだったからです。

##Q値の更新
Q値より行動を選択し、その行動を実行することにより報酬ｒを得ます。
得た報酬に基づきQ値を更新します。

reward = [(0, 1, -1), (-1, 0, 1), (1, -1, 0)]    #報酬

def update(s, a):
    return Q[s][a] + alpha * (reward[s][a] - Q[s][a])

Q[state][action] = update(state, action)         #Q値の更新

報酬rewardには３つのタプルが入っています。一つ目の報酬(0, 1, -1)は状態がグー、二つ目の報酬(-1, 0, 1)はパーのときです。報酬は勝った場合＋１、引き分けの場合０、負けるとー１が与えられます。例えば、先手がグーを出した場合、報酬は1番目のタプル(0, 1, -1)の要素のどれかです。仮に後手がグーを出すと報酬は０、パーを出すと＋１、チョキを出すとー１が与えられます。

報酬を得るとQ値を更新します。Q値の更新式は次のようになります。
$Q(s,a) \gets Q(s,a) + \alpha(r - Q(s,a))$
行動の結果、得られた報酬が正ならばQ値は増え、負なら減ります。
こうしてQ値を更新していき、決められた学習回数になれば学習を終了します。

#結果
学習の結果を図にしてみました。横軸は学習回数、縦軸はQ値になります。

##先手がグーを出したとき
この図は先手がグーを出したときのQ値の学習の様子です。
はじめはチョキが最大値となっていましたが、マイナスの報酬が与えられ徐々に下がっているのがわかります。そして正解の手であるパーのQ値が徐々に上がっています。

##先手がパーを出したとき

##先手がチョキを出したとき

#全体のコード
最後にコードを載せておきます。

import random

random.seed()

num_action = 3
num_state = 3
num_train = 50
alpha = 0.1
epsilon = 0.3
# ROCK 0
# PAPER 1
# SCISSORS 2
actions = ["ROCK", "PAPER", "SCISSORS"]
reward = [(0, 1, -1), (-1, 0, 1), (1, -1, 0)]
Q = [[random.random() for _ in range(num_action)] \
                      for _ in range(num_state)]

def choice_action(s):
    return random_action() if random.random() < epsilon else max_action(s)

def max_action(s):
    return Q[s].index(max(Q[s]))

def random_action():
    random_value = random.random()
    if random_value < 0.33:
        return 0
    elif random_value < 0.66:
        return 1
    return 2

def update(s, a):
    return Q[s][a] + alpha * (reward[s][a] - Q[s][a])

def train():
    print("Initial Q_value")
    print_q_value()
    for i in range(num_train):
        print("Training {}".format(i+1))
        hand = random.choice(actions)
        state = actions.index(hand)
        action = choice_action(state)
        Q[state][action] = update(state, action) # update q value
        print_q_value()

def print_q_value():
    print("Rock Paper Scissors")
    for i in range(num_state):
        print("{:.3f} {:.3f} {:.3f}\t".format(*Q[i]), end='')
    print()

def test(s):
    return Q[s].index(max(Q[s]))


if __name__ == "__main__":
    train()
    for state in [0, 1, 2]:
        result = test(state)
        print(actions[state], actions[result])