Dinamik Programlama ve Markov Karar Süreçleri

Sıralı Karar Verme, Dinamik Programlama, Bellman Denklemi ve Genel Fayda Fonksiyonlarını öğreniyoruz.

Basit Açıklama

Sıralı Karar Verme

Sıralı karar verme, bir karar vericinin zaman içinde bir dizi karar alması gereken bir süreçtir. Bu süreçte, her bir karar gelecekteki sonuçları etkiler ve belirli bir hedefe ulaşmak için en iyi stratejiyi bulmak hedeflenir. SDP, genellikle aşağıdaki unsurlardan oluşur:

• Durum (State): Sistemin mevcut durumunu tanımlayan bilgi. Örneğin, bir oyun tahtasındaki taşların konumu bir “durum” olabilir.
• Eylem (Action): Karar vericinin mevcut durumda yapabileceği seçeneklerdir.
• Geçiş Kuralları (Transition Rules): Bir eylemin, sistemi bir durumdan başka bir duruma nasıl taşıdığını belirler.
• Ödül (Reward): Her durum veya eylem için alınan ödül veya maliyettir.
• Politika (Policy): Her durumda hangi eylemin seçileceğini belirleyen bir stratejidir.

Örnek: Bir robotun bir labirentten çıkış yolunu bulması bir SDP problemidir. Robot, mevcut durumuna göre hareket (eylem) seçer, labirentte bir sonraki duruma geçer ve ödül (örneğin, doğru yola ilerleme) alır.

Dinamik Programlama

Dinamik programlama, karmaşık sorunları daha küçük, daha yönetilebilir alt sorunlara ayırarak çözme yöntemidir. Özellikle, bir problemdeki alt problemler tekrar tekrar çözülebiliyorsa, bu yöntemin verimliliği büyük ölçüde artar.

Dinamik programlama şu iki temel prensibe dayanır:

• Optimal Alt Yapı (Optimal Substructure): Sorunun çözümü, alt sorunların optimal çözümlerinden oluşur.
• Alt Problemlerin Tekrarı: Aynı alt problemler birçok kez ortaya çıkabilir ve bunların çözümü yeniden hesaplanmadan depolanarak kullanılabilir.

Kullanım Alanları:

• Fibonacci sayılarını hesaplamada,
• Kısa yol problemlerinde (örneğin, Dijkstra algoritması),
• Çizelgeleme problemlerinde kullanılabilir.

Bellman Denklemi

Bellman Denklemi, sıralı karar verme süreçlerinde optimal bir politika belirlemek için kullanılan bir denklemdir. Bu denklem, bir durumdaki maksimum beklenen ödülü (veya faydayı), o durumdaki mevcut ödülleri ve gelecekteki durumlara geçişten kaynaklanan beklenen ödülleri birleştirerek tanımlar.

Matematiksel Form:

V(s)=max​_a[R(s,a)+γ∑_{s′}​P(s′∣s,a)V(s′)]

Burada:

• V(s): Durum s’deki beklenen maksimum ödül.
• R(s,a): Durum s’de eylem a yapıldığında alınan ödül.
• P(s′∣s,a): Durum s’den s′’ye geçiş olasılığı.
• γ: Gelecekteki ödülleri bugünkü değerlere indirgemek için kullanılan indirim faktörü.

Kullanımı: Bu denklem, özellikle Markov Karar Süreçleri (MDP) gibi problemlerde optimal politikanın belirlenmesinde kullanılır.

Genel Fayda Fonksiyonları

Genel fayda fonksiyonları, bir karar vericinin belirli bir durum ya da eylem kombinasyonuna ne kadar değer verdiğini ölçmek için kullanılan matematiksel araçlardır. Fayda fonksiyonu, bir eylemin veya bir durumun “iyiliğini” ya da “etkililiğini” temsil eder ve karar verici bu fonksiyona göre en iyi kararı alır.

Temel Özellikler:

• Fayda Maksimizasyonu: Karar verici, faydayı maksimize etmeye çalışır.
• Subjektiflik: Fayda fonksiyonu, karar vericinin tercihlerini ve risk algısını yansıtabilir.
• Risk Hassasiyeti: Fayda fonksiyonları, riskten kaçınma veya risk alma gibi davranışları temsil etmek için şekillendirilebilir.

Örnek: Bir yatırım problemini düşünün. Fayda fonksiyonu, bir yatırımın getirisiyle birlikte riskini de göz önünde bulundurarak karar vericinin toplam tatminini hesaplayabilir.

Giriş

Bu yazının amacı, zamanla biriken bazı maliyet veya ödülleri etkileyen karar dizilerini içeren herhangi bir dinamik süreci ifade eden ardışık karar süreci (SDP: Sequential Decision Process) kavramını tanıtmaktır. İdeal olarak, maliyeti veya ödülü optimize eden kararlar belirlenebilir. Bu birimde, bu tür modellerin nasıl kesin olarak tanımlanabileceği, maliyetin (ödülün) nasıl hesaplanabileceği ve performansı optimize eden kararların nasıl belirlenebileceği ele alınacaktır. Kullanacağımız matematiksel yöntemler, büyük ölçüde Richard Bellman tarafından 1950'lerde formüle edilen dinamik programlama temellidir. İlginç bir şekilde, nispeten basit tek bir fikir, bu alana dikkat çekici bir birlik kazandırmakta ve operasyon araştırması, ekonomi, kontrol teorisi ve yapay zeka gibi alanlarda geniş bir uygulama yelpazesinin esasen aynı yapıyı paylaştığı görülmektedir. Yöntemin çeşitli versiyonları, 1940'larda bazı seçkin matematikçiler ve ekonomistler tarafından tanıtılmıştır.

Sıralı Karar Vermeye Giriş

Dinamik Programlamanın Uygulamaları

Dinamik programlama, SDP’ler olarak formüle edilebilen şaşırtıcı derecede geniş çeşitlilikte optimizasyon problemlerinin temelini oluşturur.

Operasyonların Araştırması

Bu alan, genellikle zaman içinde sıralı olan karmaşık süreçlerde karar alma sistemine bilgi vermek için matematiksel teorinin kullanımıyla ilgilenir. Genellikle nicel bir performans metriği tanımlanabilir (örneğin, toplam gelir veya başarı olasılığı gibi), böylece amaç bu metriğe göre performansı optimize eden bir karar kuralı belirlemek olur.

Operasyon araştırması, yönetim, mühendislik, ulaşım, askeri veya kurtarma operasyonlarındaki sorunları çözmek için yaygın olarak kullanılır. Yöntemleri, özellikle kaynak tahsisi, arama sorunları ve planlama için en uygun stratejileri belirlemek için uygundur. Özellikle öne çıkan örnekler arasında tedarik zinciri yönetimi, envanter sistemleri, kuyruk sistemleri, kamu hizmeti genişlemesi ve proje planlaması yer alır. Bu türdeki uygulamalar (örneğin, envanter kontrol sorunu) oldukça erken ortaya çıktı ve Richard Bellman tarafından dinamik programlama teorisinin resmi olarak geliştirilmesinden önce geldi.

Ekonomi

Dinamik programlama, çok çeşitli yönetim ve mühendislik uygulamalarının verimliliğini artırmadaki kullanımının yanı sıra, çeşitli türden ekonomi problemlerini çözmek için kullanılır. Yaygın bir uygulama, genellikle bir karar teorik çerçevesi içinde, optimum yatırım ve tasarruf stratejilerinin tasarımıdır. Dinamik programlama ayrıca insan karar alma modellerini geliştirmek için kullanılır (örneğin, emeklilik davranışının dinamik bir programlama modeli (Rust, 1989)’da önerilmiştir). Dinamik programlamanın kamu politikası değerlendirmesine uygulanmasına ilişkin bir inceleme sunar (örneğin, asgari ücretin genç işsizliği üzerindeki etkisini tahmin etmek için). Ekonomideki dinamik programlama uygulamaları genellikle nitel niteliktedir ve belirli karar kurallarından ziyade genel ilkelere yol açmayı amaçlar. Bu, özellikle dinamik programlamanın oyun teorisine uygulanması için geçerlidir.

Yapay Zeka

Dinamik programlama, birçok yapay zeka uygulamasında yaygın olarak kullanılmaktadır. Ayrıca, ödüllerin gözlemlenmesi ve değişken eylemler uygulanarak sonuçların etkilenmesi yoluyla, sıralı bir karar verme süreci için optimal kararların belirlenmesine odaklanan pekiştirmeli öğrenme olarak bilinen bir makine öğrenimi dalının matematiksel temelini sağlamaktadır. Bir bakıma, pekiştirmeli öğrenme dinamik programlamanın yaklaşık bir formu olarak kabul edilebilir. Pekiştirmeli öğrenmenin özellikle dikkat çeken erken bir uygulaması, rekabetçi seviyede tavla oynayabilen TD-Gammon olarak bilinen bir SDP’nin geliştirilmesidir. Daha yakın zamanda ise, DeepMind Technologies tarafından pekiştirmeli öğrenme kullanılarak AlphaZero adlı bir satranç oynama programı oluşturulmuştur (“DeepMind’ın AlphaZero’su dört saat içinde tüm insan satranç bilgisini öğrenip aştı”, The Telegraph, 6 Aralık 2017). Bu yöntem, özellikle derin sinir ağı modelleriyle (derin pekiştirmeli öğrenme) birleştirildiğinde, oyun oynama uygulamalarının geliştirilmesine son derece uygundur ve günümüzde örneğin oldukça etkili video oyun oynama uygulamaları oluşturmak için kullanılmaktadır. Daha genel olarak, dinamik programlama ve pekiştirmeli öğrenme sıralı karar verme içeren yapay zeka uygulamaları için kullanılabilir. Bu durum, onları otonom araçların navigasyon kontrolü için özellikle uygun hale getirmekte ve otomobiller (You et al., 2018) veya helikopterler (Xue et al., 2019) için bu tür uygulamaların geliştirilmesi şu anda gelişen bir araştırma alanı haline gelmiştir. Sağlık hizmetleri ise bu alandaki bir diğer öne çıkan uygulama alanıdır (Esteva et al., 2019) ve bilgisayar destekli tanı, özellikle dikkat çekici bir uygulama olarak öne çıkmaktadır (Kao et al., 2018).

Bu yazıda, ele alacağımız SDP modellerini tanımlayarak başlayacağız. Bu tanım, süreci yöneten dinamik kuralları, maliyetin birikme yöntemini, sürecin (eğer sona eriyorsa) sona erdiği kuralları ve karar verme sürecinin tam şeklini içerecektir. Ardından, ele alacağımız yöntemlerin çoğunun temelini oluşturan optimizasyon ilkesini formüle eden Bellman denklemini tanıtacağız. Bu denklem kullanıma sunulduktan sonra, optimal politikaları belirlemek için algoritmalar geliştirebiliriz. Bu algoritmalar, optimal maliyet veya ödül elde etmek için kullanılan karar kurallarını ifade eder. Daha sonra, maliyet veya ödülün nesnel ölçütleri yerine daha genel bir değer kavramını, özellikle risk veya servet birikimi konularında farklı tercihlere sahip karar vericiler için, ikame eden fayda teorisini ele alacağız. Bu, dinamik programlamanın ekonomi ve finans alanındaki uygulamaları açısından önem taşımaktadır. Ancak öncelikle klasik posta arabası problemi kullanılarak dinamik programlamanın temel kavramlarını tanıtacağız.

Dinamik Programlamaya Giriş: Posta Arabası (Stagecoach) Problemi

Posta arabasının yönlü bir grafik biçimindeki haritasını düşünelim. Kasabalar, A’dan K’ye kadar etiketlenmiş 11 düğümle temsil edilmiş olsun. Bir yolcu A’dan başlayarak K’ye gitmek istemektedir. Kasabalar arasındaki mevcut yollar oklar veya yönlendirilmiş kenarlarla temsil edilmiştir. Her kenar, yolun mesafesiyle etiketlenmiştir. Amaç, toplam mesafenin en az olduğu yolu bulmaktır.

Yolcunun bir seçim yapması gerekmektedir. A’dan K’ye yapılan bir yolculuk, K’ye ulaşmadan önce D, F, G ve I üzerinden geçebilir. Kolaylık olması açısından bu rotayı A-D-F-G-I-K olarak göstereceğiz. Neyse ki, haritada bu rotanın toplam mesafesini hesaplamak için yeterli bilgi bulunmaktadır. Örneğin, A-D kenarının mesafesini D{A − D} = 2 olarak yazın. A-D-F-G-I-K rotasının mesafesini hesaplamak için aşağıdaki mesafelere ihtiyacımız olacak:

Açıkçası, yolculuğun toplam mesafesini hesaplamak için, yolculuğu tanımlayan kenarları etiketleyen mesafeleri toplamamız yeterlidir:

D {A − D − F − G − I − K} = 2 + 4 + 6 + 4 + 3 = 19

Bu rotanın toplam mesafesi 19'dur. Ancak bu, konuyu pek de açıklığa kavuşturmaz, çünkü A-D-F-G-I-K mevcut tek rota değildir ve muhtemelen A’dan K’ye en az toplam mesafeye sahip rotayı bulmak istiyoruz. En iyi rotayı bulmak için en iyi strateji nedir?

Numaralandırmayı (Enumeration)Kullanarak Minimum Mesafeli Rotayı Bulma

Numaralandırma, bir kümenin elemanlarının sayısını değerlendirme sorununa veya bu elemanların okunabilir bir listesini oluşturma sorununa atıfta bulunabilir. Bir küme, benzersiz elemanlardan oluşan sırasız bir koleksiyondur. İkinci sorun yapıcı numaralandırma olarak adlandırılır. Bir numaralandırmadan bahsettiğimizde, yapıcı bir numaralandırmanın mevcut olduğunu varsayacağız. Numaralandırma stratejisi (aynı zamanda kaba kuvvet yaklaşımı olarak da bilinir) belirgin bir seçimdir. Tüm olası rotaları sayar ve listeler, her birinin toplam mesafesini hesaplarız. Ardından basitçe en kısa rotayı seçeriz. Gösterildiği gibi aşağıdaki şekilde yer alan harita, bu yaklaşımı basitleştirecek bir yapıya sahiptir. Dikkatli bir inceleme sonucunda düğümlerin doğal olarak {A}, {B}, {C}, {D}, {E}, {F}, {G}, {H}, {I}, {J}, {K} kümelerine bölündüğü görülebilir. Bu, A’dan K’ye giden herhangi bir rotanın kümeler arasında açıkça tanımlanmış aşamalar halinde bölünmesine olanak tanır.

Posta Arabası Problemi Haritası

Yukarıdaki şekilde, orijinal harita aşamalara bölünmüş şekilde gösterilmektedir (K düğümü aşama 6’nın tek üyesi olmaktadır). Bu, örneğin, rotanın 3. aşamasının, yolcunun E veya F’den G veya H’ye yolculuk ettiği kısmı içerdiği anlamına gelir (bu geçişlerden tam olarak biri yolculuğun bir parçası olmalıdır). A’dan K’ya bir rota, aşama 1’den aşama 5’e kadar olan bölümleri içerir. Bu, rotaları sıralamayı kolaylaştırır. Aşama 1’de n₁ = 3 seçeneğimiz vardır (A’dan B, C veya D’ye yolculuk yapılabilir). Aşama 2’de, aşama 1’de hangi seçim yapılmış olursa olsun E veya F’ye yolculuk edilebileceğine dikkat edin (bu, hayal edilebilecek tüm haritalar için geçerli olmasa da aşağıdaki şekilde gösterilen harita için doğrudur).

Posta arabası problemi. Şekil 2.1'deki harita k = 1, …, 6 Aşamalarına bölünmüş olarak gösterilmektedir.

Böylece 2. aşamada n2​=2 seçeneğimiz var. Bu şekilde devam ettiğimizde 3, 4 ve 5. aşamalarda mevcut seçeneklerin sayısı sırasıyla n3​=2, n4=1 ve n5​=1 olacaktır.

