Markov Decision Process

Dua chapter sebelumnya memberi kita kosakata (agent, environment, reward) dan bukti bahwa desain reward mengubah perilaku. Untuk menghitung kebijakan optimal secara sistematis, kosakata itu perlu dirumuskan menjadi model matematis, dan model standar di RL adalah Markov Decision Process (MDP). Dari MDP lahir dua alat yang dipakai sepanjang sisa section ini: return diskonto sebagai ukuran kebijakan, dan persamaan Bellman sebagai mesin penghitung nilai. Pada chapter ini kita menyusun MDP kecil empat state, menghitung return diskonto secara manual, lalu menjalankan value iteration dengan NumPy hingga konvergen — hasilnya kita cocokkan dengan hitungan tangan sampai ke digit terakhir.

Lima Komponen MDP #

Sebuah MDP adalah tupel (S, A, P, R, γ) dengan makna berikut:

Satu sifat menempel pada nama kerangka ini: Markov property — masa depan hanya bergantung pada state sekarang, bukan pada jalur yang dilalui untuk sampai ke sana. Posisi agen di GridWorld memenuhi sifat itu: dari (2,2), langkah kanan menuju (2,3) apa pun yang terjadi sebelumnya. Pada dunia yang belum memenuhi sifat ini, kita memperluas state (misalnya menambah memori posisi) hingga memenuhi — itulah sebabnya state didefinisikan sebagai informasi penentu masa depan, bukan sekadar potret terkini.

Return Diskonto #

Kebijakan dinilai dari return G_t, yaitu jumlah reward yang akan terkumpul mulai langkah t, dengan tiap reward masa depan dikalikan γ satu kali per langkah jauhnya:

G_t = r_(t+1) + γ·r_(t+2) + γ²·r_(t+3) + ...

Diskonto dua arah gunanya. Pertama, jumlah bergaya geometri tetap terbatas meski episode tak berujung, sehingga γ < 1 memungkinkan masalah berumur panjang. Kedua, γ mengatur seberapa jauh agen memandang ke depan: γ = 0 membuat agen hanya mengejar reward langkah berikutnya, sedangkan γ → 1 membuat agen bersabar menabung nilai jangka panjang. Dengan γ = 0.9, reward tiga langkah mendatang masih terasa 0.81 kali lipatnya.

Demo: Return Manual dan Value Iteration #

Berkas value_iteration.py memakai MDP empat state pada tabel di atas: agen harus maju tiga kali menuju terminal, tiap perpindahan -1, dan lompatan terakhir dari state 2 bernilai +9. Bagian pertama menghitung return dari belakang (return di state terminal dianggap 0), bagian kedua menjalankan value iteration — pembaruan Bellman yang diulang sampai nilai tidak berubah lagi:

