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，我們的目標就是移動球拍以獲得儘可能的多的獎勵。

在解決方案的探討中，會儘量減少對該遊戲的假設，僅作為玩具案例來學習。

策略梯度#

Policy Gradient 算法因其端到端特性而備受青睞：它有明確的策略和原則性方法，直接優化預期獎勵

Policy Network#

Pasted image 20240910211934

定義一個 Agent 的策略網絡，它接收遊戲狀態，決定應該採取的決策（向上或向下）。這裡使用一個兩層的 nn，接收原始圖像像素（210×160×3=100,800 210\times160\times3=100,800 ），並生成一個表示向上移動概率的數。通常使用隨機策略而不是確定性決策，即每次迭代時從概率分佈中進行採樣（即拋一枚有偏的硬幣，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 幀圖像（以檢測到運動）。為了簡化操作，我們可以對輸入圖像做預處理，即輸入當前幀與上一幀的差值。

Credit Assignment Problem#

到這裡可以想象，可能在經過數百個時間步後才得到非零獎勵，但這時我們也不知道是哪一步起了作用，是上一步，第 10 幀和第 90 幀還是那幾個參數？

這便是 RL 中的信用分配問題（Credit Assignment Problem, CAP）。在我們的場景下，得到 + 1 獎勵的原因是我們碰巧把球彈出了良好的軌跡並超過了對方的拍子，但這一個動作是得到獎勵前的許多幀之前做的。也就是說，在某一步之後，我們採取的所有動作都對獲得獎勵沒有幫助。

Supervised Learning#

在深入策略提督解決方案前，先回顧一下與強化學習很像的監督學習。監督學習的目標是通過反向傳播調整參數，使模型越來越精確地預測出正確的類別。

模型接收圖片輸入，輸出類別的概率。例如，網絡給出類別 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。

Policy Gradient#

但是在強化學習場景中，我們沒有正確的標籤，這就是 PG 的用武之地了：

