Lima Chapter sebelumnya menyiapkan seluruh perangkat satu per satu: kosakata lingkar agent-environment, formalisme MDP, aturan pembaruan TD, dan strategi eksplorasi. Chapter ini adalah rangkaiannya — kita merakit agent Q-learning utuh dari nol dan menurunkannya ke gridworld 6×6 yang jauh lebih menantang: ada dinding yang membentuk lorong, satu lubang berhadiah −20 di tempat yang menggoda, dan tujuan bernilai +20 yang hanya dapat dicapai lewat dua jalur sama panjang. Seluruh program tetap NumPy murni tanpa satu pun pustaka RL: peta berupa daftar string, Q-table berupa array (6, 6, 4), dan agent berupa lingkar Python biasa. Di akhir Chapter, tiga artefak akan kita periksa: kurva belajar selama 1.500 episode, grid kebijakan serakah sebagai panah, dan jejak lengkap satu episode serakah.

Merancang Peta sebagai Data #

Peta didefinisikan sebagai enam string pendek — S untuk sel mulai, # untuk dinding, X untuk lubang, G untuk tujuan, dan titik untuk lantai biasa. Format ini dipilih karena peta dapat dibaca sekilas seperti denah asli, mudah diubah untuk eksperimen, dan mudah dipindai program menjadi himpunan DINDING berisi koordinat (baris, kolom). Desain peta sengaja dibuat bercerita: kecelakaan paling sering di awal pelatihan adalah jatuh ke lubang dari kantong kiri-bawah — wilayah yang secara alami dikunjungi pejalan acak — sementara dua jalur optimal di paruh atas dan kolom kanan tetap bersih. Ganjaran yang dipilih (−1 per langkah, +20 tujuan, −20 lubang) membuat kecepatan dan keselamatan sama-sama dihargai.

Komponen yang Diwariskan #

Tidak ada satu pun mekanisme baru pada program ini; seluruhnya adalah bawaan Chapter-Chapter sebelumnya yang dipasang ulang pada dunia lebih besar. Tabel berikut memetakan setiap komponen ke asalnya:

KomponenBentuk pada programAsal konsep
Lingkar episodefungsi jalankan_episodeKonsep Reinforcement Learning
Transisi & ganjaranlangkah + ganjaran_transisi (P dan R implisit)Markov Decision Process
Pembaruan nilaiQ[s][a] += ALPHA * (target - Q[s][a])Q-Learning
Pemilihan aksiepsilon-greedy menurun 1,0 → 0,05Exploration vs Exploitation
Reproducibilitasnp.random.default_rng(42) tunggalseluruh Section

Dua penyesuaian ukuran layak dicatat. Epsilon menurun dengan faktor 0,995 per episode — lebih lambat daripada 0,99 pada gridworld 4×4 — karena dunia yang lebih besar butuh lebih lama untuk dijelajahi; epsilon mencapai lantai 0,05 sekitar episode ke-600 dan pelatihan berlanjut sampai 1.500 episode agar nilai-nilai sempat menyetel. Batas langkah dinaikkan menjadi 120 supaya episode-episode acak awal tetap sempat menemui tujuan atau lubang dan mengirim sinyal belajar, bukan berhenti kosong di tengah peta.

Pelatihan dan Tiga Artefak Akhir #

Alur program: render peta, latih 1.500 episode sambil membukukan total ganjaran, hasil akhir, dan jumlah langkah per episode, lalu cetak tiga pemeriksaan. Kurva belajar dirangkum per 100 episode — rata-rata ganjaran yang naik, jumlah langkah yang menurun, dan persentase keberhasilan yang mendekati satu adalah tanda tiga klasik pembelajaran yang sehat. Grid kebijakan menampilkan panah argmax Q untuk setiap sel lantai: jalur yang dihasilkan harus menghindari dinding dan lubang. Jejak episode serakah menjalankan kebijakan akhir tanpa eksplorasi dan tanpa pembaruan tabel, lalu mencetak urutan sel yang dikunjungi — bukti ujung ke ujung bahwa tabel yang terlatih benar-benar menghasilkan perilaku yang bisa dibaca manusia.

python 
# Capstone Section Reinforcement Learning: gridworld 6x6 dengan dinding,
# satu lubang, dan satu tujuan. Kita merakit agent Q-learning utuh dari
# nol -- lingkungan dari peta teks, epsilon-greedy menurun, pembaruan TD
# -- lalu melatihnya dan memeriksa tiga artefak akhir: kurva belajar,
# grid kebijakan serakah sebagai panah, dan jejak satu episode serakah.

import numpy as np

PETA = [
    "S..#..",
    ".#....",
    ".###..",
    "...#..",
    "#..#..",
    "...X.G",
]
BARIS_N = len(PETA)
KOLOM_N = len(PETA[0])

MULAI = (0, 0)
TUJUAN = (5, 5)       # ganjaran +20, terminal
LUBANG = (5, 3)       # ganjaran -20, terminal
DINDING = {(r, c) for r in range(BARIS_N) for c in range(KOLOM_N)
           if PETA[r][c] == "#"}