Artık kombinatorikte “çarpım kuralı” olarak bilinen bir ilkeye güvenebiliriz. Bir prosedürün K göreve ayrılabileceğini ve her bir i. görevin ni farklı şekilde gerçekleştirilebileceğini varsayalım, burada i=1,…,K olsun.

Çarpım kuralı, K görev dizisini gerçekleştirme yollarının sayısını listeleyen bir kombinatorik yöntemdir. Bu durumda, tüm prosedürü gerçekleştirmek için n1​×n2​×⋯×nK​ farklı yol olacaktır. Her göreve yönelik mevcut seçeneklerin setinin diğer görevler için yapılan tercihlere bağlı olabileceğini unutmayın. Ancak, bir görev için seçeneklerin sayısının her zaman aynı olması önemlidir.

Açıkça görüldüğü gibi, bu koşul at arabası problemi için geçerlidir. Dolayısıyla çarpım kuralına göre A’dan K’ye olan toplam rota sayısı:

N_rota ​= n1​×n2​×n3​×n4​×n5 ​= 3×2×2×2×1 = 24

Bu sayı aşırı büyük görünmemektedir ve yeterli sabırla bilgisayar veya hatta kalem-kağıt kullanarak listeleme yaklaşımı uygulanabilir. Daha sonra bir rotanın (örneğin, A-D-F-G-I-K) başka bir rotadan (örneğin, A-D-F-G-J-K) daha tercih edilir olup olmadığına karar vermek basit bir iştir. Sadece toplam mesafeleri hesaplar ve karşılaştırırız.

Açıkça, A-D-F-G-J-K tercih edilir. Ancak, aşama sayısı K ve/veya seçim sayısı n1 , …, nK birkaç büyüklük sırası kadar artırılırsa, sayma yaklaşımını uygulamak için gereken hesaplama süresi üssel olarak artacak ve sonunda uygulanamaz hale gelecektir. Tavla oyununda, iki oyuncunun her birinin 24 pozisyonlu bir tahtaya yerleştirilmiş 15 işaretçisi vardır. Durum alanını belirleyen benzersiz işaretçi yapılandırmalarının sayısı yaklaşık 1020'dir. Şimdi, kritik soru şudur: Sayma stratejisinin hesaplama karmaşıklığını iyileştirebilir miyiz?

Böl ve Yönet Algoritmaları

Bu noktada, bu hesaplamanın bariz görünen bir özelliğine dikkat çekeceğiz. Özellikle, toplam mesafeyi hesaplama problemi bağımsız alt problemlere ayrılabilir:

Her bir rota için daha doğrudan: [A’dan K’ye toplam mesafe] + [A’dan G’ye toplam mesafe] = [G’den K’ye toplam mesafe]. Başka bir deyişle, G’den K’ye olan mesafeyi hesaplamak için G’den önceki rota hakkında hiçbir şey bilmemize gerek yoktur. K’ye kalan minimum rotayı belirlemek için yalnızca G düğümünde olduğumuzu bilmemiz yeterlidir. Daha önce önerildiği gibi, rota mesafelerini hesaplama problemiyle ilgili olarak bu durum bariz görünüyor. Ancak, bu durum rota mesafelerini en aza indirme problemiyle ilgili çok önemli sonuçlar doğuruyor. Bu nedenle, A-D-F-G-I-K orijinal rotasında yapılacak basit bir değişikliğin toplam mesafeyi nasıl azaltabileceği açıktır; Bu da kaba kuvvet yöntemiyle daha iyisini yapabileceğimizi göstermektedir. Bu nedenle farklı bir yaklaşımı ele alıyoruz. Böl ve yönet algoritması, karmaşık bir problemi birden fazla, daha basit alt probleme böler. Bu genellikle bir özyineleme yöntemiyle gerçekleştirilir. Böl ve yönet yöntemi doğal olarak bu probleme uygulanır. Eğer rota segmentlerinin mesafesi birbirinden bağımsız olarak hesaplanabiliyorsa, bunlar birbirinden bağımsız olarak da minimize edilebilir. Bu noktada, bazı yeni gösterim kurallarını tanıtmamız ve yalnızca A’dan K’ye minimum mesafeli rotayı belirleme problemini değil, farklı kümelerden herhangi iki düğüm arasında minimum mesafeli rotayı belirleme problemlerinin tamamını ele almamız gerekecek.

Bu tür minimum mesafeleri göstermek için D∗ sembolünü kullanacağız; örneğin, D∗(B,I), B’den I’ye minimum mesafeyi ifade eder. Diyelim ki bir sonraki adımda, G’den geçen A’dan K’ye minimum mesafeli rotayı belirlemek istiyoruz. Optimizasyon teorisinde, böyle bir koşul genellikle bir “kısıtlama” olarak adlandırılır. Cevabı belirlemek için, A’dan G’ye ve G’den K’ye minimum mesafeli rotaları bağımsız olarak belirleyebiliriz. Gösterimimizi kısıtlamaları tanıtacak şekilde değiştirebiliriz; böylece D∗(A,K∣G), G’den geçen A’dan K’ye olan tüm rotaların minimum mesafesini ifade eder (normalde koşullu olasılık P(A∣B) için kullanılan gösterimi ödünç alarak). O zaman elimizde şu olur:

Elbette, 1. problemin amacı D*(A, K)’yi ve bu mesafeye sahip herhangi bir rotayı belirlemektir. Bu noktada, herhangi bir rotanın G veya H’den geçmesi gerektiğini not ediyoruz. Bu nedenle, şu kimliğe sahip olmalıyız:

Şimdi, D*(A, G), D*(G, K), D*(A, H) ve D*(H, K)’yi (ve ilişkili rotaları) belirlediğimizde D*(A, K)’yi belirleyebildiğimizden, böl ve yönet algoritmasına yaklaşan bir şeye sahibiz. Ancak bu, kaba kuvvet sayım yöntemini iyileştirir mi? Dört niceliğin her birini hesaplamak için sayılması gereken rota sayısını hesaplamak için ürün kuralı yöntemini kullanabiliriz:

Bu nedenle, sayılması gereken toplam rota sayısı 6 + 6 + 2 + 2 = 16'dır, denklemde hesaplanan A ve K arasındaki 24 rotadan daha azdır. Ayrıca, sayılan rotaların daha az düğüm içerdiğini ve bu nedenle toplam rota mesafelerini hesaplamak için daha az aritmetik işlem gerektiğini de not ediyoruz. Dolayısıyla, rota sayımlarının bu karşılaştırması, denklemdeki yönteminin avantajını olduğundan az gösteriyor.

Dinamik Programlama

Dinamik programlama, böl ve yönet algoritmasının bir örneğidir ve bu yapı, hesaplama süresinde önemli bir azalmaya izin verir. Hesaplama verimliliğinde daha fazla iyileştirme, çeşitli yaklaşım teknikleri kullanılarak elde edilebilir. Genel olarak, bu, yalnızca kaba kuvvet sayımı kullanılarak düşünülemeyen optimizasyon problemlerinin çözümünü mümkün kılar. Ancak, hangi verimlilikler ve yaklaşımlar tanıtılırsa tanıtılsın, büyük bir SDP sınıfı için en genel çözüm yöntemleri, daha sonra tanıtacağımız tek bir model türüne dayanır.

Dinamik Programlama Modelleri

SDP’ler genellikle stokastik modellerdir, yani bileşenlerinden en azından bazıları rastgele belirlenir. Bu başlıkta stokastik modellerin bazı temel fikirlerini tanıtacağız.

Rastgele Değişkenler ve Stokastik Modeller

Olasılıkları hesaplamak için, bir örneklem uzayı S ile başlarız. Bu, tüm olası sonuçların kümesidir. S’nin bir öğesi rastgele seçildiğinde rastgele bir deney gerçekleşir. E’nin S’nin bir alt kümesi olduğunu varsayalım (yani, E’nin tüm öğeleri de S’dedir). O zaman E bir olay olarak adlandırılır ve P(E), E’nin gerçekleşme olasılığıdır veya alternatif olarak, P(E), rastgele deneyin sonucunun E’de olma olasılığıdır. Her zaman 0 ≤ P(E) ≤ P(S) = 1 olmalıdır.
Rastgele değişken, rastgele bir deneyle ilişkili sayısal bir sonuç olan X ∈ ℝ’dir. Alt kümeler E ⊂ ℝ için A = {X ∈ E} biçimindeki ilişkili kümelerin olasılık kurallarına uyduğu varsayılır.

Rastgele değişken, SX ⊂ ℝ sonuçlarının örneklem uzayına sahip bir rastgele deney olarak da düşünülebilir, bu durumda X, SX’te bir değer olmalıdır. SX kümesi, X’in desteği olarak adlandırılır. SX ayrıksa, X ayrık bir rastgele değişkendir, genellikle tam sayı değişkenleridir. Ayrık bir küme sonludur veya a1, a2, …. dizinli bir dizi olarak temsil edilebilir.

SX sürekliyse, X sürekli bir rastgele değişkendir, örneğin gerçek sayılardır. Sürekli bir küme sonsuzdur ve a1, a2, …. dizinli bir dizi olarak temsil edilemez.

Bir rastgele değişken X’in dağılımı, P X ∈ E biçimindeki olasılıklar olarak ifade edilebilir. PX(E) = P(X ∈ E) kısaltmasını benimseyebiliriz. Eğer SX tam sayılardan oluşuyorsa, pi = P(X = i) kısaltmasını kullanırız.

Bu durumda, X’in dağılımı tüm i ∈ SX için pi değerlerinden oluşur.

Örnek: Yazı Tura

Diyelim ki bir parayı üç kez havaya atıyoruz. Tüm olası sonuçların eşit olasılıklara sahip olduğunu varsayalım. Sonuçlar HHH HHT HTH HTT THH THT TTH TTT’dir.

X’in kafa sayısı olduğunu varsayalım. O zaman SX = {0, 1, 2, 3}. O zaman X’in dağılımı şöyledir:

p0 = P(X = 0) = P(TTT)= 1/8

p1 = P(X = 1) = P(TTH, THT, HTT) = 3/8

p2 = P(X = 2) = P(HHT, HTH, THH) = 3/8

p3 = P(X = 3) = P(HHH) = 1/8

Beklendiği gibi p0 + p1 + p2 + p3 = 1 olduğuna dikkat edin.

B verildiğinde bir A olayının koşullu olasılığı, B’nin de gerçekleştiğini bildiğimizde A’nın gerçekleşme olasılığıdır. B verildiğinde A’nın koşullu olasılığı P(A|B) = P(A∩B) / P(B) olarak tanımlanır.

P(B)> 0 sağlandığı takdirde. Önceki örnek göz önüne alındığında, şunlara sahibiz:

P(X = 3 | {Xisodd}) = P({X=3}and{Xisodd}) / P({Xisodd})=

P({X=3}) / P ({Xisodd})

= 1/8 / (3/8 + 1/8)

= 1/4

Dinamik Programlama Modelinin Bileşenleri

Bir SDP’yi zaman endeksli aşamaların bir dizisi olarak düşünebiliriz. Her aşama bir maliyet veya ödülle ilişkilendirilir. Ek olarak, her aşama içinde bir karar veya eylem alınmalıdır. Bunlar SDP’nin gelecekteki davranışını ve maliyetini etkiler. Sürecin kendisi, bir durum alanı X’e ait durumlar arasındaki geçişlerden oluşur. Bir SPD, her aşamada tek bir durum varsayar. Durum alanı X, tüm olası durumların kümesidir. SDP yeni bir duruma geçtikten sonra, bir eylem alanı A’dan seçilen bir eylem biçiminde bir karar verilir.

Dinamik programlama modelinin bileşenleri aşağıdaki gibidir:

1. Bir SDP, ayrı zaman noktalarında veya dönemlerde, j = 1, 2, …, tanımlanan dinamik bir süreçtir. Her dönem j ile bir aşama ilişkilendirilir. Her aşamada j, bir durum xj ve eylem aj içerir. Daha sonra bir durum eylem çifti (xj, aj) ifade ederiz. Kavramsal olarak, bir aşama içerisinde, önce durum xj gözlenir. Daha sonra, durum bilgisiyle, iyi tanımlanmış bir olasılık kümesinden seçilen bir eylem aj biçiminde bir karar verilir. Ancak, bu tanımı iyileştirmek ve tüm eylemlerin a ∈ A’nın herhangi bir verilen durum x’ten elde edilemeyebileceğini belirtmek olağan bir uygulamadır. Daha sonra Ax’in durum x’ten elde edilebilen tüm eylemler olduğunu varsayalım. Bu durumda, eylem a’nın durum x’ten izinli olması durumunda (x, a), kabul edilebilir bir durum-eylem çiftidir. Tüm kabul edilebilir durum-eylem çiftlerinin kümesi durum-eylem uzayıdır. K = {(x, a) : x ∈ X, a ∈ Ax}.
2. Eylem aj, durum xj’den seçildiğinde, her kabul edilebilir durum-eylem çifti (x, a) ∈ K için tanımlanan maliyet (ödül) fonksiyonu olan R(xj, aj) maliyet (veya ödül) tanımlanır.
3. SDP’nin xj durumundan xj+1 durumuna nasıl hareket ettiğini belirleyen bir geçiş kuralı vardır. Bu kural, geçerli durum-eylem çiftine (xj, aj) bağlıdır. Rastgele durum geçişlerine stokastik geçişler denir; bu, sonraki durum xk + 1'in geçerli durum-eylem çiftine (xk, ak) bağlı bir olasılık dağılımının sonucu olarak belirlendiği anlamına gelir. Stokastik geçişler, her olası durum-eylem çifti x, a için tanımlanan bir olasılık çekirdeği P(y ∣ x, a) tarafından yönetilir. Geçerli durum-eylem çifti (xj, aj) verildiğinde, sonraki durum xj + 1'in y’ye eşit olma olasılığı P(y ∣ xj, aj)’dir. Geçişler büyük olasılıkla deterministiktir; yani xj, aj bilindiğinde, sonraki durum xj+1 için yalnızca bir olası değer vardır. Bu durumda, olasılık çekirdeği P(y∣xj, aj) bir geçiş fonksiyonu q(x, a) ile değiştirilebilir, bu da geçiş kuralını xj + 1 = q(xj, aj) verir. Deterministik bir geçiş kuralı, her kabul edilebilir x, a ∈ K için bir q x, a ∈ X eşlemesiyle temsil edilebilir. Elbette, bu, olasılık çekirdeği tarafından şu şekilde ayarlanarak da modellenebilir:

Bu, P{xj+1 = q(xj, aj)} = 1 anlamına gelir ve bu da deterministik bir geçiş kuralını tanımlar.

SDP modelinin bileşenleri, sürecin nasıl davranacağını yöneten kuralları tanımlar. Bir SDP’nin bileşenleri topluca bir model olarak adlandırılır. Özellikle, bu durum uzayı X, eylem uzayı A, durum eylem uzayı K, maliyet fonksiyonu R(x, a) ve geçiş fonksiyonu q(x, a) (deterministik geçişler için) veya olasılık çekirdeği P(y ∣ x, a) (stokastik geçişler için) içerir. En azından ilk başta, modelin karar verici tarafından tamamen bilindiğini varsayacağız (aslında, pekiştirmeli öğrenme kısmen bunun böyle olmama olasılığından motive olur). Ancak, henüz bir karar problemi formüle etmedik ve bunu yapmanın birden fazla yolu olacak.

Dinamik Programlama Modeli Kullanarak Posta Arabası Probleminin Formüle Edilmesi

Pratikte, dinamik programlama ile ilişkili analiz türü matematiksel netliği ödüllendirir (ve ayrıca bunun eksikliğini cezalandırır). Bu nedenle, SDP’yi oluşturan tüm nesnelerin X, A ve K ile başlayarak dikkatlice tanımlandığından emin olmak önemlidir. Posta arabası problemi için şunlara sahibiz:

