Policy Gradient 入門学習

本文は、Andrej Karpathy の Deep RL Bootcamp とそのブログの記録です。ブログリンク：Deep Reinforcement Learning: Pong from Pixels

RL の進展は新奇で驚くべきアイデアによって主に推進されているわけではありません:

2012 年の AlexNet は、1990 年代の ConvNets の拡張（より深く、より広く）に過ぎません。
2013 年の ATARI ゲームに関する深層 Q 学習の論文は、実際には標準的なアルゴリズムの実装（すなわち、関数近似を伴う Q 学習、Sutton 1998）であり、関数近似器はちょうど ConvNet です。AlphaGo は、ポリシー勾配とモンテカルロ木探索（MCTS）を組み合わせて使用しましたが、これらも標準的なコンポーネントです。もちろん、これらのアルゴリズムを効果的に動作させるためには多くのテクニックと忍耐が必要であり、古いアルゴリズムに基づいて多くの巧妙な改良が開発されましたが、大まかに言えば、最近の進展の主な推進力はアルゴリズム自体ではなく、（コンピュータビジョンと同様に）計算能力、データ、インフラストラクチャです。——Andrej Karpahy

ATARI Pong#

Pong はマルコフ決定過程（MDP）の特例です：各ノードが特定のゲーム状態を表し、各エッジが可能な（通常は確率的な）遷移を表すグラフです。各エッジには報酬が与えられ、目標は任意の状態で報酬を最大化するための最適な行動を計算することです。

Pasted image 20240910163109

マルコフ決定過程（Markov Decision Process, MDP）は、不確実な環境での意思決定のための数学的枠組みです。MDPは、現在の状態、可能な行動、状態遷移確率、報酬関数を考慮することで、意思決定者がランダムな要因に直面したときに最適な意思決定を行うのを助けます。

ゲーム原理#

私たちは画像フレーム（ピクセル値を表す 0-255 のバイト配列）を受け取り、それに基づいてラケットを上または下に移動させるかどうかを決定します（二項選択）。選択を行った後、ゲームシミュレーターはこの操作を実行し、私たちに報酬を与えます：ボールが相手を越えた場合（勝利）報酬は + 1、ボールに当たらなかった場合は - 1、そうでなければ報酬は 0 です。私たちの目標は、できるだけ多くの報酬を得るためにラケットを移動させることです。

解決策の検討においては、このゲームに対する仮定をできるだけ少なくし、単なるおもちゃのケースとして学ぶことを目指します。

ポリシー勾配#

ポリシー勾配アルゴリズムは、そのエンドツーエンドの特性から好まれています：明確なポリシーと原則的な方法があり、期待報酬を直接最適化します。

ポリシーネットワーク#

Pasted image 20240910211934

エージェントのポリシーネットワークを定義します。これはゲーム状態を受け取り、取るべき決定（上または下）を決定します。ここでは、原始画像ピクセル（210×160×3=100,800 210\times160\times3=100,800）を受け取り、上に移動する確率を表す数を生成する 2 層の nn を使用します。通常、確率的ポリシーを使用し、決定論的な決定ではなく、各イテレーションで確率分布からサンプリングします（すなわち、偏ったコインを投げる、p p & (1−p) (1-p) ）ことで実際の移動を取得します（エージェントが時々次善の行動を選択することを許可し、より良いポリシーを発見する可能性があります）。

h = np.dot(W1, x)     # 隠れ層ニューロンの活性化を計算（重み行列と入力のドット積）
h[h < 0] = 0          # ReLU：0未満の値を0に設定、すなわちmax(0, h)
logp = np.dot(W2, h)  # 上に移動する対数確率を計算、W2は隠れ層から出力層への重み行列
# Sigmoidを使用してlog確率を上に移動する確率値（0, 1）に変換
p = 1.0 / (1.0 + np.exp(-logp))

直感的には、隠れ層のニューロン（重みはW1の行に配置されている）はさまざまなゲームシーンを検出でき、W2の重みは各状況で上に移動すべきか下に移動すべきかを決定します。初期状態では、ランダムに初期化されたパラメータの効果は、プレイヤーがその場で痙攣しているようなもので、目標はゲームをマスターするW1、W2を見つけることです。

