【入門】Q学習の解説とpythonでの実装 〜シンプルな迷路問題を例に〜

今回は強化学習の代表的なアルゴリズムであるQ学習を紹介します。

Q学習は一言でいってしまうと、遷移先状態の最大Q値を使う手法で、楽観的な手法と呼ばれる強化学習手法です。

これから丁寧に説明していきます。

強化学習とは

以下の図を使って説明してきます。

左のロボットが強化学習で学習するとします。 このロボットのように強化学習で学習する対象をエージェント強化学習エージェントと呼びます。

エージェントは環境に対して何かしらの行動を行います。 その行動によって変化した状態報酬を環境から受け取ります。

エージェントは受け取った状態と報酬を元に、累積報酬の最大化を目指して行動パターンを学習していきます。

強化学習では、エージェントに正解データではなく報酬を与えます。 報酬は正解や不正解といったものではなく、アクションの良さといったものになります。 なので、教師あり学習と教師なし学習の中間的な手法と呼ばれます。

詳しくは以下の記事にまとめました。 https://www.tcom242242.net/entry/2017/09/20/060902/

Q学習とは

Q学習は代表的な強化学習手法の1つです。

Q学習では、各状態\(s\)に対する各行動\(a\)のQ値を保存しておくQテーブル\(Q(s, a)\)というテーブルを保持しています。(図の左)

Q学習ではこのQテーブルの値を以下の式によって更新します。