Unutmayın ki durum uzayı X, K’yı içermez. Bu gerekli değildir, çünkü terminal düğüm olduğundan, K’dan hiçbir karar verilmez. Benzer şekilde, A başlangıç düğümü olduğundan ve hiçbir eylemi tanımlamadığından, A da A’da yer almaz.

Ancak, dinamik programlama konusunda daha deneyimli hale geldikçe, belli bir esneklik gerekli hale gelir. Belki de daha büyük bir sürecin içine gömülebilecek bir ardışık karar süreci tanımlamaktayız ve bu nedenle ileriye dönük olarak K’yı durum uzayına dahil etmek isteyebiliriz. Sorun şu ki, AK kümesi boş olacaktır ve bu da sorun yaratma potansiyeline sahiptir (dinamik programlama teorisinde AK’nın boş olmaması yaygın bir düzenlilik varsayımıdır). Kolay bir çözüm, bir ‘sahte eylem’ Δ tanımlamaktır. Bu eylemi süreci durdurma işlevini yerine getirmek üzere bile atayabiliriz. Daha sonra AK={Δ} olarak belirleriz, böylece K durumundan erişilebilir tek eylem Δ olur. Maliyet fonksiyonunu R(K, Δ) = 0 olacak şekilde genişletirsek, karar sürecini gelecekteki değişiklikleri kolaylaştırmaktan başka önemli bir şekilde değiştirmemiş oluruz (bu fikri aşağıda daha kesin bir şekilde tanımlıyoruz).

Aksi takdirde, durum-eylem uzayı K’nın, ‘Posta arabası problemi haritası’ başlıklı şekildeki harita ile birebir örtüştüğünü görebiliriz, çünkü bir durumdan bir eylem, yolculuğa devam edilecek kenarın seçiminden başka bir şey değildir.
Benzer şekilde, maliyet fonksiyonu R(x, a), x − a kenarı ile ilişkili mesafeden başka bir şey değildir. Örneğin, ‘Posta Arabası problemi haritası’ başlıklı şekilde şunu görmekteyiz:

Son olarak, ortam tanımını tamamlamak için, eylem aj xj durumundan alınırsa, geçiş kuralı xj + 1 = q(xj, aj) = aj atamasıyla tam olarak tanımlanır. O zaman şuna sahip oluruz:

Hafızasız SDP’ler

Bu noktada, kritik bir kavramı tanıtacağız. Karar süreci hafızalı veya hafızasız olabilir. Sezgisel olarak, bu, optimum bir karar almak için sürecin yalnızca mevcut durumunu bilmemiz gerektiği ve geçmişini bilmememiz gerektiği anlamına gelir. Elbette bunun, daha sonra vereceğimiz resmi bir matematiksel tanımı bulunmaktadır.

Bir SDP, bellekten yoksundur; yani, aşağıdaki kurallar geçerliyse, tüm sonraki davranış ve maliyetler yalnızca mevcut durum-eylem çiftine bağlıdır:

• Durum xj’den xj+1'e geçiş kuralı yalnızca mevcut aşama verilerine (xj, aj) bağlıdır.
• Süreç tarafından durum xj’den itibaren biriken toplam kalan maliyet yalnızca mevcut aşama verilerine (xj, aj) bağlıdır.

Geçiş fonksiyonu q(x, a) veya olasılık çekirdeği P(y ∣ x), a ile tanımlanan geçiş kuralları bellekten yoksundur; ancak, maliyet birikiminin ve karar kurallarının da bellekten yoksun olduğundan emin olmamız gerekir

SDP Lifetime

Bir SDP’nin (Dinamik Programlama Problemi) ömrü tam olarak tanımlanmalıdır. Bir SDP, aşama sayısının önceden belirlenmiş ve sonlu bir K<∞ değerine sahip olduğu durumlarda sonlu bir ufka sahiptir. Buna karşılık, bir SDP’nin ufku sonsuzdur eğer aşama sayısı sonsuzsa, yani süreç süresiz olarak devam ediyorsa. Son olarak, en kısa yol SDP’si için aşama sayısı sonludur ancak değişken olabilir. Bir SDP, xΔ∈X şeklinde bir terminal durum olarak adlandırılan bir duruma sahip olabilir. Süreç bu duruma ulaşıldığında sona erer. “Süreç sona erer” dediğimizde, bu genellikle sürecin xΔ durumundan hiç ayrılmadığını ve artık herhangi bir maliyet oluşmadığını ifade edebilir. Bu şekilde, sonsuz ufuklu bir süreç terminal bir durumda “sona erebilir”. Bir en kısa yol SDP’si mutlaka bir terminal duruma sahip olmalıdır.

Bu sınıflandırma sisteminde biraz esneklik vardır, çünkü bir sınıfa ait bir problemi başka bir sınıfa ait bir problem olarak yeniden formüle etmek genellikle mümkündür. Örneğin, sonlu ufuklu bir problemi her zaman bir en kısa yol problemi olarak formüle etmek mümkündür. Menzil arabası (stagecoach) problemi doğal olarak sonlu ufuklu bir problem olarak ifade edilir, ancak terminal durumu xΔ=K olarak tanımlayarak bir en kısa yol problemi olarak formüle edilebilir. Sezgisel olarak, sonlu ufuklu bir SDP ile en kısa yol SDP’si arasındaki belirgin fark, sürecin aşama sayısının sabit veya değişken olup olmadığıdır. Bununla birlikte, diğer önemli bir fark, aşamanın tam olarak oynadığı rolle ilgilidir. Tüm SDP’lerde aşama, bir xj durumunun işgal edildiği, bir aj​ eyleminin yapıldığı ve bir R(xj,aj) maliyetinin oluştuğu ayrık bir dönemi tanımlar. Ancak, menzil arabası probleminde aşama, SDP’ye daha fazla yapı kazandırır. Hem durumlar hem de eylemler aşama tarafından bölünmüştür; bu, her bir durum ve her bir eylemin yalnızca bir aşamada gözlemlenebileceği anlamına gelir (örneğin, x3=E durumu yalnızca j=3 aşamasında meydana gelebilir). Bir SDP’nin hafızasız olabileceği, ancak çeşitli bileşenlerin aşamaya göre değişebileceği olasılığını göz önünde bulundurmalıyız.

Zaman Homojenliği

Bir modelin bir bileşeninin aşamalara göre değiştiği bir SDP, zamanla değişen (zaman homojen olmayan) bir SDP olarak adlandırılır; aksi takdirde, zaman homojen bir SDP süreci olarak kabul edilir. Bu, zaman homojen olmayan bir SDP için, maliyet fonksiyonunun veya geçiş kuralının aşamalar ilerledikçe sabit kalmadığı, buna karşın zaman homojen SDP’lerde sabit kaldığı anlamına gelir. Sınırlı ufuklu bir süreç genellikle zaman homojen olmayan bir süreçtir, oysa en kısa yol süreci genellikle zaman homojen bir süreçtir. Bu nedenle, sınırlı ufuklu bir problemin durum uzayı aşamaya göre doğal olarak ayrılmadığında, bir durumun tanımını genişleterek bir aşama indeksini içermesi gerekebilir. Örneğin, bir envanter kontrol modelinde bir aşamayı bir gün olarak tanımladığımızı varsayalım. Aşama j’de, durum xj günün başındaki stok miktarı, eylem aj ise mevcut stok xj​’yi dikkate aldıktan sonra o gün yeniden sipariş edilen stok miktarı olabilir. Daha sonra durumu xj=(wj,j) olarak genişletebiliriz, burada wj artık j gününün başlangıcındaki stok miktarını, gün indeksi j ise artık durumun bir parçası olarak içerir. Dinamik programlama modelleri tasarlarken akılda tutulması gereken bir şey, bir SDP’yi formüle etmenin genellikle birden fazla yolu olduğudur.

SDP Maliyet Hesaplama Yöntemi

SDP, aşama maliyetlerini veya ödüllerini tek bir değere nasıl konsolide edeceğini tanımlayan bir maliyet biriktirme yöntemi içerir. Bir SDP’nin başlangıç durumu x1 olsun ve ufku veya sonlanma koşuluna göre devam etsin. Bu süreç, yinelemeli olarak tanımlanabilen toplam bir maliyet biriktirir. Diyelim ki, x1 durumunda a1 eylemi seçiliyor. Modelin maliyet fonksiyonuna göre anlık aşama maliyeti R(x1, a1) olur ve süreç, modelin geçiş kuralına göre x2 durumuna geçer. Sürecin, şu anki başlangıç durumu olan x2'den yeniden başladığını hayal edebiliriz. Bu SDP’nin toplam birikmiş maliyetinin R2 olduğunu varsayalım. O zaman, başlangıç durumu x1 olan orijinal SDP’nin toplam birikmiş maliyeti R1 = H(R(x1, a1), R2) olarak ifade edilir; burada H(a, b) fonksiyonu birikim yöntemini tanımlar. Bu tür bir maliyet birikiminin, SDP’ler için bellekten bağımsızlık (memoryless) özelliğini sağladığını belirtmek önemlidir. H(a, b) fonksiyonu, çeşitli biçimler alabilen bir maliyet biriktirme yöntemini tanımlar.

Toplam Maliyet Hesaplama Yöntemi

Sonlu ufuk veya en kısa yol SDP, toplam maliyet/ödül problemidir. Bu durumda, toplam tahakkuk eden maliyet/ödül, aşama maliyetleri/ödüllerinin toplamıdır:

Burada K aşamalı sonlu ufuk problemi için N = K’dir. Bu, H a, b = a + b ile tanımlanan hesaplama yöntemine karşılık gelir.

İndirimli Maliyet Hesaplama Yöntemi

Sonsuz ufuk ömrünü dikkate almanın motivasyonu, süresiz çalışması beklenen SPD’leri modellemektir. Örneğin, bir oyun genellikle doğal bir son duruma sahipken, bir envanter kontrol sisteminin genellikle süresiz devam etmesi beklenebilir, böylece toplam hesaplanan maliyet sonsuz bir toplam olacaktır. Bu, maliyetin yeterince hızlı bir oranda sıfıra yakınsamasını beklemediğimiz sürece, toplam hesaplanan maliyetin sonsuz olacağı ve optimizasyon probleminin iyi tanımlanmayacağı anlamına gelir (açıkçası, bu makul bir kısıtlama olmayacaktır). Yaygın olarak kullanılan bir çözüm, indirim uygulamaktır. Bir SDP, toplam hesaplanan maliyet şuysa indirim faktörü β ∈ [0, 1] olan bir indirim yapılmış maliyet/ödül problemidir:

sonlu bir ufuk veya en kısa yol problemi için veya

sonsuz ufuk problemi için. Bu, H(a, b) = a + βb ile tanımlanan hesaplama yöntemine karşılık gelir. Daha önce olduğu gibi, toplam hesaplanan maliyet/ödül, aşama maliyetleri/ödüllerinin toplamıdır, ancak, her terim artık gelecekteki maliyetlerin/ödüllerin indirim yapıldığı oranı belirleyen bir indirim faktörü β ≤ 1 ile değiştirilmiştir.

İndirimin nasıl çalıştığını görmek için, tüm aşama maliyetlerinin negatif olmadığını ve üstten sonlu bir sabit M ≥ R(x, a) ≥ 0 ile sınırlandırıldığını varsayalım. β < 1 olsun.

O zaman herhangi bir a1, a2, … eylem dizisi için geometrik seriden yararlanarak şuna sahip olacağız:

Bu nedenle, β < 1 olduğu sürece, toplam indirim yapılmış maliyet sonlu olacaktır.

Toplam ve indirimli maliyet hesaplama yöntemlerine katkısal (özellikle H(a, b), a ve b’nin doğrusal bir kombinasyonudur) olarak atıfta bulunabiliriz. Stokastik SDP’leri ele alırken bu özelliğin önemli olduğunu göreceğiz. Ancak, maliyet hesaplama yöntemlerinin katkısal olması gerekmez, bunu daha sonra göreceğiz.

Minimax Maliyet Hesabı

Bir minimax maliyet problemi için toplam hesaplanan maliyet, tüm aşamalar üzerindeki maksimum aşama maliyetidir.

Bir SDP, hesaplanan maliyet şuysa bir minimax maliyet problemidir:

sonlu bir ufuk veya en kısa yol problemi için veya

Sonsuz ufuk problemi için. Bu, H(a, b) = max{a, b} tarafından tanımlanan hesaplama yöntemine karşılık gelir.

Maksimin (Maximin) Ödül Kazancı

Maksimin, minimumların maksimumuna denir. Maksimin ödül problemi için toplam hesaplanan ödül, tüm aşamalar üzerindeki minimum aşama ödülüdür.

Sonlu ufuk veya en kısa yol SDP, hesaplanan ödül şu ise bir maksimizasyon ödülü problemidir:

Sonlu ufuk veya en kısa yol problemi için veya sonsuz ufuk problemi için:

Bu, H(a, b) = min{a, b} ile tanımlanan hesaplama yöntemine karşılık gelir. Minimax ve maksimin kriterlerinin doğal bir performans hedefi tanımlayacağı iki uygulama sunuyoruz.

Rota Sapmasının Kontrolü: Minimax Kriteri

Bir aracın navigasyonunu kontrol etmek için dinamik programlamanın kullanılacağını varsayalım. Böyle bir sistem muhtemelen bir dizi göreve bölünebilir. Bu görevlerden biri, aracın iki nokta arasında düz bir çizgide hareket etmesi olabilir. Düzenli karar verme anlarında, planlanan yörüngeden sapma sensörler tarafından ölçülecek ve bir rota düzeltmesi uygulanacaktır.

Aşama k’deki sapmanın ϵk ile verildiğini ve rota sapmasının hiçbir zaman bir güvenlik eşiği τS’yi aşmaması gerektiğini varsayalım. Böyle sistemlerde, tolerans sınırını aşan herhangi bir tek sapmanın |ϵk| > τS bir sistem arızasına (örneğin, bir otoyoldan çıkma ya da bir duvara çarpma) yol açacağı senaryolarla kaçınılmaz olarak karşılaşırız. Bu nedenle, her rota düzeltmesini yönetecek bir karar kuralı oluşturmak gereklidir. Bu karar kuralının performans hedefi, toplamda bir anlamda rota sapmasını en aza indirmek olacaktır.

ϵk’nin işaretinin sapmanın sol/sağ yönünü belirttiğini varsayabiliriz. Aşama maliyeti, bu durumda, mutlak sapma ϵk olarak alınabilir. Toplam eklenebilir maliyet şu şekilde yazılabilir:

N yörüngenin sonunu tanımlar. Bu uygun bir optimizasyon hedefi midir? Performans kriteri olarak Rtot kullanmanın sorunu, optimizasyonunun her bir sapmanın belirli bir sınır içinde olacağını garanti etmemesidir. Rtot’u en aza indirme açısından, en iyi stratejinin, daha sonraki aşamalarda daha küçük bir toplam mutlak sapma elde etmek için yörüngenin başlangıcında az sayıda büyük rota sapmasını kabul etmek olduğu olasılığını göz ardı edemeyiz.

Elbette, bu bir sistem arızasına yol açacaktır. Açıkça, daha uygun bir hesaplama yöntemi, aşağıdakileri en aza indirmeye çalışan minimax yöntemidir:

Yörünge üzerindeki herhangi bir noktada Rmax τk’ya ulaşan bir karar kuralı.

Minimum Yakıt Gereksinimlerini Koruma: Maksimin Kriteri

Şimdi maksimin ödül kriterinin uygun olacağı bir SDP örneğini verelim.

Bir ulaşım ağı dağıtım sistemi için dinamik bir programlama modelinin bir aracın mevcut konumunu ve bir sonraki varış noktasına ilişkin bir kararı aşama olarak tanımladığını varsayalım. Aşama k’daki işlem durumu, mevcut araç konumu xk’den ve araçta şu anda bulunan yakıt miktarı fk’den oluşur. Ardından, bir karar ak = (xk + 1, gk) çifti olarak tanımlanır; burada xk + 1 bir sonraki varış noktası ve gk araca eklenecek yakıt miktarıdır. Ardından, dk’nın xk ile xk+1 arasındaki mesafe olmasına izin verin. Görev için kilometre başına toplam kullanılabilir yakıt şu şekildedir:

Açıkça, temel amaç aracın görev için yeterli yakıt içermesini sağlamaktır ve herhangi bir karar kuralı bu kısıtlamayı karşılamalıdır. Fikirleri düzeltmek için, kilometre başına minimum yakıt gereksinimini belirten bir güvenlik eşiği, diyelim ki τF olduğunu varsayacağız, böylece rk ≥ τF’ye sahip olmalıyız. Her aşama için k. Uygun bir performans kriteri, aşama maliyeti olarak rka alınarak ve ardından maksimin ödül tahakkuk yöntemi kullanılarak tanımlanabilir. Optimizasyon problemi daha sonra minimum ödülü maksimize etmek olacaktır:

Bu, her görev için asgari yakıt gereksinimlerinin karşılanmasını sağlayacaktır. SPD’nin sonsuz bir ufka sahip olabileceğini ve Rmin’in sınırlı kalmasını sağlamak için indirime güvenmesi gerektiğini unutmayın.

Politikalar ve Eylemler

Bir SDP, her aşamada eylem seçme yöntemi olan bir politika tarafından kontrol edilir. Bir politikanın amacı genellikle toplam hesaplanan maliyeti veya ödülü optimize etmektir. Bunu başarmak için, bir politika genellikle en azından mevcut duruma bağlı olmalıdır. Bu nedenle, eylem seçimini bilgilendirmek için tam olarak hangi bilgilerin mevcut olabileceğini tanımlamak önemlidir.

Karar Teorisi ve Bilgi

Karar vermek için bilgi X’in mevcut olduğunu ve optimal karar kuralının, belirli bir maliyeti minimize etme anlamında δX(X) olduğunu varsayalım. Daha sonra, yeni bir bilgi Y’nin mevcut olduğunu ve (X, Y) birleşik bilgisine dayanarak en iyi karar kuralının δXY(X, Y) olduğunu varsayalım. Bu durumda, δXY, δX’ten en az onun kadar iyi bir karar kuralıdır, çünkü her zaman δXY(X, Y) = δX(X) olarak (yani yeni bilgi Y’yi görmezden gelerek) ayarlayabiliriz.

Tersine, bilgi (X, Y)’ye dayalı optimal bir karar kuralı olan δXY(X, Y) verildiğini varsayalım. Matematiksel ya da ampirik bir araştırma yoluyla, X’e dayalı optimal karar kuralı δX(X)’in, aslında δXY’ye eşit olduğunu keşfederiz. Bu durumda, karar kuralı δX(X) tercih edilir, özellikle hesaplama verimliliği açısından.

Bilgi ve karar kuralları arasındaki ilişki bir denge sunar. Ek bilgi, optimal bir karar kuralını asla kötüleştiremez, ancak onu hesaplamak için kullanılan herhangi bir algoritmanın hesaplama karmaşıklığını artırabilir. Dinamik programlamada bu konu belirleyici olabilir. Göreceğimiz gibi, herhangi bir SDP’nin tasarımında kritik bir adım, karar vermek için mevcut olan bilginin tanımlanması ve bu bilginin ne kadarının kullanılacağının belirlenmesidir.

Bir SDP için geçmiş, işlem geçmişi, bir eylemin seçilmesinden hemen önceki bir zaman noktasında mevcut olan tüm aşama verilerinin kaydıdır.
Bir SDP’de, bir Aşama j kararı aj, xj durumu gözlemlendikten sonra yapılır. Ayrıca (ideal olarak) o aşamaya kadar olan geçmiş bilinir, bu da tüm önceki aşamalar için tüm durum-eylem çiftleri xi, ai’den oluşur i = 1, …, j − 1, bunları şu şekilde gösteririz: Hj = (x1, a2, …, xj − 1, aj − 1).

Örneğin, posta arabası probleminde, j = 3 aşamasında olduğumuzu varsayalım. Yolcu E düğümündeyse, durum x3 = E olur. Bu aşamada alınacak karar, bir sonraki şehrin kararıdır yani G veya H. Matematiksel olarak, bunu a3 ∈ {G, H} olarak gösteririz. Ardından, işlem geçmişi iki durum-eylem çiftinden (x1, a1), (x2, a2) oluşur. Şimdiye kadar izlenen rota A — C — E — H ise, j = 3 aşamasındaki geçerli durum-eylem çifti ve geçmişi şöyledir:

Bir karar kuralının en genel biçimi hem mevcut durumu hem de geçmişi kullanacaktır ve bu nedenle şu biçimi alacaktır:

Aşama j için. Bu noktada, karar kuralı (Hj, xj) bilgisini kullanır. Bunlardan ne kadarına ihtiyacımız var? Genellikle, mevcut durum xj hakkında bilgi sahibi olmadan optimal bir kararın alınamamasını bekleriz. Ama Hj’ye ihtiyacımız var mıdır? SDP hafızasızsa, gelecekteki davranışı tahmin etmek için kullanılabilecek tüm bilgiler yalnızca xj’de bulunur. Bu nedenle, optimal bir karar yalnızca xj’ye bağlı olabilir ve aşama j için her duruma tek bir eylem atayarak bir karar kuralı tanımlayan bir politika fonksiyonu ϕj(x)’in daha basit biçimini alabilir: aj = ϕj(xj).

Politika fonksiyonunun j aşamasına bağlı olmasına izin verdiğimizi unutmayın. Bu noktadan sonraki tercihimiz bu bağımlılığı kaldırmak olacaktır. Gerekirse, aşamanın tanımlanması duruma dahil edilebilir. Bu durumda, aşamaya bağlı olmayan ve bu nedenle ϕj(x) = ϕ(x) olarak yazılabilen durağan bir politika fonksiyonundan yararlanabiliriz, yani j alt dizinini kaldırabiliriz. Burada, karar kuralları tüm aşamalar için aynıdır. Bu karar kuralı formunun belleksiz özelliğini sağladığını belirtmek önemlidir.

Değer Fonksiyonları

Bir modelimiz ve maliyet tahakkuk yöntemimiz olduğunda, bir politikaya bir maliyet atayabilir ve bu temelde sabit politikaları ele alırken ϕ* olarak gösterdiğimiz en uygun politikayı seçebiliriz. Fikirleri sabitlemek için, politika değer fonksiyonu Vϕ(x)’i, herhangi bir yöntem altında, başlangıç ​​durumu x’ten politika ϕ altında tahakkuk eden toplam maliyet/ödül olarak tanımladığımızı varsayalım. O zaman en uygun politika ϕ*(x), en uygun toplam tahakkuk eden maliyet/ödülü elde eder. Başka bir deyişle, V ϕ* = V *.

Deterministik SDP Modelleri

Deterministik bir SDP, deterministik durum geçişleri fonksiyonu q(x, a)’yı kullanacaktır. Toplam maliyet tahakkuk yöntemi kullanılarak en kısa yol SDP için durağan bir politika ϕ(x) verildiğini varsayalım. O zaman Denklem (2.3)’ten şunu elde ederiz:

Herhangi bir x = x1'i düzeltmek. Politika değeri fonksiyonunun tanımı başlangıç ​​durumu için aynıdır:

x = x2 :

Denkleme geri konulduğunda şu elde edilir:

Maliyet hesaplama yöntemine uygun olan H(a, b) = a + b. Genel olarak, o zaman:

İndirimli maliyeti kullanırsak ne olur? Argüman, indirimli maliyetlerin ne kadar elverişli bir şekilde faktör olduğu nedeniyle hemen hemen aynıdır. Denklem şu hale gelir:

Önceki denklemde Vϕ(x2)’yi değerlendirdiğimizde, indirim yapmanın x2'nin 1. aşamanın başlangıç ​​durumu olduğu gibi yeniden başlatıldığını belirtmek önemlidir. Daha genel bir gösterim kullanıldığında şu elde edilir:

Yukarıdaki yineleme formülleri arasındaki tek fark, birinde indirim faktörü β’nin görünmesidir. Bu nedenle β = 1 (tanımımızın izin verdiği) olarak ayarlayarak elde edilen denklemin özel bir durumu olarak düşünebiliriz.

Bir minimaks SDP için, Denklemlerde verilen yinelemeli ilişki türü artık şu hale gelecektir:

Stokastik SDP Modelleri

Stokastik bir SDP için, aşama maliyeti rastgele bir değişken olacaktır. Değer fonksiyonu maliyetlerin tahakkukunu ölçtüğünden, gerçekleşen maliyet yerine beklenen maliyeti kullanmak olağan bir uygulamadır. Bu nedenle, stokastik bir SDP modelinin maliyetini tanımlamak için, rastgele değişken X’in beklenen değeri kavramını kullanmamız gerekir.

Rastgele Değişkenin Beklenen Değeri

E[X] niceliği, bir rastgele değişken X’in beklenen değeri olarak adlandırılır ve sonsuz büyüklükte bir örneğin teorik ortalamasını temsil eder. μ = μX = E[X] gösterimi sıklıkla kullanılır. Ayrık rastgele değişkenler için beklenen değer şu şekilde hesaplanır:

Yani, destek SX’teki her olası sonuç için toplama xP(X = x) katkıda bulunuruz. Bir olay A’ya koşul koyabilir ve P(X) = x yerine koşullu olasılıklar P(X = x ∣ A) kullanabiliriz. Bu koşullu beklenen değeri verir:

Rastgele Maliyetlerin/Ödüllerin Birikimi

Deterministik SDP modellerinin ardındaki bu ilkeler, durum geçişleri stokastik olduğunda da hemen hemen aynıdır, ancak o zaman olasılık hesabına güvenmeliyiz (hem maliyet R(x, a) hem de durum geçiş kuralları stokastik olabilir). Stokastik durum geçişlerini modellemek için stokastik çekirdek P(y ∣ x, a)’yı zaten tanıttık. Ayrıca maliyet fonksiyonu R(x, a)’yı (x, a)’ya bağlı bir dağılıma sahip olan rastgele değişken R(x, a) ile değiştirebiliriz. Ancak bu durumda, orijinal maliyet fonksiyonuna benzer bir şey şu şekilde tanımlanmış olarak yeniden ortaya çıkacaktır:

Daha sonra başlangıç ​​durumu x1 olan stokastik bir SDP’nin beklenen toplam maliyetini ele alacağız.

O zaman Vϕ(x), x1 = 1 başlangıç ​​durumu koşuluna bağlı beklenen toplam maliyettir. Dolayısıyla şunu tanımlarız:

(Koşullu beklentilerin kullanımına dikkat edin). İndirim, yukarıdaki denklemlerin getirisine yol açan aynı şekilde tanıtılabilir.

Ancak, SDP’nin stokastik özellikleri önemli bir teknik hususu gündeme getirir. Genel olarak, beklenti doğrusal bir işlemdir. Bu, X ve Y herhangi iki rastgele değişken ve a ve b iki sabit ise, şuna sahip olduğumuz anlamına gelir: E[aX + bY] = aE[X] + bE[Y].

Bu, hesaplama yöntemi eklendiğinde, gerçek gözlemlenen maliyetlere ek olarak beklenen maliyetlere bir maliyet hesaplama yöntemi H(a, b) uygulanmasına olanak tanır. Bu, yukarıdaki denklemin geçerli olmasını sağlar. Aksi takdirde, kullanışlı bu yapı mevcut olmayabilir. Bu, minimax maliyet için geçerli olacaktır, çünkü genel olarak maxE[X], E[Y] ≤ E[maxX, Y] ve eşitsizlik genellikle katıdır.

Markov Karar Süreçleri

Stokastik bir süreç, X durum uzayında bir değer varsayarak {Xt}, t ∈ T rastgele değişkenlerinin dizinlenmiş bir koleksiyonu olarak tanımlanabilir. Genellikle t indeksi zamanı temsil eder, ancak stokastik süreçler aynı zamanda bazı uzaylarda tanımlanan rastgele süreçleri tanımlamak için de kullanılabilir.

Çoğu stokastik süreç ya ayrık zamandır ve X1, X2, …, dizisinin veya sürekli zamanın şeklini alır ve t ∈ [0, ∞) alt kümesinde bir X[t] süreci olarak temsil edilebilir, burada X[t] sürecin t anındaki değeridir.

Markov zinciri ayrık zamanlı bir stokastik süreçtir. Tanımlayıcı özellik, belleksiz özellik veya Markov özelliğidir, esasen gelecekteki durumların dağılımının mevcut durum Xj’ye bağlı olduğu, ancak önceki durumlara bağlı olmadığı anlamına gelir.

Markov Zincirinin Tanımı

Diyelim ki bize Xn ∈ X, i = 0, 1, 2, … olan ayrık zamanlı stokastik bir süreç veriliyor ve bu süreç ayrık durum uzayı X’te değerler alıyor. Genellikten ödün vermeden ya sonlu durum uzayı X = 0, 1, …, n ya da sayılabilir durum uzayı X = 0, 1, … ‘e sahibiz. O zaman aşağıdaki belleksiz özellik geçerliyse Xi bir Markov zinciridir:

Pij niceliğine i durumundan j durumuna geçiş olasılığı denir. Ayrıca geçiş olasılığı matrisimiz (veya geçiş matrisimiz) de vardır:

Geçiş matrisi P’nin i. satırı koşullu olasılığa eşdeğerdir.

Ayrıca, X sayılabilir olduğunda P’nin sonsuz boyutlu bir matris olacağını unutmayın. Ayrıca, durum uzayı pozitif ve negatif tam sayılar kümesi {…, − 2, − 1, 0, 1, 2, … } olduğunda P’yi ‘çift sonsuz’ olarak kavramakta da zorluk çekmeyiz; bu da tanımımızda önemli bir değişiklik gerektirmez.

Markov Zinciri Örneği

Basitliğine rağmen Markov zincirlerinin bir dizi önemli özelliğini gösteren iki durumlu bir Markov zincirinin örneğini ele alalım.

Resmi olarak, durum uzayımız X = {0, 1}.

Örneğin, zaman indeksi i = 0, 1, 2, … bir gün dizisini temsil edebilir ve i = 0'ın sağlıklı bir durumu, Hand i = 1'in ise hasta bir durumu (örneğin, bir enfeksiyondan dolayı) temsil ettiği basit bir enfeksiyon modeli tanımlamak isteyebiliriz. Geçiş matrisi bu nedenle 2 × 2 matrisidir.

Ancak, P’nin gerçek serbestlik derecesi 2'dir, çünkü her satır, bir olasılık dağılımı olarak, 1'e toplanacak şekilde kısıtlanmıştır. Bu nedenle, genellikten ödün vermeden şunu yazabiliriz:

İki sayı α, β ∈ 0, 1 için. Bu, bir denek i. günde sağlıklıysa, i + 1. günde α olasılıkla hasta olduğu ve denek i. günde hastaysa, i + 1. günde β olasılıkla hasta veya sağlıklı olduğu anlamına gelir. Bir enfeksiyon modeli için durum geçiş diyagramı aşağıdaki şekilde gösterilmiştir:

Şekil 5: Enfeksiyon modeli için durum geçiş diyagramı.

Markov Karar Sürecinin Tanımı

Özellikle önemli bir SDP sınıfı, durum-eylem alanı K, maliyet fonksiyonu R x, a ve olasılık çekirdeği P(y ∣ x, a) olan sonsuz ufuklu bir SDP olan Markov karar süreci (MDP) olarak bilinir. İndirim faktörü β ile indirimli maliyet/ödül hesaplama yöntemini kullanır. Aslında, bunu stokastik geçişler ve indirimli maliyet hesaplama yöntemi ile zaman homojen sonsuz ufuklu bir SDP olarak zaten tanıttık (teori ortalama maliyet modeline de uzansa da). Model, n-tuple 77 K, R, P, β ile tanımlanır, burada K durum-eylem uzayı K ⊂ X × A’dır ve bize maliyet fonksiyonu R(x, a), (x, a) ∈ K, olasılık çekirdeği P(y ∣ x, a) ve iskonto faktörü β ∈ [0, 1] verilir (genellikle β < 1 olduğunu varsayarız, ancak β = 1 kabul edilebilir bir seçimse matematiksel teori daha esnektir).