初始階段：模型計算出 UP 的概率為 30% $(\log p = -1.2)$ 和 DOWN 的概率為 70%( $\log p = -0.36$ ），我們從這個分佈中隨機採樣一個動作，比如選擇 DOWN，並執行。
梯度計算：我們可以像監督學習一樣，立刻對所選動作（DOWN）的對數概率計算梯度。但此時我們還不知道這個動作是否是好動作。
等待反饋：可以等待遊戲結束後，獲得獎勵。例如在 Pong 中，如果我們輸了遊戲，得到獎勵 -1，則將這個 -1 作為 DOWN 動作的梯度進行反向傳播。
優化效果：在這個例子中，DOWN 導致了失敗，梯度會使網絡減少未來對 DOWN 動作的選擇。

因此，策略梯度方法根據延遲獎勵來調整策略，使得模型在未來更可能採取成功的動作。

Training Protocol#

完整的訓練流程如下：

用隨機的 W1、W2 初始化策略網絡
進行 100 場 Pong 遊戲（策略回放，rollouts）

假設每場比賽有 200 幀，總共做了 20,000 次向上或向下的決策。我們可以為每次決策計算參數梯度，這告訴我們如何調整模型以鼓勵特定狀態下的決策。

學習更新：

假設贏了其中的 12 場比賽，則在這 12 場比賽中的 2400 次決策會被正向更新（梯度填入 +1.0），鼓勵這些決策。
由於輸了另外 88 場比賽，則在這 88 場比賽中的 17600 次決策會被負向更新，不鼓勵這些決策。

網絡會略微增加有效動作的概率，並略微減少無效動作的概率。

我們使用這個略微改進的策略再玩 100 局遊戲，重複 2，3 的過程，不斷優化策略。

[!Karpathy's summary]
Policy Gradients: Run a policy for a while. See what actions led to high rewards. Increase their probability.
策略梯度：運行策略一段時間。觀察哪些行動帶來了高回報。增加它們的概率。

如圖，每個黑色圈代表遊戲狀態，每個箭頭表示狀態轉移，並附上採樣的動作。使用 PG 時，我們選取贏的兩場比賽，輕微地鼓勵該回合中的每一個動作，反之則抑制。

那麼問題來了，假設我們在第 50 幀做了 “將球彈回” 的正確決策，但最終結果是在第 150 幀錯過了球而失敗，根據上面的訓練規則，該回合的每一個動作都將被抑制，那這樣會打擊到我們第 50 幀所做的正確決策嗎？

答案是會的，然而當我們考慮到整個遊戲樣本空間中成千上萬，甚至上百萬的比賽過程時，正確的決策會讓我們在未來更有可能獲勝，因此平均來看，我們的最終策略會做出正確的行動。

策略梯度與監督學習的聯繫#

策略梯度法其實和監督學習類似，只是：

我們用模型採樣到的動作作為 “標籤”。
我們根據動作的好壞（獎勵或懲罰）調整損失函數的權重。

在標準的監督學習中，目標是最大化每個訓練樣本的對數概率 $\log p(y_i \mid x_i)$ 其中 $x_i$ 是輸入（圖片）， $y_i$ 是正確標籤（圖片的類別）。

在強化學習中，我們沒有正確標籤 $y_i$ 。所以，我們把策略模型採樣到的動作（例如向上或向下）作為 “假標籤”。我們根據最終結果（例如贏或輸）來調整每個樣本的損失權重，用來增加有效動作的概率，減少無效動作的概率。

因此在強化學習中，損失函數會看起來像是 $\sum_i A_i \log p(y_i \mid x_i)$ 其中：

$y_i$ 是我們模型採樣到的動作（即 “假標籤”）。
$A_i$ $A_{i}$ 是優勢值，用來衡量這個動作最終的好壞結果。
- 如果動作最終導致了勝利， $A_i = 1.0$ ；
- 如果導致了失敗， $A_i = -1.0$ 。

因此，強化學習可以看作是 在不斷變化的數據集（回合） 上進行的監督學習，而這些數據集是從不同的遊戲或情景中採樣出來的，並且我們根據結果來調整每個樣本的損失大小。

General Advantage Function#

我們先前是基於是否贏球來判斷每個行動的好壞，而在更一般的 RL 環境中，我們會在每個時間步獲得某種即時獎勵 $r_t$ ，例如遊戲中的得分、環境中的反饋等。

Discounted Reward#

常見的方式是使用 折扣獎勵（Discounted Reward） 來計算某個動作之後的累計回報。折扣獎勵的公式為：

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

$\gamma$ 是折扣因子，範圍在 0 到 1 之間（例如 0.99），用於降低未來獎勵的影響。
從當前時間 $t$ 開始，未來每個時間步的獎勵 $r_{t+k}$ 都按距離當前時刻的遠近乘以折扣，離得越遠的獎勵被減弱得越多。

Normalize Returns#

當我們為 20,000 個動作（例如 100 局 Pong 遊戲中的所有動作）計算完 $R_t$ 後，將這些返回值進行標準化是一種常見的做法。如減去均值並除以標準差來實現：

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

標準化可以平衡鼓勵和懲罰的動作比例，確保在一個 batch 中大約有一半的動作被鼓勵，另一半被懲罰。從數學上來講，這可以解釋為控制策略梯度估計方差的一種方法。減少方差意味著梯度更新更加穩定，模型更容易收斂。

PG 推導#

策略梯度是一種更一般的評分函數梯度估計器的特例。我們考慮以下表達式:

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

其中:

$f(x)$ 是標量值評分函數 (在強化學習中通常是獎勵函數或優勢函數)
$p(x;\theta)$ 是由參數 $\theta$ 參數化的概率分佈 (在強化學習中通常是策略網絡)

目標：找出如何調整分佈 (通過改變其參數 $\theta$ ) 來增加其樣本的得分。

[! 理解這裡的 trick]
對數函數求導的基本性質：

\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)$ ，並且如果我們能夠在環境中運行該策略以收集軌跡數據集，我們就可以計算策略梯度並採取更新步驟。

Practice in GYM#

模型初始化#

H = 200 # 隱藏層神經元數量
batch_size = 10 # 每多少個episode更新一次參數
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}

實現策略網絡的 forward & backward

主循環#

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) # 記錄獎勵

Episode 結束時處理#

    if done:
        episode_number += 1

        # 堆疊這個episode的所有輸入、隱藏狀態、動作梯度和獎勵
        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] # 在batch中累積梯度

每個 episode 結束時計算策略梯度並累積到梯度緩衝中。

參數更新#

grad_buffer = { k : np.zeros_like(v) for k,v in model.items() } # update buffers that add up gradients over a batch
rmsprop_cache = { k : np.zeros_like(v) for k,v in model.items() } # rmsprop memory

    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) # 重置batch梯度緩衝

使用 RMSProp 算法更新模型參數。

AK 的反思#

對於人類，我們會說 “你控制一個可以上下移動的球拍，你的任務是將球反彈過 AI 對手”，而在標準強化學習問題中，我們通過與環境交互來假設一個任意的獎勵函數。人類玩家會帶入大量先驗知識（如球軌跡遵循物理定律，AI 對手可能的移動策略這樣的直覺心理學），並且需要時刻看到正常的遊戲畫面。但對於策略梯度解決方案，甚至如果對獲取幀的像素隨機排列，使用全連接網絡的策略梯度甚至都察覺不到有差異。

因此，策略梯度是一種暴力破解方法，發現正確的行動並內化為策略。

策略梯度能在很多遊戲中輕鬆擊敗人類。特別是那些需要頻繁獎勵信號、精確操作、快速反應且不需要太多長期規劃的遊戲，因為這些短期獎勵與行動之間的關聯可以被該方法輕易 “察覺”，並通過策略精心完善執行。在 Pong 遊戲訓練後期的結果就可以看出：Agent 等球快到了，就迅速移動接住球，然後以快速且高垂直速度發射球。在許多 ATARI 遊戲中，深度 Q 學習正是以這種方式徹底超越了人類的基礎表現 —— 例如彈球、打磚塊等。