前処理#

理想的には、神経ネットワークに少なくとも 2 フレームの画像を入力したいと考えています（運動を検出するため）。操作を簡素化するために、入力画像を前処理し、現在のフレームと前のフレームの差分を入力することができます。

クレジット割り当て問題#

ここまで来ると、数百の時間ステップ後に非ゼロの報酬を得る可能性があることを想像できますが、その時点ではどのステップが効果を発揮したのか、前のステップ、第 10 フレーム、第 90 フレーム、またはそのいくつかのパラメータなのかはわかりません。

これが RL におけるクレジット割り当て問題（Credit Assignment Problem, CAP）です。私たちのシナリオでは、+1 の報酬を得た理由は、偶然にもボールを良好な軌道で弾き、相手のラケットを越えたからですが、この 1 つの動作は報酬を得る前の多くのフレームの前に行われたものです。つまり、あるステップの後、私たちが取ったすべての動作は報酬を得るのに役立たなかったということです。

教師あり学習#

ポリシー勾配解決策に入る前に、強化学習に非常に似た教師あり学習を振り返ります。教師あり学習の目標は、逆伝播を通じてパラメータを調整し、モデルが正しいクラスをより正確に予測できるようにすることです。

モデルは画像を入力として受け取り、クラスの確率を出力します。たとえば、ネットワークが UP と DOWN のクラスの対数確率 $(-1.2, -0.36)$ を出力し、対応する実際の確率は30%と70%です。私たちは正しいラベル（たとえば UP）を知っているため、最適化の目標は最大化このラベルの対数確率です。私たちは UP の対数確率の勾配を計算し、逆伝播を使用してネットワークのパラメータを調整します。
$\nabla_W \log p(y=UP \mid x)$ を計算することで勾配を得て、この勾配は各パラメータをどのように調整すればモデルが UP を予測する傾向を強めるかを教えてくれます。

もしあるパラメータの勾配が - 2.1 であれば、そのパラメータを減少させることで（たとえば 0.001 を減少させることで）、UP の対数確率を $2.1 \times 0.001$ だけ下げることができます。
パラメータの更新が完了すると、ネットワークは類似の状況で UP を予測する傾向がわずかに高まります。

ポリシー勾配#

しかし、強化学習のシナリオでは、正しいラベルがありません。これが PG の出番です：

初期段階：モデルは UP の確率を 30% $(\log p = -1.2)$ 、DOWN の確率を 70%( $\log p = -0.36$ ) と計算し、この分布からランダムにサンプリングしてアクションを選択します。たとえば、DOWN を選択し、実行します。
勾配計算：教師あり学習のように、選択したアクション（DOWN）の対数確率に対してすぐに勾配を計算できます。しかし、この時点ではこのアクションが良いアクションであるかどうかはわかりません。
フィードバックを待つ：ゲームが終了した後、報酬を得ることができます。たとえば、Pong でゲームに負けた場合、報酬 - 1 を得ると、この - 1 を DOWN アクションの勾配として逆伝播します。
最適化効果：この例では、DOWN が失敗を引き起こしたため、勾配はネットワークが将来の DOWN アクションの選択を減少させるようにします。

したがって、ポリシー勾配法は遅延報酬に基づいてポリシーを調整し、モデルが将来成功するアクションを取る可能性を高めます。

トレーニングプロトコル#

完全なトレーニングプロセスは次のとおりです：

ランダムなW1、W2でポリシーネットワークを初期化します。
100 試合の Pong ゲームを行います（ポリシーリプレイ、ロールアウト）。

各試合に 200 フレームがあると仮定し、合計で 20,000 回の上または下の決定を行いました。私たちは各決定に対してパラメータ勾配を計算でき、これが特定の状態での決定を促すためにモデルを調整する方法を教えてくれます。

学習更新：

12 試合に勝ったと仮定すると、これらの 12 試合での 2400 回の決定が正の更新（勾配に + 1.0 を加える）され、これらの決定を促します。
さらに 88 試合に負けたため、これらの 88 試合での 17600 回の決定が負の更新され、これらの決定を促しません。

