Pemrograman Dinamis Stokastik — Pengambilan Keputusan Sekuensial di Bawah Ketidakpastian
- Diperkenalkan oleh
- Bellman, R.; formalized for stochastic settings by Puterman, M. L.
- Tahun
- 1957
- Jenis
- Sequential optimization under uncertainty
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman Dinamis Stokastik (SDP) adalah kerangka kerja optimasi matematis untuk masalah pengambilan keputusan sekuensial di mana hasil sebagian bersifat acak.
SDP memperluas prinsip optimalitas Bellman ke lingkungan stokastik, merepresentasikan masalah sebagai Proses Keputusan Markov (MDP) dan menghitung kebijakan optimal dengan menyelesaikan persamaan nilai rekursif atas keadaan (state) dan periode waktu.
Intuisi di balik metode
Bayangkan mengelola waduk selama berbulan-bulan: setiap bulan Anda memutuskan berapa banyak air yang akan dilepaskan, tetapi curah hujan tidak pasti. SDP memecah ini menjadi serangkaian keputusan satu periode dan bertanya: mengingat tingkat air saat ini dan semua kemungkinan masa depan, kebijakan pelepasan mana yang memaksimalkan total manfaat yang diharapkan? Dengan bekerja mundur dari periode terakhir (atau beriterasi ke titik tetap), SDP menemukan tindakan optimal secara global di setiap keadaan yang memungkinkan — bahkan sebelum ketidakpastian terselesaikan. Wawasan kuncinya adalah bahwa nilai masa depan dari berada dalam suatu keadaan independen dari bagaimana Anda sampai di sana (properti Markov), yang membuat rekursi dapat dilacak.
Sejarah
Richard Bellman memperkenalkan pemrograman dinamis dalam bukunya tahun 1957, menetapkan prinsip optimalitas yang mendasari DP deterministik dan stokastik. Formalisme Proses Keputusan Markov Stokastik dikembangkan secara sistematis sepanjang tahun 1960-an–1970-an dan disatukan secara komprehensif oleh Martin Puterman dalam monografnya tahun 1994, yang tetap menjadi referensi standar untuk teori SDP cakrawala terbatas dan tak terbatas.
Kapan digunakan
Gunakan SDP ketika keputusan terungkap secara sekuensial dari waktu ke waktu atau tahapan, hasil bergantung pada transisi acak yang memenuhi properti Markov, dan model probabilitas lengkap untuk transisi tersebut tersedia atau dapat diestimasi. Pemicu umum: alokasi sumber daya dengan ketidakpastian permintaan, kontrol inventaris, penggantian peralatan, perencanaan pengobatan dengan respons pasien yang tidak pasti, atau pengiriman sistem energi. JANGAN gunakan ketika ruang keadaan terlalu besar untuk dihitung (kutukan dimensionalitas membuat SDP eksak secara komputasi tidak mungkin dilakukan tanpa aproksimasi), ketika probabilitas transisi tidak diketahui dan tidak dapat dimodelkan (pertimbangkan pembelajaran penguatan sebagai gantinya), ketika keputusan bersifat satu kali tanpa struktur sekuensial (gunakan optimasi statis), atau ketika asumsi Markov dilanggar oleh ketergantungan riwayat yang kuat.
Batasan dan pertimbangan
- Menderita kutukan dimensionalitas: persyaratan komputasi dan memori tumbuh secara eksponensial dengan jumlah variabel keadaan.
- Memerlukan spesifikasi eksplisit probabilitas transisi, yang mungkin tidak diketahui atau mahal untuk diestimasi.
- Metode eksak terbatas pada ruang keadaan dan tindakan diskrit (atau didiskretisasi); ruang kontinu memerlukan aproksimasi.
- Mengasumsikan properti Markov; sistem dengan memori panjang atau observabilitas parsial memerlukan ekstensi yang lebih kompleks (POMDP).
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menjamin kebijakan optimal secara global untuk MDP cakrawala terbatas atau tak terbatas yang didiskontokan dengan baik.
- Secara alami menangani ketidakpastian multi-tahap dengan mengkodekan semua kemungkinan masa depan dalam fungsi nilai.
- Struktur Markov secara dramatis mengurangi ruang pencarian dibandingkan dengan penelusuran ke depan yang menyeluruh.
- Algoritma iterasi kebijakan dan iterasi nilai dipahami dengan baik dengan jaminan konvergensi yang terbukti.
- Diperluas ke kriteria yang peka terhadap risiko (CVaR, varians rata-rata) dan MDP terbatas tanpa mengubah alur kerja dasar.
Penerapan
- Manajemen inventaris: menemukan jumlah pesanan yang meminimalkan biaya total yang diharapkan di bawah permintaan acak di berbagai periode.
- Perencanaan sumber daya air: penjadwalan pelepasan waduk di bawah aliran masuk yang tidak pasti untuk menyeimbangkan pembangkit listrik tenaga air dan risiko banjir.
- Perencanaan pengobatan kesehatan: memilih urutan pengobatan pasien mengingat probabilitas perkembangan penyakit yang tidak pasti.
- Sistem energi: strategi pengiriman dan pengisian daya penyimpanan optimal di bawah ketidakpastian pembangkitan terbarukan dan harga listrik.
- Keuangan: penyeimbangan kembali portofolio dan penetapan harga opsi di bawah dinamika harga aset stokastik.
- Penjadwalan pemeliharaan: menentukan kebijakan inspeksi dan penggantian untuk meminimalkan biaya umur peralatan yang diharapkan di bawah kegagalan acak.
Cara kerjanya
Cara kerjanya
Definisikan tupel MDP (S, A, P, R, gamma): ruang keadaan S yang menangkap semua konfigurasi sistem yang relevan, ruang tindakan A(s) dari keputusan yang diizinkan per keadaan, probabilitas transisi P(s'|s,a) yang menjelaskan bagaimana sistem berevolusi secara acak di bawah tindakan a, fungsi imbalan R(s,a) yang mengukur imbalan langsung, dan faktor diskonto gamma dalam [0,1] yang menimbang imbalan masa depan versus imbalan saat ini.
Ekspresikan fungsi nilai optimal V*(s) melalui persamaan optimalitas Bellman: V*(s) = max atas tindakan dari [R(s,a) + gamma * jumlah atas s' dari P(s'|s,a)*V*(s')]. Persamaan rekursif ini menyatakan bahwa nilai terbaik dalam keadaan s sama dengan imbalan langsung terbaik ditambah nilai yang diharapkan dari keadaan berikutnya yang didiskontokan di bawah kebijakan optimal.
Rumus
V^*(s) = \max_{a \in A(s)} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V^*(s') \right]Selesaikan V* secara iteratif. Inisialisasi V_0 secara sewenang-wenang (misalnya, semua nol), lalu terapkan operator Bellman berulang kali: V_{k+1}(s) = max_a [R(s,a) + gamma * jumlah_{s'} P(s'|s,a) V_k(s')]. Di bawah kondisi standar, urutan tersebut konvergen secara geometris ke V*.
Rumus
V_{k+1}(s) = \max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V_k(s') \right]Setelah konvergensi tercapai, ekstrak kebijakan optimal pi*(s) sebagai tindakan yang mencapai maksimum dalam persamaan Bellman di setiap keadaan. Kebijakan serakah ini terhadap V* terbukti optimal untuk masalah cakrawala tak terbatas yang didiskontokan.
Rumus
\pi^*(s) = \arg\max_{a} \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a)\, V^*(s') \right]Hentikan iterasi nilai ketika jarak norma sup antara fungsi nilai berturut-turut turun di bawah toleransi epsilon: ||V_{k+1} - V_k||_inf < epsilon. Kebijakan pi* yang dihasilkan adalah epsilon/(1-gamma)-optimal.
Rumus
\| V_{k+1} - V_k \|_\infty < \varepsilonKesalahan umum
- Mendiskretisasi keadaan kontinu terlalu kasar memperkenalkan kesalahan aproksimasi besar yang merambat melalui fungsi nilai.
- Memilih faktor diskonto gamma yang mendekati 1 memperlambat konvergensi secara dramatis; pengaturan yang mendekati 1 memerlukan kriteria penghentian yang cermat.
- Mengabaikan kondisi batas terminal dalam masalah cakrawala terbatas menyebabkan estimasi nilai yang secara sistematis salah pada tahap akhir.
- Memperlakukan kesalahan pemodelan sebagai dapat diabaikan: jika probabilitas transisi yang diasumsikan sangat berbeda dari kenyataan, kebijakan yang dihitung mungkin berkinerja buruk dalam praktik.
- Mencampuradukkan kebijakan (pemetaan dari keadaan ke tindakan) dengan fungsi nilai; hanya melaporkan V* tanpa mengekstrak pi* membuat masalah keputusan tidak terselesaikan.
Pertanyaan yang sering diajukan
Apa perbedaan antara pemrograman dinamis deterministik dan stokastik?
Dalam DP deterministik, keadaan berikutnya sepenuhnya ditentukan oleh keadaan dan tindakan saat ini, sehingga tidak ada probabilitas yang terlibat. Dalam SDP, keadaan berikutnya ditarik dari distribusi probabilitas bersyarat P(s'|s,a), membuat hasilnya acak. Persamaan Bellman dalam SDP mengambil ekspektasi atas transisi ini, yang merupakan perbedaan struktural utama.
Bagaimana cara menangani ruang keadaan yang terlalu besar untuk dihitung?
Ketika SDP eksak secara komputasi tidak mungkin dilakukan, gunakan pemrograman dinamis aproksimasi (ADP) atau pembelajaran penguatan. Teknik-teknik ini meliputi aproksimasi fungsi linier dari fungsi nilai, aproksimator berbasis jaringan saraf (deep RL), dan metode berbasis simulasi seperti iterasi kebijakan aproksimasi, yang semuanya menukar jaminan optimalitas dengan skalabilitas.
Apakah SDP sama dengan Proses Keputusan Markov?
MDP adalah model matematis (tupel S, A, P, R, gamma). Pemrograman Dinamis Stokastik mengacu pada keluarga algoritma — iterasi nilai, iterasi kebijakan, dan variannya — yang digunakan untuk menyelesaikan MDP. Istilah-istilah ini sering digunakan secara bergantian dalam praktik.
Kapan saya harus menggunakan iterasi kebijakan daripada iterasi nilai?
Iterasi kebijakan cenderung konvergen dalam lebih sedikit iterasi daripada iterasi nilai untuk banyak masalah, tetapi setiap iterasi lebih mahal karena memerlukan penyelesaian sistem persamaan linier. Iterasi nilai lebih mudah diimplementasikan dan lebih disukai ketika ruang keadaan besar. Untuk masalah kecil hingga menengah, iterasi kebijakan seringkali lebih cepat secara keseluruhan.
Bisakah SDP menangani banyak tujuan yang bersaing?
Ya, melalui MDP terbatas (CMDP), di mana biaya sekunder kumulatif yang diharapkan harus tetap di bawah anggaran, atau melalui MDP multi-objektif yang menghasilkan himpunan kebijakan Pareto-optimal. Namun, formulasi tujuan tunggal standar mengasumsikan imbalan skalar; penskalaan banyak tujuan memerlukan pemilihan bobot yang cermat.
Metode terkait
Sumber
Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.
ISBN: 9780486428093Disalin.Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, New York.
ISBN: 9780471619772Disalin.