MDP’lerin matematiksel teorisi oldukça zengindir ve bunun MDP’nin kontrollü bir Markov süreci olarak alternatif kimliğiyle çok ilgisi vardır. Bir politika ϕ sabitlediğimizi varsayalım. Bunu, SDP’deki eylemin rolünü ortadan kaldırmak olarak düşünebiliriz, bu daha sonra geçiş olasılıklarına sahip bir Markov zinciri haline gelir.

Bu nedenle, bir MDP’yi (Markov Karar Süreci) iyi tanımlanmış bir karar problemine uygun olacak şekilde seçilebilen (ve değiştirilebilen) bir Markov zincirleri sınıfı olarak düşünebiliriz. Eğer okuyucu bu konuya yeni başlıyorsa, iyi bir başlangıç noktası (S. Ross, 2014) olacaktır. Daha sonra (S. M. Ross, 1996) metni Markov zincirlerini bir sonraki seviyede ele alır. Bu ikinci cilt, MDP’lerin incelenmesinden kaynaklanan çoğu sorun için yeterli teoriyi kapsar. Dinamik sistemlerin incelenmesine özellikle uygun, Markov zincirlerine yönelik daha ileri düzey bir yaklaşım ise (Brémaud, 1999) içinde bulunabilir. Genellikle, K’nin ayrık bir küme olduğunu varsayacağız, ancak mutlaka sonlu olması gerekmez. Ayrıca, SDP’nin (Stokastik Dinamik Programlama) zaman indeksleri i=1,2,… üzerinde tanımlanmış bir ayrık zaman süreci olduğunu varsaydık. Eğer i’nin herhangi bir nicel yorumu (veya zaman birimi) varsa, bu genellikle önemli bir rol oynamaz (Bkz. Ek C’deki vaka çalışması). Elbette, bu varsayımları ihlal eden ancak yine de bu ders kitabında ele alınan SDP’lerin tüm özelliklerine sahip gibi görünen SDP modellerini düşünmek kolaydır. Gerçekten de, hem durum (x) hem de eylemin (a) gerçek sayılar olduğu bir SDP’yi inceleyeceğiz. Bu tür durumlarda, genellikle gerçek değerli fonksiyonlarla ilişkili yöntemlere, özellikle birinci dereceden türev kısıtlamalarını kullanarak optimalite için gerekli (veya durağan) koşulların tanımlanmasına güvenmek mümkün olabilir. Gerçek durum-eylem uzaylarına sahip bir SDP, grid bölümleri kullanılarak ayrık durum-eylem uzaylarına sahip yaklaşık SDP’lere yaklaştırılabilir. Bu yöntem (Chow & Tsitsiklis, 1989) ve (Chow & Tsitsiklis, 1991) içinde oldukça geliştirilmiştir.

Bellman Denklemi

Dinamik programlamayı, maliyetin en aza indirilmesiyle ilişkili bir optimizasyon problemi olarak görmek için birkaç yol vardır. En basiti, bunu, sabit bir x için tüm olası politika fonksiyonlarını (ϕ∈Φ) dikkate alarak Vϕ(x)’yi en aza indirme problemi olarak görmektir. Ancak, bunu yalnızca tek bir durum x=x1∈X için gerçekleştirmekle ilgilenebiliriz. Bununla birlikte, Vϕ(x1)’in değerlendirilmesinin, diğer durumlarda Vϕ(x)’in değerlendirilmesini gerektirdiğini zaten gördük. Bu nedenle, dinamik programlama teorisi, Vϕ​’yi, fonksiyon uzayında tanımlanmış bir fonksiyon olarak (Vϕ∈V) değerlendirmeyi ele alır. Burada V, en azından tüm olası politika değer fonksiyonlarını (Vϕ(x)) içerir. Peki, bunu iyi tanımlanmış bir optimizasyon problemi haline nasıl getirebiliriz? Zaten, Φ’nin tüm geçerli politikalarını temsil ettiği yerde, bir politika fonksiyonunu (ϕ∈Φ) sabitleyebileceğimizi ve başlangıç durumu x altında bu politika ile biriken toplam maliyeti veren politika değer fonksiyonunu (Vϕ(x)) değerlendirebileceğimizi gördük. O halde, bir politikanın (ϕ∗∈Φ) optimal olduğunu söylemek ne anlama gelir? Belleksiz (memoryless) özelliği geçerliyse, bu, her bir başlangıç durumu (x∈X) için aynı politikanın (ϕ∗) optimal olduğu anlamına gelmelidir. Bu durumda şu sonuca ulaşırız:

Tüm ϕ ∈ Φ için. Yani, bir politika herhangi bir başlangıç ​​durumu x’ten hesaplanan maliyeti en aza indiriyorsa optimaldir. Ters yönde çalışarak, x başlangıç ​​durumu olduğunda optimal toplam hesaplanan maliyet/ödülü veren optimal değer fonksiyonu V * x’i tanımlayabiliriz.

Herhangi bir başlangıç ​​durumu x için, V*(x) tüm kabul edilebilir politikalar arasında hesaplanan maliyet için en büyük alt sınırdır. İşlemlerin denklemlerde tanımlandığı sırayı anlamak önemlidir. Önce durum x’i sabitleriz, sonra ϕ ∈ Φ üzerinde en aza indiririz. Yazdığımız gibi, en aza indiren ϕ(x) ile değişebilir ve bu nedenle bazı politika ϕ* için V *(x) = Vϕ*(x) garantisi yoktur. Ancak, şunu garanti edebiliriz:

Herhangi bir ϕ ∈ Φ için, yani V * ≡ V ϕ* olan bir ϕ* ∈ Φ bulabilirsek, bu en iyi politika olur. O zaman, indirimli maliyet hesabına sahip minimum maliyetli stokastik SDP için böyle bir en iyi politika ϕ*’nin var olduğunu varsayalım. Politika değer fonksiyonu V ϕ* = V *, denklemimizi karşılayacaktır:

Sonra, optimal politika ϕ*’nin ufak bir modifikasyonunu ele alacağız. Durum x’ten eylem a ∈ Ax’i seçiyoruz, sonra tüm sonraki durumlardan optimal politika ϕ*’yi devam ettiriyoruz. Bu modifiye edilmiş politikanın beklenen tahakkuk eden maliyetini şu şekilde gösteriyoruz:

V ϕ* = V * olduğunu not edelim. Ancak, hafızasız özellik sayesinde, bir SDP’deki herhangi bir xj durumundan en iyi olan politika, xj başlangıç ​​durumu olsaydı en iyi olacak politikayla aynıdır. Bu nedenle, herhangi bir x durumundan en iyi politika, her x ∈ X için V *(x, a)’yı a üzerinde en aza indirerek Denklem (2.24)’ten çıkarılabilir:

Pekiştirmeli öğrenmede, V*(x, a) niceliği aynı zamanda bir Q faktörü olarak da bilinir ve Q(x, a) ile gösterilir; burada Q(x, a), eylem seçildiğinde hesaplanan toplam maliyet/ödüldür, daha sonra en uygun politika kullanılır.

Bellman’ın Optimizasyon İlkesi

Artık dinamik programlamanın temel ilkesini belirtebiliriz. Bize hafızasız bir SDP verildi. V*(x), başlangıç ​​durumu x’ten elde edilen en iyi hesaplanan maliyet olsun. V*(x, a), eylem a başlangıç ​​durumu x’ten seçildiğinde hesaplanan maliyet olsun ve en iyi politika sonraki durumdan itibaren uygulansın. O zaman Bellman denklemi, özdeşlikten çıkar:

Bellman denklemi, çözümü hafızasız SDP’ler için optimum değer fonksiyonu V *(x) veren bir fonksiyonel denklemdir. Bellman denkleminin çeşitli biçimleri yukarıdaki denklemden çıkar. SDP deterministikse ve maliyet tahakkuk yöntemi H(a, b) kullanıyorsa, o zaman:

SDP stokastik ise ve indirimli maliyet hesabını kullanıyorsa, o zaman:

İndirimli maliyetli deterministik model için bu şu hale gelir:

ve en düşük maliyet için:

Optimal politikayı, yukarıdaki denklemin hangi biçimde olursa olsun minimize eden eylemi ϕ(x) olarak belirleyerek belirleyebiliriz. Bu aynı zamanda gerekli bir koşuldur çünkü sürecin herhangi bir örneği bunun bir çözümü olmalıdır. Aşağıda inceleyeceğimiz tüm örnekler bu işlemi kullanacaktır. Ancak, önemli matematiksel meseleler dikkate alınmalıdır. Bir denklemin sadece formüle edilmesi, onun bir çözüme sahip olduğunu garanti etmez. Örneğin, şu durumu ele alalım: x²=−1 denklemini sağlayan bir gerçek sayı x bulun. Alternatif olarak, bir denklemin birden fazla çözümü olabilir, bu da elde edebileceğimiz herhangi bir çözümü tanımlama gerekliliğine yol açar (bu sorun genellikle bir fonksiyonu birinci dereceden durgunluk koşulları kullanarak maksimuma veya minimuma çıkarmaya çalışırken ortaya çıkar). Optimizasyonda ek bir sorun, özellikle gerçek bir optimal çözümün varlığı veya yokluğu (bu kayayı, o duvara mümkün olduğunca yakın yerleştir, ama ona dokunmadan) meselesidir. Burada sunulan argümanlarımız gerektiği kadar ayrıntılı olacaktır, ancak kullanılan tekniklerin derinlemesine matematiksel ispatı için okuyucuyu literatüre yönlendiriyoruz. Önemli bir endişe, Bellman denkleminin görünüşteki sadeliğine rağmen, çözümünün özellikle durum uzaylarının çok büyük olduğu durumlarda önemli bir hesaplama zorluğu temsil edebilmesidir (örneğin, tavla için |X| ≈ 10²⁰ olduğunu hatırlayın). Richard Bellman, bunu boyutluluk laneti olarak adlandırmıştır ve bu, bu alandaki araştırmaların büyük bir kısmını motive etmektedir.

Geriye Doğru Tümevarım

Sonlu ufuk problemleri için uygun olan denklemi çözmenin bir yöntemi geriye doğru tümevarım olarak bilinir. Genellikle basit bir çözümü olan son aşama için en uygun politikayı belirleyerek ilerler. Bu yapıldıktan sonra, son aşamadan başlayarak geriye doğru bir dizideki aşamalar için en uygun politikalar belirlenebilir. İyi tanımlanmış bir son aşamanın varlığına dayanır. Yukarıdaki denklemde, bu durumda basit bir çözüm yöntemi üreten ilginç bir özellik fark edebiliriz.

Verilen x durumu için denklemin sağ tarafındaki tüm nicelikleri biliyorsak V *(x) değerini hesaplayabiliriz. R(x, a) değerini bileceğiz, dolayısıyla konu, x’in geçebileceği tüm durumlardaki değer fonksiyonunun değerlerini temsil eden V *(q(x, a)) değerlerini (deterministik SDP için) bilip bilmediğimizdir. Sonlu ufuk probleminin aşama yapısı bu yaklaşıma izin verir. Sonlu ufuk SDP’sinin son aşamasıyla ilişkili durumlar için V*(x) değerinin hesaplanması genellikle önemsiz olacaktır.

Daha sonra, K — 1 aşamasındaki tüm durumlar için V*(x) değerini, K aşamasındaki tüm durumlar için bildiğimizden, yukarıdaki denklemi kullanarak değerlendirebiliriz. İşlemi K — 2, K — 3, …, 1 aşamaları için tekrarlarız, böylece V*(x) tüm durumlar için hesaplanır ve bu da problemi çözer. Sonra, yöntemi özetleriz. Bize durum uzayı X ve son durum xΔ ∈ X olan sonlu ufuklu K-aşamalı bir SDP veriliyor. Durum uzayının aşamaya göre bölünebileceğini varsayıyoruz, X = X1 ∪ … ∪ XK ∪ xΔ böylece j aşamasındaki herhangi bir durum Xj’nin bir elemanı olmalıdır. V * xΔ’nin bilindiğini varsayıyoruz. O zaman herhangi bir durum x ∈ XK için, maliyet hesaplama yöntemi H(a, b) olan deterministik modeller için,

Daha sonra aşamayı j = K − 1 olarak ayarlıyoruz ve çözüyoruz:

Daha sonra j = K − 1, K − 2, …, 1'i yinelemeli olarak azaltırız. Stokastik katkısal maliyet modeli için algoritma esasen aynıdır. K aşamasının her zaman xΔ terminal durumuna geçtiğini varsayarız.

Daha sonra hesaplayalım:

Aşama j = K − 1'i ayarlayın ve çözün:

Daha sonra j = K − 1, K − 2, …, 1'i yinelemeli olarak azaltırız. Toplam maliyet tahakkuku için β = 1'i belirleriz.

Geriye Doğru Tümevarım Kullanarak Posta Arabası Problemini Çözmek

Bu noktada, dinamik bir programlama modeli ve bir maliyet hesaplama yöntemi tanımladık. Dolayısıyla, terminal durumu V*(K) = 0'daki değer fonksiyonuyla başlayarak, şimdi geriye doğru tümevarım uygulayarak posta arabası problemini çözüyoruz.

Aşama 5:

Şekildeki orijinal haritanın “Posta arabası sorun haritası” başlıklı bölümü, aşağıdaki şekilde 5. aşamadan 6. aşamaya geçişi temsil eder. Basitçe, V*(I) = 3 ve V*(J) = 2. Bunun nedeni, her bir I ve J durumundan yalnızca bir eylemin, K, mevcut olmasıdır ve bu da sırasıyla 3 ve 2 aşama maliyetlerine karşılık gelir. Bu nedenle ϕ*(I) = K ve ϕ*(J) = K.

Posta arabası problemi. Şekil 2.1'deki haritanın 5. Aşamadan 6. Aşamaya geçişi gösteren kesiti.

Aşama 4:

Denklem doğrudan uygulanabilir. Önce V *(x, a)’yı değerlendiririz, sonra her x için a üzerinde en aza indiririz:

Örneğin, G’den I’a geçişin aşama maliyeti 4 olduğundan R(G, I) = 4 (“Posta Arabası Problem Haritası” başlıklı şekil). Bu nedenle, Git’ten ϕ*(G) = J’ye gitmek en iyisidir, bu da G’den kalan en iyi mesafenin V*(G) = 4 olmasını sağlar. Aynısını H durumu için de yapıyoruz:

Bu nedenle, H’den ϕ*(H) = I noktasına gitmek en uygunudur; bu da H’den kalan en uygun uzaklığın V*(H) = 6 olmasını sağlar.

Aşama 3:

Tekrar, denklem doğrudan uygulanabilir. Önce V*(x, a)’yı değerlendiririz, sonra her x için a üzerinde en aza indiririz:

Yani, E’den ϕ*(E) = G’ye gitmek en uygunudur, bu da E’den kalan en uygun uzaklığın V*(E) = 11 olmasını sağlar. Aynısını F durumu için de yapıyoruz:

Bu nedenle, F’den ϕ*(F) = H’ye gitmek en uygunudur; bu da F’den kalan en uygun uzaklığın V*(F) = 9 olmasını sağlar.

Aşama 2:

Daha önce olduğu gibi, önce V*(x, a) değerini değerlendiriyoruz, ardından her x için a üzerinde en aza indiriyoruz:

Yani B’den iki tane optimum eylem vardır; bunları ϕ*(B) = {E, F} şeklinde ifade edeceğiz; bu da B’den kalan optimum uzaklığın V*(B) = 15 olmasını sağlar.

Bu nedenle, C’den ϕ*(C) = F’ye gitmek en uygunudur; bu da C’den kalan en uygun uzaklığın V*(C) = 12 olmasını sağlar.

