Ardışık Karar Verme (MDP'ler)
Ardışık karar verme, bir aracının stokastik bir ortamda zaman içinde nasıl hareket etmesi gerektiğini biçimlendiren bir yaklaşımdır. Bu yaklaşım, eylemlerin ödüller sağladığı ve durumu olasılıksal olarak değiştirdiği Markov karar süreçlerini kullanarak, uzun vadeli beklenen ödülü maksimize eden bir politika hesaplamayı hedefler.
Tanım
Bir Markov karar süreci, durumlar, eylemler, bir geçiş olasılığı fonksiyonu ve bir ödül fonksiyonu ile tanımlanmaktadır. Ardışık karar verme, model verildiğinde, beklenen kümülatif (genellikle iskontolu) ödülü maksimize eden, durumları eylemlere eşleyen bir politika aramaktadır.
Kapsam
Bu konu, zaman içinde karar teorik planlamayı kapsamaktadır: durumlar, eylemler, geçiş olasılıkları, ödüller ve iskonto etme (discounting) içeren Markov karar süreci (MDP) modelini; politikaları ve değer fonksiyonlarını; optimal davranışı karakterize eden Bellman denklemlerini; ve bilinen bir modeli çözmek için değer iterasyonu (value iteration) ve politika iterasyonu (policy iteration) dinamik programlama algoritmalarını. Ayrıca, kısmen gözlemlenebilir MDP'leri (POMDP'ler) ve inanç durumu (belief-state) planlamasını da tanıtmaktadır. Odak noktası, modelin verildiği durumlarda planlama yapmaktır; bilinen bir model olmaksızın deneyimden politika öğrenme ise makine öğrenimi alt alanına ait olan pekiştirmeli öğrenmedir.
Temel sorular
- Stokastik geçişler altında zaman içinde hareket etme, durumlar, eylemler, geçişler ve ödüller olarak nasıl modellenmektedir?
- Bellman optimallik denklemi, optimal bir politikanın değeri hakkında ne söylemektedir?
- Model bilindiğinde, değer iterasyonu ve politika iterasyonu optimal bir politikayı nasıl hesaplamaktadır?
- Kısmi gözlemlenebilirlik, POMDP'lere ve inanç durumları üzerinden planlamaya nasıl yol açmaktadır?
Anahtar kavramlar
- durumlar, eylemler, geçişler, ödüller
- politika
- değer fonksiyonu
- iskonto faktörü
- Bellman denklemleri
- değer iterasyonu
- politika iterasyonu
- POMDP ve inanç durumu
Temel kuramlar
- Bellman optimallik denklemi
- Bir durumun optimal değeri, en iyi anlık ödül artı bir sonraki durumun iskontolu beklenen optimal değerine eşittir; bu özyinelemeli ilişki, optimal ardışık davranışı karakterize eder ve dinamik programlama çözümlerinin temelini oluşturur.
- Değer ve politika iterasyonu
- Bilinen bir MDP için, değer iterasyonu yakınsayana kadar Bellman güncellemesini tekrar tekrar uygular ve politika iterasyonu politika değerlendirmesi ile iyileştirmeyi dönüşümlü olarak yapar; her ikisi de optimal bir politika bulmayı garanti etmektedir.
- Kısmen gözlemlenebilir MDP'ler
- Durum doğrudan gözlemlenemediğinde, planlama gözlemlerden güncellenen bir inanç durumu (durumlar üzerindeki bir dağılım) üzerinden yapılır; bu tür POMDP'leri çözmek, tamamen gözlemlenebilir duruma göre çok daha zordur ancak gerçekçi algılama sınırlamalarını yakalamaktadır.
Klinik önem
MDP ve POMDP tabanlı karar verme, robot navigasyonu ve kontrolünün, otomatik diyalog yönetiminin, bakım ve envanter kararlarının ve kaynak tahsisinin temelini oluşturmaktadır. Ayrıca, ortam modelinin öğrenilmesi gerektiğinde pekiştirmeli öğrenmenin üzerine inşa edildiği karar teorik planlama temelini de sağlamaktadır.
Tarihçe
Ardışık karar verme, Bellman'ın dinamik programlamasından (1957) ve Howard'ın politika iterasyonundan (1960) gelişmiştir. Puterman'ın 1994 tarihli monografisi, Markov karar süreçleri teorisini pekiştirmiş; Kaelbling, Littman ve Cassandra (1998) ise kısmen gözlemlenebilir MDP'leri, belirsiz algı altında hareket etme modeli olarak yapay zeka ana akımına taşımıştır.
Öne çıkan isimler
- Richard Bellman
- Ronald A. Howard
- Martin L. Puterman
- Leslie P. Kaelbling
- Michael L. Littman
İlgili konular
Temel eserler
- bellman1957
- puterman1994
- kaelbling1998
Sıkça sorulan sorular
- Bu, pekiştirmeli öğrenmeden nasıl farklıdır?
- MDP'lerle ardışık karar verme, geçiş ve ödül modelinin bilindiğini varsayar, bu nedenle optimal bir politika dinamik programlama ile doğrudan hesaplanabilir. Pekiştirmeli öğrenme ise modelin bilinmediği ve aracının deneyimden iyi bir politika öğrenmesi gereken durumu ele alır; MDP'yi temel biçimciliği olarak kullanır.
- Bir POMDP'de inanç durumu nedir?
- Kısmen gözlemlenebilir bir MDP'de aracı, gerçek durumu göremez, bu nedenle eylemler yaptıkça ve gözlemler aldıkça güncellenen, olası durumlar üzerindeki bir olasılık dağılımı olan bir inanç durumu sürdürür. Planlama daha sonra doğrudan gizli durumlar üzerinden değil, bu inanç durumları üzerinden gerçekleştirilir.