Markov Decision Process (MDP)

Bir Markov karar süreci (MDP), ardışık bir karar probleminin matematiksel modelidir: Bir ajan bir durumu gözlemler, bir eylem seçer, bir ödül alır ve kısmen seçimine, kısmen de şansa bağlı olan bir sonraki duruma geçer. Biçimsel olarak MDP; durumlar kümesinden, eylemler kümesinden, geçiş olasılıklarından P(s′ | s, a), bir ödül fonksiyonundan R(s, a) ve genellikle 0 ile 1 arasında bir iskonto faktörü γ'dan oluşur. Çözüm, her durumda bir eylem seçen kural olan ve gelecekteki ödüllerin beklenen iskontolu toplamını en üst düzeye çıkaran bir politika bulmaktır. MDP'ler, Richard Bellman'ın dinamik programlamasının bunları çözmek için yöntemler sağladığı 1950'lerde yöneylem araştırması alanında ortaya çıktı ve pekiştirmeli öğrenme (RL) için standart problem tanımıdır.

Markov Özelliği#

Tanımlayıcı varsayım Markov özelliğidir: Sonraki durum ve ödül, oraya götüren yola değil, yalnızca mevcut duruma ve eyleme bağlıdır. Bu sayede durum, ajan için önemli olan her şeyin eksiksiz bir özeti olur. Tek bir kamera karesi, hareketli bir nesne için bu varsayımı karşılamaz; çünkü konumu gösterir ama hızını göstermez. Bu nedenle DeepMind'ın Atari oynayan DQN'si, hareketi görebilmesi için ağa üst üste bindirilmiş son dört kareyi verdi.

Ajan, sensörleri gürültülü ya da engellenmiş bir robotta olduğu gibi tam durumu gözlemleyemediğinde problem kısmen gözlemlenebilir MDP (POMDP) olur. Ajan bu durumda doğrudan durum üzerinden değil, bir filtre ya da bir tekrarlayan ağ kullanarak sürdürdüğü durum inancı üzerinden eylemde bulunur.

Bir MDP'nin Bileşenleri#

• Durumlar: Ajanın içinde bulunabileceği durumlar; örneğin bir robotun eklem açıları ve uzanmaya çalıştığı nesnenin konumu.
• Eylemler: Her durumda kullanılabilen seçenekler. Eylem uzayı ayrık (sola dön, sağa dön) ya da sürekli (derece cinsinden direksiyon açısı) olabilir.
• Geçiş olasılıkları: Bir eylemden sonra gerçekleşebilecek her bir sonraki durumun olasılığı; tekerleklerin kaymasını, diğer sürücüleri ve rastgeleliğin diğer kaynaklarını kapsar.
• Ödüller: Bir geçiş için verilen anlık sayısal geri bildirim. Görev, tasarımcının ödül seçimine bağlıdır ve özensiz bir seçim ödülün istismar edilmesine yol açar.
• İskonto faktörü: Gelecekteki ödüllerin, anlık ödüllere kıyasla ne ölçüde dikkate alınacağını belirler. γ = 0.9 olduğunda, on adım sonraki bir ödül, aynı ödülün şimdi alınan değerinin 0.9¹⁰ ≈ 0.35'i kadardır.

Bölüm sona erene kadar her zaman adımında aynı etkileşim tekrarlanır:

Bir MDP'yi Çözme#

Bir durumun değeri, bir politika altında o durumdan elde edilmesi beklenen getiridir ve en iyi değerler Bellman denklemini sağlar: Her durumun değeri, en iyi eylemin anlık ödülüyle bu eylemin götürdüğü durumların olasılık ağırlıklı ve iskontolu değerinin toplamıdır. Geçiş olasılıkları ve ödüller biliniyorsa dinamik programlama bu denklemi doğrudan çözer. Değer yinelemesi (Bellman, 1957), değerler değişmeyi bırakana kadar denklemi tekrar uygular; politika yinelemesi (Howard, 1960) ise bir politikayı değerlendirme ve iyileştirme adımlarını sırayla tekrarlar.

