こんにちは。nosukeruです。

今回は強化学習のアルゴリズムを実際に実装し、この分野で一般的なベンチマークとして用いられるOpenAI Gymを使って遊んでみました。

コードはここに置いています（今後も追加予定）。深層学習のライブラリにはPyTorchを使っています。

Introduction to RL

強化学習ではエージェントがある環境下に置かれた状態で、環境とのやりとりを行いながら状況に応じた良い行動を習得することを目指します。時刻 $t$ におけるエージェントの状態(state)*1を $s_t \in S$ 、そこでエージェントが取る行動(action)を $a_t \in A$ と表します。*2

エージェントが行動を起こすことにより環境とのやりとりが行われ、エージェントの状態が $s_{t+1}$ に変化するとともに、報酬(reward) $r_t \in R$ を得ることができます。報酬は正とは限らず、負の場合にはペナルティとみなすことができます。このプロセスを繰り返してエージェントはゲームを進めていきます。

f:id:ey_nosukeru:20190504104131p:plain:w360 — エージェントと環境の関係. 引用元: http://ainow.ai/2016/11/07/104056/

エージェントの目的はこの報酬の和を最大化することなのですが、単純な和を取るだけだと行動を先送りにして「明日から本気出す」的なダメダメエージェントができてしまうことが考えられるので、割引率 $\gamma$ を導入し、近い将来の報酬により大きな価値を与える重み付け和が用いられることが多いです。

\begin{align} R = \sum _ {t=0} ^ {\infty} \gamma ^ t \end{align}

エージェントはこの報酬を最大化するため、自身の置かれている状態に対して適切な行動 $a_t$ を選択する必要があります。この基準となるのが方策(policy) $\pi(s, a) = P(a|s)$ で、状態sのもとで行動aを取る確率を表します。環境の状態遷移も確率的に定義されていることが多く、また確率的な方策の方がより幅広い戦略を取ることが可能になるため、このように確率的に定義しています。

その他、状態 $s$ で行動 $a$ を取った時次の状態 $s'$ に遷移する環境の確率を $P _ {s s'} ^ {a}$ と書き、状態や行動の潜在的な価値を表すものとして

