Properti Markov

Kapan masa kini meringkas masa lalu dan kapan properti ini menyesatkan.

Daftar isi

Properti Markov adalah pernyataan bahwa masa kini merangkum seluruh masa lalu yang relevan untuk memprediksi masa depan, sehingga masa depan hanya bergantung pada state saat ini dan tidak pada rentetan state sebelumnya. Topik ini menjelaskan kapan asumsi tersebut benar-benar berlaku pada sebuah rantai Markov kecil, kapan asumsi itu justru menyesatkan ketika agen tidak melihat seluruh state, dan apa konsekuensinya bagi algoritma reinforcement learning yang dibangun di atas kerangka MDP. Pembaca akan memperoleh definisi formal properti Markov, contoh simulasi numerik, dan batas berlakunya asumsi tersebut.

Properti Markov sebagai asumsi atas masa lalu#

Sebuah state bersifat Markov apabila distribusi probabilitas state berikutnya hanya bergantung pada state saat ini, tidak pada state-state sebelumnya. Secara formal, untuk sebarang riwayat $S_0, S_1, \dots, S_t$ berlaku

\Pr(S_{t+1}=s' \mid S_t=s, S_{t-1}, \dots, S_0) = \Pr(S_{t+1}=s' \mid S_t=s).

Persamaan ini menyatakan bahwa seluruh informasi yang berguna untuk memprediksi masa depan sudah terkandung dalam $S_t$ . Jika kondisi itu terpenuhi, riwayat $S_{t-1}, \dots, S_0$ menjadi berlebihan dan dapat dibuang tanpa kehilangan daya prediksi. Inilah alasan algoritma reinforcement learning cukup menyimpan state saat ini, bukan seluruh riwayat interaksi.

Asumsi ini bukan klaim tentang dunia, melainkan klaim tentang representasi yang dipilih. Sebuah sistem fisis mungkin memiliki banyak variabel tersembunyi, tetapi selama state yang dipakai menangkap seluruh variabel yang relevan, properti Markov tetap berlaku. Dalam praktik, state sering merupakan hasil rekayasa fitur sehingga asumsi tersebut mendekati benar. Ketika asumsi itu tidak terpenuhi, algoritma yang mengandalkan MDP tetap bisa dijalankan, tetapi hasilnya menjadi bias dan konvergensinya tidak dijamin menuju solusi yang optimal.

Rantai Markov dan matriks transisi#

Pada rantai Markov (Markov chain), sistem hanya memiliki state tanpa aksi, sehingga seluruh perilakunya dirangkum oleh sebuah matriks transisi $P$ . Elemen $P_{ij}$ menyatakan peluang berpindah dari state $i$ ke state $j$ dalam satu langkah. Setiap baris pada $P$ berjumlah satu karena agen pasti berpindah ke salah satu state. Bentuk ini memungkinkan simulasi lintasan state hanya dengan mengambil sampel berturut-turut dari distribusi baris yang sesuai.

Sebagai contoh, anggap tiga state cuaca harian, yaitu cerah, mendung, dan hujan. Peluang transisi antarstate dapat ditulis sebagai matriks $3 \times 3$ , dan lintasan cuaca selama beberapa hari disimulasikan dengan mengambil sampel beruntun dari matriks tersebut. Karena state cuaca diasumsikan Markov, cuaca besok hanya bergantung pada cuaca hari ini, bukan pada cuaca minggu lalu. Bila asumsi itu terbukti salah, matriks transisi tetap bisa dihitung, tetapi prediksi yang dihasilkan akan lebih buruk daripada model yang memperhitungkan riwayat.

Simulasi rantai Markov#

Blok berikut membangun matriks transisi $P$ untuk tiga state cuaca, lalu mensimulasikan sepuluh langkah dari state awal “cerah”. Seed acak ditetapkan agar keluaran dapat direproduksi persis.

python properti_markov.py

import warnings
warnings.filterwarnings("ignore")
import numpy as np

np.random.seed(0)

# Tiga state cuaca: cerah, mendung, hujan
states = ["cerah", "mendung", "hujan"]

# Matriks transisi P[i][j] = peluang dari state i ke state j
P = np.array([
    [0.6, 0.3, 0.1],
    [0.3, 0.4, 0.3],
    [0.2, 0.3, 0.5],
], dtype=float)

print("Matriks transisi P:")
print(np.array2string(P, precision=4))

# Simulasi 10 langkah dari state awal "cerah"
state = 0
trajectory = [states[state]]
for _ in range(10):
    state = np.random.choice(3, p=P[state])
    trajectory.append(states[state])

print("Lintasan 10 langkah dari 'cerah':")
print(" -> ".join(trajectory))

text Keluaran