この式からわかる通り(赤線部分)、Q学習では遷移先状態\(s'\)の最大Q値\(max_{a'} Q(s, a')\)を使って学習するのが主な特徴となります。

つまり、遷移した先の状態の最も良いところだけを利用します。 そのため楽観的な手法と言われます。

ちなみに\( r+\gamma \max_{a'}Q(s',a') -Q(s,a)\)をTD誤差といい、 Q学習ではこの誤差を小さくするように学習していきます。

\(\alpha\)は学習率といい0〜1の間の値をとるパラメータです。 TD誤差をどれだけ反映させるかを決定します。

\( \gamma\)は割引率といい、遷移先の最大Q値をどれだけ利用するかを決めるパラメータです。

学習手順

では、具体的なQ学習の学習手順(アルゴリズム)を見ていきます。

まず箇条書きで示します。

  1. 現在の状態\(s\)で、\(Q(s, a)\)に従ってある行動\(a\)を選択し実行
  2. 環境から遷移先状態\(s'\)と報酬\(r\)を受け取る
  3. 得られた遷移先状態\(s'\)と報酬\(r\)を元に以下のように\(Q(s, a)\)を更新
    • \(Q(s, a) \leftarrow Q(s,a) + \alpha (r+\gamma max_{a'} Q(s',a') - Q(s,a))\)
  4. ステップ1〜3を繰り返す

各ステップを図を使いながら、説明していきます。

1.現在の状態\(s\)で、\(Q(s, a)\)に従ってある行動\(a\)を選択し実行

まず、強化学習エージェントは現在の状態\(s\)で、Qテーブルの\(Q(s, a)\)に従って行動選択をします。

図中の赤いところが\(Q(s, a)\)となります。 ここからε-greedy行動選択softmax行動選択等を用いて行動を選択をします。 基本的どの手法も\(Q(s, a)\)が高い行動を優先的に選択します。

ここでは、行動\(a\)を選択したとします。

行動を選択したら実際に行動を実行します。

2.環境から遷移先状態\(s'\)と報酬\(r\)を受け取る

次に行動\(a\)によって遷移した状態\(s'\)と報酬\(r\)を環境から受け取ります。

これを強化学習では観測と言ったりします。

3. 得られた遷移先状態\(s'\)と報酬\(r\)を元に\(Q(s, a)\)を更新

そして、先程紹介したQ値の更新式を使って、\(Q(s, a)\)を更新します。

先程もお話した通り、遷移先状態\(s'\)の最大Q値\(\max_{a'}Q(s', a')\)を使うことがQ学習の特徴となります。

4. ステップ1〜3を繰り返す

あと、\(Q(s, a)\)がある程度収束するまで、ステップ1〜3を繰り返します。

実装と実験

問題設定

以下のようなグリッドワールドの問題を扱います。 かなりシンプルなマップになります。

強化学習エージェントは最初に左下にいます。 右上にゴール、左上に危険地帯があるとします。 ここからエージェントは右上の家に向けての最短経路を学習することが目的となる問題です。

細かい設定

状態、行動、報酬は以下の通りです。

  • 状態:マス目(座標)
  • 行動:上下左右の4択
  • 報酬:右上に着けば100、左上は-100、通常の地点は0、壁や境界線であれば-1の報酬

左上か右上に到着したら、ゲーム終了とみなし、 エージェントを左下に戻します。 (これをエピソードという単位で表現します)

ソースコード

Pythonを用いて実装します。 ちなみにPythonの3系を用います。 前回と同様にQ学習エージェントクラス、環境(グリッドワールド)クラスに分けて実装します。

GitHubにも上げてあります。 以下、GitHubのリンク https://github.com/tocom242242/QLearning_in_GridWorld

Q学習エージェント(qlearning_agent.py)

まずQ学習です。 コードは以下のようになります。

import copy
import numpy as np

class QLearningAgent:
    """
        Q学習 エージェント
    """

    def __init__(
            self,
            alpha=.2,
            epsilon=.1,
            gamma=.99,
            actions=None,
            observation=None):
        self.alpha = alpha
        self.gamma = gamma
        self.epsilon = epsilon
        self.reward_history = []
        self.actions = actions
        self.state = str(observation)
        self.ini_state = str(observation)
        self.previous_state = None
        self.previous_action = None
        self.q_values = self._init_q_values()

    def _init_q_values(self):
        """
           Q テーブルの初期化
        """
        q_values = {}
        q_values[self.state] = np.repeat(0.0, len(self.actions))
        return q_values

    def init_state(self):
        """
            状態の初期化
        """
        self.previous_state = copy.deepcopy(self.ini_state)
        self.state = copy.deepcopy(self.ini_state)
        return self.state

    def act(self):
        # ε-greedy選択
        if np.random.uniform() < self.epsilon:  # random行動
            action = np.random.randint(0, len(self.q_values[self.state]))
        else:   # greedy 行動
            action = np.argmax(self.q_values[self.state])

        self.previous_action = action
        return action

    def observe(self, next_state, reward=None):
        """
            次の状態と報酬の観測
        """
        next_state = str(next_state)
        if next_state not in self.q_values:  # 始めて訪れる状態であれば
            self.q_values[next_state] = np.repeat(0.0, len(self.actions))

        self.previous_state = copy.deepcopy(self.state)
        self.state = next_state

        if reward is not None:
            self.reward_history.append(reward)
            self.learn(reward)

    def learn(self, reward):
        """
            Q値の更新
        """
        q = self.q_values[self.previous_state][self.previous_action]  # Q(s, a)
        max_q = max(self.q_values[self.state])  # max Q(s')
        # Q(s, a) = Q(s, a) + alpha*(r+gamma*maxQ(s')-Q(s, a))
        self.q_values[self.previous_state][self.previous_action] = q + \
            (self.alpha * (reward + (self.gamma * max_q) - q))

33〜41行目のactメソッドでエージェントは行動選択をします。 ここではε-greedy手法によって行動選択をします。

43〜56行目のobserveメソッドで遷移先の状態と報酬を観測します。 ここでは報酬が観測したときにのみ学習するようにしています。

58〜65行目のlearnメソッドでQ値の更新をしています。

グリッドワールド(grid_world.py)

グリッドワールドクラスでは、 エージェントからの行動を受け取り、遷移先状態や報酬を返します。

import copy

class GridWorld:

    def __init__(self):

        self.filed_type = {
            "N": 0,  # 通常
            "G": 1,  # ゴール
            "W": 2,  # 壁
            "T": 3,  # トラップ
        }
        self.actions = {
            "UP": 0,
            "DOWN": 1,
            "LEFT": 2,
            "RIGHT": 3
        }
        self.map = [[3, 2, 0, 1],
                    [0, 0, 0, 2],
                    [0, 0, 2, 0],
                    [2, 0, 2, 0],
                    [0, 0, 0, 0]]

        self.start_pos = 0, 4   # エージェントのスタート地点(x, y)
        self.agent_pos = copy.deepcopy(self.start_pos)  # エージェントがいる地点

    def step(self, action):
        """
            行動の実行
            状態, 報酬、ゴールしたかを返却
        """
        to_x, to_y = copy.deepcopy(self.agent_pos)

        # 移動可能かどうかの確認。移動不可能であれば、ポジションはそのままにマイナス報酬
        if self._is_possible_action(to_x, to_y, action) == False:
            return self.agent_pos, -1, False

        if action == self.actions["UP"]:
            to_y += -1
        elif action == self.actions["DOWN"]:
            to_y += 1
        elif action == self.actions["LEFT"]:
            to_x += -1
        elif action == self.actions["RIGHT"]:
            to_x += 1

        is_goal = self._is_end_episode(to_x, to_y)  # エピソードの終了の確認
        reward = self._compute_reward(to_x, to_y)
        self.agent_pos = to_x, to_y
        return self.agent_pos, reward, is_goal

    def _is_end_episode(self, x, y):
        """
            x, yがエピソードの終了かの確認。
        """
        if self.map[y][x] == self.filed_type["G"]:      # ゴール
            return True
        elif self.map[y][x] == self.filed_type["T"]:    # トラップ
            return True
        else:
            return False

    def _is_wall(self, x, y):
        """
            x, yが壁かどうかの確認
        """
        if self.map[y][x] == self.filed_type["W"]:
            return True
        else:
            return False

    def _is_possible_action(self, x, y, action):
        """
            実行可能な行動かどうかの判定
        """
        to_x = x
        to_y = y

        if action == self.actions["UP"]:
            to_y += -1
        elif action == self.actions["DOWN"]:
            to_y += 1
        elif action == self.actions["LEFT"]:
            to_x += -1
        elif action == self.actions["RIGHT"]:
            to_x += 1

        if len(self.map) <= to_y or 0 > to_y:
            return False
        elif len(self.map[0]) <= to_x or 0 > to_x:
            return False
        elif self._is_wall(to_x, to_y):
            return False

        return True

    def _compute_reward(self, x, y):
        if self.map[y][x] == self.filed_type["N"]:
            return 0
        elif self.map[y][x] == self.filed_type["G"]:
            return 100
        elif self.map[y][x] == self.filed_type["T"]:
            return -100

    def reset(self):
        self.agent_pos = self.start_pos
        return self.start_pos

実行用のコード(main.py)

Q学習エージェントとグリッドワールドを組み合わせて、エージェントに学習させます。 以下のコードを実行するとエピソード毎に得られる報酬をプロットします。

import numpy as np
import matplotlib.pyplot as plt
from qlearning_agent import QLearningAgent
from grid_world import GridWorld

# 定数
NB_EPISODE = 100    # エピソード数
EPSILON = .1    # 探索率
ALPHA = .1      # 学習率
GAMMA = .90     # 割引率
ACTIONS = np.arange(4)  # 行動の集合

if __name__ == '__main__':
    grid_env = GridWorld()  # grid worldの環境の初期化
    ini_state = grid_env.start_pos  # 初期状態(エージェントのスタート地点の位置)
    # エージェントの初期化
    agent = QLearningAgent(
        alpha=ALPHA,
        gamma=GAMMA,
        epsilon=EPSILON,  # 探索率
        actions=ACTIONS,   # 行動の集合
        observation=ini_state)  # Q学習エージェント
    rewards = []    # 評価用報酬の保存
    is_end_episode = False  # エージェントがゴールしてるかどうか?

    # 実験
    for episode in range(NB_EPISODE):
        episode_reward = []  # 1エピソードの累積報酬
        while(is_end_episode == False):    # ゴールするまで続ける
            action = agent.act()  # 行動選択
            state, reward, is_end_episode = grid_env.step(action)
            agent.observe(state, reward)   # 状態と報酬の観測
            episode_reward.append(reward)
        rewards.append(np.sum(episode_reward))  # このエピソードの平均報酬を与える
        state = grid_env.reset()  # 初期化
        agent.observe(state)    # エージェントを初期位置に
        is_end_episode = False

    # 結果のプロット
    plt.plot(np.arange(NB_EPISODE), rewards)
    plt.xlabel("episode")
    plt.ylabel("reward")
    plt.savefig("result.jpg")
    plt.show()

実験結果

エピソード毎の累積報酬をプロットしました。 (1エピソードはスタート地点からゴールに着くまで)

f:id:ttt242242:20190904104147j:plain

横軸はエピソード、縦軸が累積報酬となります。

学習が進むことに高い報酬を得れていることがわかります。

参考文献(教科書)

1.最も古典的な強化学習の教科書です。

強化学習

2.最近出版された強化学習の教科書です。

強化学習アルゴリズム入門 「平均」からはじめる基礎と応用

3.最近の強化学習の研究等を紹介しています。 教科書としては微妙かもしれませんが、様々な強化学習の発展分野について紹介しています。

これからの強化学習

タイトルとURLをコピーしました