Reduksi varians

Rewards-to-go, baseline, dan gagasan advantage.

Daftar isi

REINFORCE murni memiliki varians gradien yang besar sehingga pelatihan sering goyah, dan topik ini mengatasi masalah itu melalui dua penyederhanaan estimator. Pertama, rewards-to-go memotong kontribusi masa lalu dari return, dan kedua, baseline mengurangi rata-rata state dari rewards-to-go menjadi sebuah advantage. Pembaca akan melihat sebuah eksperimen kecil yang mengukur varians estimator gradien pada tiga bentuk, yaitu full return, rewards-to-go, dan rewards-to-go dikurangi baseline, dengan hasil yang menurun tajam dari 740 menjadi 160.

Sumber varians pada REINFORCE#

Estimator REINFORCE memperkirakan gradien sebagai rata-rata $\nabla_\theta \log \pi_\theta(a_t\mid s_t)$ yang dibobot $G$ , dengan $G$ return kumulatif sepanjang trajectory. Bobot $G$ berskala besar dan berosilasi antar trajectory, sehingga satu sampel yang ekstrem dapat mendominasi pembaruan. Semakin panjang trajectory dan semakin besar rentang return, semakin tinggi varians estimator, dan semakin banyak sampel yang diperlukan untuk memperkirakan gradien yang stabil.

Reduksi varians tidak mengubah rata-rata estimator selama reduksinya tidak memperkenalkan bias. Rewards-to-go mengganti $G$ dengan $G_t = \sum_{k=t}^{T} \gamma^{k-t} r_{k+1}$ , yaitu return mulai dari langkah $t$ . Karena reward sebelum $t$ tidak bergantung pada aksi $a_t$ , membuangnya tidak mengubah ekspektasi gradien, namun memangkas kontribusi yang hanya menambah derau. Baseline mengurangi sebuah nilai $b(s_t)$ yang hanya bergantung pada state, sehingga ekspektasi gradien tetap karena $\mathbb{E}_{a\sim\pi}[\nabla_\theta \log \pi_\theta(a\mid s_t)]=0$ , namun varians turun karena nilai negatif dan positif saling menetralkan.

Eksperimen tiga estimator#

Berkas reduksi_varians.py berikut menjalankan 200 trajectory pendek dengan tiga langkah, lalu mengukur varians gradien pada tiga bentuk estimator. Estimator (a) memakai full return $G$ , (b) memakai rewards-to-go $G_t$ , dan (c) memakai rewards-to-go dikurangi baseline rata-rata seluruh trajectory.

python reduksi_varians.py

import warnings; warnings.filterwarnings("ignore")
import numpy as np, torch, random
np.random.seed(0); torch.manual_seed(0); random.seed(0)

GAMMA = 0.99
N_TRAJ = 200
T = 3
STATE_DIM = 2
N_AKSI = 2

states = torch.tensor(np.random.randn(T, STATE_DIM), dtype=torch.float32)
reward_table = torch.tensor(np.random.randn(T, N_AKSI), dtype=torch.float32)
theta = torch.zeros(N_AKSI, STATE_DIM, requires_grad=True)


def grad_logp(s_t, a_t):
    logits = theta @ s_t
    logp = torch.log_softmax(logits, dim=-1)[a_t]
    g, = torch.autograd.grad(logp, theta)
    return g.detach()


all_actions = []
all_rewards = []
for _ in range(N_TRAJ):
    actions = []
    rewards = []
    for t in range(T):
        with torch.no_grad():
            logits = theta @ states[t]
            probs = torch.softmax(logits, dim=-1)
        a = torch.multinomial(probs, 1).item()
        actions.append(a)
        rewards.append(float(reward_table[t, a]))
    all_actions.append(actions)
    all_rewards.append(rewards)

returns_all = [sum(GAMMA ** k * r[k] for k in range(T)) for r in all_rewards]
baseline = float(np.mean(returns_all))

trajs_a, trajs_b, trajs_c = [], [], []
for traj_idx in range(N_TRAJ):
    actions = all_actions[traj_idx]
    rewards = all_rewards[traj_idx]
    G = sum(GAMMA ** k * rewards[k] for k in range(T))
    Gt = [0.0] * T
    running = 0.0
    for t in reversed(range(T)):
        running = rewards[t] + GAMMA * running
        Gt[t] = running
    g_a = torch.zeros(N_AKSI, STATE_DIM)
    g_b = torch.zeros(N_AKSI, STATE_DIM)
    g_c = torch.zeros(N_AKSI, STATE_DIM)
    for t in range(T):
        gl = grad_logp(states[t], actions[t])
        g_a = g_a + gl * G
        g_b = g_b + gl * Gt[t]
        g_c = g_c + gl * (Gt[t] - baseline)
    trajs_a.append(g_a)
    trajs_b.append(g_b)
    trajs_c.append(g_c)