ALPHA = 0.2
GAMMA = 0.95
EPSILON_MULAI = 1.0
EPSILON_MIN = 0.05
PENURUNAN = 0.995
N_EPISODE = 1500
BATAS_LANGKAH = 120

PANAH = ["^", ">", "v", "<"]


def langkah(state, aksi):
    """Transisi deterministik; dinding dan tepi peta menahan agent."""
    r, c = state
    if aksi == 0:
        r = max(r - 1, 0)
    elif aksi == 1:
        c = min(c + 1, KOLOM_N - 1)
    elif aksi == 2:
        r = min(r + 1, BARIS_N - 1)
    else:
        c = max(c - 1, 0)
    if (r, c) in DINDING:
        return state
    return (r, c)


def ganjaran_transisi(state_baru):
    """Ganjaran transisi dan penanda terminal."""
    if state_baru == TUJUAN:
        return 20.0, True
    if state_baru == LUBANG:
        return -20.0, True
    return -1.0, 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, hasil, jejak state)."""
    state = MULAI
    total = 0.0
    hasil = "habis langkah"
    jejak = [state]
    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
        jejak.append(state)
        if terminal:
            hasil = "sampai tujuan" if state_baru == TUJUAN else "jatuh ke lubang"
            break
    return total, hasil, jejak


print("Peta gridworld 6x6 (# dinding, X lubang, G tujuan, S mulai):")
for baris in PETA:
    print(" ", " ".join(baris))
print(f"alpha={ALPHA} gamma={GAMMA} epsilon 1.0 -> {EPSILON_MIN} "
      f"(x{PENURUNAN}/episode) | episode={N_EPISODE} "
      f"batas langkah={BATAS_LANGKAH}")
print("Jalur terpendek S -> G: 10 langkah, ganjaran optimal = -9 + 20 = +11\n")

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

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

print("Ganjaran episode pada titik sampel (episode ke-1 setiap 250):")
for ep in range(0, N_EPISODE, 250):
    total, hasil = statistik[ep][0], statistik[ep][1]
    print(f"  episode {ep + 1:>4}: total {total:>+7.1f}  ({hasil})")

UKURAN_BUCKET = 100
print("\nKurva belajar (ringkasan per 100 episode):")
print(f"{'episode':>11} {'rata2 total':>12} {'rata2 langkah':>14} "
      f"{'%tujuan':>8} {'%lubang':>8} {'%habis':>7}")
for k in range(0, N_EPISODE, UKURAN_BUCKET):
    potongan = statistik[k:k + UKURAN_BUCKET]
    total = [s[0] for s in potongan]
    langkah_rata = np.mean([s[2] 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):>12.2f} "
          f"{langkah_rata:>14.1f} {g / UKURAN_BUCKET:>8.2f} "
          f"{x / UKURAN_BUCKET:>8.2f} {l / UKURAN_BUCKET:>7.2f}")

print("\nGrid kebijakan serakah (panah = argmax Q per sel):")
for r in range(BARIS_N):
    sel = []
    for c in range(KOLOM_N):
        pos = (r, c)
        if pos == TUJUAN:
            sel.append(" G ")
        elif pos == LUBANG:
            sel.append(" X ")
        elif pos == MULAI:
            sel.append(" S ")
        elif pos in DINDING:
            sel.append(" # ")
        else:
            sel.append(f" {PANAH[int(np.argmax(Q[pos]))]} ")
    print("".join(sel))

total_g, hasil_g, jejak_g = jalankan_episode(Q, 0.0, rng, latih=False)
print(f"\nJejak satu episode serakah murni ({hasil_g}):")
print("  " + " -> ".join(f"({r},{c})" for r, c in jejak_g))
print(f"  jumlah langkah: {len(jejak_g) - 1}, total ganjaran: {total_g:+.1f}")

Output yang Dihasilkan:

text 
Peta gridworld 6x6 (# dinding, X lubang, G tujuan, S mulai):
  S . . # . .
  . # . . . .
  . # # # . .
  . . . # . .
  # . . # . .
  . . . X . G
alpha=0.2 gamma=0.95 epsilon 1.0 -> 0.05 (x0.995/episode) | episode=1500 batas langkah=120
Jalur terpendek S -> G: 10 langkah, ganjaran optimal = -9 + 20 = +11

Ganjaran episode pada titik sampel (episode ke-1 setiap 250):
  episode    1: total  -120.0  (habis langkah)
  episode  251: total    +8.0  (sampai tujuan)
  episode  501: total   +11.0  (sampai tujuan)
  episode  751: total    +9.0  (sampai tujuan)
  episode 1001: total   +11.0  (sampai tujuan)
  episode 1251: total    +7.0  (sampai tujuan)

Kurva belajar (ringkasan per 100 episode):
    episode  rata2 total  rata2 langkah  %tujuan  %lubang  %habis
    1-100         -48.08           52.8     0.54     0.35    0.11
  101-200           1.40           18.8     0.98     0.02    0.00
  201-300           5.87           15.1     1.00     0.00    0.00
  301-400           8.85           12.2     1.00     0.00    0.00
  401-500           9.72           11.3     1.00     0.00    0.00
  501-600          10.31           10.7     1.00     0.00    0.00
  601-700          10.31           10.7     1.00     0.00    0.00
  701-800          10.42           10.6     1.00     0.00    0.00
  801-900          10.44           10.6     1.00     0.00    0.00
  901-1000         10.36           10.6     1.00     0.00    0.00
 1001-1100         10.39           10.6     1.00     0.00    0.00
 1101-1200         10.52           10.5     1.00     0.00    0.00
 1201-1300         10.43           10.6     1.00     0.00    0.00
 1301-1400         10.32           10.7     1.00     0.00    0.00
 1401-1500         10.44           10.6     1.00     0.00    0.00

Grid kebijakan serakah (panah = argmax Q per sel):
 S  >  v  #  v  v
 ^  #  >  >  >  v
 ^  #  #  #  >  v
 v  v  ^  #  >  v
 #  >  ^  #  >  v
 ^  v  ^  X  >  G

Jejak satu episode serakah murni (sampai tujuan):
  (0,0) -> (0,1) -> (0,2) -> (1,2) -> (1,3) -> (1,4) -> (1,5) -> (2,5) -> (3,5) -> (4,5) -> (5,5)
  jumlah langkah: 10, total ganjaran: +11.0

Mari kita bedah bagian-bagian pentingnya:

  1. Baris 9–24 (peta sebagai data): enam string PETA adalah satu-satunya definisi dunia; DINDING dipindai darinya lewat pemahaman set (set comprehension) berisi koordinat. Menggambar ulang peta cukup dengan mengubah teks — tidak ada logika lain yang perlu disentuh.
  2. Baris 37–50 (langkah): empat cabang menggerakkan koordinat dengan max/min sebagai tepi peta, lalu pemeriksaan if (r, c) in DINDING mengembalikan agent ke posisi lama — beginilah dinding “menahan” tanpa tabel transisi eksplisit.
  3. Baris 69–88 (jalankan_episode): lingkar lengkap episode — pilih aksi, bergerak, catat ganjaran, perbarui Q bila latih=True, catat jejak, dan hentikan bila terminal. Dibanding versi 4×4 pada Chapter Q-Learning, hanya pencatatan jejak yang baru.
  4. Baris 99–106 (pelatihan): satu Generator berseed 42 menyuapi seluruh 1.500 episode; epsilon dihitung ulang tiap episode dengan rumus max(0,05, 1,0 × 0,995^ep).
  5. Baris 128–143 (render kebijakan): setiap sel lantai digambar sebagai panah argmax Q, sementara sel khusus (S, X, G, #) dicetak apa adanya — kebijakan tabel berubah menjadi denah yang bisa dibaca tanpa membuka angka.
  6. Baris 145–148 (jejak akhir): satu episode dengan epsilon nol dan latih=False membekukan tabel; jejak sel yang dicetak adalah perilaku murni kebijakan akhir.

Keluaran program menampilkan transformasi yang lengkap. Episode pertama — nyaris acak total — mengakhiri dirinya dengan −120,0 setelah kehabisan 120 langkah tanpa menemukan apa pun. Kurva belajar kemudian naik cepat: rata-rata −48,1 pada 100 episode pertama (35% di antaranya berakhir di lubang) menjadi +10,4 dengan 100% keberhasilan sejak episode ke-201, sementara jumlah langkah rata-rata menyusut dari 52,8 menjadi 10,6 — nyaris menyentuh panjang jalur terpendek. Grid kebijakan menunjukkan dua koridor panah yang mengalir menuju G tanpa menyentuh X, dan jejak episode serakah mengonfirmasi secara eksplisit: sepuluh langkah dari (0,0) melalui (0,1), (0,2), (1,2), (1,3), (1,4), (1,5), (2,5), (3,5), (4,5), menuju (5,5) dengan total +11,0 — persis nilai optimal yang dihitung tangan di header program.

Program ini menuntaskan perkakas tabular: peta, ganjaran, eksplorasi, dan pembaruan nilai bekerja sama dalam satu berkas yang berjalan di bawah setengah detik. Batas berikutnya bukan soal algoritme, melainkan soal ukuran — apa yang terjadi ketika jumlah state membengkak menjadi jutaan sehingga tabel tidak lagi muat di memori, dan mengapa neural network lalu menjadi keharusan? Pertanyaan itu membuka babak penutup Section pada Chapter Arah Deep Reinforcement Learning.

Referensi Resmi #

  • numpy — Random sampling (numpy.random) — dokumentasi resmi Generator default_rng yang menjaga 1.500 episode pelatihan tetap reproducible.
  • numpy — numpy.argmax — API resmi pemilihan panah kebijakan pada grid serakah.
  • Gymnasium — situs resmi pustaka lingkungan RL; lingkungan ala FrozenLake-nya dapat menggantikan peta teks kita dengan dunia standar untuk uji banding, meski tidak terpasang di lingkungan Course.