Q学習で迷路探索AIを作ってみた

はじめに

機械学習ライブラリを使って遊んでいるうちに、「実際にはどのような仕組みで学習しているのか」を自分でも理解したくなり、PythonでQ学習を実装してみることにしました。
今回はQテーブルを使ったシンプルなQ学習をPythonで実装してみます。

Q学習(Q-learning)とは

Q学習は、エージェントが環境の中で行動を繰り返し、その結果得られる報酬をもとに、より良い行動を学習していく強化学習の手法です。

Q学習では、「ある状態で、どの行動を選ぶと良いのか」を数値で評価します。この評価値をQ値といいます。

わかりやすく言うと、Q値は 「その状況で、その行動をしたらどれくらい良い結果になりそうか」 を表す値です。

例えば迷路で、あるマスに立った時、「右」と「下」のどちらに進むかを考えているとします。

右：Q値 = 8
下：Q値 = 3

この場合、AIは「右に進んだほうが良さそう」と判断できます。

このようなQ値を、状態と行動の組み合わせごとに表として保存したものがQテーブルです。

Q値をQテーブルに保存する表形式のQ学習は、状態や行動の数が少ない比較的シンプルな環境に適しています。

今回は、表形式のQ学習を使って、迷路を探索するAIを作っていきます。

説明コメント付きコードはGitHubに上げています。
実行すると学習したルートを出力するのでまずは試してみてください。

学習の流れ

図:状態（座標）と行動の組み合わせをQテーブルで管理するイメージ

※この図は生成AIを使用して作成しています。

エージェント = 環境の中で状態を観測し、行動を選択する主体です。
わかりにくい場合は、今回は「エージェント＝AI」と考えてください。

学習中のエージェントは、ある状態において「上・下・左・右」の行動からQ値を比較し、よりQ値の大きい行動を選択して移動します。移動すると次の状態に移り、そこでまた行動を選択します。

ただし、学習中は常に最大Q値の行動を選ぶわけではありません。一定の確率でランダムな行動を選ぶことで、ほかの行動も試します（ ε-greedy 法）。
※ ε-greedy 法は、最大Q値の行動だけを選び続けて探索が偏るのを防ぎ、まだ試していない行動も探索するための方法です。

学習時、エージェントは行動するたびに報酬を受け取ります。

今回の迷路では、壁にぶつかれば -5、壁にぶつからず移動できれば -1、ゴールに到達できれば +100 の報酬を受け取ります。

この報酬をもとにQ値を更新していきます。

この探索とQ値の更新を何度も繰り返すことで、各マス(状態)において、どの行動を選ぶとより良い結果につながるのかを学習していきます。

コード解説

ここまでで、Q学習によってAIがどのように迷路を探索していくのかを説明しました。
ここからは実際のコードを見ながら、どのように実装しているのかを説明します。

まず、Q値を更新するにはどのような情報が必要なのかを確認します。

以下の式でQ値を更新します。