Matriks transisi P:
[[0.6 0.3 0.1]
 [0.3 0.4 0.3]
 [0.2 0.3 0.5]]
Lintasan 10 langkah dari 'cerah':
cerah -> cerah -> mendung -> mendung -> mendung -> mendung -> mendung -> mendung -> hujan -> hujan -> mendung

Keluaran tersebut menunjukkan bahwa walaupun matriks transisi tetap, lintasan yang dihasilkan bersifat acak. Setiap langkah mengambil sampel dari distribusi baris state saat ini, sehingga dua simulasi dengan seed berbeda menghasilkan lintasan yang berbeda pula. Meskipun demikian, distribusi jangka panjang lintasan akan konvergen ke distribusi stasioner matriks $P$ , yang tidak bergantung pada state awal. Sifat inilah yang menjadi dasar analisis teoretis MDP, termasuk keberadaan solusi optimal dan konvergensi algoritma pemrograman dinamis.

Kapan properti Markov menyesatkan#

Properti Markov menjadi menyesatkan apabila agen tidak melihat state sebenarnya, melainkan hanya sebuah observasi yang sebagian mengungkapkan state. Ranah seperti ini disebut partially observable MDP atau POMDP. Pada POMDP, observasi tunggal tidak cukup untuk memprediksi masa depan karena dua state berbeda dapat menghasilkan observasi yang sama. Akibatnya, keputusan optimal tidak lagi bergantung pada observasi saat ini, melainkan pada riwayat observasi atau pada belief state, yaitu distribusi probabilitas atas state yang tersembunyi.

Sebagai ilustrasi, pada permainan poker agen tidak mengetahui kartu lawan, sehingga observasi berupa kartu di tangan dan kartu di meja tidak bersifat Markov. Dua situasi dengan observasi yang sama dapat menyembunyikan kartu lawan yang berbeda, sehingga aksi terbaik bisa berbeda. Dalam kasus seperti ini, mengabaikan riwayat dan memperlakukan observasi sebagai state Markov akan menyesatkan karena algoritma mengasumsikan informasi yang sebetulnya tidak dimiliki. Banyak algoritma praktik menanggapi hal ini dengan memakai jendela riwayat terkini atau jaringan rekuren sebagai pengganti state.

Konsekuensi praktisnya sederhana. Sebelum memodelkan sebuah masalah sebagai MDP, periksa apakah state yang dipakai benar-benar merangkum seluruh informasi yang relevan untuk keputusan berikutnya. Jika ya, algoritma standar seperti pemrograman dinamis dan Q-learning berlaku langsung. Jika tidak, diperlukan representasi yang memuat riwayat atau perkiraan state tersembunyi. Banyak masalah reinforcement learning nyata berada di antara kedua kutub ini, sehingga pemilihan representasi state sering menjadi keputusan desain yang menentukan kualitas solusi akhir.

Kesalahan umum#

Menganggap observasi sama dengan state. Penyebabnya, observasi terlihat seperti state karena keduanya sama-sama berupa vektor yang diterima agen dari lingkungan. Akibatnya, observasi dimasukkan langsung ke algoritma MDP tanpa pemeriksaan. Perbaikannya, periksa apakah observasi bersifat Markov dengan menguji apakah dua observasi yang sama dapat menyembunyikan kondisi masa depan yang berbeda. Bila ya, tambahkan riwayat atau perkiraan belief state ke dalam representasi.

Memakai seed acak tanpa kontrol pada eksperimen. Penyebabnya, keluaran simulasi rantai Markov bergantung pada generator acak, sehingga hasil berubah-ubah antar proses. Akibatnya, angka yang dilaporkan tidak dapat direproduksi dan perbandingan antar metode menjadi tidak adil. Perbaikannya, tetapkan seed secara eksplisit pada awal setiap blok yang mengandalkan acak, dan catat seed tersebut bersama hasilnya.

Ringkasan#

State bersifat Markov apabila masa depan hanya bergantung pada state saat ini, sehingga riwayat dapat dibuang tanpa kehilangan daya prediksi.
Rantai Markov dirangkum oleh matriks transisi $P$ yang baris-barisnya berjumlah satu, dan lintasannya disimulasikan dengan mengambil sampel beruntun dari baris state saat ini.
Properti Markov menjadi menyesatkan pada POMDP, yaitu ketika agen hanya menerima observasi parsial sehingga riwayat atau belief state menjadi perlu.
Pemilihan representasi state menentukan apakah algoritma MDP standar berlaku langsung atau memerlukan modifikasi.

Referensi#

Reinforcement Learning: An Introduction, ch. 3 — Sutton & Barto — Definisi formal MDP dan properti Markov pada bab “Finite Markov Decision Processes”.
Markov property — Wikipedia — Definisi matematis properti Markov dan konteksnya pada proses stokastik.