ネットワークは有効なアクションの確率をわずかに増加させ、無効なアクションの確率をわずかに減少させます。

このわずかに改善されたポリシーを使用して再度 100 試合のゲームを行い、2、3 のプロセスを繰り返してポリシーを最適化します。

[!Karpathy の要約]
ポリシー勾配：ポリシーをしばらく実行します。どのアクションが高い報酬につながったかを確認します。それらの確率を増加させます。
ポリシー勾配：ポリシーを一定期間実行します。どのアクションが高い報酬をもたらしたかを観察します。それらの確率を増加させます。

図のように、各黒い円はゲーム状態を表し、各矢印は状態遷移を示し、サンプリングされたアクションが付随しています。PG を使用する際、私たちは勝利した 2 試合を選択し、そのラウンド内のすべてのアクションをわずかに促し、逆に抑制します。

さて、問題が発生します。もし私たちが第 50 フレームで「ボールを弾き返す」という正しい決定を下したとしますが、最終的な結果が第 150 フレームでボールを逃して失敗した場合、上記のトレーニングルールに従って、そのラウンドのすべてのアクションが抑制されることになります。そうすると、第 50 フレームでの正しい決定に影響を与えることになりますか？

答えは「はい」です。しかし、ゲームのサンプル空間全体に数千、さらには数百万の試合プロセスがあることを考慮すると、正しい決定は将来的に勝利する可能性を高めるため、平均的には最終的なポリシーは正しいアクションを取ることになります。

ポリシー勾配と教師あり学習の関係#

ポリシー勾配法は、実際には教師あり学習に似ていますが、次の点が異なります：

モデルがサンプリングしたアクションを「ラベル」として使用します。
アクションの良し悪し（報酬または罰）に基づいて損失関数の重みを調整します。

標準的な教師あり学習では、目標は最大化各トレーニングサンプルの対数確率 $\log p(y_i \mid x_i)$ であり、ここで $x_i$ は入力（画像）、 $y_i$ は正しいラベル（画像のクラス）です。

強化学習では、正しいラベル $y_i$ がありません。したがって、ポリシーモデルがサンプリングしたアクション（たとえば上または下）を「擬似ラベル」として使用します。最終結果（たとえば勝利または敗北）に基づいて、各サンプルの損失重みを調整し、有効なアクションの確率を増加させ、無効なアクションの確率を減少させます。

したがって、強化学習は ** 変化するデータセット（ラウンド）** 上での教師あり学習と見なすことができ、これらのデータセットは異なるゲームやシナリオからサンプリングされ、結果に基づいて各サンプルの損失の大きさを調整します。

一般的な優位関数#

以前は、勝利したかどうかに基づいて各アクションの良し悪しを判断していましたが、より一般的な RL 環境では、各時間ステップで何らかの即時報酬 $r_t$ を得ることになります。たとえば、ゲーム内の得点や環境からのフィードバックなどです。

割引報酬#

一般的な方法は、** 割引報酬（Discounted Reward）** を使用して、あるアクションの後の累積報酬を計算することです。割引報酬の公式は次のとおりです：

R_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k}

$\gamma$ は割引因子で、0 から 1 の範囲（たとえば 0.99）で、将来の報酬の影響を減少させるために使用されます。
現在の時間 $t$ から始まり、将来の各時間ステップの報酬 $r_{t+k}$ は、現在の時刻からの距離に応じて割引され、遠く離れた報酬はより多く減少します。

リターンの正規化#

20,000 のアクション（たとえば 100 試合の Pong ゲーム中のすべてのアクション）に対して $R_t$ を計算した後、これらの戻り値を標準化することは一般的な慣行です。たとえば、平均を引き、標準偏差で割ることで実現します：

R'_t = \frac{R_t - \mu}{\sigma}

標準化は、アクションの促進と罰の比率をバランスさせ、バッチ内で約半分のアクションが促進され、もう半分が罰せられることを保証します。数学的には、これはポリシー勾配推定の分散を制御する方法として説明できます。分散を減少させることは、勾配更新をより安定させ、モデルが収束しやすくなることを意味します。

