Q学習で最良経路をPythonで求めてみる

導入Q学習

いきなりですが強化学習の勉強始めています．強化学習は教師なし学習の1つの手法で，与えられた環境に対して様々な行動を試し，一番報酬が得られる行動を学習していきます．その中でQ値と呼ばれるものがあります．これは状態，行動をとり，方策に従って得られる割引累積報酬の期待値です．ざっくりと言い切ってしまうと，を実行すると将来どれぐらいの報酬が期待できるか？といったことを意味しています．

学習にはQ学習，Actor-Critic，SARSAなどがありますが，今回の記事ではQ学習を取り扱います．これは方策オフ型のTD学習であり，どうのような行動をとるか？という方策に関係なく，行動価値関数の大きな値に合わせていくスタイルです．この更新を繰り返していくことで（学習していくことで）最適な行動価値を導き出します．

今回強化学習に関しての詳しい説明はしません．いずれしたいと思いますが，今日はとてもわかりやすいリンク及び書籍を紹介しておきます．
強化学習の基礎,小池　康晴，鮫島 和行

イラストで学ぶ 人工知能概論 (KS情報科学専門書)

手を動かして実装してみる

価値関数を最大化するためのQ学習の良い例題として，素敵なサイトを見つけたので，そこの例題をPythonで解いてみます．英語ですがとてもわかりやすく書いているのでぜひ読んで欲しいのですが，ざっくりと説明すると０〜５の6つの部屋（ステート）があり，ステート5の部屋に辿り着くように報酬を設定することで，Q学習を行っているサンプルです．
mnemstudio.org

このサイトの例だとQ値更新の式がだいぶ簡略化されています．のペアで得られる即時報酬にの次の状態で報酬を最大化できる行動にをかけたものを加えて更新されます．

ステート遷移図と行動（矢印の経路をたどること）の報酬はこんな感じです．

今回書いたコードを載せておきます．ランダムで取得したstateから，可能な行動のうちQ値が最大となるような行動をとりつつ，各Q値を更新していきます．ゴールしたらまた適当な地点から開始します．この試行をとりあえず1000回行わせました．開始からゴールまでを１エピソードと数えるのが普通のようで，本来はこれを1000エピソード分，行わせた方がよかったかもしれませんが，まぁこんかいのでも十分に学習できるので特に問題ないと思います．

reinforcement-practice/simple-q-learning.py at master · jojonki/reinforcement-practice · GitHub

# -*- coding: utf-8 -*-
"""
Created on Thu May  5, 2016

@author: jonki
"""

import numpy as np
import random
import sys

# sample ref
# http://mnemstudio.org/path-finding-q-learning-tutorial.htm

# Reward matrix
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]
])

# Initial Q-value
Q = np.zeros((6,6))

LEARNING_COUNT = 1000
GAMMA = 0.8
GOAL_STATE = 5

class QLearning(object):
    def __init__(self):
        return
        
    def learn(self):
        # set a start state randomly
        state = self._getRandomState()
        for i in range(LEARNING_COUNT):        
            # extract possible actions in state
            possible_actions = self._getPossibleActionsFromState(state)
            
            # choise an action from possible actions randomly
            action = random.choice(possible_actions)        
            
            # Update Q-value
            # Q(s,a) = r(s,a) + Gamma * max[Q(next_s, possible_actions)]
            next_state = action # in this example, action value is same as next state
            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 an agent reached a goal state, restart an episode from a random start 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) # convert float to int for redability

    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)
            
            # get best action which maximaizes Q-value(s, a)
            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)
            
            # get a best action from candidates randomly
            best_action = random.choice(best_action_candidates)
            print "-> choose action: %d" % best_action
            state = best_action # in this example, action value is same as next state
        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)

実行してみる

このプログラムの最後ではステート０〜４から開始して，最良の経路を通っているかテストしています．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値（実行枚に若干異なります）です．マップしてみるとステート５へと続く経路のQ値は他の経路よりも高くなっていることが確認できますね．

まとめ

今回かなり単純化した問題設定のもと，Q学習を行ってみましたが，どうだったでしょうか？私自体，これが初となるQ学習の実装なので誤っているところあればビシバシ指摘していただきたいです．これぐらい簡単な問題にして実装してみることで，肌感でQ学習が何かが徐々にわかってきました．次は他のTD学習などについても触れたいですね．