Yani D’den iki tane optimal eylem vardır ϕ*(D) = {E, F}, bunlardan her biri DofV *(D) = 13'ten optimal kalan mesafeyi verir.

Aşama 1:

Şekildeki orijinal haritanın “Posta arabası problem haritası” başlıklı bölümü, 1. aşamadan 2. aşamaya geçişi temsil eder ve aşağıdaki şekilde vurgulanır. Şimdi aynı yöntemi kullandığımız başlangıç ​​durumuna ulaştık:

Posta arabası problemi. Şekil 2.1'deki haritanın 1. Aşamadan 2. Aşamaya geçişi gösteren kesiti.

Yani, A’dan iki tane optimum eylem vardır ϕ*(A) = {C, D}, bunlardan her biri A’dan V*(A) = 15'lik optimum kalan uzaklığı verir.

Şimdi posta arabası problemine bir çözümümüz var. A’dan K’ye mümkün olan en düşük mesafe 15'tir. Ancak bunun birden fazla rota ile elde edildiğini unutmayın. Ait’ten C veya D’ye gitmek en uygunudur. C’den Ki’ye giden tek optimum rota C-F-H-I-K’dir. Dit’ten E veya F’ye gitmek eşit derecede en uygunudur. E’den K’ye giden tek optimum rota E-G-J-K’dir ve F’den K’ye giden tek optimum rota F-H-I-K’dir. Bu, mümkün olan en düşük mesafe olan 15'e ulaşan toplam üç rota verir:

Posta Arabası Problemini Yeniden Ele Alıyoruz: Ödül ve Maliyet

Sonra, hafızasız mülkle ilgili bazı sorunları vurgulayarak posta arabası problemini değiştirmeyi düşünüyoruz. Orijinal problemde olduğu gibi, A’dan K’ye etiketlenmiş 11 kasaba vardır ve bir yolcu, “Posta arabası problem haritası” başlıklı şekilde gösterilen haritaya göre A kasabasından başlayıp K kasabasında biten bir rota seçmelidir. Yolcunun rota boyunca bir emtia satma fırsatı olduğunu varsayalım. Bu, yalnızca bir kez yapılabilir ve C veya H düğümünde yapılmalıdır. Bu satış yolcuya 100$ kar sağlayacaktır. Yolculuğun kendisi yolcuya 2$ × D’ye mal olur, burada D, alınan rotanın toplam mesafesidir. Bu nedenle, amaç ödülü en üst düzeye çıkaran rotayı bulmaktır R = 100 × I_C,H − 2 × D, burada rota C veya H’yi (muhtemelen her ikisini de) içeriyorsa I_C,H = 1 ve aksi takdirde I_C,H = 0.

Dikkat edilmesi gereken ilk şey, bunun bir maksimizasyon problemi olduğudur, orijinal posta arabası problemi ise bir minimizasyon problemidir. Neyse ki, bu dinamik programlamanın matematiğini önemli bir şekilde değiştirmez, çünkü yapmamız gereken tek şey ödülü -1 ile çarpıp maliyete dönüştürmektir. Bunu, denklemde ödül R(x, a)’yı maliyet −R(x, a) ile değiştirerek uygulayabiliriz:

İstersek bunu şu şekilde yeniden yazabiliriz:

veya alternatif olarak:

Orijinal denklemde V*(x)’in belirlenmesi gereken bilinmeyen bir fonksiyon rolü oynadığını hatırlayın. Bu rol denklemde [−V*(x)] tarafından oynanır.

Elbette, bu sembol sadece çözülmesi gereken bir fonksiyon için bir yer tutucudur, bu yüzden denklem, [−V*(x)]’in örneğin V′(x) veya hatta orijinal V*(x) ile değiştirilmesi durumunda yorumunu korur. Başka bir deyişle, eğer R(x, a) bir ödülse ve biriken ödülü maksimize etmek istiyorsak, denklemi yalnızca şu şekilde değiştirmemiz gerekir:

Çözüm yöntemi aynı kalır, ancak minimize etmek yerine maksimize ederiz. Ancak bu problem için dikkate alınması gereken başka bir konu daha vardır. SDP’lerin hafızasızlık özelliğini karşılamaz. Bunu görmek için “Posta arabası problem haritası” başlıklı şekle geri dönün ve E düğümünde olduğumuzu ve bir sonraki aşama için G ve H arasında seçim yapmamız gerektiğini varsayalım. C veya H düğümlerinden birini ziyaret edersek 100$ ödül kazandığımızı hatırlayın. Hafızasızlık özelliğinin ihlal edildiği yer burasıdır. C’yi daha önce ziyaret ettiysek H’yi ziyaret ederek 100$ ödül kazanmayız, aksi takdirde kazanırız. Dolayısıyla, gelecekteki ödül yalnızca mevcut aşama durumuna ve eyleme değil, aynı zamanda süreç geçmişine de bağlıdır.

Ancak, dinamik programlama bu problemin çözümünde hala önemli bir rol oynayabilir. Toplam ödül R = 100 × I_C,H − 2 × D’dir. Her iki terimi de optimize eden bir rota varsa, bu en iyi çözüm olacaktır. Başka bir deyişle, C veya H’den geçerken 15'lik minimum mesafeyi elde eden bir rota arıyoruz.
Öyle ki, Denklem (2.26)’da listelenen üç en iyi rotadan ikisi bu kısıtlamayı karşılar. Durum böyle olmasaydı, A’dan C’ye; A’dan H’ye; C’den K’ye; ve H’den K’ye en kısa rotaları bularak, C veya H’den geçen en iyi rotayı bulmak için dinamik programlamayı kullanabilirdik. Bu rotayı, C veya H’den geçmeyen en iyi rotayla karşılaştırmamız gerektiğini de unutmayın.

Stokastik Dinamik Programlama: Optimum Hazine Arama

Daha sonra stokastik dinamik programlama problemini ele alalım. Bahamalar’da tatil yaparken yaklaşık 13.000 dolar değerinde batık bir hazine duyduğunuzu hayal edin. Saatlik 700 dolara günde 5 saate kadar bir tekne, ekipman ve mürettebat kiralayabilirsiniz. Hazineyi bulmanın aldığı sürenin, ortalaması μ = 13 saat olan üstel bir rastgele değişken olduğunu tahmin ediyorsunuz.

Tatilinizde sadece üç gününüz kaldı. Tekneyi her gün ne kadar süreyle kiralamalısınız? Optimizasyon problemlerini çözerken çözümün genel biçimini tahmin etmeye çalışmak faydalıdır. Belirli bir günde tekneyi 5 saatliğine kiralamaya karar verdiğimizi varsayalım. Bu kararın, günün araması başlamadan önce alınması gerektiği anlaşılmaktadır. Dolayısıyla, ilk saatlik aramadan sonra hazine bulunursa, planlanan kalan dört saat için yine de ödeme yapmalıyız (dinamik programlama, bu tür planlama problemlerini çözmek için sıklıkla kullanılır).

Daha sonra “zarfın arkası” bir hesaplama yapabiliriz. Diyelim ki tekneyi 13 saatliğine kiralamaya önceden karar verdik (beklenen arama süresi).

Hazineyi bulma olasılığı 1 − exp(− 13/13) ≈ 0 . 632 olacaktır.

Toplam beklenen ödül bu nedenle R = 13.000 $ × 0.632 − 700 $ × 13 = − 884 $ olur ve beklenen net zararı verir. Açıkça, aramayı bir SDP olarak planlamak daha iyi olurdu.

Daha sonra K = 3 aşamaya sahip sonlu bir ufuk SDP’miz olur (kalan üç günün her biri bir aşamayı tanımlayacaktır). Öncelikle x durumunu nasıl tanımlayacağımıza karar vermeliyiz. Hafızasız bir SDP formüle etmek ve ayrıca bir karar vermek için gereken tüm bilgileri dahil etmek istiyoruz. Açıkça, hazinenin bulunup bulunmadığını bilmemiz gerekiyor (eğer bulunmuşsa tekneye para harcamayız). Bu nedenle, hazine bulunduysa s = 1, aksi takdirde s = 0 olarak ayarlayın. Ancak, tartışmamız kalan arama günü sayısının da önemli bir bilgi olacağını gösteriyor. Bu niceliği w olarak gösterelim. Bu nedenle, üçüncü ve son günümüzün sabahında hazine henüz bulunmadıysa durum x3 = (w, s) = (1, 0) ve bulunduysa x3 = (1, 1) olur. Eylem alanı A = {0, 1, 2, 3, 4, 5} (teknede geçirilebilecek olası saat sayısı) ve aşama ödülü şudur:

R(w, 1, a) = 0 olduğunda Bellman denklemi şu hale gelir:

s = 0, 1 için terminal değer fonksiyonu V*(0, s) = 0'dır. Bu, V*(w − 1, 0) değerini biliyorsak, bunu Denklem (2.29)’daki V *(w, 0, a) ifadesine koyabileceğimiz, sonra V*(w, 0), a’yı a ∈ A üzerinde maksimize edebileceğimiz anlamına gelir. Bu, V*(w, 0) değerini verir ve maksimize eden eylem a*, hazineyi daha önceden bulmuşsak tekneyi kiralamanın bir faydası olmayacağından, ϕ*(w, 1) = 0 iken, ϕ*(w, 0) = a* olan optimum politikayı belirler.

Son aşama 3'te V*(0, 0) = 0 ile başlayarak aşağıdaki hesaplamayı yapıyoruz:

Aşama 3:

V*(0, 0) = 0'ı denklem (2.29)’a koyun.

sonra a ∈ A üzerinde maksimize edin. V *(1, 0, a)’nın maksimumunu her a = 0, 1, …, 5 için değerini hesaplayarak bulabiliriz. Bunu yaptıktan sonra, optimum eylemin ϕ*(1, 0) = a* = 5 olduğunu ve V*(1, 0) = 650,7 .

Aşama 2:

V * 1, 0 = 650,7'yi (2.29) denklemine koyun.

sonra ∈ A üzerinde maksimize edin. Şimdi, optimum eylem ϕ*(2, 0) = a* = 4 olacak ve V*(2, 0) = 1121,5 elde edilecektir.

Aşama 1:

Son olarak, V *(2, 0) = 1121,5'i Denklem (2.29)’a koyun.

Daha önce olduğu gibi, ∈ A üzerinde maksimize etmek, optimum eylem ϕ*(3, 0) = a* = 3 ve değer fonksiyonu V *(3, 0) = 1469,4 sonucunu verir.

En iyi strateji, gerektiğinde tekneyi sırasıyla 1, 2 veya 3. günlerde 3, 4 veya 5 saatliğine kiralamaktır. Bu, 1469,40$’lık beklenen bir ödül getirir. Öngörüldüğü gibi, en iyi strateji, planlamada daha fazla esneklik olduğunda programın başında arama süresini daha az bütçelemektir.

Geriye Dönük Tekrarlamayı Sonsuza Kadar Uzatma

Bu noktaya kadar, hazine arama problemini K = 3 aşamalı sonlu ufuklu bir SDP olarak tasarladık. Gerektiğinde hazine aramak için fazladan bir günümüzün olmasını sağlayacak şekilde işleri ayarlamayı başardığımızı varsayalım. Buna göre, K = 4 aşamalı sonlu ufuklu bir SDP için optimum kontrolü yeniden hesaplamaya karar veririz. Ancak, K = 4 aşamalı SDP’nin son 3 günü için optimum politikanın, K = 3 Aşamalı SDP’nin 3 günü için hesaplananla aynı olacağı açık olmalıdır. Aslında, w = 0, 1, 2, 3 ve s = 0, 1 için V*(w, s) ve ϕ*(w, s), herhangi bir K ≥ 3 aşamalı SDP için aynı olacaktır. Bu, (2.29) Denklem’inin biçiminden ve herhangi bir sayıda aşama K için V*(0, s) = 0 olması gerektiği gerçeği kaynaklanmaktadır.

Bu, dinamik programlamanın ilginç bir özelliğine yol açar. Sabit ufuklu bir SDP için genel bir çözüm belirlemek için, genellikle sabit sayıda aşama K belirtmemize gerek kalmaz. V*(0, 0) = 0 olduğunu bildiğimizde, Denklem (2.29)’u yinelemeli olarak değerlendirerek (w yinelemeleri gerektirir) herhangi bir pozitif tam sayı w için V*(w, 0)’ı değerlendirebiliriz.

Aşağıdaki şekilde gösterilen iki grafiği üretmek için bir bilgisayar programı kullanıldı; bu grafikler, en uygun politika ϕ*(w)’yi (w arama günü kaldığında tekneyi kiralamak için gereken saat sayısı) ve en uygun değer fonksiyonu V*(w)’yi (w arama günü kaldığında beklenen en uygun ödül) çizer. Programımızda, w = 500'e kadar yinelemeler gerçekleştirildi. Başlangıçta, en uygun eylem ϕ*(w)’nin w arttıkça azalma eğiliminde olduğunu belirtmiştik. Bunun nedeni, planlamada daha fazla esnekliğe sahip olduğumuzda harcamalarımızda daha dikkatli olmamızın mantıklı olmasıdır. Bu, hazineyi keşfettikten sonra teknenin parasını ödemek zorunda kalmamız durumundan kaçınmamızı sağlar.

Hazine Arama problemi için örnek python programının çıktısı Bölüm u2.sec.treasure.example.

Aslında, ele alınan aralığın çoğu için en uygun politika ϕ*(w) = 1'dir; bu, hazineyi ararken mümkün olan en dikkatli kaynak harcamasını temsil eder (yukarıdaki şeklin sol grafiği). Çözümün bir diğer ilginç özelliği de, yeterince büyük tüm w değerleri için en uygun politikanın ϕ*(w) = 0 olmasıdır; bu durumda o gün hiçbir arama yapılmaz. Başka bir deyişle, en uygun şekilde tahsis edilmiş olsa bile toplam arama süresini sonsuza kadar artırmanın sonunda beklenen ödülde bir azalmaya yol açacağı anlamında, en uygun olma konusunda katı bir üst sınır vardır. Buna göre, beklenen ödül asla belirli bir değeri, 3.500$ civarında bir değeri aşamaz (yukarıdaki şeklin sağ grafiği).

Değer Tekrarı

Değer yinelemesi ve genel olarak daha gelişmiş optimizasyon teorisinin büyük bir kısmı, işlevsel analiz açısından daha doğal hale gelecektir. Genellikle y = f(x) fonksiyonunu bir gerçek sayı x’in başka bir gerçek sayı y’ye eşlenmesi olarak düşünürüz. İşlevsel analiz tipik olarak g = Tf’nin bir f(x) fonksiyonundan başka bir g(x) fonksiyonuna eşlenmesiyle ilgilidir. Bu durumda, T genellikle bir operatör olarak adlandırılır. Bir operatör bir fonksiyonu başka bir fonksiyona eşler.

Okuyucu şüphesiz bu terminolojinin kullanılıp kullanılmadığına bakılmaksızın birçok örnekle karşılaşmıştır. Örneğin, f(x) = x² + 1 fonksiyonunu ele alalım.

Türev operatörü iyi bilinmektedir:

Fonksiyonel analizde, bir operatörün genelliğini vurgulamak için onu şu şekilde yazabiliriz:

Daha sonra Bellman Denkleminin aşağıdaki formunu ele alalım:

Dinamik programlamayı veya Bellman operatörü T’yi tanımlamak için denklemi kullanabiliriz. Diyelim ki bize herhangi bir V ′:X →ℝ fonksiyonu verildi. Operatörü V′’ye uygulayarak başka bir V ′′:X →ℝ fonksiyonu üretelim:

Her x ∈ X için. Bu daha sonra V ′′ = T V ′ olarak daha kompakt bir şekilde yazılabilir, burada T V ′’nin değerlendirmesinin her x ∈ X için ayrı bir hesaplamayı içerdiği anlaşılmaktadır. O zaman Bellman’ın denklemi V * = T V * olur.

