読むとGPAが上がるブログ(仮)

GPA芸人が気の赴くままに何かを書くブログ

強化学習のアルゴリズム紹介（その1：DQN）

機械学習 強化学習 強化学習のアルゴリズム紹介 
\usepackage{amsmath,amssymb}
\usepackage{pifont}

\usepackage{bigints}
\usepackage{bm}
\usepackage{siunitx}

\newcommand{\hs}[1]{\hspace{#1zw}}
\newcommand{\vs}[1]{\vspace{#1zh}}
\newcommand{\hsh}{\hs{0.5}}
\newcommand{\vsh}{\vs{0.5}}

\newcommand{\eref}[1]{\text{式\eqref{eq:#1}}}

\newcommand{\Nset}{\mathbf{N}}
\newcommand{\Zset}{\mathbf{Z}}
\newcommand{\Qset}{\mathbf{Q}}
\newcommand{\Rset}{\mathbf{R}}
\newcommand{\Cset}{\mathbf{C}}

\DeclareMathOperator*{\argmax}{\mathrm{arg\,max}}
\DeclareMathOperator*{\argmin}{\mathrm{arg\,min}}

\mathchardef\ordinarycolon\mathcode`\:
\mathcode`\:=\string"8000
\begingroup \catcode`\:=\active
  \gdef:{\mathrel{\mathop\ordinarycolon}}
\endgroup

はじめに

こんにちは。 まさかの新シリーズです。 このシリーズでは、強化学習の基礎シリーズで説明をふっとばした、「学習本体」に焦点をあてていきます。

具体的には、各アルゴリズムの実装をしながら、そのイメージを説明するところを目的とします。 なので数式とかはなるべく出さないようにするつもりですが、数式があった方がイメージしやすいところは使います。

扱うアルゴリズムは、

  • DQN
  • Rainbow
  • REINFORCE
  • PPO
  • A2C

です。 今回は、最初のDQNを扱います。

あと、今回もコードはGitHubに上げてあります。

DQNの概要

DQNはドキュンじゃないです。 Deep Q-Networkを指します。 Q学習に深層学習（Deep）を取り入れたものとなっています。

Q学習の概要

Q学習では、強化学習の基礎シリーズで説明したのとは異なるアプローチを考えます。 強化学習の基礎シリーズでは、「エージェントは入力を受け取って（望ましい）行動を出力する」と説明しました。 従って、強化学習の実装例とその解説で紹介したように、行動そのもの、もしくはその確率を直接出力するのが自然です。

しかし、Q学習は少し異なるアプローチを用います。 Q学習のエージェントは、「（入力を受け取り、そこでの）行動の価値」を出力します。 そして、エージェントは行動の価値が高い行動を取る、という風にするわけです。

この行動の価値を行動価値といい（そのまま）、数式中では $Q(s, a) として表すので、Q学習といいます。 なお、$s は状態（＝入力）、$a は行動を表します。 ちなみに、強化学習ではよく入力を状態と言います。

そして、入力から出力を求める演算部分に（層が多めの）ニューラルネットワークを使うと、DQNとなります。

DQNの学習方法

今回は、状態から行動価値を求める演算を自動調整することになります。 で、どう調整するのかと言うと、

Q(s_t, a_t)=r_{t+1}+\gamma\max_{a}Q(s_{t+1}, a)

となる方向に調整します。 ただし、状態 $s_t において行動 $a_t をとることで、報酬 $r_{t+1} を得て、状態 $s_{t+1} になったものとします。

要は、行動価値を再帰的に作りたいわけです。 $\gamma という謎の文字がありますが、とりあえず無視すると、

「ある行動の価値は、その行動で貰えた報酬と、『その行動で遷移した先の状態における行動価値の最大値』との和」

であるということになります。 これを解釈すると、行動価値とは、「（行動価値が最大の行動を取ると仮定して）その行動をしてから貰える報酬の和」ということです。 これが無限級数になってしまうので、行動価値を用いて漸化式で表現している、という感じです。

そして、この $\gamma は、時間割引率といいます。 未来の価値（報酬）を小さめにするための係数で、0と1の間の値をとります。 これはまあ数学的な事情によるものですが、すぐ貰える報酬（＝行動価値）の方が未来に貰えるそれよりも価値が高い、という風に考えてもいいと思います。 クレジットカードも個人情報を支払う対価として未来に（価値の低くなった）現金を支払っているわけですが、これと同じことです。

また、「〜〜となる方向に更新」という表現がありますが、これは本当にイコールになるようにすると今までの学習が無駄になってしまうので、イコールになるように（差を小さくするように）少しだけ更新する、という方法を通常取るからです。 これは機械学習フレームワークで機能が提供されているし、今回の本題でもないので、詳しい説明は割愛します。

DQNの実装

前回の記事では、方策勾配法というやつを紹介しました。 これと比べて、出力するものが行動（の確率）から行動の価値に変わるだけなので、根本的なところは変わりません。 どうせどちらも数値なので、見た目ではほぼ同じです。

方策勾配法との主要な違いは、

  • 基本的に価値が大きい行動をとる（greedy方策という）。
    • ただし、その価値はあくまで推定値であり嘘かもしれないので、たまに（確率 $\varepsilon で）ランダムに行動してみる（これを $\varepsilon-greedy 方策という）。
      • $\max_aQ(s_{t+1}, a) の部分が推定値になっている

くらいです。

なお、$\varepsilon-greedy方策に代わるものとして、ボルツマン方策とかがありますが、説明は割愛します。

学習の流れ

おおまかには以下の流れで学習を進めます。

  1. 環境をresetし、観測結果を受け取る。

  2. 観測結果をニューラルネットワークに通し、各行動の価値を出力する。

  3. 確率 $\varepsilon でランダムな行動を、確率 $1-\varepsilon で行動価値最大の行動を取る。新しい観測結果、報酬を受け取る。

  4. $Q(s_t, a_t)=r_{t+1}+\gamma\max_aQ(s_{t+1}, a) となる方向にニューラルネットワークを更新する。すなわち、誤差関数を $\mathit{loss}:=\bigl\{r_{t+1}+\gamma\max_aQ(s_{t+1}, a)-Q(s_t, a_t)\bigr\}^2 とし、これを最小化する方向に更新する。

    1. に戻る

環境

環境としては、CartPole-v0という、gym環境にデフォルトで付属してるやつを使いました。 小学校でよくやる、箒を逆さに立てて倒さないようにするあれです。 まあこの環境では箒ではなくて棒なんですが。

観測結果は要素数4のリスト（棒の位置・速度・角度・角速度）で、行動は2種類（棒を左に動かす・右に動かす）です。

エージェント

エージェントのニューラルネットワークは全結合層3層としました。

実装例

これを実装すると、以下のような感じになります。

agent.py

import torch
import torch.nn as nn
import torch.nn.functional as F

class Agent(nn.Module):
    def __init__(self, hidden):
        super().__init__()

        self.fc1 = nn.Linear(4, hidden)
        self.fc2 = nn.Linear(hidden, hidden)
        self.fc3 = nn.Linear(hidden, 2)

    def forward(self, x):
        x = F.relu(self.fc1(x))
        x = F.relu(self.fc2(x))
        return self.fc3(x)

train.py

from random import random

import gym
import tensorboardX as tbx
import torch
import torch.nn.functional as F
import torch.optim as opt
from tqdm import tqdm

from agent import Agent


# ハイパーパラメータ
HIDDEN_NUM = 32  # エージェントの隠れ層のニューロン数
EPISODE_NUM = 2000  # 何エピソード実行するか
GAMMA = .99  # 時間割引率

agent = Agent(HIDDEN_NUM)
env = gym.make('CartPole-v0')
optimizer = opt.Adam(agent.parameters())


# 状態を受け取り、行動価値最大の行動とその行動価値を返す
def calc_q(obs, train=False, random_act=False):
    obs = torch.tensor(obs, dtype=torch.float32).unsqueeze(0)
    if train:
        agent.train()
        qs = agent(obs).squeeze()
    else:
        agent.eval()
        with torch.no_grad():
            qs = agent(obs).squeeze()

    if random_act:
        action = env.action_space.sample()
    else:
        action = torch.argmax(qs).item()

    return action, qs[action]


def do_episode(epsilon):
    obs = env.reset()
    done = False
    reward_sum = 0

    while not done:
        # 確率epsilonでランダム行動
        action, q = calc_q(obs, train=True, random_act=(random() < epsilon))
        next_obs, reward, done, _ = env.step(action)

        reward_sum += reward

        # エージェントを更新
        if done:
            next_q = torch.zeros((), dtype=torch.float32)  # doneなら次の状態は存在せず行動価値も0
        else:
            _, next_q = calc_q(next_obs)  # max_{a} Q(s_{t+1}, a)
        loss = F.mse_loss(q, reward + GAMMA*next_q)

        optimizer.zero_grad()
        loss.backward()
        optimizer.step()

        obs = next_obs

    return reward_sum


if __name__ == '__main__':
    with tbx.SummaryWriter() as writer:
        for episode in tqdm(range(1, EPISODE_NUM + 1)):
            epsilon = .5 - episode * .5 / EPISODE_NUM  # epsilonを線形に小さくする
            reward_sum = do_episode(epsilon)
            writer.add_scalar('data/reward_sum', reward_sum, episode)

結果

全2000エピソード実行し、各エピソードで得られた報酬の和（割り引いていない和）のグラフを以下に示します。 横軸はエピソード番号、縦軸は報酬和です。 なお、CartPole-v0は、1ステップごとに、棒が倒れていなければ報酬1が貰えます。 200ステップするとゲームクリアということで強制的に終了する（doneがTrueになる）ので、最大報酬は200です。

エピソードが進むにつれて学習も進んでいき、（バラツキはあるものの）エピソード1000あたりから200ステップ棒を立たせ続けることができるようになっています。

f:id:gpageinin:20200118155459p:plain
報酬のグラフ

まとめ

単純なDQNのイメージと実装を紹介しました。 最後におさらいすると、

  • エージェントは（ある状態における）行動価値 $Q(s, a) を出力し、基本的にそれが最大になるように行動する
  • $Q(s_t, a_t)=r_{t+1}+\gamma\max_aQ(s_{t+1}, a) となるようにする

というのがDQNの要点です。

ただ、今回の問題は簡単だったので工夫せずとも学習が進みましたが、難しい問題はこのままではなかなか上手くいきません。 また、学習が進んでいても結果にバラツキがあるのも難点です。

これを解消するために、DQNには様々な工夫が取り入れられています。 特に、それらを全部入りにした「Rainbow」というやつが有名です。

次回は、このRainbowに取り入れられている工夫のイメージ説明と実装例を扱います。