def variance(trajs):
    stack = torch.stack(trajs)
    mean = stack.mean(dim=0)
    var = ((stack - mean) ** 2).sum(dim=0).mean()
    return float(var.item())


print(f"varians (a) full return    = {variance(trajs_a):.4f}")
print(f"varians (b) rewards-to-go  = {variance(trajs_b):.4f}")
print(f"varians (c) rtgo-baseline  = {variance(trajs_c):.4f}")
print(f"baseline b                 = {baseline:.4f}")

text Keluaran

varians (a) full return    = 740.0016
varians (b) rewards-to-go  = 472.3082
varians (c) rtgo-baseline  = 160.2618
baseline b                 = 1.3400

Membaca penurunan varians#

Varians turun bertahap dari 740,0016 pada full return, ke 472,3082 pada rewards-to-go, lalu ke 160,2618 setelah dikurangi baseline 1,3400. Penurunan dari (a) ke (b) terjadi karena reward masa lalu yang tidak relevan dengan $a_t$ dibuang, sehingga derau dari kontribusi yang seharusnya tidak ada hilang. Penurunan dari (b) ke (c) lebih dramatis, sebab pengurangan baseline menggeser distribusi bobot ke sekitar nol, sehingga nilai negatif dan positif saling menetralkan dan varians menyempit.

Yang penting, ketiga estimator memiliki ekspektasi gradien yang sama selama baseline hanya bergantung pada state. Rewards-to-go sah karena reward sebelum $t$ tidak bergantung pada $a_t$ , dan baseline sah karena $\mathbb{E}_{a\sim\pi}[\nabla_\theta \log \pi_\theta(a\mid s_t)]=0$ . Dengan demikian, reduksi varians ini tidak menambah bias, melainkan hanya menambah efisiensi sampel. Konsep yang muncul dari pengurangan baseline ini adalah advantage $A(s_t,a_t)=G_t - V(s_t)$ , yang menjadi inti actor-critic pada topik selanjutnya.

Kesalahan umum#

Memakai baseline yang bergantung pada aksi. Penyebabnya, baseline dihitung dari nilai aksi terpilih sehingga pengurangannya memengaruhi ekspektasi gradien. Akibatnya, estimator menjadi bias dan rata-rata gradien bergeser dari nilai sebenarnya. Perbaikannya, batasi baseline agar hanya bergantung pada state, misalnya estimasi $V(s_t)$ dari jaringan nilai terpisah.

Menganggap rewards-to-go selalu menurunkan varians secara besar. Penyebabnya, hasil eksperimen yang menunjukkan penurunan dari 740 ke 472 digeneralisasi. Akibatnya, ekspektasi yang tidak realistis diterapkan pada lingkungan dengan struktur berbeda. Perbaikannya, ukur varians pada lingkungan target, sebab magnitudo penurunan bergantung pada seberapa besar kontribusi reward masa lalu relatif terhadap reward masa depan.

Ringkasan#

Varians besar pada REINFORCE berasal dari bobot return $G$ yang berosilasi antar trajectory, sehingga satu sampel ekstrem dapat mendominasi pembaruan.
Rewards-to-go $G_t$ membuang reward masa lalu yang tidak bergantung pada $a_t$ , dan baseline $b(s_t)$ mengurangi rata-rata state tanpa menambah bias karena $\mathbb{E}[\nabla \log \pi]=0$ .
Eksperimen 200 trajectory menunjukkan varians turun dari 740,0016 (full return) ke 472,3082 (rewards-to-go) ke 160,2618 (rewards-to-go dikurangi baseline 1,3400), tanpa mengubah ekspektasi gradien.

Referensi#

Policy Gradient — OpenAI Spinning Up — Penjelasan rewards-to-go dan baseline sebagai teknik reduksi varians pada policy gradient.
Reinforcement Learning: An Introduction, ch. 13 — Sutton & Barto — Bab “Policy Gradient Methods” yang memperkenalkan baseline dan kebenaran ekspektasi gradiennya.