🦔

TRPO&PPOについて

に公開
機械学習
強化学習
tech

①方策勾配法の復習

強化学習の流れ

報酬を最大化するような方策を得ること

用語 説明
環境 プレイヤーが暴れまわるところ（行動に対してフィードバックが返ってくる）
行動 環境の中でプレイヤーが行う動作
方策 プレイヤーが行動を選ぶ際の指針となるもの
状態 プレイヤーの環境内での状態（位置、速度など）
報酬 行動に対する良さ度を表す値
エピソード ゲーム開始からゲーム終了までの一連の流れ

強化学習で使いそうな式

軌道：

\tau = (s_1, a_1, r_1, s_2, a_2, r_2, \ldots, s_T, a_T, r_T)

エピソード一連の状態，行動，報酬をまとめただけ．1エピソードの数式

収益：

G(\tau) = R_t+\gamma R_{t1}+\gamma^2 R_{t2}+\dots+\gamma^T R_T

収益は軌道中の報酬の総和．

目的関数：

J(\theta) = E_{\tau\sim\pi_\theta}[G(\tau)]

Jは報酬の期待値らしい．Eは期待値．当然収益は軌道によって変わるので報酬の期待値も変わる．
Jは1エピソードで平均してどれだけ報酬が与えられたのかがわかる．

更新式：

\theta \leftarrow \theta + \alpha\Delta_{\theta} J(\theta)

αはハイパーパラメータ．

で，そもそもこのθはなんぞやというと，方策をニューラルネットワーク化したもの重みパラメータとなる．

\pi(a|s) → \pi_\theta(a|s)

ニューラルネットワークになったため，今までのように目的関数の勾配を求めて更新していこう

今わからないのは目的関数の勾配

\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta} [\nabla_\theta \log \pi_\theta(a|s) Q^{\pi_\theta}(s,a)]

G(\tau)\Delta_{\theta}\log{\pi_\theta(A_t|S_t)}

→ 収益 x 状態S_t で 行動A_t を取る確率が最も高い方向

方策勾配法の問題点

上の式でもあるように，最もいい報酬になるような行動の方向は計算しているが，適切なステップ幅がわかっていない．

ステップ幅になりうる値：α or G(tau)

どちらも変えられない値になっているのでこれを改造する必要がありそう．

何となく変えられるとしたら…[上の更新式か?]

これを変えれるのがTRPO法となっている．

②TRPO（Trust region policy optimization)

TRPOは更新前と更新後の戦略があまり離れない，ようは徐々に変化できるように制約をかけるもの．更新前(old)の行動分布と更新後の行動分布がδ以下になるように制約がかかる．

E_t[KL[\pi_{\theta_{\text{old}}}(a_t|s_t)，\pi_\theta(a_t|s_t)]] \leq \delta

  • KL制約とは

    二つの確率分布の間の距離や違いを図るための指標．

この制限下で最大になるように目的関数を最大化するθを求める．方策勾配法とは全く違う

TRPO法の目的関数：

J(\theta) = E_{\tau\sim\pi_\theta} \left[ \frac{\pi_\theta(a|s)}{\pi_{\theta_{\text{old}}}(a|s)} A^{\pi_{\theta}}(s,a) \right]

ここでAはアドバンテージ関数であり、以下の式で定義される：

A^{\pi_{\theta_{\text{old}}}}(s,a) = Q^{\pi_{\theta_{\text{old}}}}(s,a) - V^{\pi_{\theta_{\text{old}}}}(s)

Qは行動価値関数

Vは状態価値関数

そもそもアドバンテージ関数とはなんぞや

アドバンテージ関数とは

A2Cについて

ここでわかっているのはアクション価値関数を求めることなく計算できるという点．

んで，この制約の中で勾配を求めるわけではない（てか求めるのだるそう）

だからTRPOでは目的関数の勾配を求めているのではなく，新しい方策と古い方策での報酬期待値の変化が大きくなるようなθを求める．

だからTRPOでは

💡 制約付きのもとで目的関数を最大化するためのパラメータ θ を求める必要がある
→ これは最適化問題として解く。