PG の導出#

ポリシー勾配は、より一般的なスコア関数勾配推定器の特例です。次の式を考えます：

$E_{x\sim p(x|\theta)}[f(x)]$

ここで：

$f(x)$ はスカラー値のスコア関数（強化学習では通常報酬関数または優位関数）
$p(x;\theta)$ はパラメータ $\theta$ でパラメータ化された確率分布（強化学習では通常ポリシーネットワーク）

目標：サンプルのスコアを増加させるために分布を調整する方法（そのパラメータ $\theta$ を変更すること）を見つけることです。

[! ここでのトリックを理解する]
対数関数の微分の基本的な性質：

\frac{\partial}{\partial \theta} \log(z(\theta)) = \frac{1}{z(\theta)} \cdot \frac{\partial z(\theta)}{\partial \theta}

$\nabla_\theta$ を $\theta$ に対する勾配として表現します：

\nabla_\theta \log(z) = \frac{1}{z} \nabla_\theta z

[!OpenAI Spinning Up のバージョン：]

Pasted image 20240911143355

これは期待値であり、サンプル平均を使用して推定できます。もし私たちが一連の軌跡 $\mathcal{D} = \{\tau_i\}_{i=1,...,N}$ を収集した場合、ここで各軌跡はエージェントが環境内でポリシー $\pi_{\theta}$ を使用して行動することによって得られたものであれば、ポリシー勾配は次の方法で推定できます：
${g} = \frac{1}{|\mathcal{D}|} \sum_{\tau \in \mathcal{D}} \sum_{t=0}^{T} \nabla_{\theta} \log \pi_{\theta}(a_t |s_t) R(\tau),$
ここで $|\mathcal{D}|$ は $\mathcal{D}$ 内の軌跡の数（ここでは $N$ ）を示します。
この最終的な表現は、我々が期待する計算可能な表現の最も単純なバージョンです。もし我々が何らかの方法で我々のポリシーを表現し、 $\nabla_{\theta} \log \pi_{\theta}(a|s)$ を計算できるなら、環境内でそのポリシーを実行して軌跡データセットを収集することができれば、ポリシー勾配を計算し、更新ステップを取ることができます。

GYM での実践#

モデルの初期化#

H = 200 # 隠れ層ニューロンの数
batch_size = 10 # 何エピソードごとにパラメータを更新するか
learning_rate = 1e-4
gamma = 0.99 # 報酬の割引因子

# モデルの初期化
D = 80 * 80 # 入力次元：80x80グリッド
model = {}
model['W1'] = np.random.randn(H,D) / np.sqrt(D) # "Xavier"初期化
model['W2'] = np.random.randn(H) / np.sqrt(H)

補助関数#

def prepro(I):
    """ 210x160x3のuint8フレームを6400 (80x80)の1D浮動小数点ベクトルに前処理します """
    I = I[35:195] # クロップ
    I = I[::2,::2,0] # ダウンサンプリング
    I[I == 144] = 0 # 背景を消去
    I[I == 109] = 0 # 背景を消去
    I[I != 0] = 1 # その他（ラケット、ボール）を1に設定
    return I.astype(np.float64).ravel()

def discount_rewards(r):
    """ 割引報酬を計算します """
    discounted_r = np.zeros_like(r)
    running_add = 0
    for t in reversed(range(0, r.size)):
        if r[t] != 0: running_add = 0 # 合計をリセット、これはゲームの境界（Pong特有）
        running_add = running_add * gamma + r[t]
        discounted_r[t] = running_add
    return discounted_r

ポリシーネットワーク#

def policy_forward(x):
    h = np.dot(model['W1'], x)
    h[h<0] = 0 # ReLU非線形
    logp = np.dot(model['W2'], h)
    p = sigmoid(logp)
    return p, h # アクション2を取る確率と隠れ状態を返します

def policy_backward(eph, epdlogp):
    """ 逆伝播 """
    dW2 = np.dot(eph.T, epdlogp).ravel()
    dh = np.outer(epdlogp, model['W2'])
    dh[eph <= 0] = 0 # 逆伝播ReLU
    dW1 = np.dot(dh.T, epx)
    return {'W1':dW1, 'W2':dW2}

