Proses Keputusan Markov

Proses keputusan Markov memformalkan pengambilan keputusan sekuensial, memodelkan agen yang memilih tindakan dalam keadaan untuk memaksimalkan imbalan jangka panjang.

Definition

Proses keputusan Markov adalah model pengambilan keputusan sekuensial yang didefinisikan oleh serangkaian keadaan, tindakan yang tersedia, probabilitas transisi antar keadaan berdasarkan tindakan, dan imbalan, di mana tujuannya adalah untuk menemukan kebijakan yang memaksimalkan akumulasi imbalan terdiskonto yang diharapkan.

Scope

Topik ini mencakup kerangka kerja matematis yang mendasari pembelajaran penguatan: keadaan, tindakan, probabilitas transisi, imbalan, dan faktor diskon; kebijakan dan fungsi nilai; persamaan optimalitas Bellman; serta metode pemrograman dinamis iterasi nilai dan iterasi kebijakan yang memecahkan proses yang diketahui. Ini mengasumsikan properti Markov bahwa masa depan hanya bergantung pada keadaan saat ini.

Core questions

• Komponen apa saja yang mendefinisikan proses keputusan Markov?
• Bagaimana persamaan Bellman menghubungkan nilai suatu keadaan dengan penerusnya?
• Bagaimana iterasi nilai dan iterasi kebijakan menemukan kebijakan optimal?
• Apa yang diasumsikan oleh properti Markov tentang lingkungan?

Key theories

Persamaan optimalitas Bellman

Nilai bertindak secara optimal dari suatu keadaan sama dengan imbalan langsung terbaik ditambah nilai terdiskonto dari keadaan yang dihasilkan, sebuah hubungan rekursif yang solusinya mendefinisikan kebijakan optimal.

Pemrograman dinamis

Ketika proses sepenuhnya diketahui, iterasi nilai dan iterasi kebijakan menghitung fungsi nilai dan kebijakan optimal dengan berulang kali menerapkan pembaruan Bellman, menjamin konvergensi ke optimum.

Diskon dan pengembalian

Imbalan di masa depan diberi bobot oleh faktor diskon sehingga total pengembalian terdefinisi dengan baik dan imbalan yang lebih dekat lebih diperhitungkan, membentuk seberapa jauh ke depan agen secara efektif merencanakan.

Clinical relevance

Proses keputusan Markov adalah tulang punggung konseptual dari pembelajaran penguatan dan sebagian besar riset operasi serta kontrol, menyediakan bahasa keadaan, tindakan, dan nilai yang hampir semua algoritma pembelajaran aproksimasi ketika model tidak diketahui atau terlalu besar untuk diselesaikan secara tepat.

History

Kerangka kerja ini muncul dari pemrograman dinamis Bellman pada tahun 1950-an dan karya iterasi kebijakan Howard, menyediakan metode solusi yang tepat untuk proses keputusan yang diketahui. Pembelajaran penguatan kemudian mengadopsi proses keputusan Markov sebagai formalisme standarnya untuk kasus di mana transisi dan imbalan harus dipelajari dari pengalaman.

Key figures

• Richard Bellman
• Ronald Howard
• Richard Sutton

Seminal works

• sutton2018
• bellman1957
• puterman1994

Frequently asked questions

Apa itu properti Markov?

Properti Markov menyatakan bahwa evolusi proses di masa depan hanya bergantung pada keadaan dan tindakan saat ini, bukan pada riwayat lengkap bagaimana agen sampai di sana. Ini menjadikan keadaan saat ini ringkasan yang cukup untuk pengambilan keputusan.

Mengapa faktor diskon digunakan?

Diskon memberikan bobot lebih besar pada imbalan yang lebih dekat daripada yang jauh. Ini menjaga total pengembalian tetap terbatas selama horizon panjang atau tak terbatas dan mengkodekan preferensi untuk imbalan yang lebih cepat, sekaligus mengontrol seberapa jauh ke masa depan agen secara efektif merencanakan.