Pembaruan TD

Bootstrapping estimasi nilai dari satu langkah tunggal.

Daftar isi

Pembaruan temporal-difference, atau pembaruan TD, adalah aturan pembaruan nilai yang memperkirakan sebuah state dengan kombinasi reward satu langkah dan estimasi nilai state berikutnya, sehingga belajar dapat dilakukan dari satu transisi tunggal tanpa menunggu seluruh episode selesai. Topik ini memperkenalkan TD(0) untuk fungsi nilai state $V$ , menjalankannya pada random walk Markov sederhana, lalu membandingkan estimasi yang dihasilkan dengan nilai sebenarnya yang dihitung via pemrograman dinamis. Setelah membaca, diharapkan pembaca memahami apa yang dimaksud dengan bootstrapping dan mengapa pembaruan TD bervarians rendah namun mengandung bias akibat bootstrapping.

Bootstrapping dari satu langkah#

Pada pemrograman dinamis, nilai sebuah state dihitung dari seluruh kemungkinan transisi yang ditimbang probabilitas. Pada pembelajaran model-free, agen tidak memiliki distribusi tersebut sehingga harus mengaproksimasi nilai melalui sampel. Pembaruan TD(0) menggantikan ekspektasi penuh dengan satu realisasi, yaitu reward yang benar-benar diterima plus nilai estimasi state berikutnya yang terdiskon. Aturan pembaruannya adalah