Sabit Nokta Algoritmaları

Denklem, çözümü sabit bir nokta olan sabit nokta denklemine bir örnektir. V = TV (burada V bir fonksiyondur) veya x = f(x) (burada x bir reel sayıdır) biçimindeki herhangi bir denkleme sabit nokta denklemi denir. Sabit nokta denkleminin herhangi bir çözümü V * bir sabit noktadır V * = TV* Bu tür denklemler uygulamalı matematikte ve sayısal analizde her yerde bulunur, bu nedenle sabit noktaların sabit nokta yineleme yöntemi kullanılarak nasıl değerlendirilebileceğini anlamak önemlidir: Burada xn + 1 = f(xn) sabit nokta yinelemelerini kullanarak x1, x2, … dizisini hesaplıyoruz. x1 için bir başlangıç ​​değeri belirtilmelidir. Eğer f, x* = f(x*) sabit noktasına sahipse, iyi bilinen koşullar altında sabit nokta yinelemelerinin dizisi x*’e yakınsar. Bu fikir operatörlere de uzanır. Eğer operatör T sabit noktası V* = T V* ise, bilinen koşullar altında sabit noktalar Vn + 1 = T Vn’yi yineler ve uygun bir başlangıç ​​fonksiyonu V1 verildiğinde V*’ye yakınsar.

Sabit Nokta Algoritması Örneği

Diyelim ki bize f x = 1 − 0 .95e^−x fonksiyonu verildi ve x = f(x) sabit nokta denklemini çözmek istiyoruz. Böyle bir denklemin çözümü sabit bir noktadır. Belirli koşullar altında sabit nokta denklemi sabit nokta algoritması kullanılarak çözülebilir:

x1=uygun şekilde seçilmiş başlangıç ​​çözümü, x_i+1=f(xi), i = 1, 2, …

Sonra lim_{i →∞} xi = x*, burada x* = f(x*) sabit bir noktadır. Bunun gibi bir örnekte, dizinin hiçbir elemanının x*’e tam olarak eşit olmayacağı anlamında kesin bir çözüm elde edemeyiz. Ancak dizinin elemanları sabit bir noktanın giderek daha doğru yaklaşımlarıdır ve sabit nokta algoritmaları teorisi kesin yaklaşım hata sınırlarını belirlememize olanak tanır. Örneğimiz için, başlangıç ​​çözümünü x1 = 1 olarak ayarlarsak, ilk birkaç yineleme şöyle olur:

yaklaşık sabit nokta x* ≈ 0 .2870483'e yol açar, f(0.2870483) = 1 − 0 .95e^(−0 .2870483) ≈ 0.2870483. Sabit nokta algoritmasının ilerlemesi aşağıdaki şekilde gösterilmiştir.

fI(x) = x özdeşliğinin oynadığı role dikkat edin. Sabit nokta, f(x) ve fI(x) fonksiyonlarının kesişimi olmalı ve (xi , f(xi)), i = 1, 2, 3, … noktaları o noktaya doğru öngörülebilir bir ilerleme göstermelidir.

Sabit nokta x* kırmızı nokta ile gösterilirken, ilk üç yineleme mavi noktalarla gösterilir. Kimlik kesikli gri çizgi ile gösterilir.

Sabit Nokta Algoritması Olarak Değer Tekrarı

Yukarıdaki denklemlerin açıkça gösterdiği gibi, optimum değer fonksiyonu V* sabit nokta denkleminin çözümü olarak yorumlanabilir. Değer yinelemesi, dinamik programlama operatörü T’ye uygulanan bir sabit nokta algoritmasıdır: Değer yinelemesinde optimum değer fonksiyonu V*’yi sabit nokta yinelemelerini V_n+1 = T V_n hesaplayarak değerlendiririz, burada T dinamik programlama operatörüdür ve V1 uygun şekilde seçilmiş bir başlangıç ​​fonksiyonudur. V1, V2, … dizisi optimum değer fonksiyonu olan sabit nokta V* = TV*’ye yakınsar.

Sabit nokta V * = TV *’yi sabit nokta yinelemelerini kullanarak belirleriz, V1=uygun şekilde seçilmiş başlangıç ​​çözümü, V_i+1=TV_i,i = 1, 2, … Daha sonra yinelemeler Vi, V*’nin giderek daha doğru yaklaşımlarıdır. Bellman operatörünün sabit noktası daha sonra bize en uygun politikayı belirleme olanağı sağlar. Bu, ϕ*’yi tatmin eden herhangi bir politikadır. V ϕ* = V *.

Politika Tekrarı: Aktör-Eleştirmen Yöntemi

Belirli bir politikanın toplam ödülünü veya maliyetini belirleme sorunu, optimal bir politika belirlemenin aksine, politika değerlendirmesi olarak adlandırılır. Sabit politika ϕ’ye sahip dinamik programlama modeli için bu, politika değer fonksiyonu Vϕ(x)’i değerlendirmeye indirgenir. Gördüğümüz gibi, optimal bir politika ϕ* belirlemek için Bellman denklemini kullanabiliriz. Öte yandan, optimizasyonla değil, herhangi bir sabit politika ϕ için herhangi bir başlangıç ​​durumu x ∈ X’ten kaynaklanan maliyet Vϕ(x)’i değerlendirmekle ilgileniyorsak, o zaman Denklemi kullanabiliriz:

Bu denklem, referans olması açısından burada tekrar verilen denklemi ile aynı yapıya sahiptir:

Özellikle, V = TϕV sabit nokta denklemini tanımlayan ve Vϕ politika fonksiyonuyla ilişkili olan politika operatörü Tϕ’yi tanıyabiliriz.

Politika operatörü, değerlendirme yöntemini kullanarak bir V′ fonksiyonunu her x ∈ X için V′′ fonksiyonuna eşler:

Bu daha kompakt bir şekilde şu şekilde yazılabilir:

O zaman denklem başka bir sabit nokta denklemidir:

ve iyi tanımlanmış koşullar altında, Vϕ, politika değeri yinelemesi olarak bilinen sabit nokta yineleme yöntemi ile keyfi olarak küçük bir hata ile yaklaşık olarak hesaplanabilir: V1=uygun şekilde seçilmiş başlangıç ​​çözümü, V i + 1=T ϕ V_{i , i} = 1, 2, … .

Algoritma, V ϕ’nin giderek daha doğru yaklaşımlarından oluşan V1, V2,… dizisini üretir.

