メインコンテンツへスキップ
見出し画像

Gymで強化学習㊳REINFORCE:理論編

    前回は、ポリシー勾配法を理論的な側面から解説しました。今回はポリシー勾配法の具体例の一つであるREINFORCEを紹介します。

    REINFORCEでは、エージェントが行動を選び、その結果得られる報酬を使って行動の確率を更新します。このアプローチは、生涯報酬(割引報酬の和)が多くなる行動がより高い確率で選ばれるようにポリシーを調整するので、徐々に最適な行動を見つけることができます。

    しかし、REINFORCEは報酬のばらつきが大きいと非効率な場合があります。それでも、この手法は理論的には任意の報酬関数とポリシーに対して有効であり、多くの問題で適用が可能です。

    では、さっそく始めましょう。

    ポリシー勾配定理のおさらい

    前回紹介したポリシー勾配定理は、目的関数J(θ)J(\theta)の勾配∇θJ(θ)\nabla_\theta J(\theta)と行動選択の対数確率log⁡πθ(at∣st)\log \pi_\theta(a_t|s_t)の勾配∇θlog⁡πθ(at∣st)\nabla_\theta \log \pi_\theta(a_t|s_t)とを結びつけるものでした。

    ∇θJ(θ)=Eτ∼πθ[(∑t=0T−1∇θlog⁡πθ(at∣st))g(τ)]\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \Biggl[ \left(\sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t)\right) g(\tau) \Biggr]

    これによって行動選択をうまく調節することで目的関数を最大化できるという関係が示されました。また、生涯報酬g(τ)g(\tau)は、トラジェクトリτ\tauから、次のように計算できます。

    g(τ)=r1+γr2+γ2r3+⋯+γT−1rTg(\tau) = r_1 + \gamma r_2 + \gamma^2 r_3 + \dots + \gamma^{T-1} r_T

    γ\gammaは割引率です。報酬ri(i=1,…,T)r_i (i = 1, \dots, T)は、環境が持つ報酬関数から与えられます。それは、各状態においてポリシーが選択した行動に依存します。もちろん、ランダム性が含まれる場合もあります。

    上述の2つの式から分かることは、理論的にはポリシー勾配定理は、任意の報酬関数とポリシーに対して有効であり、多くの問題で適用が可能です。

    しかし、実際にポリシー勾配定理を実践するには、具体的にはどうしたら良いでしょうか。

    この問いに答える一つの手法が今回紹介するREINFORCEになります。

    REINFORCE(REward Increment = Nonnegative Factor X Offset Reinforcement X Characteristic Eligibility)は、ポリシー勾配定理を基にした強化学習アルゴリズムの一つです。このアルゴリズムは、エージェントが環境内で行動を選択し、その行動がもたらす報酬をもとにポリシー(行動選択の確率分布)を更新します。

    ポリシー勾配定理をそのまま実装すると学習の効率が悪くなるので、幾つかの点においてアプローチを修正しています。

    マルコフ性と行動選択の評価

    ポリシー勾配定理では、トラジェクトリ全体(エピソードの最初から最後までの経験)から得られる生涯報酬を勾配の計算に使っています。これは、エージェントがエピソード全体でどれだけ良いパフォーマンスを示したかを評価するためであり、マルコフ性とも矛盾しません。

    しかし、エピソードの最初ではなく、途中のステップからの最適な行動選択を評価するとしたらどうでしょうか。つまり、あるエピソードの途中のステップttからエピソードの終了までの部分トラジェクトリτt\tau_tを考えてもポリシー勾配定理は成り立つはずです。

    また、このように考えられるのはマルコフ性のおかげです。なぜなら、マルコフ性の前提においては、状態sts_tにおける行動ata_tの選択の確率はそれより前の状態には依存しないからです。よって、過去に得た報酬を行動の評価に加える必要はありません。

    そこで、各ステップttにおいて次のように分解して考えます。

    • 行動選択ata_tの対数確率log⁡πθ(at∣st)\log \pi_\theta(a_t|s_t)とその勾配∇θlog⁡πθ(at∣st)\nabla_\theta \log \pi_\theta(a_t|s_t)

    • ステップttからエピソード終了までの部分トラジェクトリτt\tau_t

    • 部分トラジェクトリτt\tau_tからの生涯報酬g(τt)g(\tau_t)

    以上より、各部分トラジェクトリτt\tau_tから目的関数に貢献する値を計算します。

    ∇θlog⁡πθ(at∣st)g(τt)\nabla_\theta \log \pi_\theta(a_t|s_t) g(\tau_t)

    これをすべてのステップに対して計算し合計したものを目的関数の勾配として使います。

    ∇θJ(θ)= Eτ∼πθ[∑t=0T−1 ∇θlog⁡πθ(at∣st)g(τt)]\nabla_\theta J(\theta) =  \mathbb{E}_{\tau \sim \pi_\theta}\left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) g(\tau_t) \right]

    これとポリシー勾配定理の式との違いは、報酬の総和をトラジェクトリ全体からのg(τ)g(\tau)としているか、部分トラジェクトリからのg(τt)g(\tau_t)としているかだけです。各ステップにおける行動選択の最適化は、その行動以後の総報酬から評価されるべきなので、過去の報酬を含めないことは、ある意味より正当な評価と言えます。

    簡単にまとめると、ポリシー勾配定理における行動評価にマルコフ性を適用し、各ステップでの行動選択がその後の生涯報酬で評価されるようになりました。これによって、行動の「良さ」をより正確に測定できるので、ポリシーの学習効率が上がる可能性があります。

    モンテカルロ法の導入

    ポリシー勾配定理では、目的関数の勾配は、さまざまなトラジェクトリから計算して得られる値の期待値として定義されています。しかし、このやり方だと多くのサンプルを集めるまでは、ポリシーのパラメータの更新が行えません。つまり、学習としての効率が悪くなります。

    そこで、REINFORCEでは、モンテカルロ法をポリシー勾配法に導入しました。モンテカルロ方法は、確率的なプロセス(例えば、環境との相互作用)からサンプルを取ることを繰り返して、近似的な解を求めるテクニックの一般名称です。

    よって、REINFORCEは、エピソード終了ごとに、目的関数の勾配を推定します。

    ∇θJ(θ)≈∑t=0T−1 ∇θlog⁡πθ(at∣st)g(τt)\nabla_\theta J(\theta) \approx \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) g(\tau_t)

    一つのエピソードから計算した目的関数の勾配を使うことで学習の効率を改善しています。

    具体的には次のようなステップに従って処理を行います。

    1. 現在のポリシーを使って環境から経験(状態、行動、報酬)を集める

    2. エピソード終了後に、目的関数の勾配を計算(推定)する

    3. ポリシーのパラメータを更新する

    4. 次のエピソードを開始し、ステップ1へ戻る

    次に、目的関数の勾配の計算をどのように行うのかを解説します。

    エピソードごとの勾配の計算

    REINFORCEでは、効率よく勾配の計算するためにトラジェクトリを逆方向に辿りながら計算します。

    例えば、エピソードが状態sTs_Tで終了したとします。すると、その一つ手前のステップからのトラジェクトリを考えることができます。

    画像

    このトラジェクトリをτT−1\tau_{T-1}と呼びましょう。トラジェクトリτT−1\tau_{T-1}の中身は、τT−1=(sT−1,aT−1,sT)\tau_{T-1} = (s_{T-1}, a_{T-1}, s_T)です。また、トラジェクトリτT−1\tau_{T-1}からの生涯報酬は以下になります。

    g(τT−1)=rTg(\tau_{T-1}) = r_T

    次に、もう一つ手前のステップT−2T-2からのトラジェクトリを考えます。このトラジェクトリをτT−2\tau_{T-2}と呼びましょう。トラジェクトリτT−2\tau_{T-2}の中身は、τT−2=(sT−2,aT−2,sT−1,aT−1,sT)\tau_{T-2} = (s_{T-2}, a_{T-2}, s_{T-1}, a_{T-1}, s_T)です。

    画像

    また、トラジェクトリτT−2\tau_{T-2}からの生涯報酬は以下になります。

    g(τT−2)=rT−1+γrTg(\tau_{T-2}) = r_{T-1} + \gamma r_T

    これを次のように表現することもできます。

    g(τT−2)=rT−1+ γg(τT−1)g(\tau_{T-2}) = r_{T-1} + \gamma g(\tau_{T-1})

    よって、ステップT−2T-2からの生涯報酬g(τT−2)g(\tau_{T-2})は、状態sT−2s_{T-2}における行動aT−2a_{T-2}から得た報酬rT−1r_{T-1}と、ステップT−1T-1からの生涯報酬g(τT−1)g(\tau_{T-1})をγ\gammaで割引したものを足したものに等しくなっています。

    より一般的に、次のように表現できます。

    g(τt)=rt+1+ γg(τt+1)g(\tau_t) = r_{t+1} + \gamma g(\tau_{t+1})

    この関係を使うと各ステップttからの生涯報酬g(τt)g(\tau_t)の計算が効率的に行えます。つまり、トラジェクトリをτT−1,τT−2,…,τ1,τ0\tau_{T-1}, \tau_{T-2}, \dots, \tau_1, \tau_0と逆方向に辿りながら、各ステップttからの生涯報酬g(τT−1),g(τT−2),…,g(τ1),g(τ0)g(\tau_{T-1}), g(\tau_{T-2}), \dots, g(\tau_{1}), g(\tau_{0})を次のように計算できます。

    g(τT−1)=rTg(τT−2)=rT−1+ γg(τT−1)⋮g(τ1)=r2+ γg(τ2)g(τ0)=r1+ γg(τ1)\begin{aligned} g(\tau_{T-1}) &= r_T \\ g(\tau_{T-2}) &= r_{T-1} + \gamma g(\tau_{T-1}) \\ \vdots \\ g(\tau_{1}) &= r_2 + \gamma g(\tau_2) \\ g(\tau_{0}) &= r_1 + \gamma g(\tau_1) \\ \end{aligned}

    各ステップにおける行動選択による目的関数の勾配への貢献の総和が目的関数の勾配の推定となります。

    ∇θJ(θ)≈∑t=0T−1 ∇θlog⁡πθ(at∣st)g(τt)\nabla_\theta J(\theta) \approx \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) g(\tau_t)

    なお、対数確率log⁡πθ(at∣st)\log \pi_\theta(a_t|s_t)は、ポリシー・ネットワークが選択した行動に対する確率を返すように実装し、その対数を計算するだけです。さらにその勾配はPyTorchなどで誤差逆伝播法を使えば自動的に計算されます。

    よって、以上からエピソード終了ごとにポリシーの勾配を計算しポリシーのパラメータの更新を行うことが可能となります。

    REINFORCEの基本的な考え方は以上となります。

    この手法では、エピソードからの部分トラジェクトリを使うことで効率的に目的関数の勾配に貢献する値を計算することができます。また、数学的な期待値を直接計算する代わりに、サンプリングによって勾配の推定を行っています。これらの勾配の推定値を用いてパラメータの更新を行うことで、ポリシーを逐次的に改善していきます。よって、ポリシー勾配定理の理論的な背景にある程度忠実でありながらも学習効率の良い現実的なアプローチを可能にしています。

    ベースラインによる分散低減

    モンテカルロ法は確率的なサンプリングに依存しているため、得られる生涯報酬の分散が高くなりがちです。目的関数の勾配が大きく上下する可能性があり、REINFORCEの学習効率に悪い影響を与える可能性があります。

    分散を低減する一つの効果的な方法は、生涯報酬のベースラインを導入することです。ベースラインとしての必要条件は、行動ata_tに依存しない関数であることです。

    具体的には、各ステップttでの生涯報酬g(τt)g(\tau_t)から、行動ata_tに依存しない関数bbを差し引きます。

    ∇θJ(θ)=Eτ∼πθ[∑t=0T−1∇θlog⁡πθ(at∣st)(g(τ) −b)]\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \Biggl[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \Bigl( g(\tau)  - b \Bigl) \Biggr]

    このように変更しても目的関数の勾配には影響しません。これは期待値の計算の中身を展開すると理解できます。


    あるステップttにおける計算だけに注目してベースラインの期待値を展開します。

    ∑aπθ(at∣st)∇log⁡πθ(at∣st)b\sum\limits_a \pi_\theta(a_t|s_t) \nabla \log \pi_\theta(a_t|s_t) b

    つまり、ある状態sts_tにおいての全ての可能な行動に対して対数行動確率の勾配∇log⁡πθ(at∣st)\nabla \log \pi_\theta(a_t|s_t)を計算し、各行動の確率πθ(at∣st)\pi_\theta(a_t|s_t)を重みとして加重平均を計算しています。

    これに対数の微分の公式(∇log⁡f=∇ff\nabla \log f = \frac{ \nabla f }{f} )を当てはめます。

    ∑aπθ(at∣st)∇πθ(at∣st)πθ(at∣st)b= ∑a(∇πθ(at∣st))b\sum\limits_a \pi_\theta(a_t|s_t) \frac{ \nabla \pi_\theta(a_t|s_t)}{ \pi_\theta(a_t|s_t) } b = \sum\limits_a (\nabla \pi_\theta(a_t|s_t)) b

    ここで、bbは、ata_tに依存しないので前に出します。

    ∑a(∇πθ(at∣st))b= b∑a∇πθ(at∣st)\sum\limits_a (\nabla \pi_\theta(a_t|s_t)) b = b \sum\limits_a \nabla \pi_\theta(a_t|s_t)

    微分の和は、和の微分であることを利用して式を書き直します。

    b∑a∇πθ(at∣st)= b∇∑aπθ(at∣st)b \sum\limits_a \nabla \pi_\theta(a_t|s_t) = b \nabla \sum\limits_a \pi_\theta(a_t|s_t)

    ∑aπθ(at∣st)=1\sum\limits_a \pi_\theta(a_t|s_t) = 1なので、その勾配はゼロです。

    b∇∑aπθ(at∣st)= b∇1=0b \nabla \sum\limits_a \pi_\theta(a_t|s_t) = b \nabla 1 = 0

    以上より、ベースラインによる目的関数の勾配への影響はゼロです。


    ただし、ベースラインを使うだけでは、生涯報酬の分散を低減できるとは限りません。そのためには、生涯報酬g(τ)g(\tau)からベースラインを差し引くことで、その絶対値が小さくなるようなベースラインを選ぶことが必要です。

    うまくベースラインを選べば、目的関数の勾配の期待値を変えることなく分散だけが低減し、学習がより効率的に行えるようになるのが理論的にわかりました。

    では、REINFORCEでベースラインを適用してみます。ポリシーが予測する状態価値関数vπθ(st)v_{\pi_\theta}(s_t)をベースラインとして使うことが効果的であることが知られています。

    ∇θJ(θ)≈∑t=0T−1 ∇θlog⁡πθ(at∣st)(g(τt)−vπθ(st))\nabla_\theta J(\theta) \approx \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) \biggl( g(\tau_t) - v_{\pi_\theta}(s_t) \biggr)

    このベースラインは状態sts_tのみに依存し、行動ata_tに依存しないのでベースラインの条件を満たしています。また、状態価値関数は、ある状態からの生涯報酬の期待値なので、g(τt)g(\tau_t)と値が近く分散を低減できることが期待されます。

    ここで、g(τt)−vπθ(st)g(\tau_t) - v_{\pi_\theta}(s_t)は、ある行動を選ぶことによるアドバンテージを計算しているのと同じです。なぜなら、g(τt)g(\tau_t)ある行動に従ったことによるトラジェクトリからの生涯報酬です。そして、vπθ(st)v_{\pi_\theta}(s_t)は、状態価値(その状態における行動確率分布による行動価値の期待値)だからです。

    つまり、Dueling DQNで使われたアドバンテージのようにどの行動を選ぶべきかを学ぶ手助けをしていると捉えることもできます。

    行動のアドバンテージが勾配の計算に影響するので、ポリシーの最適化によりどの行動を選ぶべきかの学習がより効率的になることが期待されます。

    次回予告

    次回は、REINFORCEの実装を行い簡単な実験をします。

    お楽しみに!

    (続く)

     
     
    「わかりやすく、具体的に」AIとサイエンスの情報を発信中

    あなたへのおすすめ