Python
機械学習
強化学習
Sarsa

強化学習:SarsaでMountain Carの学習


はじめに

Sarsaは強化学習の一種です。

本記事では、OpenAI GymのMountain CarをSarsaで学習させることを目標にします。

以前書いたQ学習の記事の続編でと思ってください。(下記リンク)

強化学習:Q学習でMountain Carの学習(Part1)

本記事の内容

・Sarsaの説明、実装

・Mountain Carの学習

知っておくと良さそうな知識

・pythonの知識

・機械学習・最適化に関するイメージ

・簡単な数学の知識(集合論、統計数学)

・強化学習・Q学習の知識

使用環境

・Windows10

・python3.6


強化学習について

強化学習は、シミュレーションを行いながら最も報酬を多く獲得できる行動列を学習する手法です。

下図は、マルコフ決定過程(強化学習のベースになっているモデル)のイメージ図になります。

MDP.png


SarsaとQ学習

Sarsaは強化学習の一種で、Q学習と同様に行動価値関数を学習する手法です。

行動価値関数の定義をおさらいしましょう。

Q^{\pi}(s_{t}, a_{t})=R(s_{t}, a_{t})+\sum_{\tau=t+1}^{T}\left\{ \gamma^{\tau-t} \sum_{a} \pi(s_{\tau}, a)R(s_{\tau}, a) \right\}

ここでは、確率的な方策$\pi$を考えているので、その場合の定義を載せています。

(Q学習のPart2に補足として載せています。)

Q学習では、方策$\pi$に従って行動を選択し、行動価値関数$Q$を最適行動価値関数のベルマン方程式

\begin{align}

Q^{\ast}(s_{t}, a_{t}) = R(s_{t}, a_{t}) + \gamma \max_{a} Q^{\ast}(s_{t+1}, a)
\end{align}

の解に近づけていくものでした。

一方、Sarsaでは、行動価値関数$Q$を、方策$\pi$に従う行動価値関数のベルマン方程式

\begin{align}

Q^{\pi}(s_{t}, a_{t}) = R(s_{t}, a_{t}) + \gamma \sum_{a} \pi(s_{t+1}, a) Q^{\pi}(s_{t+1}, a)
\end{align}

の解に近づけています。

(ベルマン方程式の導出は省略します。)

Q学習とSarsaの違いは分かりにくいですが、以下の点で違います。

・Q学習は、状態$s_{t+1}$以降に全て最適行動を選択したときの行動価値関数を考えている

・Sarsaは、状態$s_{t+1}$以降に方策$\pi$に従って行動を選択したときの行動価値を考えている

つまり、Q学習では行動価値関数がエージェントの方策に依存しないのに対して、Sarsaでは行動価値関数がエージェントの方策に依存します。

このことから、Q学習を方策オフ型、Sarsaを方策オン型の学習と呼びます。

行動価値関数の更新について、Q学習では以下の式で更新を行いました。

\begin{align}

Q(s_{t}, a_{t}) \leftarrow \alpha \left\{ R_{t+1} + \gamma \max_{a} Q(s_{t+1}, a) \right\} + (1-\alpha)Q(s_{t}, a_{t})
\end{align}

一方、Sarsaでは以下の式で更新を行います。

\begin{align}

Q(s_{t}, a_{t}) \leftarrow \alpha \left\{ R_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) \right\} + (1-\alpha)Q(s_{t}, a_{t})
\end{align}

Sarsaの更新には、次の状態$s_{t+1}$でエージェントが選択した行動$a_{t+1}$も必要です。実装時に注意しましょう。


Sarsaの実装

GitHubに今回のソースコードを公開しています。

https://github.com/highcheap/qiita/blob/master/RL/MountainCar_Sarsa.py

以前作成したQ学習のクラスQLとほとんどの機能を共有していますので、QLを継承して、書き換えが必要なメソッドのみオーバーライドします。

(今回、QLも微修正しましたが、以前作成したQLを継承させてもちゃんと動きます。)

書き換えるメソッドは、run_episodeとupdateです。

Q学習のPart3を参照)

class Sarsa(QL):

"""
Sarsa algorithm.
"""

def run_episode(self, train):
"""
run_episodeの書き換え
"""

