Value iteration pada chapter sebelumnya menghitung nilai optimal, tetapi dengan syarat yang berat: tabel transisi dan reward harus diketahui di muka. Agent sungguhan tidak punya keistimewaan itu — yang ada hanyalah pengalaman berupa urutan (state, aksi, reward, state_baru). Jembatannya adalah value function: penaksir nilai yang diperbarui dari pengalaman, bukan dari model. Pada chapter ini kita membedakan dua wujud nilai — V(s) dan Q(s,a) — lalu melatih Q-learning tabular pada GridWorld 4x4 dan menyaksikan tabel Q yang mulanya kosong tumbuh menjadi peta panah berisi jalur optimal enam langkah.

Dua Wujud Nilai #

SimbolPertanyaan yang dijawabBentuk tabel pada GridWorld 4x4
V(s)seberapa menjanjikan state s?16 angka
Q(s,a)seberapa menjanjikan mengambil a di s?16 × 4 = 64 angka

Q lebih boros memori, tetapi membawa satu keuntungan yang menentukan: kebijakan bisa dibaca langsung tanpa memeriksa transisi. Cukup pilih argmax_a Q(s,a) — kebijakan greedy — dan agent pun siap bertindak. Keduanya terhubung lewat V*(s) = max_a Q*(s,a); tabel V pada akhir demo kita pun diperoleh dengan cara persis seperti itu.

Pembaruan Q-Learning #