V(s) \leftarrow V(s) + \alpha \left[ r + \gamma V(s') - V(s) \right].

Selisih $r + \gamma V(s') - V(s)$ disebut TD error, yaitu selisih antara target baru dan estimasi lama. Karena $V(s')$ sendiri belum tentu akurat, pembaruan ini disebut bootstrapping, yaitu memperkirakan sesuatu dari estimasi yang juga masih berkembang. Learning rate $\alpha$ mengatur seberapa besar koreksi diterapkan, dengan nilai kecil membuat estimasi berubah secara bertahap dan nilai besar membuatnya responsif tetapi berosilasi.

Berbeda dari Monte Carlo yang menunggu return penuh sampai episode berakhir, TD(0) memperbarui nilai pada setiap langkah. Konsekuensinya, TD belajar lebih cepat pada episode yang panjang dan dapat dipakai pada masalah berkelanjutan tanpa episode diskret. Trade-off-nya adalah varians yang lebih rendah karena hanya satu langkah yang dilibatkan, tetapi bias karena $V(s')$ yang belum konvergen mengandung kesalahan yang diturunkan ke $V(s)$ .

Implementasi TD(0) pada random walk#

Blok berikut membangun random walk Markov dengan lima state linear $0,1,2,3,4$ , di mana state $0$ dan $4$ bersifat terminal. Agen mulai dari state $2$ di setiap episode, lalu memilih aksi kiri atau kanan secara acak. Reward $1{,}0$ hanya diberikan saat agen berpindah dari state $3$ ke state $4$ , sedangkan seluruh transisi lain memberi reward $0$ . TD(0) dijalankan selama 500 episode dengan $\alpha=0{,}1$ dan $\gamma=0{,}9$ , lalu estimasi $V$ dibandingkan dengan nilai sebenarnya yang dihitung via evaluasi kebijakan acak seragam pada blok yang sama.

python TD(0) pada random walk dan perbandingan dengan DP

import warnings; warnings.filterwarnings("ignore")
import numpy as np

np.random.seed(0)

states = [0, 1, 2, 3, 4]
actions = [0, 1]
gamma = 0.9
alpha = 0.1
n_episodes = 500


def is_terminal(s):
    return s == 0 or s == 4


def step(s, a):
    if a == 0:
        ns = max(0, s - 1)
    else:
        ns = min(4, s + 1)
    r = 1.0 if (s == 3 and a == 1) else 0.0
    return ns, r


V = {s: 0.0 for s in states}
rng = np.random.default_rng(0)

for ep in range(n_episodes):
    s = 2
    while not is_terminal(s):
        a = int(rng.integers(2))
        ns, r = step(s, a)
        td_target = r + gamma * V[ns]
        V[s] += alpha * (td_target - V[s])
        s = ns

print("V estimasi TD(0) (random walk 5 state, gamma=0.9, alpha=0.1, 500 episode):")
for s in [1, 2, 3]:
    print(f"  V({s}) = {V[s]:.4f}")

Vpi = {s: 0.0 for s in states}
theta = 1e-8
while True:
    delta = 0.0
    newV = dict(Vpi)
    for s in [1, 2, 3]:
        total = 0.0
        for a in actions:
            ns, r = step(s, a)
            total += 0.5 * (r + gamma * Vpi[ns])
        newV[s] = total
        delta = max(delta, abs(newV[s] - Vpi[s]))
    Vpi = newV
    if delta < theta:
        break

print()
print("V sebenarnya (DP, kebijakan acak seragam):")
for s in [1, 2, 3]:
    print(f"  V({s}) = {Vpi[s]:.4f}")

text Keluaran

V estimasi TD(0) (random walk 5 state, gamma=0.9, alpha=0.1, 500 episode):
  V(1) = 0.1375
  V(2) = 0.3950
  V(3) = 0.6854

V sebenarnya (DP, kebijakan acak seragam):
  V(1) = 0.1702
  V(2) = 0.3782
  V(3) = 0.6702

Estimasi TD(0) mengikuti pola nilai sebenarnya, yaitu meningkat dari state $1$ menuju state $3$ karena state $3$ lebih dekat ke sumber reward di state $4$ . Selisih antara estimasi dan nilai sebenarnya, misalnya $V(1)$ sebesar $0{,}1375$ dibanding $0{,}1702$ , mencerminkan kombinasi bias bootstrapping dan varians pengambilan sampel. Pada state $3$ , estimasi justru sedikit lebih tinggi dari nilai sebenarnya karena transisi yang kebetulan sering mencapai reward menarik nilai ke atas sebelum rata-rata benar-benar stabil. Dengan jumlah episode yang lebih banyak atau $\alpha$ yang menurun seiring waktu, estimasi akan menuju nilai sebenarnya secara bertahap.

Mengapa TD dipilih bukan Monte Carlo#

Pilihan atas TD bukan sekadar urusan kecepatan. Pada episode yang panjang atau pada masalah berkelanjutan tanpa batas episode, Monte Carlo tidak dapat digunakan karena return penuh tidak pernah tersedia. TD memperbarui nilai segera setelah satu langkah, sehingga agen memperoleh sinyal belajar jauh lebih awal dan dapat beradaptasi pada lingkungan yang berubah. Kompromi yang dibayar adalah bias akibat bootstrapping, tetapi pada praktiknya bias ini sering dapat ditoleransi karena estimasi state berikutnya juga ikut membaik seiring belajar, sehingga kesalahan diturunkan berulang kali sampai konvergen.

Kesalahan umum#

Memasang $\alpha$ terlalu besar. Penyebabnya, koreksi yang besar terlihat mempercepat belajar pada beberapa langkah pertama. Akibatnya, estimasi $V$ berosilasi tajam dan gagal konvergen karena setiap pembaruan menimpa hampir seluruh estimasi sebelumnya. Perbaikannya, gunakan $\alpha$ kecil seperti $0{,}1$ , atau jadwalkan $\alpha$ yang menurun seiring jumlah kunjungan state bertambah.

Menganggap $V(s')$ sudah benar. Penyebabnya, rumus TD terlihat seperti perhitungan eksak, padahal $V(s')$ adalah estimasi yang masih berkembang. Akibatnya, kesalahan pada state berikutnya diturunkan ke state sekarang dan menumpuk. Perbaikannya, kesadari bahwa konvergensi TD bergantung pada seluruh state diperbarui secara bertahap, bukan pada satu pembaruan yang dianggap final.

Ringkasan#

Pembaruan TD(0) memperbarui $V(s)$ dengan satu langkah, yaitu $V(s) \leftarrow V(s) + \alpha [r + \gamma V(s') - V(s)]$ , sehingga belajar dapat dilakukan tanpa menunggu episode selesai.
Selisih $r + \gamma V(s') - V(s)$ disebut TD error, dan penggunaan $V(s')$ yang belum akurat membuat pembaruan ini bersifat bootstrapping.
Pada random walk 5 state, TD(0) dengan $\alpha=0{,}1$ dan 500 episode menghasilkan estimasi yang dekat dengan nilai sebenarnya dari evaluasi kebijakan DP, tetapi belum sepenuhnya konvergen.
TD dipilih daripada Monte Carlo karena belajar lebih cepat pada episode panjang dan dapat dipakai pada masalah berkelanjutan tanpa episode diskret.

Referensi#

Reinforcement Learning: An Introduction (2nd ed.), ch. 6 — Sutton & Barto — Bab “Temporal-Difference Learning” memperkenalkan TD(0), TD error, dan bootstrapping sebagai inti pembelajaran tanpa model.
Tabular TD(0) — Wikipedia — Penjelasan rumus pembaruan TD(0) dan hubungannya dengan persamaan Bellman.