ポリシーネットワークのフォワード＆バックワードを実装します。

メインループ#

while True:
    # 観察を前処理します
    cur_x = prepro(observation)
    x = cur_x - prev_x if prev_x is not None else np.zeros(D)
    prev_x = cur_x

    # フォワードプロパゲーションを行いアクションをサンプリングします
    aprob, h = policy_forward(x)
    action = 2 if np.random.uniform() < aprob else 3

    # 中間状態を記録します
    xs.append(x) # 観察
    hs.append(h) # 隠れ状態
    y = 1 if action == 2 else 0 # "擬似ラベル"
    dlogps.append(y - aprob) # 取ったアクションの勾配を促します

    # アクションを実行します
    observation, reward, done, info = env.step(action)
    reward_sum += reward
    drs.append(reward) # 報酬を記録します

エピソード終了時の処理#

    if done:
        episode_number += 1

        # このエピソードのすべての入力、隠れ状態、アクション勾配、報酬をスタックします
        epx = np.vstack(xs)
        eph = np.vstack(hs)
        epdlogp = np.vstack(dlogps)
        epr = np.vstack(drs)
        xs,hs,dlogps,drs = [],[],[],[] # 配列のメモリをリセット

        # 割引報酬を計算します
        discounted_epr = discount_rewards(epr)
        # 報酬を標準化します
        discounted_epr -= np.mean(discounted_epr)
        discounted_epr /= np.std(discounted_epr)

        epdlogp *= discounted_epr # 優位性を使用して勾配を調整します（ポリシー勾配の核心）
        grad = policy_backward(eph, epdlogp)
        for k in model: grad_buffer[k] += grad[k] # バッチ内で勾配を累積します

各エピソード終了時にポリシー勾配を計算し、勾配バッファに累積します。

パラメータ更新#

grad_buffer = { k : np.zeros_like(v) for k,v in model.items() } # バッチ内で勾配を累積するための更新バッファ
rmsprop_cache = { k : np.zeros_like(v) for k,v in model.items() } # rmspropメモリ

    if episode_number % batch_size == 0:
        for k,v in model.items():
            g = grad_buffer[k] # 勾配
            rmsprop_cache[k] = decay_rate * rmsprop_cache[k] + (1 - decay_rate) * g**2
            model[k] += learning_rate * g / (np.sqrt(rmsprop_cache[k]) + 1e-5)
            grad_buffer[k] = np.zeros_like(v) # バッチ勾配バッファをリセット

RMSProp アルゴリズムを使用してモデルパラメータを更新します。

AK の反省#

人間にとっては、「上下に動かせるラケットを制御し、あなたの仕事はボールを AI の対戦相手に弾き返すことです」と言いますが、標準的な強化学習の問題では、環境との相互作用を通じて任意の報酬関数を仮定します。人間のプレイヤーは、ボールの軌道が物理法則に従う、AI の対戦相手の可能な移動戦略などの直感的な心理学のような多くの先入観を持ち込み、常に通常のゲーム画面を見る必要があります。しかし、ポリシー勾配解決策においては、フレームのピクセルがランダムに並べられていても、全結合ネットワークのポリシー勾配はその違いを認識できません。

したがって、ポリシー勾配は、正しいアクションを発見し、それをポリシーとして内面化するための暴力的な解法です。

ポリシー勾配は、多くのゲームで人間を簡単に打ち負かすことができます。特に、頻繁な報酬信号、正確な操作、迅速な反応を必要とし、あまり長期的な計画を必要としないゲームでは、これらの短期的な報酬とアクションの関連性がこの方法によって容易に「認識」され、ポリシーが巧みに実行されます。Pong ゲームのトレーニング後期の結果からもわかるように、エージェントはボールが近づくとすぐに動いてボールをキャッチし、その後迅速かつ高い垂直速度でボールを発射します。多くの ATARI ゲームにおいて、深層 Q 学習はこの方法で人間の基本的なパフォーマンスを完全に超えました —— たとえば、ブロック崩しやピンボールなどです。