$$
Q(s_t,a_t)
\leftarrow
Q(s_t,a_t)
+\alpha
\left[
r_{t+1}
+\gamma\max Q(s_{t+1},a')
-Q(s_t,a_t)
\right]
$$

この式では、現在のQ値に、今回の行動によって得られた報酬$r_{t+1}$と、次の状態$s_{t+1}$で得られそうな将来の価値を反映させて、新しいQ値を求めています。

$s_t$：現在の状態
$a_t$：現在選択した行動
$r_{t+1}$：行動した結果得られた報酬
$s_{t+1}$：行動後の状態
$\alpha$：学習率(今回得た経験を、現在のQ値にどれくらい反映させるか)
$\gamma$：割引率(将来得られる報酬をどれくらい重視するか)
$\max Q(s_{t+1},a')$：次の状態における、上下左右それぞれのQ値の中で最も大きい値

次の状態のQ値を現在のQ値の更新に利用するため、ゴールに近い状態で高くなったQ値が、その手前の状態のQ値にも反映されます。これを繰り返すことで、ゴールにつながる行動のQ値が徐々に高くなり、各状態でより良い行動を選択できるようになります。

この式を実際のコードに落とし込んでいくことで、Q学習の仕組みを確認していきます。

maze = [
    "########",
    "#      #",
    "# # #  #",
    "# #    #",
    "#    #G#",
    "########"
]

#スタート地点とゴール地点を座標で表す
start = (1, 1)
goal = (4, 6)


#行動をrow,colの変化量として定義
actions = {
    0: (-1, 0),  # 上
    1: (1, 0),   # 下
    2: (0, -1),  # 左
    3: (0, 1)    # 右
}

ここまでのコードでは、まず迷路を文字列のリストとして表現しています。(#:壁,G:ゴール)
そして、エージェントの初期位置をstart、ゴール位置をgoalとして、それぞれ座標で定義します。
また、actionsでは、行動ごとの移動量をベクトルで定義しています。エージェントの現在位置にこの移動量を足すことで、移動後の座標を求められるようになっています。

def move(state, action): #state:(r,c),action: 0~3
    row, col = state

    dr, dc = actions[action]

    #行動後のrow,col
    new_row = row + dr
    new_col = col + dc

    #壁にぶつかったら戻る(引数のstateをそのまま返す)
    if maze[new_row][new_col] == "#":
        return state

    return (new_row, new_col)

次はmove関数です。
エージェントの移動先の位置を返すだけの関数で、壁にぶつかると元の位置を返すようにしています。

def get_reward(old_state, new_state):
    if new_state == goal: # I
        return 100
    
    if old_state == new_state: # II
        return -5

    return -1 # III

これはQ値を更新するために必要な報酬$r_{t+1}$を返す関数で、元の位置と移動先の位置を比較して報酬を返しています。

ゴールに到達 +100 -- I
壁にぶつかった -5 -- II
普通に移動 -1 -- III

Q = {}

for row in range(len(maze)):
    for col in range(len(maze[row])):
        if maze[row][col] != "#":
            Q[(row, col)] = [0,0,0,0]
        #歩ける範囲の座標に対応したアクション別Q値を設定（初期値０）

ここではQテーブルの初期化を行っています。
定義するQテーブルのイメージは、

Q = {
    (1,1): [0,0,0,0],  # → [上, 下, 左, 右]に対応
    (1,2): [0,0,0,0],
    (1,3): [0,0,0,0],
    ...
}

で、位置と上下左右ごとのQ値を結び付けています。
Q値の更新に使う$\max Q(s_{t+1},a')$はこのQテーブルから参照しています。

epsilon = 0.3 #30%の確率でランダムな行動をする。

def choose_action(state):
    if random.random() < epsilon:
        return random.randint(0,3) #ランダムなアクションを返す

    return Q[state].index(max(Q[state]))
    #70%の確率で、その状態でのQ値が最大のアクションを返す。

これはε-greedy法を用いた探索で、今回は30%の確率でランダムな行動を選択します。
返り値はactionsの0~3の値です。

def update_q(state, action, reward,next_state):
    alpha = 0.1
    gamma = 0.9

    old_q = Q[state][action]

    best_next_q = max(Q[next_state])

    new_q = old_q + alpha * (reward + gamma * best_next_q - old_q)

    Q[state][action] = new_q

Q値更新を行う関数です。

$$
Q(s_t,a_t)
\leftarrow
Q(s_t,a_t)
+\alpha
\left[
r_{t+1}
+\gamma\max Q(s_{t+1},a')
-Q(s_t,a_t)
\right]
$$

コード解説の冒頭で説明したものの通りに実装しています。

episodes = 1000 #挑戦回数
max_steps = 80 #1 Episodeあたりの最大行動回数

for episode in range(episodes):
    state = start

    for step in range(max_steps):

        if state == goal:
            break

        action = choose_action(state)

        next_state = move(state, action)

        reward = get_reward(state, next_state)

        update_q(state, action, reward, next_state)

        state = next_state

Q値計算に必要な関数を準備し終え、いよいよ学習する関数です。

学習する上で、このコードにあるepisodeとstepについて説明しておきます。
episodeは、エージェントがスタート位置からゴールを目指して探索する1回の試行です。今回は各episodeの開始時にスタート位置へ戻しているため、episodesは探索の試行回数に相当します。
episodesを大きくするほど、エージェントは何度も探索をし、学習を重ねていきます。

stepは、エージェントの行動回数です。
max_stepsは、1episodeあたりの最大行動回数(今回でいえば１episodeで何歩歩けるか)を表しています。

ゴールすればそのepisodeの探索は終了します。

※学習結果の出力処理は割愛します。

実験結果

GitHubに上げているコードをそのまま実行すると、以下の結果が得られました。

(1, 1) → (1, 2) → (1, 3) → (2, 3) → (3, 3) → (3, 4) → (3, 5) → (3, 6) → (4, 6)

Step数 : 8

今回の設定(episodes = 1000,max_steps = 80)では、学習後にスタート地点からゴールまで8stepで到達するルートを得ることができました。

考察

実際にQ学習を実装してみると、非常にシンプルな計算を繰り返すことで学習が行われていることが分かりました。

学習したAIは、Qテーブルに記録された各行動の評価をもとに、最もQ値の高い行動を選択しているため、まるで「Qテーブルというマニュアル」に従って動いているようにも感じました。

一方で、今回のような表形式のQ学習の限界も感じました。
今回の実装では、迷路上の各座標を状態としてQテーブルに登録しているため、迷路の形が変わると、これまで学習したQテーブルをそのまま利用することができません。新しい迷路に対応するには、改めて学習する必要があります。

このように、状態の数が増えたり、環境が複雑になったりすると、すべての状態をQテーブルに記録する方法には限界があります。

まとめ

今回実装したQ学習では、エージェントが迷路の中で行動し、行動した結果として得られる報酬をもとにQ値を更新していきます。

学習を繰り返すことで、ゴールに近い状態で高くなったQ値が、その手前の状態のQ値の更新にも利用され、最終的にゴールまでの経路を選択できるようになります。

一方で、今回のような表形式のQ学習では、状態ごとにQ値をQテーブルへ保存する必要があります。そのため、状態の数が増えるほどQテーブルも大きくなり、複雑な環境ではすべての状態を管理することが難しくなります。また、迷路の形が変わった場合には、それまでに学習したQテーブルをそのまま利用することができません。

そこで登場するのが、DQN（Deep Q-Network） です。
DQNは、強化学習のアルゴリズムである Q学習（Q-learning）にディープラーニング（深層ニューラルネットワーク）を組み合わせた手法です。
DQNでは、ニューラルネットワークを学習させることで、状態からQ値を予測できるようにします。
そのため、学習したことのない状態に対しても、学習した知識からQ値を推定できる可能性があるのです。
いつかDQNも実装してみたいと思います。