Anatomi MDP

State, aksi, dinamika, reward, dan faktor diskon gamma.

Daftar isi

Proses keputusan Markov, atau MDP, adalah kerangka formal yang dipakai seluruh algoritma reinforcement learning untuk memodelkan interaksi antara agen dan lingkungan. Topik ini membongkar lima komponen yang menyusun sebuah MDP, yaitu himpunan state, himpunan aksi, fungsi transisi, fungsi reward, dan faktor diskon gamma, lalu menyusunnya menjadi satu struktur data Python yang dapat diakses per state dan per aksi. Setelah membaca topik ini, pembaca dapat membaca definisi formal MDP dan menerjemahkannya menjadi data yang siap dipakai algoritma pada modul-modul berikutnya.

Lima komponen MDP#

Sebuah MDP didefinisikan sebagai sebuah tuple $\langle S, A, P, R, \gamma \rangle$ yang terdiri atas lima komponen. $S$ adalah himpunan state yang menggambarkan seluruh situasi mungkin yang dialami agen. $A$ adalah himpunan aksi yang dapat dipilih agen pada setiap state. $P$ adalah fungsi transisi $P(s' \mid s, a)$ yang menyatakan peluang berpindah ke state $s'$ bila agen berada di state $s$ dan memilih aksi $a$ . $R$ adalah fungsi reward $R(s, a, s')$ yang memberi nilai numerik atas transisi tersebut. $\gamma \in [0, 1)$ adalah faktor diskon yang menentukan seberapa besar reward masa depan dibobotkan terhadap reward sekarang.

Komponen $P$ dan $R$ bersama-sama disebut dinamika MDP. Karena properti Markov berlaku, dinamika ini sepenuhnya diringkas oleh pasangan $(s, a)$ , tanpa perlu mengingat riwayat sebelumnya. Akibatnya, seluruh perilaku lingkungan dapat dihitung dari tabel transisi dan reward yang berukuran $|S| \times |A|$ . Pada masalah nyata, tabel ini bisa sangat besar atau bahkan tak terhingga, sehingga algoritma belajar mengaproksimasinya dari pengalaman. Pada modul ini, contoh dipertahankan kecil agar seluruh struktur dapat dicetak dan diperiksa secara manual.

Faktor diskon gamma#

Faktor diskon $\gamma$ mengendalikan horizon keputusan agen. Nilai $\gamma = 0$ membuat agen hanya mempedulikan reward langsung dari langkah berikutnya, sehingga perilakunya menjadi rakus jangka pendek. Nilai $\gamma$ mendekati satu membuat agen menimbang reward jauh ke depan hampir sama dengan reward sekarang, sehingga perilakunya menjadi perencana jangka panjang. Pemilihan $\gamma$ yang umum berada antara 0,9 dan 0,99, bergantung pada seberapa jauh horizon yang dianggap relevan.

Selain mengatur horizon, $\gamma < 1$ juga menjamin bahwa jumlah reward yang terdiskon tetap hingga, yaitu $\sum_{t=0}^{\infty} \gamma^t R_t$ tidak divergen. Jaminan ini menjadi syarat matematis agar fungsi nilai terdefinisi dengan baik dan agar algoritma iterasi nilai dapat konvergen. Tanpa diskon, sebuah episode tak berhingga dengan reward positif konstan akan menghasilkan return tak hingga, sehingga perbandingan antar kebijakan menjadi tidak bermakna.

MDP gridworld mini sebagai struktur data#

Blok berikut mendefinisikan sebuah MDP gridworld mini dengan empat state (s0 sampai s3) dan dua aksi (kiri dan kanan). Dinamika disimpan sebagai dict bersarang transisi[state][action], yang nilainya adalah daftar tuple (next_state, prob, reward). Daftar ini memuat seluruh kemungkinan outcome, termasuk yang bersifat stokastik, sehingga jumlah probabilitas dalam satu daftar harus berjumlah satu.

python anatomi_mdp.py

import warnings
warnings.filterwarnings("ignore")

# MDP gridworld mini: 4 state (s0..s3), 2 aksi (kiri, kanan)
states = ["s0", "s1", "s2", "s3"]
actions = ["kiri", "kanan"]
gamma = 0.9

# transisi[state][action] = [(next_state, prob, reward), ...]
transisi = {
    "s0": {
        "kiri": [("s0", 1.0, 0.0)],
        "kanan": [("s1", 1.0, 0.0)],
    },
    "s1": {
        "kiri": [("s0", 1.0, 0.0)],
        "kanan": [("s2", 1.0, 0.0)],
    },
    "s2": {
        "kiri": [("s1", 1.0, 0.0)],
        "kanan": [("s3", 0.8, 1.0), ("s2", 0.2, 0.0)],
    },
    "s3": {
        "kiri": [("s3", 1.0, 0.0)],
        "kanan": [("s3", 1.0, 0.0)],
    },
}

print("State:", states)
print("Aksi:", actions)
print("gamma:", gamma)
print()
for s in states:
    for a in actions:
        outcomes = transisi[s][a]
        pairs = ", ".join(f"({ns}, {p:.2f}, {r:.1f})" for ns, p, r in outcomes)
        print(f"transisi[{s}][{a}] = [{pairs}]")

text Keluaran

State: ['s0', 's1', 's2', 's3']
Aksi: ['kiri', 'kanan']
gamma: 0.9

transisi[s0][kiri] = [(s0, 1.00, 0.0)]
transisi[s0][kanan] = [(s1, 1.00, 0.0)]
transisi[s1][kiri] = [(s0, 1.00, 0.0)]
transisi[s1][kanan] = [(s2, 1.00, 0.0)]
transisi[s2][kiri] = [(s1, 1.00, 0.0)]
transisi[s2][kanan] = [(s3, 0.80, 1.0), (s2, 0.20, 0.0)]
transisi[s3][kiri] = [(s3, 1.00, 0.0)]
transisi[s3][kanan] = [(s3, 1.00, 0.0)]

Keluaran tersebut memperlihatkan dua sifat penting. State s0, s1, dan s2 bersifat deterministik pada aksi kiri, sedangkan aksi kanan dari s2 bersifat stokastik dengan dua outcome, yaitu mencapai s3 dengan peluang 0,8 dan reward 1,0, atau tetap di s2 dengan peluang 0,2 dan reward 0,0. State s3 bersifat terminal karena kedua aksi mengembalikan s3 itu sendiri dengan reward nol, sehingga agen tidak lagi berpindah. Struktur dict bersarang ini menyimpan dinamika lengkap dalam satu objek, dan setiap algoritma cukup mengakses transisi[s][a] untuk memperoleh seluruh outcome beserta peluang dan rewardnya.

Mengapa struktur ini cukup#

Struktur transisi[state][action] sudah memuat seluruh informasi yang dibutuhkan algoritma reinforcement learning berbasis model. Sebuah algoritma dapat menghitung expected reward untuk satu langkah dengan menjumlahkan prob * reward atas seluruh outcome, dan dapat menghitung expected value state berikutnya dengan menjumlahkan prob * V[next_state]. Karena data disimpan dalam bentuk daftar tuple, pembaruan iteratif menjadi langsung dan tidak memerlukan representasi matriks tiga dimensi. Struktur ini juga mendukung transisi stokastik secara alami tanpa perlu kode khusus.

Pemisahan antara dinamika ( $P$ dan $R$ ) dengan kebijakan agen menjadi inti kerangka MDP. Dinamika adalah milik lingkungan dan tidak berubah selama agen belajar, sedangkan kebijakan adalah objek yang dipelajari agen untuk bertindak optimal. Topik berikutnya membahas kebijakan secara terpisah, kemudian fungsi nilai yang mengukur kualitas kebijakan terhadap dinamika ini. Dengan demikian, struktur dict di atas menjadi fondasi yang dipakai berulang sepanjang modul.

Kesalahan umum#

Lupa menormalisasi peluang transisi. Penyebabnya, outcome ditulis satu per satu tanpa memeriksa jumlah peluangnya. Akibatnya, distribusi tidak berjumlah satu sehingga perhitungan expected value menjadi bias. Perbaikannya, tambahkan pengecekan otomatis bahwa sum(prob) untuk setiap transisi[s][a] sama dengan satu, atau gunakan fungsi pembantu yang memvalidasi seluruh entri sebelum dipakai algoritma.

Menganggap reward terikat pada state, bukan pada transisi. Penyebabnya, banyak contoh sederhana memakai reward yang hanya bergantung pada state tujuan. Akibatnya, reward ditulis sebagai atribut state, padahal definisi formal MDP mengaitkannya pada transisi $(s, a, s')$ . Perbaikannya, simpan reward di dalam tuple outcome bersama next_state dan prob, sehingga transisi yang berbeda menuju state yang sama dapat membawa reward yang berbeda.

Ringkasan#

MDP adalah tuple $\langle S, A, P, R, \gamma \rangle$ yang terdiri atas state, aksi, fungsi transisi, fungsi reward, dan faktor diskon.
Faktor diskon $\gamma \in [0, 1)$ mengatur horizon keputusan sekaligus menjamin return terdiskon tetap hingga.
Dinamika $P$ dan $R$ diringkas oleh pasangan $(s, a)$ akibat properti Markov, sehingga dapat disimpan sebagai transisi[state][action] berupa daftar tuple (next_state, prob, reward).
Pemisahan dinamika dari kebijakan memungkinkan agen mempelajari kebijakan optimal tanpa mengubah lingkungan.

Referensi#

Reinforcement Learning: An Introduction, ch. 3 — Sutton & Barto — Definisi formal MDP, dinamika, dan faktor diskon pada bab “Finite Markov Decision Processes”.