\begin{align} Q ^ {\pi} (s, a) &= r + \gamma E _ {s' \sim P _ {s s'} ^ {a}} [V ^ {\pi} (s')] = r + \gamma \sum _ {s'} P _ {s s'} ^ {a} V ^ {\pi} (s') \\ V ^ {\pi} (s) &= E _ {a \sim \pi(s) } [Q ^ {\pi} (s, a)] = \sum _ {a} \pi (s, a) Q ^ {\pi} (s, a) \end{align}

を定義します。これらは価値関数(Value Function)と呼ばれ、方策 $\pi$ に従って行動した時に現在の状態や行動によってどれくらいの将来的な報酬が見込めるかというのを表しています。

Policy Gradient

強化学習の手法は、大きく次の2つに分けられます。

価値反復法(Value-Based Algorithm)

価値関数をモデル化し、 $Q(s, a)$ を最大化するような行動 $a$ を選ぶ方法

方策勾配法(Policy-Gradient Algorithm)

方策をモデル化し、報酬に対する方策の勾配を使って最適化する方法

今回は後者の方策勾配法を用います。価値反復法に比べると学習が遅いというデメリットがありますが、学習が安定している、確率的な振る舞いを取り込めるなどのメリットも多くあります。

PolicyGradientでは方策 $\pi$ をパラメータ $\theta$ でパラメータ化します。つまりパラメータ $\theta$ を持つモデルで表現しようということです。勾配やパラメータ最適化と聞くとニューラルネットが思い浮かベる人が多いと思いますが、今回の実装でも例に漏れずニューラルネットを用います。勾配を自動で計算してくれるのはやはり大きなポイントですね。

問題の目的は報酬の最大化なので、目的関数は

\begin{align} J(\theta) = V ^ {\pi} (s) = E _ {a \sim \pi(s; \theta)} [Q ^ {\pi} (s, a)] \end{align}

となります。 *3 この関数を最大にするように方策 $\pi$ もといパラメータ $\theta$ を最適化します。

目的関数が設定できたので、とりあえず微分してみます。

\begin{align} \frac{\partial J} {\partial \theta} &= \frac{\partial} {\partial \theta} E _ {a \sim \pi(s; \theta)} [Q ^ {\pi} (s, a)] \\ &= \frac{\partial} {\partial \theta} \sum _ {a} \pi (s, a; \theta) Q ^ {\pi} (s, a) \\ &= \sum _ {a} (\frac{\partial} {\partial \theta} \pi (s, a; \theta)) Q ^ {\pi} (s, a) \end{align}

ここで、 $\pi$ に関してサンプリングを行いたいので、 $\pi \times (何か)$ という形にしたいです。そこで対数微分の式

\begin{align} \frac{\partial} {\partial \theta} (\ln f) = \frac{1}{f} \frac{\partial f} {\partial \theta} \iff \frac{\partial f} {\partial \theta} = f \frac{\partial} {\partial \theta} (\ln f) \end{align}

を使うと、

\begin{align} \frac{\partial J} {\partial \theta} &= \sum _ {a} \pi (s, a; \theta) (\frac{\partial} {\partial \theta} \ln \pi (s, a; \theta)) Q ^ {\pi} (s, a) \\ &= E_ {a \sim \pi (s; \theta)} [(\frac{\partial} {\partial \theta} \ln \pi (s, a; \theta)) Q ^ {\pi} (s, a)] \\ &\simeq \frac{1}{N} \sum _ {a \sim \pi (s; \theta)} (\frac{\partial} {\partial \theta} \ln \pi (s, a; \theta)) Q ^ {\pi} (s, a) \end{align}

となり、状態 $a$ に対して現在の方策に基づいて $a$ をサンプリングし、中の式を評価して平均を求めることで目的関数の勾配を得ることができました。実装上はさらに、

\begin{align} (\frac{\partial} {\partial \theta} \ln \pi (s, a; \theta)) Q ^ {\pi} (s, a) = \frac{\partial} {\partial \theta} (\ln \pi (s, a; \theta) Q ^ {\pi} (s, a)) \end{align}

なので、誤差関数を $L = - \ln \pi (s, a; \theta) Q ^ {\pi} (s, a)$ とおけば普通の教師あり学習と同じように学習させることができます。誤差が最小化なのに対し今回の問題は報酬の最大化なのでマイナスをつける必要があることに注意です。

最後に「価値関数 $Q$ が計算できない」というあまりにも重大な問題が残っているのですが、一番ナイーブなPolicyGradientの実装ではこれをなんと1回のエピソード*4で得られた実際の報酬で近似してしまうという豪快な解決法をとります。一応 $Q$ は考えられる全ての状態遷移列に対して報酬和の平均を取ったものなので、試行回数1のサンプリング・精度の荒い近似という形で正当化することはできそうです。

ちなみに、Actor-Critic系のアルゴリズムは、この $Q$ 関数の近似部分にValue-Basedな手法を取り入れることで、より近似精度を挙げて効率的に学習されるようにしたハイブリッド型のアルゴリズムです。

さて、以上をまとめると、PolicyGradientのアルゴリズムは次のようになります。

現在の方策 $\pi(s, a; \theta)$ に基づいて行動し、状態・行動・報酬の列 $\tau = (s_0, a_0, r_0), (s_1, a_1, r_1), ..., (s_n, a_n, r_n)$ を得る。
$\tau$ のそれぞれについて、その状態以降の報酬和 $R = \sum _ {t'=t} ^ {n} \gamma ^ {t' - t} r_{t'}$ と $\pi(s_0, a_0; \theta)$ から誤差 $L$ を計算( $Q$ を $R$ で近似)。
$L$ をもとにモデルを学習、 $\theta$ を更新。
1~3を繰り返す。

3の学習のタイミングには1回ステップごと/1エピソードごと/複数エピソードごとなど任意性がありますが、今回は1エピソードごとに誤差を足し合わせて重みを更新するようにしました。

CartPole

OpenAI Gymには環境として様々なゲームが用意されていますが、今回扱うゲームは一番シンプルなCartPoleというゲームです。幼少期誰でも一度はやったであろう、手のひらの上でほうきを立てた状態をどれくらいの間キープできるかというあれです。友達の中に一人は暇を持て余してこのゲームを極め、悟りの境地に入った状態で永遠にやってる奴がいるあれです。

このゲームの目的は車を左右に動かしながら出来るだけ長い間棒を立った状態でキープすることになります。棒が右に倒れそうになったら車も右に移動し、といった具合にバランスを保つのが重要になります。棒と地面の角度が一定以下になったり、画面外に出てしまったりするとゲームオーバーとなります。

エージェントの取れる行動としては「車を左に動かす」「車を右に動かす」の2つしかなく、とてもシンプルです。

また、状態(観測)としては4つの数字からなる配列が与えられます。これらはそれぞれ車の位置、車の速度、棒の角度、棒の角速度を表しているそうです。

なお、実装上はこれらの数値・行動の意味を知る必要はありません。優れた強化学習のアルゴリズムは、事前知識を一切必要とすることなく、環境とのやりとりの中で物理法則なども含めたゲームの仕組みを学習することができます。

報酬としては、出来るだけ長い間ゲームオーバーにならないことが目的なので、1回アクションを起こすごとに一定値1の報酬が与えられ、プレイ時間がそのまま報酬になります。なお、CartPole-v0では200フレーム、CartPole-v1では500フレーム維持できれば自動的にクリアとなり、ゲームが終了します。

Implementation

コードの主要な部分だけ抜き出しています。全体はレポジトリを参照してください。

モデルの定義

class PolicyNet(nn.Module):
    def __init__(self, nInput: int, nHidden: int, nOutput: int):
        super(PolicyNet, self).__init__()
        self.fc1 = nn.Linear(nInput, nHidden)
        self.fc2 = nn.Linear(nHidden, nOutput)

    def forward(self, x):
        l1 = F.relu(self.fc1(x))
        return F.softmax(self.fc2(l1), dim=1)

学習

    env = gym.make('CartPole-v1')
    policyNet = policy.PolicyNet(nState, 20, nAction)
    optimizer = optim.Adam(policyNet.parameters())

    for episode in range(nEpisode):
        state = env.reset()
        steps: List[Step] = [] # step info for calculating loss

        # Exploration loop
        done = False
        while not done:
            env.render()

            # Make decision
            x = Variable(torch.Tensor([state]))
            probs = policyNet(x)

            action = np.random.choice(range(nAction), p=probs.detach().numpy()[0])
            nextState, reward, done, _ = env.step(action)

            steps.append(Step(probs[0][action], reward))
            state = nextState

        # Training
        loss = Variable(torch.tensor(1, dtype=torch.float32))
        for i, step in enumerate(steps):
            reward = sum([(gamma ** j) * s.reward for j, s in enumerate(steps[i:])])
            loss += -torch.log(step.confidence) * reward

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

GymとPyTorchの基本的な機能だけを使って上のアルゴリズムをシンプルに実装することができました。

Results

学習初期(~100epoch)

まだ仕組みをうまく学習できておらずすぐにゲームオーバーになってしまい、かくついて見えます。

学習中期(~500epoch)

かなりうまくなってきましたが棒を立てたまま画面外に飛んで行ってしまうパターンが多い印象です。

学習末期(~3000epoch)

かなりの割合でクリアできるようになってきました。

学習グラフ

f:id:ey_nosukeru:20190504145857p:plain — 訓練回数(エピソード)とその報酬

f:id:ey_nosukeru:20190504145811p:plain — 直近100エピソードの報酬平均と標準偏差

前半は順調に学習が進んでおり、後半は目に見えてクリアの回数が増えていることもわかりますが、依然として低スコアで終わってしまう場合があり、分散は高いままです。この分散が高くなりやすいという性質はPolicyGradientの欠点の一つであり、 $Q$ 関数を1回のサンプリング値で大雑把に近似していることに起因しているのですが、Actor-Critic系の派生アルゴリズムで改善されていくことになります。

おわりに

今回はGymの中でも一番簡単なCartPoleを使いましたが、今後もDQN/Actor-Critic/PPO/Curiosity-Learningなど近年の強化学習の手法を勉強しつつ、より難易度の高いゲームにもチャレンジしていきたいと思います。

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

参考文献

Gym

OpenAI Gymの公式チュートリアル。これだけでGymの基本的な使い方は大体わかります。

ライトニングpytorch入門 - Qiita

ライトニングにPyTorch入門できます。

An introduction to Policy Gradients with Cartpole and Doom

英語ですが、近年の強化学習の手法を一通り学ぶことができ、とてもわかりやすいです。

強化学習入門 Part2 - TensorflowとKerasとOpenAI GymでPolicy Gradientを実装してみよう！ - Platinum Data Blog by BrainPad

実装上でかなり参考にさせて頂きました。

https://papers.nips.cc/paper/1713-policy-gradient-methods-for-reinforcement-learning-with-function-approximation.pdf

PolicyGradientの元論文です。

*1:観測(observation)と呼ばれることもあります。

*2: $A$ は $s_t$ に依存すると考えることもできますが、ここではどの状態でも取れる行動は一定であるとします。

*3:スタートとゴールが明確に決まるゲームだと $s_0$ の方が適切なようにも思えますが、状態を限定してしまうよりもあらゆる状態に対してパフォーマンスを上げるようにした方が効率よく訓練できるので、この定義を採用することにします。またこの式ではsが束縛されておらず、厳密に書くと $s$ に関する期待値を取らなければいけませんが、 $s$ の分布を考えると複雑になってしまう( $s$ の分布が $\pi$ に依存しているなど)ので、ここでは「 $\pi$ に従って現れる $s$ に対して平均的に $J(\theta)$ を最適化する」ぐらいのニュアンスで捉えてもらえれば良いかと思います。厳密な証明については元論文を参照。