def update(self, obs, action, reward, is_terminal, next_obs, next_action):
"""
updateの書き換え
"""


Sarsaの実装 ~updateの書き換え~

Q学習での行動価値関数の更新に$s_{t}, a_{t}, r_{t+1}, s_{t+1}$が必要でしたが、Sarsaでの更新では更に$a_{t+1}$も必要になります。

引数にnext_actionを追加し、上記の更新式をもとに実装します。

    def update(self, obs, action, reward, is_terminal, next_obs, next_action):

state = self.to_integer(obs)
next_state = self.to_integer(next_obs)
q = self.q_function[state, action]
target = reward
if not is_terminal:
target += self.gamma * self.q_function[next_state, next_action]
self.q_function[state, action] = self.alpha * target + (1 - self.alpha) * q

Q学習のときは、targetの計算を以下のような行っていました。

        target = reward

if not is_terminal:
target += self.gamma * self.q_function[next_state,:].max()

next_stateの行動価値関数の最大値を計算に用いています。

一方、Sarsaでは、targetの計算が以下のようになっています。

        target = reward

if not is_terminal:
target += self.gamma * self.q_function[next_state, next_action]

agentがnext_state時に選択した行動next_actionの行動価値を計算に用いています。

ここがQ学習とSarsaの大きな違いです。


Sarsaの実装 ~run_episodeの書き換え~

Q学習では、以下のようにエピソードを実行していました。

①状態$s_{t}$をもとに行動$a_{t}$を選択

②状態を遷移させ、次の状態$s_{t+1}$と報酬$R_{t+1}$を観測

③$s_{t}, a_{t}, R_{t+1}, s_{t+1}$をもとに行動価値関数を更新

一方、Sarsaでは、以下のようにエピソードを実行します。

①(初回のみ)行動$a_{1}$を選択

②状態を遷移させ、次の状態$s_{t+1}$と報酬$R_{t+1}$を観測

③状態$s_{t+1}$をもとに行動$a_{t+1}$を選択

④$s_{t}, a_{t}, R_{t+1}, s_{t+1}, a_{t+1}$をもとに行動価値関数を更新

Sarsaでは、状態遷移の直後に次の行動も決定して、それを更新に使います。

run_episodeの実装は以下になります。

    def run_episode(self, train):

step_count = 0
obs = self.env.reset()
next_action = None
done = False
while not done:
step_count += 1

if train:
if step_count == 1:
action = self.act(obs)
else:
action = next_action

next_obs, reward, done, info = self.env.step(action)

if done:
self.update(obs, action, reward, done, next_obs, None)
else:
next_action = self.act(next_obs)
self.update(obs, action, reward, done, next_obs, next_action)

obs = next_obs
else:
action = self.act_greedily(obs)
obs, reward, done, info = self.env.step(action)

#record statistics

self.episode_count += 1
if self.average_episode_step is None:
self.average_episode_step = step_count
else:
self.average_episode_step *= (1 - self.ema_coeff)
self.average_episode_step += self.ema_coeff * step_count

ここで、終端状態時にはnext_actionにNoneを与えています。

以上で、実装は完了です。


SarsaによるMountain Carの学習

Q学習による学習と同様のハイパパラメータを設定します。

    env = gym.make('MountainCar-v0')

frequency = lambda x: (x + 1) % 500 == 0
env = wrappers.Monitor(env, directory='movies_Sarsa', force=True, video_callable=frequency)
model = Sarsa(env, alpha=0.1, gamma=0.99, epsilon=0.1, bins=40)
model.run(20000, result_callable=frequency)
env.env.close()

2000エピソード程度の学習で山登りに成功し、最終的には150ステップ前後で山登りができるようになりました。

Q学習と同質の結果です。

20000エピソード時点のエピソードのgifです。

Sarsa.gif

下図は、Q学習とSarsaの1エピソードあたりのステップ数の推移をプロットしたものです。

QLvsSarsa.png


おわりに

今回、強化学習の一種であるSarsaの説明と実装をしました。

行動価値関数が方策に依存しているからなのか、Q学習と比較してあまり語られていない気がします。

次は、DQN(Deep Q-Network)について書きたいと思っています。