【AI入門】強化学習の基本概念とSarsaアルゴリズムを用いた迷路探索の実装

はじめに

こんにちは、野村です。
学生をしながら静岡の株式会社HIBARIでAIを用いたプロダクト開発をしています。大学では情報通信分野で研究を行っています。

本記事は、強化学習とその学習手法について学んだ内容をまとめたものです。学習および実装にあたっては、次の書籍と公式リポジトリを参考にしています。

• 参考書籍：
  小川雄太郎：作りながら学ぶ! 深層強化学習 PyTorchによる実践プログラミング（マイナビ出版）

• 参考リポジトリ：
  GitHub サポートリポジトリ(MIT License)

強化学習の位置づけ

まず、「AI」、「機械学習」、「強化学習」という言葉の関係を示しておこうと思います。

「AI」という言葉の定義は研究者によって異なります。ここでは、

人間が知的だと感じるシステムや、そのようなシステムを搭載したロボット

と表現します。

AIを実現する手法の一つが「機械学習」です。機械学習には、次の3つの手法があります。

• 教師あり学習

• 教師なし学習

• 強化学習

教師あり学習とは、学習データに正解ラベルがあるものを指します。例えば、数字の文字認識が挙げられます。

教師なし学習とは、学習データに正解ラベルがないものを指します。例えば、クラスタリングが挙げられます。

強化学習とは、すべての場合に対して正解を与えず、特定の状態に対して報酬を付与する学習手法のことを指します。例えば、ロボットの歩行制御や、囲碁・将棋などが挙げられます。

強化学習では、すべての状態に対して最適な行動を考えることが困難なため、ロボットがうまく歩行できたりゲームで勝ったりした際に報酬を与えるという形でフィードバックを行います。強化学習は主に、時間変化を伴うシステムの制御に用いられます。

強化学習の構成要素

次に、強化学習を行う際に定める要素を紹介します。強化学習を行うためには、制御対象がどのような状態を取るか、それぞれの状態でどのような行動ができるか、を定義する必要があります。

エージェントは方策を基に行動を決定します。そして、エージェントの行動によって状態が変化します。この繰り返しによって、ロボットの歩行や盤面が変化していきます。

つまり、上に示した要素を定めることで、状態遷移のルールを定義することができます。

強化学習の迷路課題への適用

ここでは、強化学習を迷路課題に適用することを考え、上述した要素の具体例を見てみたいと思います。

上の図に示すような迷路を考えます。橙丸がプレイヤーです。青の線は壁を表し、左上（S0）から右下（S8）に向かいます。このような問題では、強化学習の各要素は次のように定められます。

強化学習の学習手法

強化学習の学習段階では、方策 $\pi_\theta(S,a)$ のパラメータ $\theta$ を更新し、行動確率を最適化します。ここでは、2つの学習手法を紹介します。

1. 方策反復法
   方策反復法とは、ランダムに行動して速くゴールしたケースを重要視する手法です。各状態における行動確率を最適化します。

2. 価値反復法
   価値反復法とは、すべての状態と行動に価値を定義し、その価値に従って行動を決定する手法です。各状態における行動価値を最適化します。

1.方策反復法

方策反復法の一つに、方策勾配法という手法があります。ここではその手法を説明します。名前の通り、深層学習の勾配降下法と似たアプローチをします。誤差の算出式とパラメータの更新式は次のように示されます。

• 更新式
  $\theta_{S_i,a_j}\gets\theta_{S_i,a_j}+\eta\ast\Delta\theta_{S_i,a_j}$

  $\Delta\theta_{S_i,a_j}=\left\{N\left(S_i,a_j\right)-P\left(S_i,a_j\right)\ N\left(S_i,a\right)\right\}/T$

ここで、各変数は次の通りです。

• $\eta$：学習率

• $T$：ゴールまでにかかった総ステップ数

• $N(S_i,a_j)$：状態 $S_i$ で行動 $a_j$ をした回数

• $P(S_i,a_j)$：状態 $S_i$ で行動 $a_j$ をする確率

• $N(S_i,a)$：状態 $S_i$で行動をした回数
  （行動回数の期待値と実際の行動回数との差を $\theta_{S_i,a_j}$ に反映します）

誤差 $\Delta\theta_{S_i,a_j}$ は、現在の行動確率と実際の行動回数を比較したときの差です。ゴールまでにかかった総ステップ数で除算することで、速くゴールした場合の誤差ほど重要視されます。
更新式では、誤差 $\Delta\theta_{S_i,a_j}$ に学習率 $\eta$ を乗算してから現在のパラメータに加えます。学習率は通常 $\eta\in{(0, 1)}$ の値を取り、急激な値の更新を防ぐ役割をします。

2.価値反復法

次に、価値反復法について説明します。
こちらの手法では、学習結果を示します。

2.1.報酬と価値

価値反復法における重要な概念として、「報酬」と「価値」があります。

2.2.価値反復法の学習手順

価値反復法の一つであるSarsaアルゴリズムを紹介します。
価値反復法では、行動価値を最適化するのでした。

• 行動価値 $Q(S_t,a_t)$ の初期値はランダムに設定します。

• 正しい行動価値が設定されている場合には、次の式を満たすはずです。
  $Q\left(S_t,a_t\right)=R_{t+1}+\gamma\ast Q(S_{t+1},a_{t+1})$
  ※詳しくは「ベルマン方程式」参照

• 現在設定されている行動価値と、理論値との誤差を求めます。この誤差をTD誤差と呼びます。
  TD誤差 $= R_{t+1} + \gamma \ast Q(S_{t+1},a_{t+1}) - Q(S_t,a_t)$

• TD誤差を用いて行動価値を更新します。
  $Q\left(S_t,a_t\right)\gets Q\left(S_t,a_t\right)+\eta\ast$ TD誤差　（$\eta$：学習率）
  更新を繰り返すことで、行動価値を最適化します。

2.3.価値反復法の学習結果

価値反復法を迷路課題に適用した際の、学習前後の状態価値の比較を次の図に示します。本実装では割引率 $\gamma=0.9$ としました。

学習前にはランダムに与えられていた状態価値ですが、学習後にはスタートからゴールへの道筋ができていることがわかります。

価値反復法によって、迷路課題の最適経路を学習できました。

まとめ

• 強化学習は時間変化を伴うシステムの制御に利用される学習手法

• 状態、行動、方策、報酬を定義することで、制御対象のシステムを表現できる

• 学習では価値反復法や方策反復法によって方策を最適化する

• 強化学習を利用することで迷路課題などを解決可能

今回は、機械学習手法の一つである強化学習について解説しました。

私の専門領域である情報通信分野においても、強化学習は非常に重要な役割を担っています。例えば、刻々と状況が変わる衛星通信のリソース割り当てや、複雑なネットワークトラフィックの自律的な最適化など、次世代の通信インフラを支える知能として活用されています。

強化学習の理論やその応用先に興味を持たれた方は、ぜひ本記事の参考にさせていただいた書籍を手に取ってみてください。

• 参考書籍：
  小川雄太郎：作りながら学ぶ! 深層強化学習 PyTorchによる実践プログラミング（マイナビ出版）

最後までお読みいただきありがとうございました！