手を動かして実装してみる
価値関数を最大化するためのQ学習の良い例題として,素敵なサイトを見つけたので,そこの例題をPythonで解いてみます.英語ですがとてもわかりやすく書いているのでぜひ読んで欲しいのですが,ざっくりと説明すると0〜5の6つの部屋(ステート)があり,ステート5の部屋に辿り着くように報酬を設定することで,Q学習を行っているサンプルです.
mnemstudio.org
このサイトの例だとQ値更新の式がだいぶ簡略化されています.のペアで得られる即時報酬にの次の状態で報酬を最大化できる行動にをかけたものを加えて更新されます.
ステート遷移図と行動(矢印の経路をたどること)の報酬はこんな感じです.
今回書いたコードを載せておきます.ランダムで取得したstateから,可能な行動のうちQ値が最大となるような行動をとりつつ,各Q値を更新していきます.ゴールしたらまた適当な地点から開始します.この試行をとりあえず1000回行わせました.開始からゴールまでを1エピソードと数えるのが普通のようで,本来はこれを1000エピソード分,行わせた方がよかったかもしれませんが,まぁこんかいのでも十分に学習できるので特に問題ないと思います.
reinforcement-practice/simple-q-learning.py at master · jojonki/reinforcement-practice · GitHub
"""
Created on Thu May 5, 2016
@author: jonki
"""
import numpy as np
import random
import sys
R = np.array([
[-1, -1, -1, -1, 0, -1],
[-1, -1, -1, 0, -1, 100],
[-1, -1, -1, 0, -1, -1],
[-1, 0, 0, -1, 0, -1],
[ 0, -1, -1, 0, -1, 100],
[-1, 0, -1, -1, 0, 100]
])
Q = np.zeros((6,6))
LEARNING_COUNT = 1000
GAMMA = 0.8
GOAL_STATE = 5
class QLearning(object):
def __init__(self):
return
def learn(self):
state = self._getRandomState()
for i in range(LEARNING_COUNT):
possible_actions = self._getPossibleActionsFromState(state)
action = random.choice(possible_actions)
next_state = action
next_possible_actions = self._getPossibleActionsFromState(next_state)
max_Q_next_s_a = self._getMaxQvalueFromStateAndPossibleActions(next_state, next_possible_actions)
Q[state, action] = R[state, action] + GAMMA * max_Q_next_s_a
state = next_state
if state == GOAL_STATE:
state = self._getRandomState()
def _getRandomState(self):
return random.randint(0, R.shape[0] - 1)
def _getPossibleActionsFromState(self, state):
if state < 0 or state >= R.shape[0]: sys.exit("invaid state: %d" % state)
return list(np.where(np.array(R[state] != -1)))[0]
def _getMaxQvalueFromStateAndPossibleActions(self, state, possible_actions):
return max([Q[state][i] for i in (possible_actions)])
def dumpQvalue(self):
print Q.astype(int)
def runGreedy(self, start_state = 0):
print "===== START ====="
state = start_state
while state != GOAL_STATE:
print "current state: %d" % state
possible_actions = self._getPossibleActionsFromState(state)
max_Q = 0
best_action_candidates = []
for a in possible_actions:
if Q[state][a] > max_Q:
best_action_candidates = [a,]
max_Q = Q[state][a]
elif Q[state][a] == max_Q:
best_action_candidates.append(a)
best_action = random.choice(best_action_candidates)
print "-> choose action: %d" % best_action
state = best_action
print "state is %d, GOAL!!" % state
if __name__ == "__main__":
QL = QLearning()
QL.learn()
QL.dumpQvalue()
for s in range(R.shape[0]-1):
QL.runGreedy(s)
実行してみる
このプログラムの最後ではステート0〜4から開始して,最良の経路を通っているかテストしています.Greedyとはあらかじめわかっている報酬があるときに,探索はせずに一番高い報酬が期待出来る行動をとります.ε-グリーディ法などあるのですが,これはまたの機会に説明します.各ステートでスタートしてから一番良い経路(報酬が高い)を選択しているのがわかります.最初に出力されている行列は学習されたQ値です.行がステート,列がアクションです.
[[ 0 0 0 0 395 0]
[ 0 0 0 316 0 493]
[ 0 0 0 316 0 0]
[ 0 395 252 0 395 0]
[316 0 0 316 0 493]
[ 0 393 0 0 395 493]]
===== START =====
current state: 0
-> choose action: 4
current state: 4
-> choose action: 5
state is 5, GOAL!!
===== START =====
current state: 1
-> choose action: 5
state is 5, GOAL!!
===== START =====
current state: 2
-> choose action: 3
current state: 3
-> choose action: 1
current state: 1
-> choose action: 5
state is 5, GOAL!!
===== START =====
current state: 3
-> choose action: 4
current state: 4
-> choose action: 5
state is 5, GOAL!!
===== START =====
current state: 4
-> choose action: 5
state is 5, GOAL!!
学習された各ステートのQ値(実行枚に若干異なります)です.マップしてみるとステート5へと続く経路のQ値は他の経路よりも高くなっていることが確認できますね.
まとめ
今回かなり単純化した問題設定のもと,Q学習を行ってみましたが,どうだったでしょうか?私自体,これが初となるQ学習の実装なので誤っているところあればビシバシ指摘していただきたいです.これぐらい簡単な問題にして実装してみることで,肌感でQ学習が何かが徐々にわかってきました.次は他のTD学習などについても触れたいですね.