Bu yöntem, optimizasyondan ziyade belirli bir politikanın performansıyla ilgilendiğimiz durumlarda açıkça uygundur. Ancak, algoritma (2.33), Bellman denklemini çözmeye yönelik bir yöntem olan politika iterasyonu veya (Howard, 1960'da tanıtılan) aktör-eleştirmen yönteminin bir bileşeni olarak da kullanılabilir. Değer iterasyonu gibi, bu algoritma da iteratiftir ancak iki adım arasında gidip gelir ve değer fonksiyonları yerine bir dizi politika fonksiyonu ϕ1, ϕ2, … üretir.

İlk adım, mevcut politika ϕn ile başlar ve politika operatörü Tϕn’ye sabit nokta iterasyon yöntemini uygulayarak politika değer fonksiyonu Vϕn’yi değerlendirmeyi içerir. Daha sonra, ϕn politikası iyileştirilerek sıradaki politika olan ϕn + 1 elde edilir. Algoritma, katı bir iyileştirmenin mümkün olmadığı durumda sona erer; bu durumda, dizideki son politika fonksiyonu optimal politika fonksiyonu ϕ* olur. Politika değerlendirme adımı eleştirmen olarak, politika iyileştirme adımı ise aktör olarak işlev görür.

Değer iterasyonu ile politika iterasyonu arasındaki önemli bir fark, değer iterasyonunun V1, V2, … gibi bir değer fonksiyonları dizisi üretirken, politika iterasyonunun ϕ1, ϕ2, … gibi bir politika dizisi üretmesidir. Ancak, her iki yöntemin amacı aynıdır. V1, V2, … dizisinin optimal değer fonksiyonu V*’ye yakınsadığını, ϕ1, ϕ2, … dizisinin ise Vϕ1, Vϕ2, … dizisinin Vϕ* = V*’ye yakınsaması anlamında bazı optimal politikalara (ϕ*) yakınsadığını bekleriz. Teknik sorun, optimal değer fonksiyonu V* her zaman benzersiz olsa da, Vϕ* = V*’yi sağlayan optimal politika ϕ*’nın benzersiz olmayabileceğidir. Bu nedenle, bir politika iterasyonu algoritması tasarlanırken bu olasılık göz önünde bulundurulmalıdır.

Politika iterasyonu algoritmasının adımları, yukarıdaki çeşitli bölümlerde zaten açıklanmıştır, bu nedenle yalnızca bunları tutarlı bir algoritma halinde bir araya getirmemiz gerekir: Başlangıçta bir ϕ1 politikası ile başlanır. Bir politika dizisi ϕ1, ϕ2, … iteratif olarak üretilir. Tek bir iterasyon şu iki adımdan oluşur:

Mevcut politika ϕi verildiğinde:

• Adım 1. Politika Değerlendirmesi (Eleştirmen): Örneğin, algoritma kullanılarak V ϕi’yi değerlendirin.
• Adım 2. Politika İyileştirme (Aktör): Değerlendirme yaparak ϕi’yi iyileştirin.

O zaman V ϕi + 1 ≤ V ϕi’ye sahip olacağız.

• Vϕi + 1 = Vϕi olduğunda yinelemeleri sonlandırın.

O zaman ϕi = ϕ* optimal bir politikadır. Terminoloji, eleştirmenin bir politikayı değerlendirirken, aktörün bir politikayı iyileştirdiğini belirtir. Politika yinelemesinin ve değer yinelemesinin aynı amaca, yani dinamik bir programlama modeli için optimal politikanın belirlenmesine sahip olduğuna dikkat edilmelidir. Bu nedenle, genel olarak değiştirilebilirler. Politika yinelemesinin bir avantajı, eylem alanı A sonlu olduğu sürece, sonlu sayıda adımda kesin bir çözüme yakınsamasıdır. Ayrıca, (Sutton & Barto, 2018a) yazarlarına göre, “[p]olitika yinelemesi genellikle şaşırtıcı derecede az yinelemede yakınsar”. Öte yandan, değer yinelemesi sonlu ufuk, en kısa yol veya sonsuz ufuk sorunları için uygunken (Ek B’deki örneğe bakın), politika yinelemesinin sonlu ufuk SPD’leri için nispeten verimsiz olduğu bildirilmiştir (bkz. (Puterman, 1994) Bölüm 6.4). En iyi seçim genellikle belirli sorunun yapısına bağlı olacaktır.

MDP’lerin Optimum Kontrolü için Algoritmalar

Bölüm 2.2.4'te dinamik programlama modelinin özellikle önemli bir özel durumu olarak Markov karar süreçlerini (MDP) tanıttık. Bunlar, nispeten kompakt bir model tanımı (K, R, P, β) kullanarak oldukça geniş çeşitlilikte SDP’yi modelleyebilirler. Ayrıca, destekleyici matematiksel teori çok zengindir ve MDP’lerin istikrarlı ve öngörülebilir uzun vadeli davranışa sahip olduğu bilinmektedir. Ancak, popüler olarak boyutluluğun laneti olarak bilinen önemli bir dezavantajı temsil edebilen başka bir özelliğe sahiptirler. Bu terim, Richard Bellman tarafından 1950'lerde bir SDP modeli daha karmaşık hale getirildikçe durum-eylem alanı K’nin boyutunun hızla artabileceği biçimi tanımlamak için kullanılmıştır (Bellman, 1957). Elbette, posta arabası problemini ele aldığımızda dinamik programlamanın kaba kuvvet sayımına göre hesaplama avantajını gördük. Ancak, kalan problem, değer yineleme algoritmasının tek bir yinelemesinin hesaplama karmaşıklığını ele aldığımızda görülebilir. İlk olarak, deterministik geçişlere sahip bir modeli ele alalım:

Her durumda kabul edilebilir eylem sayısının Na ile sınırlandırıldığını varsayalım, böylece her x ∈ X için |Ax| ≤ Na olur. Modelin formüle edilme biçimine bağlı olarak, Na’nın |A|’dan çok daha küçük olması mümkündür, bu durumda Na önemli sayıdır. Örneğin, bir tavla oyununda eylem alanı Am bir oyuncunun yapabileceği tüm olası hamleleri temsil edebilir.
Ancak, her verilen durum x (tahta yapılandırması) için yalnızca küçük bir alt küme Ax ⊂ A kullanılabilir.

O zaman her x ∈ X için, R(x, a) + βV q x, a biçimindeki bir nicelik Na kez hesaplanmalıdır. Bu, her durum için yapılmalıdır, bu nedenle bu tür hesaplamaların toplam sayısı şudur: Yineleme karmaşıklığı (belirleyici model) = Nx × Na, burada Nx = X durum sayısıdır.

Karmaşıklık stokastik model için daha büyüktür. Değer yineleme algoritmasının tek bir yinelemesi şu biçimi alır:

Deterministik durumda olduğu gibi, bu denklem Nx × Na kadar hesaplanmalıdır. Ancak, Denklem (2.34)’ün aksine, hesaplama, bir beklenen değeri değerlendirmek için kullanılan X üzerinde bir toplamayı da içerir (Denklem (2.15)’i hatırlayın). Karmaşıklık artık şöyledir:
İterasyon karmaşıklığı (stokastik model) = Nx² × Na.

Ayrıca, depolama maliyetini de dikkate almamız gerekir. V(x), ϕ(x), V(x, a), R(x, a) ve P(y ∣ x, a) analitik formlara sahip değilse, bunlar bilgisayar belleğinde tablo şeklinde saklanmalıdır. Bu durumda, V x ve ϕ x Nx girdilerini saklamak zorundadır; V(x, a) ve R(x, a) NxNa girdilerini; ve P(y ∣ x, a) Nx²Na girdilerini saklamak zorundadır.

Belirli bir modelin özellikleri, hesaplama ve depolama karmaşıklığını azaltabilir. Örneğin, stokastik çekirdek P(y ∣ x, a) herhangi bir durum-eylem çifti (x, a) için yalnızca iki diğer duruma geçişe izin verirse, Denklem (2.36)’daki y ∈ X üzerindeki toplam yalnızca iki sıfırdan farklı terime sahip olur ve iterasyon karmaşıklığı Nx²Na yerine NxNa olarak değiştirilebilir. Seyrek matris yöntemleri, bu tür durumlarda önemli bir rol oynayabilir (Van Loan & Golub, 1983).

Karmaşıklık analizi oldukça zorlu sonuçlar sunmaktadır. Diyelim ki birden fazla kuyruklu bir sistemi (bir süpermarket, bir havaalanı güvenlik kontrol noktası gibi örnekler) modellemek istiyoruz. Amaç, örneğin, mevcut kuyruk uzunluklarına dayalı olarak kuyruk sayısını kontrol etmek için bir SDP geliştirmek olabilir. Maliyet fonksiyonu, bir kuyruğun açık tutulmasının maliyetini (daha fazla kuyruğun açılmasının daha fazla maliyete neden olacağı şekilde) içerebilir, ancak aynı zamanda daha uzun kuyrukları cezalandıran bir terim de içerebilir (çok uzun bir kuyrukla karşılaşan bir müşteri başka bir yerde alışveriş yapmayı tercih edebilir, bu da ölçülebilir bir maliyeti temsil eder).

Bir durumun tanımına hangi bilgiler dahil edilmelidir? Her kuyruğun sonlu bir kapasiteye (K) sahip olduğunu varsayabiliriz. Uygulamada, mevcut sistem maliyetinin veya gerekli dağılımsal özelliklerin değerlendirilmesi, her kuyruğun müşteri sayısının (kuyruk konfigürasyonu) bilinmesini gerektirir. Bunu, M kuyruklu bir sistem için (W1, W2, …, WM) olarak yazabiliriz. Her bir Wi, 0 ile K arasında bir tam sayı olduğu için, bu tür konfigürasyonların sayısı (K + 1)^M’dir. K = 20, M = 10 kapasitesine sahip büyük, ancak uygulanabilir bir kuyruk sistemi, (K + 1)^M ≈ 1.67 × 1⁰¹³ değerini verir. Bu sayı, iterasyon karmaşıklığı için bir alt sınırı temsil eder ve değer iterasyonunu, en azından tam formunda, hesaplama açısından uygulanamaz hale getirir. Ancak böyle sistemler vardır ve dolayısıyla optimal kontrol sistemlerine de ihtiyaç vardır. Geriye doğru türetme genellikle MDP’lere uygulanamaz, ancak hem değer iterasyonu hem de politika iterasyonu yaygın olarak kullanılır.

Genel Yardımcı Fonksiyonlar

Şimdiye kadar ele aldığımız karar problemlerinde, bir maliyeti veya ödülü, muhtemelen beklenen bir değer olarak, nesnel birimler (örneğin para birimi veya mesafe) olarak adlandırabileceğimiz şeylerle ifade edilebilecek şekilde optimize etmeye çalıştık. Bu tür bir modelin iki olası eksikliği vardır:

1. Bir maliyeti veya ödülü beklenen bir değer olarak optimize etmek riski hesaba katmaz. Örneğin, aşağıdaki ödeme tablosunu düşünün:

İki eylem mevcuttur ve alınan ödeme iki olaydan hangisinin gerçekleştiğine bağlıdır. Beklenen ödemeyi en üst düzeye çıkarmak için Eylem 2 seçilir. Ancak, 1.000$ kaybetme olasılığı kabul edilemez derecede yüksek olabilir ve karar verici her iki olaydan sonra 500$ ödeme almanın kesinliğini tercih edebilir.

2. Farklı karar vericiler, mevcut çeşitli ödeme seviyelerine karşı farklı tutumlara sahip olabilir ve stokastik varyasyon, göreceli tercihleri ​​bilgilendirebilir. Yukarıdaki tabloda gösterilen türden kararlar alan biri, uzun vadede rastgele varyasyondan kaynaklanan belirsizlik azalacağı için Eylem 2'yi tekrar tekrar seçebilir. Kararı yalnızca bir kez veren biri, Eylem 1'i tercih edebilir.

Fayda Fonksiyonları

Yukarıda tanıtılan sorun türleri, belirli bir karar vericinin maliyet, ödül ve riske karşı tutumunu niceliksel olarak belirleyen fayda teorisiyle çözülebilir. Bu, birden fazla karar vericinin aynı ekonomik koşullar kümesine farklı tepki vermesi durumunda önemlidir. Örnek olarak, bir karar vericinin x şişe meşrubat için ne kadar para ödemeye razı olacağı sorununu ele alalım. Sıcak bir günde susamış bir müşteri, ilk meşrubat için 1,00 dolar ödemeye razı olabilir (örneğin, meşrubatın müşteriye sunulacağı nominal fiyat). Ancak, müşteri ek içecekler için bu fiyatı ödemeye razı olmayabilir. Belki de kabul edilebilir maksimum fiyat, ikinci içecek için sadece 0,50 dolar, üçüncü içecek için 0,20 dolar vb. olabilir ve müşteri artık susamaz. Sonra, bir perakendeciyi ele alalım. Meşrubatların genellikle şişe başına 1,00 dolara satıldığını varsaydık. Bu nedenle, kar elde edilecekse, perakendecinin ödediği fiyat daha az, örneğin şişe başına 0,25 dolar olmalıdır. Ayrıca, ek bir şişe stoklamanın marjinal avantajı, stok miktarı x arttıkça sonunda azalacaktır. Müşteri ve perakendecinin her biri, bir karar verici için bir miktar malın x değerini temsil eden kendi fayda fonksiyonu u x’e sahiptir. Bu senaryoda, malın nominal bir fiyatı olabilir, ancak fayda bir karar vericinin ödemeye istekli olacağı fiyattır. Fayda nominal fiyatın altındaysa, müzakereler yapılmadığı sürece satın alma işlemi muhtemelen yapılmayacaktır. Aşağıdaki şekil, karar vericilerin tercihlerini yansıtabilecek iki olası fayda fonksiyonunu göstermektedir. Susamış müşteri bir içecek için 1,00 dolarlık nominal fiyatı ödemeye isteklidir. Müşterinin fayda fonksiyonu (aşağıdaki şekildeki kırmızı fonksiyon) bu nedenle x = 1'e ulaşana kadar birim başına sabit 1,00 dolarlık bir oranda artar (referans için gri çizgileri kullanın). Ancak, x = 1'in üzerinde fayda fonksiyonunun eğimi hızla azalır ve bu da müşterinin ikinci bir içecek için 1,00 dolarlık nominal fiyatı ödemeye istekli olmadığını (ve bu nedenle muhtemelen tek bir içecekle yetineceğini) gösterir. Elbette, herhangi bir sayıdaki x biriminin bir yükümlülükten ziyade bir varlık olarak kabul edileceğini varsayarsak, fayda fonksiyonu her zaman artmaktadır.

Bölüm 2.4.1'deki meşrubat örneği için susamış müşteri ve perakendeci için fayda fonksiyonları. Gri çizgiler şişe başına 1,00 ABD Doları ve 0,25 ABD Doları sabit marjinal faydayı temsil eder.

Perakendeci için fayda fonksiyonu da gösterilmiştir (yukarıdaki şekildeki mavi fonksiyon). Perakendeci kar elde etmekle ilgilenmektedir, bu nedenle nominal fiyattan emtia satın almanın bir anlamı olmayacaktır. Perakendeci, devam eden operasyonun %75'lik bir kar marjı gerektireceğini tahmin edebilir. Bu nedenle, mevcut nominal fiyatta perakendeci birim başına 0,25 dolardan fazla ödeme yapmak istemeyecektir, bu nedenle perakendecinin fayda fonksiyonunun eğimi x = 0'a yakındır (referans için gri çizgileri kullanın). Ancak, beklenen talebe bağlı olarak, ek bir yeni birim satın almanın marjinal avantajı x arttıkça muhtemelen azalacaktır. Buna karşılık, perakendecinin fayda fonksiyonunun eğimi x arttıkça azalır.

Fayda Fonksiyonunun Riske Göre Sınıflandırılması

Yukarıdaki şekildeki fayda fonksiyonlarına bakarsak, artarken, artış hızlarının düştüğünü görebiliriz. Bu bize, birim sayısı arttıkça her yeni edinilen birime daha az değer verildiğini söyler. Bu tür nitel özelliklerin fayda teorisinde önemli olduğu ortaya çıktı, bu yüzden aşağıdaki tanımlara ihtiyacımız olacak.

İçbükey ve Dışbükey Fonksiyonlar

Bir u(x) fonksiyonuna, eğri üzerindeki herhangi iki nokta için bu noktaları birleştiren doğru parçası eğrinin altında veya üzerinde yer alıyorsa içbükey denir. Eğer doğru parçası, uç noktalar hariç eğrinin altında yer alıyorsa, o zaman fonksiyonun kesinlikle içbükey olduğu söylenir. Benzer şekilde, bir u(x) fonksiyonuna, eğri üzerindeki herhangi iki nokta için bu noktaları birleştiren doğru parçası eğrinin üstünde veya üzerinde yer alıyorsa dışbükey denir. Eğer doğru parçası, uç noktalar hariç eğrinin üzerinde yer alıyorsa, o zaman fonksiyonun kesinlikle dışbükey olduğu söylenir. Aşağıdaki şekle bakın. u(x) doğrusal bir fonksiyonsa, hem içbükey hem de dışbükey olduğunu, ancak ne kesinlikle içbükey ne de kesinlikle dışbükey olmadığını unutmayın. Ayrıca, eğer u(x) iki kez türevlenebilirse, o zaman ux, ancak ve ancak ikinci türev u′′(x) tüm x için negatif (pozitif) ise kesinlikle içbükeydir (dışbükeydir). Ayrıca, bir fayda fonksiyonunun hemen hemen her zaman artan bir fonksiyon olduğunu da belirtelim. Bu, fayda fonksiyonları için önemli bir sınıflandırma sistemine yol açar.

Fayda Fonksiyonlarının Riske Göre Sınıfları

Bir karar vericinin riske karşı tutumunu, fayda fonksiyonunun dışbükey, içbükey veya doğrusal olup olmadığına bakarak karakterize edebiliriz:

• Bir fayda fonksiyonu kesinlikle içbükey ise riskten kaçınan bir fonksiyondur.
• Bir fayda fonksiyonu doğrusal ise riskten bağımsızdır.
• Bir fayda fonksiyonu kesinlikle dışbükey ise risk arayıcıdır.

Örnekler aşağıdaki şekilde gösterilmiştir:

Riskten kaçınan, riskten nötr ve risk arayan fayda fonksiyonlarına örnekler.

Risk ve dışbükeylik arasındaki ilişki, u(w) bir karar verici için o servetin faydasını ölçtüğünde servet w’deki değişiklikleri göz önünde bulundurarak analitik olarak ifade edilebilir. Servetin sabit bir miktar Δw kadar artırıldığını varsayalım. O zaman fayda şu miktarda artar:

Sonra servetin aynı miktarda Δw azaldığını varsayalım. O zaman fayda şu miktarda azalır:

Eğer Δu − > Δu + ise karar verici serveti artırmaktan çok kayıpları önlemekle ilgilenir. Bu davranış uygun bir şekilde riskten kaçınan olarak nitelendirilir. Dahası, Δu − > Δu + kısıtlaması basitçe içbükeyliğin alternatif bir tanımıdır. Benzer şekilde, eğer Δu + > Δu − ise karar verici serveti artırmakla daha çok ilgilenir ve bunu yapmak için bir miktar kayıp riskine katlanmaya isteklidir. Bu davranış uygun bir şekilde risk arayan olarak nitelendirilir. Bu durum basitçe dışbükeyliğin alternatif bir tanımıdır. Fayda teorisini kullanan dinamik programlama probleminin bir örneği Ek D’de verilmiştir.

Minimax Kriteri: Posta Arabası Problemi Yeniden Ele Alındı

Orijinal posta arabası probleminde olduğu gibi, A’dan K’ye kadar etiketlenmiş 11 kasaba vardır ve bir yolcu, “Posta arabası problem haritası” başlıklı şekilde gösterilen haritaya göre, A kasabasından başlayıp K kasabasında biten bir rota seçmelidir. Şimdiye kadar, uygulamalarımız ek maliyet tahakkuk yöntemlerini kullandı. Bu doğal görünüyor, çünkü örneklerimizde maliyet veya ödül, kendileri ek olan birimlerle (para, mesafe vb.) ifade edilebiliyordu. Ancak, özellikle ekonomi alanında, riskten kaçınan, riskten nötr veya risk arayan davranış için karar teorik tercihlerini yakalamak üzere en uygun politikaların kullanılmasına izin veren daha genel maliyet biçimleri tanımlanır. Faydanın bu amaç için nasıl kullanılabileceğini daha önce gördük. Bu daha yüksek düzeydeki genellik, maliyet tahakkuk yöntemine genişletilebilir. Aslında, maliyet tahakkuku eklenmediğinde, SDP’nin belleksiz yapısını koruması koşuluyla dinamik programlama uygulanabilir; bu, Denklem (2.6)’da tanıtılan minimax kriteri için geçerli olacaktır. Posta arabası probleminin hedeflerini değiştirdiğimizi varsayalım. Kasabalar arasındaki arazinin oldukça zorlu olabileceğini kabul ediyoruz (özellikle atlarımız için). Bu yüzden kasabalar arasında büyük mesafeler olan rotalardan kaçınmak istiyoruz. Rotamız üzerindeki bir kasabaya ulaştığımızda, yolculuğumuzun bir sonraki bölümüne kadar ihtiyacımız olduğu kadar dinlenebiliriz. Bu nedenle, hedef toplam seyahat mesafesini en aza indiren bir rota seçmek değil, kasabalar arasındaki maksimum mesafeyi en aza indiren bir rota seçmektir. Bu, minimax kriterinin bir örneğidir (bunun aksine, maximin kriteri minimum ödülü en üst düzeye çıkarmaya çalışır). Maliyete uygulanan minimax kriteri, riskten kaçınan tercihin bir örneğidir. Daha önce, deterministik K aşamalı sonlu ufuk SDP için minimum toplam mesafe ile ilişkili politika değer fonksiyonu şuydu:

Burada R(x, a) aşama mesafelerini temsil eden maliyet fonksiyonudur ve ϕ politikadır. Minimax kriter problemi için toplam maliyet şu şekilde olur:

Bu gösterimde, x1 durumunun mutlaka A durumu olmadığını unutmayın, çünkü tüm durumlar için V ϕ tanımlamamız gerekir. Ancak, her zaman aynı terminal durumu ϕ(xK) = K’ye sahip olacağız. Bu nedenle Vϕ(x), ϕ politikası altında x durumundan K durumuna en küçük mesafe maliyetini temsil eder. Daha sonra, Bellman denklemi (2.25) temelinde optimum değer fonksiyonu V*(x) için yinelemeli bir ifade oluşturabiliriz:

Bu noktada geriye doğru tümevarım algoritması kullanarak V ∗(x)’i belirleyebiliriz. Aşağıdaki şekil Aşama 4 ve 5 için hesaplamaları göstermektedir.

Minimaks maliyet kriterli posta arabası problemi. Şekil 2.1'deki haritanın 4. ve 5. aşamalar için hesaplamaları gösteren kesiti.

Aşama 5:

Basitçe, V*(I) = 3 ve V*(J) = 2 (her I ve J durumundan yalnızca bir eylem, ϕ*(I) = ϕ*(J) = K mevcuttur).

Aşama 4:

Denklem doğrudan uygulanabilir.

Bu nedenle, G’den ϕ*(G) = J noktasına gitmek en uygunudur; bu da G’den kalan en uygun minimaks uzaklığı olan V*(G) = 2'yi verir.

Aynısını H durumu için de yapıyoruz:

Bu nedenle, H’den ϕ*(H) = I noktasına gitmek en uygunudur; bu da H’den kalan en uygun minimaks uzaklığın V*(H) = 3 olmasını sağlar.

Okuyucu, A’dan K’ye giden benzersiz en uygun minimax rotasının A-C-F-H-I-K ve en uygun minimax mesafesinin V*(A) = 3 olduğunu doğrulayarak kalan aşamaları tamamlayabilir. Orijinal en uygun toplam mesafe probleminde (Bölüm 2.3.1) eşit en uygun toplam mesafe 15 olan üç yol olduğunu hatırlayın. Bunlar, Denklem (2.26)’dan alınmıştır:

Bunlardan ilki (ama sadece ilki) minimax kriterine göre de en iyisidir.

Özet

Bu bölümde, sıralı karar verme süreci (SDP) ile tanıştık, tarihçesini ve dinamik programlamanın oynadığı birleştirici rolü inceledik. Daha sonra dinamik programlama modelini resmi olarak tanımladık, avantajlarını ve dezavantajlarını tartıştık. Özellikle, “boyut laneti”nin, modeli daha hesaplama açısından verimli hale getirme yollarının araştırılmasını ve geliştirilmesini nasıl motive ettiğini açıkladık. Dinamik programlamanın üç temel algoritmasını, geriye doğru türetme (backward induction), değer yinelemesi (value iteration) ve politika yinelemesi (policy iteration) inceleyerek, SDP’ler için optimal kontrol politikalarını türetmek amacıyla nasıl kullanıldığını gözden geçirdik. Ayrıca, bu optimizasyon prensiplerinin bilgisayar programlarıyla nasıl uygulanabileceğini de anlattık. Bunun ardından, ekonomi alanından, maliyet ve ödül tanımlarında daha fazla esneklik sağlamak için fayda teorisini kullanan özel bir SDP problem sınıfı tanıtıldı. Dinamik programlama yöntemlerinin bu problemlere nasıl uyarlanabileceğini gördük.