Sekali pengalaman (s, a, r, s') memberi satu koreksi terhadap dugaan lama:

Q(s,a) ← Q(s,a) + α · (target − Q(s,a)) dengan target = r + γ · max_a' Q(s',a')

Sisi kanan kurung adalah galat temporal difference: selisih antara dugaan baru (r plus nilai terbaik di s') dan dugaan lama Q(s,a). Learning rate α mengatur seberapa cepat dugaan lama ditimpa — perannya sama dengan learning rate pada Gradient Descent . Karena target memakai max, pembaruan ini memperkirakan Q* dari kebijakan terbaik apa pun yang kelak ditemukan, tanpa perlu tahu kebijakan itu seperti apa (off-policy). Untuk mengumpulkan pengalaman, agent memakai epsilon-greedy: sesekali memilih aksi acak — mekanisme yang kita bedah tuntas pada chapter Exploration vs Exploitation .

Demo: Q-Learning Tabular pada GridWorld 4x4 #

Dunianya diperluas dari chapter Markov Decision Process : papan 4x4, mulai (0,0), target (3,3), reward -0.05 per langkah dan +1 saat tiba, batas 25 langkah per episode. Berkas q_learning.py menjalankan 500 episode:

python 
"""Q-learning tabular pada GridWorld 4x4 dengan kebijakan epsilon-greedy.

Agen mulai di (0,0) dan harus mencapai target (3,3). Empat aksi: atas,
bawah, kiri, kanan; menabrak dinding papan membuat agen diam. Setiap
langkah bernilai -0.01, mencapai target bernilai +1 dan episode berakhir.
Tabel Q berukuran 4 x 4 x 4 diisi lewat pembaruan
Q(s,a) <- Q(s,a) + alfa x (target - Q(s,a)).
"""

import numpy as np

rng = np.random.default_rng(7)

UKURAN = 4
START, GOAL = (0, 0), (3, 3)
AKSI = [(-1, 0), (1, 0), (0, -1), (0, 1)]   # atas, bawah, kiri, kanan
PANAH = ["^", "v", "<", ">"]
MAKS_LANGKAH = 25


def step(state, aksi):
    """Satu interaksi; kembalikan (state_baru, reward, selesai)."""
    db, dk = AKSI[aksi]
    nb, nk = state[0] + db, state[1] + dk
    state_baru = (nb, nk) if (0 <= nb < UKURAN and 0 <= nk < UKURAN) else state
    selesai = state_baru == GOAL
    reward = 1.0 if selesai else -0.05
    return state_baru, reward, selesai


Q = np.zeros((UKURAN, UKURAN, 4))
alfa, gamma, epsilon = 0.05, 0.9, 0.1
kunjungan = np.zeros((UKURAN, UKURAN, 4))

riwayat = []
for episode in range(1, 501):
    state, total = START, 0.0
    for _ in range(MAKS_LANGKAH):
        if rng.random() < epsilon:                       # eksplorasi
            aksi = int(rng.integers(0, 4))
        else:                                            # eksploitasi
            aksi = int(np.argmax(Q[state[0], state[1]]))
        state_baru, reward, selesai = step(state, aksi)
        q_maks_berikut = 0.0 if selesai else Q[state_baru[0], state_baru[1]].max()
        target = reward + gamma * q_maks_berikut
        Q[state[0], state[1], aksi] += alfa * (target - Q[state[0], state[1], aksi])
        kunjungan[state[0], state[1], aksi] += 1
        total += reward
        state = state_baru
        if selesai:
            break
    riwayat.append(total)

print("Q-learning tabular, 500 episode, epsilon=0.1, alfa=0.05")
print("Total reward 10 episode pertama (Q masih hampir kosong):")
for i in range(10):
    print(f"  episode {i + 1:2d}: {riwayat[i]:+.2f}")
print("Mean total reward per blok 50 episode:")
for i in range(0, 500, 50):
    blok = riwayat[i:i + 50]
    print(f"  episode {i + 1:3d}-{i + 50:3d}: {np.mean(blok):+.3f}")

print(f"\nSukses mencapai target (blok awal) : "
      f"{sum(r > 0 for r in riwayat[:50])}/50")
print(f"Sukses mencapai target (blok akhir): "
      f"{sum(r > 0 for r in riwayat[-50:])}/50")

print("\nKebijakan greedy dari tabel Q (panah = aksi terbaik):")
for b in range(UKURAN):
    baris = []
    for k in range(UKURAN):
        if (b, k) == GOAL:
            baris.append(" G ")
        else:
            baris.append(f" {PANAH[int(np.argmax(Q[b, k]))]} ")
    print("  " + "".join(baris))

print("\nV(s) = max_a Q(s,a) dibulatkan 2 desimal:")
for b in range(UKURAN):
    nilai = [f"{Q[b, k].max():5.2f}" if (b, k) != GOAL else "  0.00"
             for k in range(UKURAN)]
    print("  " + " ".join(nilai))

state, rute, total = START, [START], 0.0
for _ in range(MAKS_LANGKAH):
    aksi = int(np.argmax(Q[state[0], state[1]]))
    state, reward, selesai = step(state, aksi)
    rute.append(state)
    total += reward
    if selesai:
        break
print(f"\nJalur greedy dari {START}: "
      + " -> ".join(f"({b},{k})" for b, k in rute))
print(f"Panjang jalur : {len(rute) - 1} langkah, total reward = {total:+.2f}")
print(f"Pasangan state-aksi tak pernah dikunjungi: "
      f"{int((kunjungan == 0).sum())}/60 "
      f"(state non-target: 15 x 4 aksi)")

Output yang Dihasilkan:

text 
Q-learning tabular, 500 episode, epsilon=0.1, alfa=0.05
Total reward 10 episode pertama (Q masih hampir kosong):
  episode  1: -1.25
  episode  2: -1.25
  episode  3: -1.25
  episode  4: +0.15
  episode  5: -0.20
  episode  6: +0.40
  episode  7: +0.40
  episode  8: -1.25
  episode  9: +0.25
  episode 10: -1.25
Mean total reward per blok 50 episode:
  episode   1- 50: +0.274
  episode  51-100: +0.687
  episode 101-150: +0.718
  episode 151-200: +0.726
  episode 201-250: +0.728
  episode 251-300: +0.720
  episode 301-350: +0.716
  episode 351-400: +0.698
  episode 401-450: +0.723
  episode 451-500: +0.725

Sukses mencapai target (blok awal) : 42/50
Sukses mencapai target (blok akhir): 50/50

Kebijakan greedy dari tabel Q (panah = aksi terbaik):
   v  v  v  v 
   >  v  >  v 
   >  >  >  v 
   <  >  >  G 

V(s) = max_a Q(s,a) dibulatkan 2 desimal:
   0.39  0.29 -0.02  0.07
   0.48  0.59  0.43  0.77
   0.33  0.71  0.85  1.00
  -0.01  0.26  0.81   0.00

Jalur greedy dari (0, 0): (0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2) -> (2,3) -> (3,3)
Panjang jalur : 6 langkah, total reward = +0.75
Pasangan state-aksi tak pernah dikunjungi: 4/60 (state non-target: 15 x 4 aksi)

Perjalanan belajarnya terbaca dari tiga lapis keluaran. Episode awal masih bergantung pada keberuntungan — total reward berayun dari -1.25 hingga +0.40 karena tabel Q nyaris kosong dan 25 langkah sering habis sebelum target. Mean per blok 50 episode naik dari +0.274 lalu stabil di sekitar +0.72; tingkat keberhasilan melompat dari 42/50 menjadi 50/50. Pada lapis kedua, panah-panah greedy membentuk aliran menuju G, dan tabel V(s) = max_a Q(s,a) memperlihatkan lereng nilai yang menanjak dari 0.39 di start menuju 1.00 di sekitar target. Lapis ketiga adalah ujian akhirnya: jalur greedy dari (0,0) menempuh enam langkah dengan total reward +0.75 — enam langkah adalah jarak terpendek yang mungkin, sehingga -0.05 × 5 + 1.0 = +0.75 adalah return optimal dunia ini. Mari kita telaah kode di atas baris per baris:

  1. Baris 12: generator acak ber-seed 7 dari numpy.random — seluruh episode, aksi eksplorasi, dan hasil demo dapat direproduksi persis.
  2. Baris 14-17: konstanta dunia — papan 4x4, start, target, empat aksi, dan batas 25 langkah.
  3. Baris 21-28 (step): satu interaksi — perpindahan dihitung, dinding membuat agen diam, reward -0.05 atau +1, episode selesai di target.
  4. Baris 31-33: tabel Q 4×4×4 nol, hyperparameter alfa=0.05, gamma=0.9, epsilon=0.1, serta tabel kunjungan untuk menghitung pasangan state-aksi yang belum pernah dicoba.
  5. Baris 39-42: pemilihan aksi epsilon-greedy — dengan peluang epsilon aksi acak diambil, selain itu aksi greedy dari tabel Q.
  6. Baris 44-46: inti algoritma — target = reward + gamma · max Q(s') (nol bila episode selesai), lalu pembaruan Q(s,a) menuju target sebesar alfa kali galat.
  7. Baris 54-66: ringkasan belajar — 10 episode pertama dicetak mentah, mean per blok 50 episode, dan tingkat keberhasilan blok awal lawan blok akhir.
  8. Baris 68-82: membaca hasil belajar — peta panah greedy, tabel V(s), dan keduanya menampilkan target sebagai G / 0.00 karena episode berakhir di sana.
  9. Baris 84-97: ujian jalur greedy murni (tanpa eksplorasi) dari start, plus laporan 4/60 pasangan state-aksi yang tak pernah dikunjungi selama training — jejak eksplorasi yang belum lengkap namun tidak menghalangi jalur optimal.

Batas Tabel #

Enam belas state muat nyaman dalam tabel, dan dunia kita bahkan deterministik — syarat paling ramah bagi Q-learning. Dua hal akan sekaligus runtuh saat dunia membesar: memori (jumlah state melonjak secara kombinatorial, apalagi bila state berupa citra) dan cakupan (sebagian besar pasangan state-aksi tak akan pernah dikunjungi, seperti 4/60 kita yang akan membesar drastis). Jalan keluarnya adalah mengganti tabel dengan fungsi penaksir. Ada dua arah: menaksir kebijakan langsung dengan jaringan — itu topik chapter Policy Gradient — atau menaksir Q itu sendiri dengan jaringan, yang kita bangun pada chapter Deep Q-Network .