Bu NumPy örneği, Sutton ve Barto'nun Reinforcement Learning: An Introduction kitabındaki geri dönüşüm robotu üzerinde değer yinelemesi çalıştırır. Robot, pili yüksek ya da düşükken kutu arama, bekleme ve şarj olma seçeneklerinden birini seçmelidir:

import numpy as np

# Geri dönüşüm robotu MDP'si: durumlar 0 = pil yüksek, 1 = pil düşük; eylemler 0 = ara, 1 = bekle, 2 = şarj ol
gamma = 0.9  # iskonto faktörü
P = np.zeros((2, 3, 2))  # P[s, a, s'] = s durumunda a eylemini gerçekleştirdikten sonra s' durumuna ulaşma olasılığı
P[0, 0] = [0.7, 0.3]  # pil yüksekken arama yapmak pili düşük seviyeye indirebilir
P[1, 0] = [0.4, 0.6]  # pil düşükken arama yapmak pilin tamamen bitmesine yol açabilir (robot kurtarılır ve şarj edilir)
P[:, 1] = np.eye(2)  # beklemek pil seviyesini değiştirmez
P[:, 2] = [1.0, 0.0]  # şarj olmak pili her zaman yüksek seviyeye getirir
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # beklenen R[s, a]; pil düşükken arama: 0.6 * 2 + 0.4 * -3 = 0

# Değer yinelemesi: Değerler değişmeyi bırakana kadar Bellman optimumluk güncellemesini uygula
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # her durumdaki her eylemin değeri
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

Sonuçta yüksek pil için 15.75, düşük pil için 14.17 değerleri ve yüksek pilde arama, düşük pilde şarj olma politikası yazdırılır: −3 kurtarma cezası riski %40 olduğundan, pil düşükken arama yapmak şarj olmaktan daha az değerlidir.

Geçiş olasılıkları bilinmediğinde pekiştirmeli öğrenme aynı değerleri deneyimlerden tahmin eder. Q-learning, eylem değerlerini örneklenmiş geçişlerden günceller; politika gradyanı yöntemleri politikayı doğrudan ayarlar; derin pekiştirmeli öğrenme ise sinir ağlarını durum uzayı listelenemeyecek kadar büyük olduğunda kullanır. Monte Carlo ağaç araması gibi planlama algoritmaları, yalnızca mevcut durumdan ulaşılabilen gelecekleri simüle ederek devasa MDP'leri çevrimiçi çözer.

MDP'ler ve İlişkili Modeller#

• Markov zinciri: Eylem ya da ödül içermeyen rastgele durumlardan oluşan bir dizi. MDP, seçenekleri ve hedefi ekler.
• Gizli Markov modeli (HMM): Durumları yalnızca gürültülü sinyaller aracılığıyla gözlemlenen bir Markov zinciri. POMDP, MDP ile benzer bir ilişki içindedir.
• Çok kollu haydut: Tek bir durumu olan ve her eylemin geçmişten bağımsız olarak getiri sağladığı MDP.
• Pekiştirmeli öğrenme: Geçiş olasılıkları verilmeden, etkileşim yoluyla bir MDP'de iyi eylemlerde bulunmayı öğrenen yöntemler ailesi.

Uygulamalar#

• Robotik ve kontrol: Kavrama, yürüme ve yön bulma MDP'ler olarak modellenir; bu görevlerin politikaları çoğunlukla simülasyonda eğitilir. Kameraya dayalı kontrolde, Ultralytics YOLO26 gibi bir algılayıcı durumu sağlayabilir ve her kareyi, ham piksellere kıyasla politika için çok daha küçük bir girdi olan nesne sınıflarının ve kutu koordinatlarının kısa bir listesine dönüştürebilir.
• Dil modeli eğitimi: RLHF ve RLVR, metin üretimini; durumun istem ve o ana kadarki belirteçlerden, eylemin sonraki belirteçten oluştuğu ve ödülün yanıt tamamlandığında verildiği bir MDP olarak ele alır.
• Yöneylem araştırması: Stok yenileme, ekipman bakımı ve dinamik fiyatlandırma klasik MDP'lerdir; Ronald Howard, Sears kataloglarının postayla gönderimini iyileştirirken politika yinelemesini geliştirdi.