Chapter Konsep Reinforcement Learning meninggalkan satu pekerjaan yang belum selesai: lingkar agent-environment di sana masih berbentuk kode Python yang kita tulis per kasus. Untuk bisa dianalisis — dihitung nilai optimalnya, dibandingkan antar-kebijakan, dan dijamin perilaku algoritmenya — lingkar tersebut perlu pakaian matematis. Pakaian itu bernama Markov Decision Process (MDP): kerangka lima komponen yang menjadi bahasa standar seluruh Section ini. Setelah membaca Chapter ini, kalimat seperti “Q-learning menaksir Q dari MDP tanpa mengenal P dan R” akan terasa wajar, bukan seperti sandi.
Properti Markov: Masa Depan Hanya Butuh Masa Kini #
Gagasan inti MDP sederhana namun berdampak besar: properti Markov menyatakan bahwa peluang transisi berikutnya hanya bergantung pada state dan aksi saat ini, bukan pada jalur yang dilalui sebelumnya. Robot mini di koridor pada Chapter sebelumnya sudah memenuhi sifat ini — peluang berpindah dari sel 3 ke sel 4 tidak berubah walau robot sempat bolak-balik ke sel 0 lebih dulu. Sebaliknya, jika ganjaran bergantung pada “sudah berapa kali barang dijatuhkan sepanjang perjalanan”, history tersebut harus diangkat menjadi bagian dari state agar properti Markov kembali berlaku.
Properti Markov adalah kesepakatan pemodelan, bukan hukum alam. Ketika dunia nyata terasa menyimpan memori, tugas perancang adalah memilih state yang cukup kaya sehingga sisa memori tidak lagi diperlukan. Keuntungannya sepadan: karena masa depan terlepas dari masa lalu, seluruh dinamika dapat ditulis sebagai tabel transisi yang ringkas.
Lima Penghuni Tuple MDP #
Sebuah MDP didefinisikan oleh lima komponen, lazim ditulis tuple ⟨S, A, P, R, γ⟩:
- S — himpunan state, misalnya posisi robot pada grid.
- A — himpunan aksi yang tersedia, boleh berbeda per state.
- P(s′ | s, a) — fungsi transisi: peluang berpindah ke state s′ jika aksi a dipilih di state s. Pada dunia deterministik, satu entri bernilai 1 dan sisanya 0.
- R(s, a, s′) — fungsi ganjaran: nilai yang diterima agent pada transisi tersebut.
- γ (gamma) — faktor diskon antara 0 dan 1 yang menimbang ganjaran masa depan.
P dan R inilah “buku aturan dunia” pada Chapter sebelumnya yang dulu tersembunyi di dalam fungsi transisi. Ketika agent mengetahui P dan R, masalahnya adalah perencanaan; ketika agent harus belajar hanya dari pasangan (s, a, r, s′) yang dialami, masalahnya menjadi pembelajaran — wilayah Q-learning.
Diskon: Mengapa Gamma Harus di Bawah Satu #
Ganjaran yang terkumpul sepanjang episode — return G_t = r_t + r_{t+1} + r_{t+2} + … — bisa berjumlah tak hingga pada masalah yang tidak memiliki akhir. Diskon memotong masalah itu: return berdiskon menjadi r_t + γr_{t+1} + γ²r_{t+2} + …, dan untuk γ < 1 jumlah deret tersebut selalu terbatas selama ganjaran per langkah terbatas. Nilai γ juga adalah pernyataan preferensi: γ = 0,9 berarti ganjaran sepuluh langkah lagi hanya “terasa” sekitar 0,9¹⁰ ≈ 0,35 kali lipat ganjaran hari ini, sehingga agent yang tepat memilih ganjaran lebih cepat daripada janji yang sama besar di masa depan.
Fungsi Nilai dan Intuisi Persamaan Bellman #
Dua pertanyaan menuntun hampir semua analisis MDP. Pertama, “seberapa baik menjadi penghuni state s sambil mengikuti kebijakan π?” — jawabannya adalah fungsi nilai V^π(s), yaitu nilai harapan return berdiskon dari s dan seterusnya. Kedua, “seberapa baik memilih aksi a di s, lalu melanjutkan dengan π?” — jawabannya fungsi nilai-aksi Q^π(s, a). Keduanya dihubungkan identitas sederhana: Q^π(s, a) adalah rata-rata berbobot P dari R + γV^π(s′).
Kekuatan sesungguhnya datang dari persamaan Bellman, yang menyatakan V^π(s) harus sama dengan nilai harapan satu langkah pertama ditambah γV^π dari state penerusnya:
V^π(s) = Σ_s' P(s'|s, π(s)) · [R(s, π(s), s') + γ · V^π(s')]Persamaan ini rekursif: nilai sebuah state dibangun dari nilai state lain. Sifat rekursif tersebut justru menjadi keuntungan, karena algoritme yang lahir darinya sangat sederhana: mulai dari V = 0 di semua state, lalu ulangi backup Bellman di atas untuk semua state secara serentak sampai angkanya berhenti berubah. Prosedur ini disebut iterative policy evaluation, dan konvergensinya dijamin oleh γ < 1.
MDP Gudang Tiga State dalam NumPy #
Mari kita bangun MDP lengkap yang cukup kecil untuk dicetak seluruh isinya. Skenarionya: robot pengantar harus membawa barang dari Gudang melewati Koridor ke Tujuan. Dua aksi tersedia — jalan yang pelan dan aman, cepat yang menempuh jalan pintas berisiko. Kita menuliskan P dan R sebagai array NumPy berindeks [aksi, state asal, state tujuan], mengevaluasi tiga kebijakan tetap dengan sapuan Bellman, memverifikasi hasilnya terhadap penyelesaian sistem linear yang eksak, lalu melakukan lookahead satu langkah untuk membangun tabel Q.
# MDP kecil dengan 3 state (Gudang, Koridor, Tujuan) dan 2 aksi
# (jalan = pelan-aman, cepat = berisiko). Seluruh dinamika lingkungan
# ditulis eksplisit sebagai tabel transisi P[a, s, s'] dan tabel
# ganjaran R[a, s, s']. Kita mengevaluasi tiga kebijakan tetap dengan
# iterative policy evaluation (sapuan Bellman), lalu memverifikasi
# hasilnya lewat penyelesaian sistem linear, dan menutup dengan
# lookahead satu langkah untuk membangun Q(s, a).
import numpy as np
np.set_printoptions(precision=2, suppress=True)
GAMMA = 0.9
NAMA_STATE = ["Gudang", "Koridor", "Tujuan"]
NAMA_AKSI = ["jalan", "cepat"]
TOLERANSI = 1e-10
MAKS_SAPUAN = 200
# P[a, s, s'] = peluang berpindah ke s' jika memilih aksi a di state s.
P = np.array([
# aksi "jalan" (pelan, aman, lambat)
[[0.0, 1.0, 0.0], # dari Gudang -> pasti ke Koridor
[0.0, 0.0, 1.0], # dari Koridor -> pasti ke Tujuan lewat jalur lama
[0.0, 0.0, 1.0]], # dari Tujuan -> terminal, menyerap
# aksi "cepat" (jalan pintas berisiko)
[[0.0, 0.7, 0.3], # dari Gudang -> 70% nyasar ke Koridor, 30% langsung Tujuan
[0.0, 0.15, 0.85], # dari Koridor -> 85% sampai, 15% terpeleset di tempat
[0.0, 0.0, 1.0]],
])
# R[a, s, s'] = ganjaran saat berpindah dari s ke s' lewat aksi a.
R = np.array([
# aksi "jalan"
[[0.0, 0.0, 0.0], # Gudang -> Koridor: gratis, hanya lambat
[0.0, 0.0, -2.0], # Koridor -> Tujuan: jalur kargo lama, biaya waktu
[0.0, 0.0, 0.0]],
# aksi "cepat"
[[0.0, -5.0, 0.0], # Gudang -> Koridor: menabrak rak, barang rusak
[0.0, -1.0, 0.0], # Koridor -> Koridor: terpeleset, kehilangan waktu
[0.0, 0.0, 0.0]],
])
def evaluasi_kebijakan(kebijakan):
"""Iterative policy evaluation dengan sapuan Bellman serentak."""
V = np.zeros(3)
riwayat = []
for sapuan in range(1, MAKS_SAPUAN + 1):
V_baru = np.zeros(3)
for s in range(3):
a = kebijakan[s]
V_baru[s] = sum(P[a, s, s_next] * (R[a, s, s_next] + GAMMA * V[s_next])
for s_next in range(3))
delta = float(np.max(np.abs(V_baru - V)))
V = V_baru
riwayat.append((sapuan, V.copy(), delta))
if delta < TOLERANSI:
break
return V, riwayat
def nilai_eksak(kebijakan):
"""Solusi persis: selesaikan (I - gamma * P_pi) V = r_pi."""
P_pi = np.array([P[kebijakan[s], s, :] for s in range(3)])
r_pi = np.array([P[kebijakan[s], s, :] @ R[kebijakan[s], s, :] for s in range(3)])
return np.linalg.solve(np.eye(3) - GAMMA * P_pi, r_pi)
print(f"MDP 3 state x 2 aksi | gamma = {GAMMA} | toleransi {TOLERANSI:.0e}")
for a, nama in enumerate(NAMA_AKSI):
print(f"\nP[{nama}] (baris = state asal, kolom = state tujuan):")
print(P[a])
print(f"R[{nama}]:")
print(R[a])
kebijakan_list = [
# Aksi pada state terminal (Tujuan) tidak berpengaruh: state menyerap.
("selalu jalan", [0, 0, 0]),
("selalu cepat", [1, 1, 1]),
("campuran (jalan lalu cepat)", [0, 1, 0]),
]
hasil_akhir = {}
for nama, keb in kebijakan_list:
print(f"\n== Evaluasi kebijakan: {nama} ==")
print(f"{'sapuan':>7} {'V(Gudang)':>10} {'V(Koridor)':>11} "
f"{'V(Tujuan)':>10} {'delta':>10}")
V, riwayat = evaluasi_kebijakan(keb)
for sapuan, Vs, delta in riwayat:
print(f"{sapuan:>7} {Vs[0]:>10.3f} {Vs[1]:>11.3f} "
f"{Vs[2]:>10.3f} {delta:>10.6f}")
V_eksak = nilai_eksak(keb)
beda = float(np.max(np.abs(V - V_eksak)))
print(f"Nilai eksak (np.linalg.solve) : "
f"[{V_eksak[0]:.3f}, {V_eksak[1]:.3f}, {V_eksak[2]:.3f}]")
print(f"Simpangan iteratif vs eksak : {beda:.2e}")
hasil_akhir[nama] = V
print("\nRingkasan V akhir (state Gudang dan Koridor):")
print(f"{'kebijakan':<28} {'V(Gudang)':>10} {'V(Koridor)':>11}")
for nama, V in hasil_akhir.items():
print(f"{nama:<28} {V[0]:>10.3f} {V[1]:>11.3f}")
# Lookahead satu langkah dari V kebijakan campuran -> Q(s, a).
V_ref = hasil_akhir["campuran (jalan lalu cepat)"]
print("\nQ(s, a) dihitung dari V kebijakan campuran:")
print(f"{'state':<10} {'Q(s, jalan)':>12} {'Q(s, cepat)':>12} aksi terbaik")
for s in range(2):
q = [sum(P[a, s, sp] * (R[a, s, sp] + GAMMA * V_ref[sp]) for sp in range(3))
for a in range(2)]
terbaik = NAMA_AKSI[int(np.argmax(q))]
print(f"{NAMA_STATE[s]:<10} {q[0]:>12.3f} {q[1]:>12.3f} {terbaik}")
print("Kebijakan serakah = jalan di Gudang, cepat di Koridor "
"(sama dengan campuran -> kebijakan optimal)")Output yang Dihasilkan:
MDP 3 state x 2 aksi | gamma = 0.9 | toleransi 1e-10
P[jalan] (baris = state asal, kolom = state tujuan):
[[0. 1. 0.]
[0. 0. 1.]
[0. 0. 1.]]
R[jalan]:
[[ 0. 0. 0.]
[ 0. 0. -2.]
[ 0. 0. 0.]]
P[cepat] (baris = state asal, kolom = state tujuan):
[[0. 0.7 0.3 ]
[0. 0.15 0.85]
[0. 0. 1. ]]
R[cepat]:
[[ 0. -5. 0.]
[ 0. -1. 0.]
[ 0. 0. 0.]]
== Evaluasi kebijakan: selalu jalan ==
sapuan V(Gudang) V(Koridor) V(Tujuan) delta
1 0.000 -2.000 0.000 2.000000
2 -1.800 -2.000 0.000 1.800000
3 -1.800 -2.000 0.000 0.000000
Nilai eksak (np.linalg.solve) : [-1.800, -2.000, 0.000]
Simpangan iteratif vs eksak : 0.00e+00
== Evaluasi kebijakan: selalu cepat ==
sapuan V(Gudang) V(Koridor) V(Tujuan) delta
1 -3.500 -0.150 0.000 3.500000
2 -3.594 -0.170 0.000 0.094500
3 -3.607 -0.173 0.000 0.012758
4 -3.609 -0.173 0.000 0.001722
5 -3.609 -0.173 0.000 0.000233
6 -3.609 -0.173 0.000 0.000031
7 -3.609 -0.173 0.000 0.000004
8 -3.609 -0.173 0.000 0.000001
9 -3.609 -0.173 0.000 0.000000
10 -3.609 -0.173 0.000 0.000000
11 -3.609 -0.173 0.000 0.000000
12 -3.609 -0.173 0.000 0.000000
13 -3.609 -0.173 0.000 0.000000
Nilai eksak (np.linalg.solve) : [-3.609, -0.173, 0.000]
Simpangan iteratif vs eksak : 4.00e-12
== Evaluasi kebijakan: campuran (jalan lalu cepat) ==
sapuan V(Gudang) V(Koridor) V(Tujuan) delta
1 0.000 -0.150 0.000 0.150000
2 -0.135 -0.170 0.000 0.135000
3 -0.153 -0.173 0.000 0.018225
4 -0.156 -0.173 0.000 0.002460
5 -0.156 -0.173 0.000 0.000332
6 -0.156 -0.173 0.000 0.000045
7 -0.156 -0.173 0.000 0.000006
8 -0.156 -0.173 0.000 0.000001
9 -0.156 -0.173 0.000 0.000000
10 -0.156 -0.173 0.000 0.000000
11 -0.156 -0.173 0.000 0.000000
12 -0.156 -0.173 0.000 0.000000
13 -0.156 -0.173 0.000 0.000000
Nilai eksak (np.linalg.solve) : [-0.156, -0.173, 0.000]
Simpangan iteratif vs eksak : 5.72e-12
Ringkasan V akhir (state Gudang dan Koridor):
kebijakan V(Gudang) V(Koridor)
selalu jalan -1.800 -2.000
selalu cepat -3.609 -0.173
campuran (jalan lalu cepat) -0.156 -0.173
Q(s, a) dihitung dari V kebijakan campuran:
state Q(s, jalan) Q(s, cepat) aksi terbaik
Gudang -0.156 -3.609 jalan
Koridor -2.000 -0.173 cepat
Kebijakan serakah = jalan di Gudang, cepat di Koridor (sama dengan campuran -> kebijakan optimal)Mari kita bedah bagian-bagian pentingnya:
- Baris 20–41 (tabel P dan R): dua array bertingkat ini adalah MDP itu sendiri. Indeks
[a, s, s']membuat baris kodeP[a, s, s_next]terbaca persis seperti notasi P(s′ | s, a); komentar per baris menjelaskan arti dunia nyata tiap entri sehingga tabel bisa diaudit tanpa membuka rumus. - Baris 44–59 (
evaluasi_kebijakan): inti algoritme. Setiap sapuan membangunV_barusepenuhnya dariVlama (sapuan serentak), menghitungdeltasebagai perubahan terbesar, dan berhenti ketika perubahan di bawahTOLERANSI. Barissum(...)adalah persamaan Bellman yang diterjemahkan hampir kata per kata. - Baris 62–66 (
nilai_eksak): karena V memenuhi persamaan linear rekursif, kita bisa menyusunP_pidanr_pimilik kebijakan lalu menyelesaikan(I − γP_pi)V = r_pidengannp.linalg.solve— jangkar kebenaran untuk menguji hasil iterasi. - Baris 77–82 (tiga kebijakan): setiap kebijakan hanyalah daftar indeks aksi per state; entri untuk state terminal diisi aksi apa pun karena state tersebut menyerap dan tidak pernah ditinggalkan.
- Baris 105–113 (lookahead satu langkah): dari V kebijakan campuran, kita menghitung Q(s, a) untuk kedua aksi di kedua state non-terminal, lalu
np.argmaxmemilih aksi terbaiknya — persis seperti yang akan dilakukan algoritme policy improvement.
Keluaran program membawa tiga pelajaran. Pertama, kecepatan konvergensi mengikuti struktur MDP: kebijakan “selalu jalan” yang deterministik mencapai nilai akhirnya dalam tiga sapuan, sedangkan kedua kebijakan lain perlu belasan sapuan karena aksi “cepat” menyisakan 15% peluang menetap di Koridor — deret geometris 0,135 per sapuan terlihat jelas pada kolom delta yang menyusut. Kedua, verifikasi np.linalg.solve menunjukkan simpangan iteratif terhadap solusi eksak hanya sekitar 10⁻¹² — sapuan Bellman memang menuju solusi yang sama, hanya dengan cara yang lebih murah. Ketiga, dan paling penting: tabel ringkasan membuktikan bahwa keputusan terbaik berbeda per state — “jalan” menang di Gudang (−0,156) dan “cepat” menang di Koridor (−0,173) — sehingga kebijakan campuran mengungguli kedua kebijakan monoton. Lookahead Q di akhir keluaran kemudian menemukan kembali kebijakan campuran dari dalam, tanda bahwa kebijakan tersebut sudah optimal menurut MDP ini.
Satu batasan penting dari seluruh perhitungan di atas: P dan R harus tersedia dan benar. Pada robot nyata, tabel semacam itu jarang diketahui — yang ada hanyalah pengalaman berupa pasangan (s, a, r, s′) yang lewat sekali dan tidak diulang. Cara memanen kebijakan baik dari arus pengalaman semacam itulah materi Chapter Q-Learning.
Referensi Resmi #
- numpy —
numpy.linalg.solve— API resmi penyelesaian sistem linear yang menjadi pembanding eksak bagi hasil sapuan Bellman. - numpy —
numpy.argmax— API resmi pemilihan aksi terbaik pada lookahead satu langkah. - numpy — Array indexing
— panduan resmi pengindeksan array bertingkat seperti
P[a, s, s']yang dipakai seluruh contoh. - Gymnasium — situs resmi pustaka lingkungan RL; banyak lingkungan bawaannya memodelkan MDP eksplisit seperti yang kita bangun manual di sini.