V(s) ← max_a [ R(s,a) + γ · V(s') ]

Intuisi pembaruannya: anggap nilai V yang ada sekarang sudah benar, hitung nilai satu langkah ke depan untuk tiap aksi, ambil yang tertinggi, lalu ulangi. Berbeda dengan gradient descent pada chapter Gradient Descent yang melangkah kecil-kecil memakai learning rate, pembaruan Bellman ini langsung menimpa nilai lama dan, untuk MDP kecil, berhenti tepat di solusi optimal dalam hitungan iterasi.

"""MDP 4-state: hitung return diskonto manual, lalu value iteration.

State 0, 1, 2 adalah state biasa; state 3 adalah terminal (episode
berakhir). Dua aksi tersedia: "maju" pindah ke state berikutnya, "mundur"
pindah ke state sebelumnya (state 0 tetap di 0). Reward perpindahan -1,
kecuali maju dari state 2 ke terminal bernilai +9. Diskonto gamma = 0.9.
"""

import numpy as np

GAMMA = 0.9
NAMA_AKSI = ["maju", "mundur"]

# P[s, a] = state tujuan; R[s, a] = reward (s = 0..2, a = 0..1)
P = np.array([[1, 0], [2, 1], [3, 2]])
R = np.array([[-1.0, -1.0], [-1.0, -1.0], [9.0, -1.0]])

# ---- Bagian 1: return diskonto dihitung manual dari belakang ----
print("Return diskonto manual (gamma = 0.9):")
print("  trajektori: state 0 -> 1 -> 2 -> 3, reward [-1, -1, +9]")
reward_traj = [-1.0, -1.0, 9.0]
G = 0.0                                    # G di state terminal = 0
print("  G3 (state 3, terminal)          = 0.00")
for t in (2, 1, 0):
    G_sebelumnya = G
    G = reward_traj[t] + GAMMA * G_sebelumnya
    print(f"  G{t} = {reward_traj[t]:+.1f} + 0.9 x {G_sebelumnya:6.2f}"
          f" = {G:.2f}")
print(f"  cek maju : -1 + 0.9(-1) + 0.81(9) = {-1 + 0.9 * -1 + 0.81 * 9:.2f}")

# ---- Bagian 2: value iteration ----
V = np.zeros(4)
print("\nValue iteration (V awal = 0 di semua state):")
iterasi_konvergen = None
for k in range(1, 11):
    V_baru = V.copy()
    for s in range(3):
        nilai_aksi = R[s] + GAMMA * V[P[s]]     # R + gamma V(s')
        V_baru[s] = nilai_aksi.max()
    delta = float(np.abs(V_baru - V).max())
    V = V_baru
    if delta == 0.0 and iterasi_konvergen is None:
        iterasi_konvergen = k
    if k <= 5 or k == 10:
        tampil = " ".join(f"{v:6.2f}" for v in V)
        print(f"  iterasi {k:2d}: V = [{tampil} ]  perubahan maks = {delta:.4f}")
print(f"  konvergen pada iterasi {iterasi_konvergen} (perubahan tepat 0)")

# ---- Bagian 3: Q(s,a) dan kebijakan greedy ----
print("\nQ(s,a) = R + gamma x V(s') pada V akhir, beserta aksi greedy:")
for s in range(3):
    q = R[s] + GAMMA * V[P[s]]
    aksi_greedy = NAMA_AKSI[int(np.argmax(q))]
    print(f"  state {s}: Q(maju)={q[0]:6.2f}  Q(mundur)={q[1]:6.2f}"
          f"  -> pilih {aksi_greedy}")

# ---- Bagian 4: verifikasi ----
residu = max(
    abs(V[s] - (R[s] + GAMMA * V[P[s]]).max()) for s in range(3)
)
print(f"\nResidu Bellman        : {residu:.6f}")
print(f"Return manual G0      : {G:.4f}")
print(f"V*(0) dari iterasi    : {V[0]:.4f}")
print(f"G0 sama dengan V*(0)  : {abs(G - V[0]) < 1e-12}")

Output yang Dihasilkan:

Return diskonto manual (gamma = 0.9):
  trajektori: state 0 -> 1 -> 2 -> 3, reward [-1, -1, +9]
  G3 (state 3, terminal)          = 0.00
  G2 = +9.0 + 0.9 x   0.00 = 9.00
  G1 = -1.0 + 0.9 x   9.00 = 7.10
  G0 = -1.0 + 0.9 x   7.10 = 5.39
  cek maju : -1 + 0.9(-1) + 0.81(9) = 5.39

Value iteration (V awal = 0 di semua state):
  iterasi  1: V = [ -1.00  -1.00   9.00   0.00 ]  perubahan maks = 9.0000
  iterasi  2: V = [ -1.90   7.10   9.00   0.00 ]  perubahan maks = 8.1000
  iterasi  3: V = [  5.39   7.10   9.00   0.00 ]  perubahan maks = 7.2900
  iterasi  4: V = [  5.39   7.10   9.00   0.00 ]  perubahan maks = 0.0000
  iterasi  5: V = [  5.39   7.10   9.00   0.00 ]  perubahan maks = 0.0000
  iterasi 10: V = [  5.39   7.10   9.00   0.00 ]  perubahan maks = 0.0000
  konvergen pada iterasi 4 (perubahan tepat 0)

Q(s,a) = R + gamma x V(s') pada V akhir, beserta aksi greedy:
  state 0: Q(maju)=  5.39  Q(mundur)=  3.85  -> pilih maju
  state 1: Q(maju)=  7.10  Q(mundur)=  5.39  -> pilih maju
  state 2: Q(maju)=  9.00  Q(mundur)=  7.10  -> pilih maju

Residu Bellman        : 0.000000
Return manual G0      : 5.3900
V*(0) dari iterasi    : 5.3900
G0 sama dengan V*(0)  : True

Tiga pemeriksaan pada keluaran menenangkan kita bahwa mesin ini benar. Pertama, hitungan manual G0 = 5.39 (dihitung dari belakang: 9.00 → 7.10 → 5.39) sama persis dengan V*(0) hasil iterasi — baris terakhir mencetak True. Kedua, iterasi konvergen pada putaran keempat dengan perubahan tepat nol; nilai 5.39, 7.10, 9.00 tidak bergeser lagi karena sudah memenuhi persamaan Bellman (residu 0.000000). Ketiga, tabel Q(s,a) yang diturunkan dari V memilih maju di ketiga state. Mari kita telaah kode di atas baris per baris:

1. Baris 11-16: kelima komponen MDP dalam tiga variabel — GAMMA, tabel transisi P[s,a] berisi state tujuan, dan tabel reward R[s,a].
2. Baris 21-29: perhitungan return manual dari belakang; G diinisialisasi 0 (nilai state terminal), lalu tiap langkah dihitung G = r + γ·G.
3. Baris 32-47: siklus value iteration — V_baru dihitung dari V lama lewat nilai_aksi = R[s] + GAMMA * V[P[s]] dan V_baru[s] = nilai_aksi.max(); delta mencatat perubahan terbesar dan iterasi konvergen tercatat saat delta tepat 0.
4. Baris 49-55: menurunkan Q(s,a) = R + γ·V(s') dari nilai akhir, lalu memilih aksi terbaik dengan argmax — fungsi np.argmax mengembalikan indeks nilai terbesar.
5. Baris 57-64: verifikasi silang — residu Bellman terbesar di antara ketiga state, kecocokan G0 dengan V*(0), hingga cetak True sebagai penutup.

Kebijakan dari Nilai #

Setelah V* diperoleh, kebijakan optimal tinggal dibaca: pada tiap state, pilih aksi dengan R(s,a) + γ·V*(s') terbesar. Seluruh perhitungan chapter ini mengasumsikan P dan R diketahui — agen perencana, bukan pembelajar. Kenyataannya agent sungguhan tidak diberi tabel transisi; agent hanya menyaksikan pasangan (s, a, r, s') yang lewat. Maka pertanyaan berikutnya: bagaimana menaksir nilai — khususnya Q(s,a) — murni dari pengalaman, tanpa model? Itulah pekerjaan Q-learning, bintang chapter Value Function .