Chapter Markov Decision Process menutup dengan pengakuan jujur: evaluasi kebijakan dan persamaan Bellman membutuhkan tabel P dan R yang benar, sementara robot nyata hanya memiliki pengalaman — pasangan (state, aksi, ganjaran, state berikutnya) yang lewat sekali dan tidak bisa diulang. Q-learning adalah algoritme yang memanen kebijakan baik tepat dari arus pengalaman semacam itu: tanpa P, tanpa R, tanpa model lingkungan apa pun. Algoritme ini termasuk keluarga model-free dan menjadi pintu masuk paling klasik ke dunia RL karena rumusnya satu baris, namun hasilnya bisa diandalkan. Chapter ini menurunkan rumus tersebut, menjelaskan watak off-policy-nya, lalu mengujinya pada gridworld 4×4 dengan satu tujuan dan satu lubang — semuanya dalam NumPy murni.

Dari Sapuan Bellman ke Pembaruan Satu Sampel #

Mari kita mulai dari titik yang sudah dikenal. Evaluasi kebijakan pada Chapter sebelumnya menghitung nilai harapan berbobot P dari R + γV(s′). Masalahnya, bobot P tidak tersedia ketika kita hanya mengalami lingkungan. Gantiannya sederhana namun jenius: gunakan satu transisi yang benar-benar terjadi sebagai sampel pengganti rata-rata. Dari sampel itulah lahir aturan pembaruan temporal-difference (TD):