これによって更新幅の最大値を一定以下に抑えつつ，更新することができる．

てことで最適化問題を解くために報酬期待値の変化を計算する．

θold からθnewへの更新による報酬期待値の変化を考える

J(π_{θ_{new}}) - J(π_{θ_{old}}) = E_{s ∼ d_{π_{θ_{new}}}, a ∼ π_{θ_{new}}}[A_{π}(s,a)]

dnewはπnewによってサンプルを集めた時の各状態sの出現確率になっている．

方策パラメータθの更新による方策改善の最大化するためには，上式の右編を最大化するようなθnewを求める．

しかし，学習に利用できるサンプルは更新前方策newによって収集されたものなので求めることができない．改善した方策はある（当然oldによって求められたもんね）が，そこから実際に行動して，状態変化dとか報酬とかを求めるには実際に行動しなくてはいけない

つまり，方策勾配法から更新幅を決めるには

なのでここからnewを求めるために重点サンプリング法を用いることで求められる

以下は重点サンプリング法を適応し，行動aの確率分布をπθoldに変える

E_{s ∼ d_{π_{θ_{new}}}, a ∼ π_{θ_{new}}}[A_{π}(s,a)] = E_{s ∼ d_{π_{θ_{new}}}, a ∼ π_{θ_{old}}}\left[\frac{π_{θ_{new}}(a|s)}{π_{θ_{old}}(a|s)}A_{π}(s,a)\right]

dnewはπnewによってサンプルを集めた時の各状態sの出現確率になっている

んで，方策の値がそもそも近いなら各状態sの出現確率は更新前後でほとんど変わらないだろうという過程をおいてdθnew＝dθoldとなる．

＝　E_{s \sim d_{\pi_{\theta_{\text{old}}}}, a \sim \pi_{\theta_{\text{old}}}} \left[ \frac{\pi_{\theta_{\text{new}}}(a|s)}{\pi_{\theta_{\text{old}}}(s|a)} \right]

この式をどこで使うかというと下の式で使うわけよ（証明はもう見たくないからいいや）

で，TRPOでの最適化問題を解くためには共役勾配法とラインサーチを使う

この式覚えておいて

\theta_{\text{new}} = \theta_{\text{old}} + \alpha \Delta \theta

1.　共役勾配法：Δθを求める

  • 方策の更新を制約付き最適化問題として考える際に、共役勾配法は制約を考慮しながら効果的に勾配の方向を見つけるための手法として用いられます。
  • 共役勾配法は、方策の更新方向を見つけるために使用されるので、更新の方向性（ベクトル）を特定します。

2.　ラインサーチ：αを求める

  • 共役勾配法で見つけた更新方向が与えられたとき、どの程度のステップサイズでパラメータを更新するかを決定するのがラインサーチの役割です。
  • このステップサイズは、目的関数の値を最大化しつつ、与えられた制約を満たすように選択されます。

これでようやく全てがわかった

TRPOから進化したからTRPOと比べて説明する．

PPO（Proximal Policy Optimization）は，TRPOの考え方をベースにしつつ，よりシンプルで実装が容易な形で方策の更新を行うためのアルゴリズム．以下に，PPOとTRPOの主な違いとPPOの要点を説明する．

1. 主な違い:

  • 制約 vs クリッピング:
    • TRPO: 方策の変化を制限するために，KLダイバージェンスの制約を使用
    • PPO: 方策の変化を制限するための特定の制約を持たず，代わりに目的関数を修正してクリッピングする．これは，方策の更新が大きくなりすぎないようにするための手法．
  • 最適化:
    • TRPO: 制約付きの最適化問題を解く必要があります。このため、共役勾配法などの高度な手法が必要．
    • PPO: 無制約の最適化問題を解くだけなので、通常の確率的勾配降下法やAdamなどの最適化手法を使用．

2. PPOの要点:

PPOの核心は、方策の更新の際に以下のような修正された目的関数を最大化します：

L_{\text{clip}}(\theta) = E\left[\min\left(r_t(\theta) \hat{A}_t, \text{clip}\left(r_t(\theta), 1 - \epsilon, 1 + \epsilon\right) \hat{A}_t\right)\right]