text 
Q(s, a) <- Q(s, a) + alpha * [ r + gamma * max_a' Q(s', a') - Q(s, a) ]

Bacaannya sebagai berikut. Agent berada di state s, memilih aksi a, menerima ganjaran r, dan tiba di state s′. Tanda kurung siku adalah galat TD: selisih antara taksiran baru r + γ·max Q(s′, ·) — ganjaran nyata ditambah nilai terbaik yang diyakini dari s′ — dan taksiran lama Q(s, a). Lalu α (alpha, laju pembelajaran) menentukan seberapa besar galat tersebut mengoreksi tabel, persis seperti laju pembelajaran pada gradient descent. Q-table berperan sebagai memori yang diperbaiki sedikit demi sedikit oleh setiap pengalaman baru; tidak ada tabel P dan R yang perlu disimpan.

Watak Off-Policy #

Perhatikan operator max_a' pada rumus: taksiran target memakai aksi terbaik menurut tabel saat ini, bukan aksi yang benar-benar diambil setibanya di s′. Konsekuensinya, Q-learning menaksir nilai kebijakan serakah (greedy) meskipun perilaku yang dikumpulkan berasal dari kebijakan eksplorasi seperti epsilon-greedy. Sifat ini disebut off-policy: kebijakan perilaku boleh berbeda dari kebijakan target yang dinilai. Manfaat praktisnya besar — data eksplorasi yang tampak “boros” tetap menghasilkan taksiran kebijakan optimal, dan pengalaman lama dari kebijakan berbeda tetap dapat dipakai ulang. Kelak pada Chapter Arah Deep Reinforcement Learning, watak inilah yang membuat experience replay pada DQN mungkin.

Kapan Q-Learning Menuju Kebenaran #

Q-learning tabular punya jaminan konvergensi yang kuat namun bersyarat, dan syaratnya layak dihafal karena menjelaskan banyak kegagalan senyap di praktik. Pertama, setiap pasangan (s, a) harus terus dikunjungi — pasangan yang tidak pernah dicoba tidak akan pernah terperbarui, sehingga eksplorasi yang menurun terlalu cepat membekukan ketidaktahuan. Kedua, laju pembelajaran harus melunur mengikuti ragam syarat klasik (misalnya α yang mengecil sehingga jumlah pembaruan efektifnya divergen tetapi kuadratnya konvergen — kondisi Robbins–Monro). Ketiga, ganjaran dan nilai harus terbatas. Pada contoh kita α tetap 0,2 demi kesederhanaan; hasilnya tetap bagus karena dunianya kecil, dan kita akan menandai batas pilihan itu secara jujur saat membaca keluaran program.

Gridworld 4×4: Tujuan, Lubang, dan Tabel yang Belajar #

Dunia ujinya adalah gridworld 4×4: agent mulai di pojok kiri atas (0, 0), tujuan bernilai +10 berada di pojok kanan bawah (3, 3), dan satu lubang bernilai −10 bersemayan di (1, 2) — keduanya mengakhiri episode. Setiap langkah berbiaya −1, gerakan deterministik, dan dinding menahan agent di tempat. Kita melatih selama 800 episode dengan epsilon-greedy yang menurun dari 1,0 menuju batas bawah 0,05 (alasan penurunan ini dibedah tuntas pada Chapter Exploration vs Exploitation), lalu memeriksa tiga hal: tren ganjaran per 100 episode, isi Q-table pada beberapa state, dan kebijakan serakah hasil ekstraksi.

python 
# Gridworld 4x4 deterministik dengan satu tujuan dan satu lubang.
# Agent dilatih dengan Q-learning tabular: epsilon-greedy memilih aksi,
# pembaruan TD berbentuk Q(s,a) <- Q(s,a) + alpha * [r + gamma*max Q(s',.) - Q(s,a)].
# Seluruh komponen (peta, Q-table, agent) adalah NumPy murni.

import numpy as np

UKURAN = 4
MULAI = (0, 0)
TUJUAN = (3, 3)      # ganjaran +10, terminal
LUBANG = (1, 2)      # ganjaran -10, terminal
GANJARAN_LANGKAH = -1.0

ALPHA = 0.2          # laju pembaruan TD
GAMMA = 0.95         # diskon
EPSILON_MULAI = 1.0  # eksplorasi penuh di awal
EPSILON_MIN = 0.05   # batas bawah eksplorasi
PENURUNAN = 0.99     # epsilon dikali faktor ini tiap episode
N_EPISODE = 800
BATAS_LANGKAH = 60

NAMA_AKSI = ["atas", "kanan", "bawah", "kiri"]
PANAH = ["^", ">", "v", "<"]


def langkah(state, aksi):
    """Transisi deterministik; dinding grid menahan agent di tempat."""
    baris, kolom = state
    if aksi == 0:
        baris = max(baris - 1, 0)
    elif aksi == 1:
        kolom = min(kolom + 1, UKURAN - 1)
    elif aksi == 2:
        baris = min(baris + 1, UKURAN - 1)
    else:
        kolom = max(kolom - 1, 0)
    return (baris, kolom)


def ganjaran_transisi(state_baru):
    """Ganjaran transisi dan penanda terminal (tujuan / lubang)."""
    if state_baru == TUJUAN:
        return 10.0, True
    if state_baru == LUBANG:
        return -10.0, True
    return GANJARAN_LANGKAH, False


def pilih_aksi(state, Q, epsilon, rng):
    """Epsilon-greedy: eksplorasi seragam atau eksploitasi argmax Q."""
    if rng.random() < epsilon:
        return int(rng.integers(4))
    return int(np.argmax(Q[state]))


def jalankan_episode(Q, epsilon, rng, latih=True):
    """Satu episode; kembalikan (total ganjaran, hasil akhir)."""
    state = MULAI
    total = 0.0
    hasil = "habis langkah"
    for _ in range(BATAS_LANGKAH):
        aksi = pilih_aksi(state, Q, epsilon, rng)
        state_baru = langkah(state, aksi)
        ganjaran, terminal = ganjaran_transisi(state_baru)
        total += ganjaran
        if latih:
            target = ganjaran + GAMMA * (0.0 if terminal else np.max(Q[state_baru]))
            Q[state][aksi] += ALPHA * (target - Q[state][aksi])
        state = state_baru
        if terminal:
            hasil = "sampai tujuan" if state_baru == TUJUAN else "jatuh ke lubang"
            break
    return total, hasil


rng = np.random.default_rng(42)
Q = np.zeros((UKURAN, UKURAN, 4))

print(f"Gridworld {UKURAN}x{UKURAN} | mulai {MULAI} | lubang {LUBANG} "
      f"| tujuan {TUJUAN}")
print(f"alpha={ALPHA} gamma={GAMMA} epsilon 1.0 -> {EPSILON_MIN} "
      f"(x{PENURUNAN} per episode) | episode={N_EPISODE} "
      f"batas langkah={BATAS_LANGKAH}\n")

statistik = []
for ep in range(N_EPISODE):
    epsilon = max(EPSILON_MIN, EPSILON_MULAI * (PENURUNAN ** ep))
    total, hasil = jalankan_episode(Q, epsilon, rng, latih=True)
    statistik.append((total, hasil))

UKURAN_BUCKET = 100
print("Tren belajar (ringkasan per 100 episode):")
print(f"{'episode':>11} {'rata2 ganjaran':>15} {'sampai G':>9} "
      f"{'jatuh X':>8} {'habis':>6}")
for k in range(0, N_EPISODE, UKURAN_BUCKET):
    potongan = statistik[k:k + UKURAN_BUCKET]
    total = [s[0] for s in potongan]
    g = sum(1 for s in potongan if s[1] == "sampai tujuan")
    x = sum(1 for s in potongan if s[1] == "jatuh ke lubang")
    l = UKURAN_BUCKET - g - x
    print(f"{k + 1:>5}-{k + UKURAN_BUCKET:<5} {np.mean(total):>15.2f} "
          f"{g / UKURAN_BUCKET:>9.2f} {x / UKURAN_BUCKET:>8.2f} "
          f"{l / UKURAN_BUCKET:>6.2f}")

print("\nQ(s, a) terlatih untuk tiga state (kolom: atas, kanan, bawah, kiri):")
for state in [(0, 0), (0, 2), (2, 2)]:
    nilai = " ".join(f"{v:>7.2f}" for v in Q[state])
    print(f"  state {state}: [{nilai}]")

print("\nKebijakan serakah dari Q (panah = argmax per state):")
for baris in range(UKURAN):
    sel = []
    for kolom in range(UKURAN):
        pos = (baris, kolom)
        if pos == TUJUAN:
            sel.append(" G ")
        elif pos == LUBANG:
            sel.append(" X ")
        elif pos == MULAI:
            sel.append(" S ")
        else:
            sel.append(f" {PANAH[int(np.argmax(Q[pos]))]} ")
    print("".join(sel))

n_uji = 20
hasil_uji = [jalankan_episode(Q, 0.0, rng, latih=False) for _ in range(n_uji)]
rata_uji = np.mean([h[0] for h in hasil_uji])
g_uji = sum(1 for h in hasil_uji if h[1] == "sampai tujuan")
print(f"\nUji {n_uji} episode serakah murni (epsilon=0): "
      f"rata-rata ganjaran {rata_uji:+.2f}, "
      f"sampai tujuan {g_uji}/{n_uji}")

Output yang Dihasilkan:

text 
Gridworld 4x4 | mulai (0, 0) | lubang (1, 2) | tujuan (3, 3)
alpha=0.2 gamma=0.95 epsilon 1.0 -> 0.05 (x0.99 per episode) | episode=800 batas langkah=60

Tren belajar (ringkasan per 100 episode):
    episode  rata2 ganjaran  sampai G  jatuh X  habis
    1-100             -9.76      0.54     0.46   0.00
  101-200              1.02      0.86     0.14   0.00
  201-300              4.02      0.98     0.02   0.00
  301-400              4.14      0.97     0.03   0.00
  401-500              4.67      0.99     0.01   0.00
  501-600              4.79      1.00     0.00   0.00
  601-700              4.19      0.97     0.03   0.00
  701-800              4.52      0.99     0.01   0.00

Q(s, a) terlatih untuk tiga state (kolom: atas, kanan, bawah, kiri):
  state (0, 0): [   1.96    3.21    2.02    1.98]
  state (0, 2): [   3.59    5.72   -9.99    3.00]
  state (2, 2): [  -5.90    4.24    8.46    1.59]

Kebijakan serakah dari Q (panah = argmax per state):
 S  >  >  v
 v  v  X  v
 >  v  v  v
 >  >  >  G

Uji 20 episode serakah murni (epsilon=0): rata-rata ganjaran +5.00, sampai tujuan 20/20

Mari kita bedah bagian-bagian pentingnya:

  1. Baris 26–37 (langkah): fungsi transisi deterministik — max dan min menampung dinding grid. Pada dunia nyata inilah letak P yang tidak diketahui agent; di sini kita, sebagai penyusun lingkungan, menuliskannya diam-diam.
  2. Baris 40–46 (ganjaran_transisi): fungsi ganjaran sekaligus penanda terminal. Tujuan dan lubang sama-sama mengakhiri episode dengan nilai yang berlawanan arah.
  3. Baris 49–53 (pilih_aksi): strategi epsilon-greedy — dengan peluang epsilon agent memilih aksi seragam acak lewat rng.integers(4), selebihnya mengeksploitasi np.argmax(Q[state]). Seluruh keacakan mengalir dari rng berseed 42 sehingga hasil selalu identik.
  4. Baris 67–68 (pembaruan TD): dua baris ini adalah keseluruhan Q-learning. Baris 67 merangkai target r + γ·max Q(s′, ·) dengan syarat nilai terminal dianggap nol, dan baris 68 menggeser Q(s, a) sebesar α kali galat TD.
  5. Baris 86–89 (pelatihan): epsilon dihitung ulang tiap episode sebagai max(0,05, 1,0 × 0,99^ep) — episode awal berjalan nyaris acak total, episode akhir hampir sepenuhnya serakah.
  6. Baris 125–131 (uji serakah): kebijakan akhir diuji 20 kali dengan epsilon nol dan latih=False, sehingga tabel tidak berubah dan yang diukur murni kualitas kebijakan.

Keluaran program membawa empat bukti belajar. Pertama, tren ganjaran naik dari rata-rata −9,76 pada 100 episode pertama menjadi sekitar +4,5 pada episode 401–800, dengan angka jatuh ke lubang yang menyusut dari 46% menuju 1–3% — kurva belajar yang sehat. Kedua, tabel Q pada state yang sering dikunjungi cocok dengan hitungan tangan: Q(0,0, kanan) = 3,21 persis sama dengan nilai teoretis −(1+0,95+0,9025+0,857+0,8145) + 0,95⁵×10, dan Q(0,2, bawah) = −9,99 adalah ganjaran lubang yang ditanam. Ketiga, grid panah menunjukkan rute serakah dari S melalui baris atas lalu kolom kanan — enam langkah yang menghindari lubang sepenuhnya, dan uji 20 episode serakah mengonfirmasi +5,00 dengan keberhasilan 20/20. Keempat — dan ini pelajaran paling jujur — beberapa entri seperti Q(2,2, atas) = −5,90 belum menuju nilai teoretis −10 karena pasangan state-aksi tersebut jarang dikunjungi akhir-akhir pelatihan; tabel hanya belajar dari pengalaman yang benar-benar lewat, sehingga kualitas eksplorasi menentukan kualitas tabel.

Ada satu pertanyaan yang sengaja kita tunda: dari mana angka epsilon itu berasal, dan kapan sebaiknya agent berhenti mencoba? Pertanyaan tersebut — ketegangan antara mencoba yang belum dikenal dan memanfaatkan yang sudah diketahui — punya teori dan eksperimen sendiri, dan menjadi tema utama Chapter Exploration vs Exploitation.

Referensi Resmi #

  • numpy — numpy.argmax — API resmi pemilihan aksi serakah yang dipakai pilih_aksi dan ekstraksi kebijakan.
  • numpy — Random sampling (numpy.random) — dokumentasi resmi Generator default_rng untuk eksplorasi epsilon-greedy yang deterministik.
  • Gymnasium — situs resmi pustaka lingkungan RL; lingkungan GridWorld-nya bisa dipakai untuk mengganti dunia buatan sendiri, meski tidak terpasang di lingkungan Course ini.