ここで、

r_t(\theta) = \frac{\pi_{\theta}(a_t | s_t)}{\pi_{\theta_{\text{old}}}(a_t | s_t)}
  • Aはアドバンテージ関数の推定値
  • clip(x,a,b)はxをa,bの間にクリッピングする関数
  • ϵは通常小さな値（例：0.1や0.2）で、方策の変化を制限するためのもの

このクリッピングされた目的関数は、方策の更新が大きくなりすぎる場合にペナルティを加えることで、方策の更新量を適切に制限

そもそもなんでこんなものが突然出てきたのかって話よ

TRPOの目的関数がこれ

J(\theta) = E_{\tau\sim\pi_\theta} \left[ \frac{\pi_\theta(a|s)}{\pi_{\theta_{\text{old}}}(a|s)} A^{\pi_{\theta}}(s,a) \right]

この中に直接KL制限を入れちまおうって話がある

つまり

J(\theta) = E_{\tau\sim\pi_\theta} \left[ \frac{\pi_\theta(a|s)}{\pi_{\theta_{\text{old}}}(a|s)} A^{\pi_{\theta}}(s,a)　-　{\beta}KL[\pi_{\theta_{\text{old}}}(a_t|s_t)，\pi_\theta(a_t|s_t)] \right]

ってのがある．

ただこれだとKL距離が大きくなるとアドバンテージ関数からもらった価値がマイナスされてしまう．（そもそも制限をかけているだけで，距離が大きくなること自体そんなに悪いことじゃない，むしろ悪いのは毎回距離が馬鹿みたいに大きくなるからいけないだけ）

だからやりたいことは

💡 更新幅を抑えつつ，得られる Advantage を最大化したい！

ってことになる．

で，出てきたのがclipとかいう目的関数自体に制限をかける．

L_{\text{clip}}(\theta) = E\left[\min\left(r_t(\theta) \hat{A}_t, \text{clip}\left(r_t(\theta), 1 - \epsilon, 1 + \epsilon\right) \hat{A}_t\right)\right]
r_t(\theta) = \frac{\pi_{\theta}(a_t | s_t)}{\pi_{\theta_{\text{old}}}(a_t | s_t)}

まず一つ一つ式を確認すると

clip(x,a,b)はxをaからbの間に制限するというもの

つまり

r_t(\theta) = \frac{\pi_{\theta}(a_t | s_t)}{\pi_{\theta_{\text{old}}}(a_t | s_t)}

となる．

つまりPPOでは古い方策と新しい方策の比率が激しく変化するのを抑えようという考えになっている．

  • 具体的なクリッピングの例はこちら

    想像してください。ある数値を0から10の範囲に制限したいとします。この場合、クリッピング関数は次のように動作します：

    • 0より小さい値は0になる
    • 10より大きい値は10になる
    • 0から10の間の値はそのままの値を取る

    具体的な計算例:

    1. x=−5 → クリッピング後: 0
    2. x=7 → クリッピング後: 7
    3. x=15 → クリッピング後: 10

    PPOの方策クリッピングの例

    PPOのクリッピングは、方策の比率 ��rt に適用されます。例として、�=0.2ϵ=0.2 の場合を考えましょう。この場合、クリッピングの範囲は [0.8, 1.2] となります。

    • rt=0.7 の場合：クリッピング後の rt は0.8
    • rt=1.0 の場合：クリッピング後の rt は1.0（変わらない）
    • rt=1.3 の場合：クリッピング後の rt は1.2

    このように、PPOのクリッピングでは、方策の比率が特定の範囲を超える場合、それを範囲内に制限します。これにより、方策の更新が過度に大きくなるのを防いでいます。

    これらの例を参考に、クリッピングがどのように動作するのかの基本的なイメージを掴むことができると思います。

てことで変な制限をかけることなく，今までの方策勾配法と同じようにするだけで，大丈夫

ただし，PPOでは方策のみを改善しているので，更新幅がわからなくても大丈夫！

だって方策を改善してるからねん！

Discussion