Stokastik dinamik programlama - Stochastic dynamic programming

Başlangıçta tarafından tanıtıldı Richard E. Bellman içinde (Bellman 1957 ), stokastik dinamik programlama problemleri modellemek ve çözmek için bir tekniktir belirsizlik altında karar verme. Yakından ilişkili stokastik programlama ve dinamik program Stokastik dinamik programlama, incelenmekte olan sorunu bir Bellman denklemi. Amaç bir hesaplamaktır politika Belirsizlik karşısında nasıl en iyi şekilde hareket edileceğini belirtmek.

Motive edici bir örnek: Kumar oyunu

Bir kumarbazın 2 doları vardır, 4 kez şans oyunu oynamasına izin verilir ve hedefi, en az 6 $ ile bitme olasılığını en üst düzeye çıkarmaktır. Kumarbaz $ bahis yaparsa ${ displaystyle b}$ oyunun bir oyununda, 0.4 olasılıkla oyunu kazanır, ilk bahsi telafi eder ve sermaye pozisyonunu $ arttırır. ${ displaystyle b}$ ; 0.6 olasılıkla, bahis tutarı $ 'ı kaybeder ${ displaystyle b}$ ; tüm oyunlar ikili bağımsız. Oyunun herhangi bir oyununda kumarbaz, oyunun başında sahip olduğundan daha fazla parayla bahis oynayamaz.^[1]

Bu problemi modellemek ve kumarbazın bahis ufkunun sonunda en az 6 $ 'lık bir servet elde etme olasılığını en üst düzeye çıkaran bir bahis stratejisi belirlemek için stokastik dinamik programlama kullanılabilir.

Oynanabilecek oyunların sayısında bir sınır yoksa, sorunun iyi bilinen bir varyant haline geleceğini unutmayın. St.Petersburg paradoksu.

Oyuncunun bahis ufkunun sonuna kadar en az 6 $ 'lık bir servet elde etme olasılığını en üst düzeye çıkaran optimal bir bahis stratejisi;

{ displaystyle b_ {t} ( $ x)}

oyun için bahis miktarını temsil eder

{ displaystyle t}

kumarbazın $ 'ı olduğunda

{ displaystyle x}

o oyunun başında. Karar verici bu politikayı izlerse, 0.1984 olasılıkla en az 6 $ 'lık bir servet elde edecektir.

Resmi arka plan

Üzerinde tanımlanan ayrı bir sistemi düşünün ${ displaystyle n}$ her aşamada ${ displaystyle t = 1, ldots, n}$ ile karakterizedir

bir başlangıç hali ${ displaystyle s_ {t} S_ {t}}$ , nerede ${ displaystyle S_ {t}}$ aşamanın başlangıcındaki uygulanabilir durumlar kümesidir ${ displaystyle t}$ ;
a karar değişkeni ${ displaystyle x_ {t} X_ {t}}$ , nerede ${ displaystyle X_ {t}}$ aşamadaki uygulanabilir eylemler dizisidir ${ displaystyle t}$ - Bunu not et ${ displaystyle X_ {t}}$ başlangıç durumunun bir işlevi olabilir ${ displaystyle s_ {t}}$ ;
bir anında maliyet / ödül işlevi ${ displaystyle p_ {t} (s_ {t}, x_ {t})}$ , aşamadaki maliyeti / ödülü temsil eden ${ displaystyle t}$ Eğer ${ displaystyle s_ {t}}$ başlangıç durumu ve ${ displaystyle x_ {t}}$ seçilen eylem;
a durum geçiş işlevi ${ displaystyle g_ {t} (s_ {t}, x_ {t})}$ sistemi devlete götüren ${ displaystyle s_ {t + 1} = g_ {t} (s_ {t}, x_ {t})}$ .

İzin Vermek ${ displaystyle f_ {t} (s_ {t})}$ aşağıdakileri takip ederek elde edilen optimum maliyeti / ödülü temsil eder optimal politika aşama aşama ${ displaystyle t, t + 1, ldots, n}$ . Aşağıdakilerde genelliği kaybetmeden bir ödül maksimizasyonu ayarını değerlendireceğiz. Deterministik olarak dinamik program genellikle ilgilenir fonksiyonel denklemler aşağıdaki yapıyı almak

{ displaystyle f_ {t} (s_ {t}) = max _ {x_ {t} içinde X_ {t}} {p_ {t} (s_ {t}, x_ {t}) + f_ {t +1} (s_ {t + 1}) }}

nerede ${ displaystyle s_ {t + 1} = g_ {t} (s_ {t}, x_ {t})}$ ve sistemin sınır koşulu

{ displaystyle f_ {n} (s_ {n}) = max _ {x_ {n} X_ {n}} içinde {p_ {n} (s_ {n}, x_ {n}) }.}

Amaç, en üst düzeye çıkaran optimum eylemler kümesini belirlemektir. ${ displaystyle f_ {1} (s_ {1})}$ . Mevcut durum göz önüne alındığında ${ displaystyle s_ {t}}$ ve mevcut eylem ${ displaystyle x_ {t}}$ , Biz kesin olarak bil mevcut aşamada ve - durum geçiş işlevi sayesinde güvence altına alınan ödül ${ displaystyle g_ {t}}$ - sistemin geçiş yapacağı gelecekteki durum.

Ancak uygulamada, mevcut aşamanın başlangıcındaki sistemin durumunu ve alınan kararın ne olduğunu bilsek bile, sistemin sonraki aşama başlangıcındaki durumu ve cari dönem ödülü genellikle rastgele değişkenler bu sadece mevcut aşamanın sonunda gözlemlenebilir.

Stokastik dinamik programlama cari dönem ödülünün ve / veya sonraki dönem durumunun rastgele olduğu problemlerle, yani çok aşamalı stokastik sistemlerle ilgilenir. Karar vericinin amacı, belirli bir planlama ufku boyunca beklenen (indirimli) ödülü maksimize etmektir.

En genel haliyle, stokastik dinamik programlar, aşağıdaki yapıyı alan fonksiyonel denklemlerle ilgilenir.

{ displaystyle f_ {t} (s_ {t}) = max _ {x_ {t} X_ {t} (s_ {t})} sol {{{ text {aşamada beklenen ödül}} t mid s_ {t}, x_ {t}) + alpha sum _ {s_ {t + 1}} Pr (s_ {t + 1} mid s_ {t}, x_ {t}) f_ { t + 1} (s_ {t + 1}) sağ }}

nerede

${ displaystyle f_ {t} (s_ {t})}$ aşamalar sırasında elde edilebilecek maksimum beklenen ödül ${ displaystyle t, t + 1, ldots, n}$ , verilen durum ${ displaystyle s_ {t}}$ aşamanın başında ${ displaystyle t}$ ;
${ displaystyle x_ {t}}$ sete ait ${ displaystyle X_ {t} (s_ {t})}$ aşamada uygulanabilir eylemlerin ${ displaystyle t}$ verilen başlangıç durumu ${ displaystyle s_ {t}}$ ;
${ displaystyle alpha}$ ... indirim faktörü;
${ displaystyle Pr (s_ {t + 1} orta s_ {t}, x_ {t})}$ aşamanın başındaki durumun koşullu olasılığı ${ displaystyle t}$ dır-dir ${ displaystyle s_ {t + 1}}$ verilen mevcut durum ${ displaystyle s_ {t}}$ ve seçilen eylem ${ displaystyle x_ {t}}$ .

Markov karar süreci temelini oluşturan özel bir stokastik dinamik programlar sınıfını temsil eder. Stokastik süreç bir durağan süreç özellikleri Markov özelliği.

Stokastik dinamik bir program olarak kumar oyunu

Kumar oyunu Stokastik Dinamik Program olarak şu şekilde formüle edilebilir: ${ displaystyle n = 4}$ oyunlar (ör. aşamalar) planlama ufkunda

durum ${ displaystyle s}$ Dönem içinde ${ displaystyle t}$ dönemin başındaki ilk serveti temsil eder ${ displaystyle t}$ ;
aksiyon verilen durum ${ displaystyle s}$ Dönem içinde ${ displaystyle t}$ bahis miktarı ${ displaystyle b}$ ;
geçiş olasılığı ${ displaystyle p_ {i, j} ^ {a}}$ eyaletten ${ displaystyle i}$ belirtmek ${ displaystyle j}$ ne zaman eylem ${ displaystyle a}$ eyalette alındı ${ displaystyle i}$ bir oyunu kazanma (0.4) veya kaybetme (0.6) olasılığından kolayca türetilir.

İzin Vermek ${ displaystyle f_ {t} (s)}$ 4. oyunun sonunda oyuncunun $ 'a sahip olduğu göz önüne alındığında, en az 6 $' a sahip olma olasılığı ${ displaystyle s}$ oyunun başında ${ displaystyle t}$ .

anlık kar eğer eylem ${ displaystyle b}$ eyalette alındı ${ displaystyle s}$ beklenen değer tarafından verilir ${ displaystyle p_ {t} (s, b) = 0.4f_ {t + 1} (s + b) + 0.6f_ {t + 1} (s-b)}$ .

Türetmek için fonksiyonel denklem, tanımlamak ${ displaystyle b_ {t} (s)}$ elde eden bir bahis olarak ${ displaystyle f_ {t} (s)}$ , sonra oyunun başında ${ displaystyle t = 4}$

Eğer ${ displaystyle s <3}$ hedefe ulaşmak imkansızdır, yani ${ displaystyle f_ {4} (s) = 0}$ için ${ displaystyle s <3}$ ;
Eğer ${ displaystyle s geq 6}$ hedefe ulaşılır, yani ${ displaystyle f_ {4} (s) = 1}$ için ${ displaystyle s geq 6}$ ;
Eğer ${ displaystyle 3 leq s leq 5}$ kumarbaz, hedefe ulaşmak için yeterince bahis yapmalıdır, yani ${ displaystyle f_ {4} (s) = 0,4}$ için ${ displaystyle 3 leq s leq 5}$ .

İçin ${ displaystyle t <4}$ fonksiyonel denklem ${ displaystyle f_ {t} (s) = max _ {b_ {t} (s)} {0.4f_ {t + 1} (s + b) + 0.6f_ {t + 1} (sb) } }$ , nerede ${ displaystyle b_ {t} {s)}$ aralıklar ${ displaystyle 0, ..., s}$ ; amaç bulmak ${ displaystyle f_ {1} (2)}$ .

Fonksiyonel denklem göz önüne alındığında, optimal bir bahis politikası, aşağıda belirtildiği gibi ileri özyineleme veya geriye dönük özyineleme algoritmaları yoluyla elde edilebilir.

Çözüm yöntemleri

Stokastik dinamik programlar, aşağıdakiler kullanılarak optimum hale getirilebilir: geriye dönük özyineleme veya ileri özyineleme algoritmalar. Memoization tipik olarak performansı artırmak için kullanılır. Ancak, deterministik dinamik programlama gibi, stokastik varyantı da boyutluluk laneti. Bu yüzden yaklaşık çözüm yöntemleri tipik olarak pratik uygulamalarda kullanılır.

Geriye doğru özyineleme

Sınırlı bir durum uzayı verildiğinde, geriye dönük özyineleme (Bertsekas 2000 ) tablo oluşturarak başlar ${ displaystyle f_ {n} (k)}$ olası her durum için ${ displaystyle k}$ son aşamaya ait ${ displaystyle n}$ . Bu değerler, ilgili optimal duruma bağlı eylemlerle birlikte tablo haline getirildikten sonra ${ displaystyle x_ {n} (k)}$ sahneye geçmek mümkün ${ displaystyle n-1}$ ve tablo haline getirin ${ displaystyle f_ {n-1} (k)}$ sahneye ait tüm olası durumlar için ${ displaystyle n-1}$ . Süreç, bir geriye ilkine kadar kalan tüm aşamaları biçimlendirin. Bu çizelge süreci tamamlandığında, ${ displaystyle f_ {1} (s)}$ - başlangıç durumuna göre optimal bir politikanın değeri ${ displaystyle s}$ - ve ilgili optimal eylem ${ displaystyle x_ {1} (s)}$ tablodan kolaylıkla alınabilir. Hesaplama geriye doğru bir şekilde ilerlediğinden, geriye doğru özyinelemenin, hesaplanması için gerekli olmayan çok sayıda durumun hesaplanmasına yol açabileceği açıktır. ${ displaystyle f_ {1} (s)}$ .

Örnek: Kumar oyunu

İleri özyineleme

Başlangıç durumu göz önüne alındığında ${ displaystyle s}$ 1. periyodun başında sistemin, ileri özyineleme (Bertsekas 2000 ) hesaplar ${ displaystyle f_ {1} (s)}$ fonksiyonel denklemi aşamalı olarak genişleterek (doğrudan geçiş). Bu, herkes için özyinelemeli çağrıları içerir ${ displaystyle f_ {t + 1} ( cdot), f_ {t + 2} ( cdot), ldots}$ verilen bir hesaplamak için gerekli ${ displaystyle f_ {t} ( cdot)}$ . Optimal bir politikanın değeri ve yapısı daha sonra bir (geri geçiş) askıya alınan özyinelemeli çağrıların çözüldüğü. Geriye doğru özyinelemeden önemli bir fark, ${ displaystyle f_ {t}}$ yalnızca hesaplanmasıyla ilgili durumlar için hesaplanır ${ displaystyle f_ {1} (s)}$ . Memoization halihazırda dikkate alınmış durumların yeniden hesaplanmasını önlemek için kullanılır.

Örnek: Kumar oyunu

Önceden tartışılan Kumar oyunu örneği bağlamında ileri yinelemeyi göstereceğiz. Başlıyoruz doğrudan geçiş dikkate alarak ${ displaystyle f_ {1} (2) = min sol {{ başla {dizi} {rr} b & { text {1,2,3,4} dönemlerindeki başarı olasılığı} hline 0 ve 0. 4f_ {2} (2 + 0) + 0.6f_ {2} (2-0) 1 ve 0.4f_ {2} (2 + 1) + 0.6f_ {2} (2-1) 2 ve 0.4f_ { 2} (2 + 2) + 0.6f_ {2} (2-2) son {dizi}} sağ.}$

Bu noktada henüz hesaplamadık ${ displaystyle f_ {2} (4), f_ {2} (3), f_ {2} (2), f_ {2} (1), f_ {2} (0)}$ hesaplamak için gerekli olan ${ displaystyle f_ {1} (2)}$ ; devam ediyor ve bu öğeleri hesaplıyoruz. Bunu not et ${ displaystyle f_ {2} (2 + 0) = f_ {2} (2-0) = f_ {2} (2)}$ bu nedenle kaldıraç kullanılabilir hafızaya alma ve gerekli hesaplamaları yalnızca bir kez yapın.

Hesaplama ${ displaystyle f_ {2} (4), f_ {2} (3), f_ {2} (2), f_ {2} (1), f_ {2} (0)}$

${ displaystyle f_ {2} (0) = min sol {{ başla {dizi} {rr} b & { text {2,3,4 dönemlerinde başarı olasılığı}} hline 0 ve 0.4f_ { 3} (0 + 0) + 0.6f_ {3} (0-0) son {dizi}} sağ.}$

${ displaystyle f_ {2} (1) = min sol {{ başla {dizi} {rr} b & { text {2,3,4 dönemlerinde başarı olasılığı}} hline 0 ve 0.4f_ { 3} (1 + 0) + 0.6f_ {3} (1-0) 1 & 0.4f_ {3} (1 + 1) + 0.6f_ {3} (1-1) end {dizi}} sağ.}$

${ displaystyle f_ {2} (2) = min sol {{ başla {dizi} {rr} b & { text {2,3,4 dönemlerinde başarı olasılığı}} hline 0 ve 0.4f_ { 3} (2 + 0) + 0.6f_ {3} (2-0) 1 ve 0.4f_ {3} (2 + 1) + 0.6f_ {3} (2-1) 2 ve 0.4f_ {3} (2 + 2) + 0.6f_ {3} (2-2) end {dizi}} sağ.}$

${ displaystyle f_ {2} (3) = min sol {{ başla {dizi} {rr} b & { text {2,3,4 dönemlerinde başarı olasılığı}} hline 0 ve 0.4f_ { 3} (3 + 0) + 0.6f_ {3} (3-0) 1 ve 0.4f_ {3} (3 + 1) + 0.6f_ {3} (3-1) 2 ve 0.4f_ {3} (3 + 2) + 0.6f_ {3} (3-2) 3 & 0.4f_ {3} (3 + 3) + 0.6f_ {3} (3-3) end {dizi}} sağ .}$

${ displaystyle f_ {2} (4) = min sol {{ başla {dizi} {rr} b & { text {2,3,4 dönemlerinde başarı olasılığı}} hline 0 ve 0.4f_ { 3} (4 + 0) + 0.6f_ {3} (4-0) 1 ve 0.4f_ {3} (4 + 1) + 0.6f_ {3} (4-1) 2 ve 0.4f_ {3} (4 + 2) + 0.6f_ {3} (4-2) end {dizi}} sağ.}$

Şimdi hesapladık ${ displaystyle f_ {2} (k)}$ hepsi için ${ displaystyle k}$ hesaplamak için gerekli ${ displaystyle f_ {1} (2)}$ . Ancak bu, aşağıdakileri içeren ek askıya alınmış yinelemelere yol açmıştır: ${ displaystyle f_ {3} (4), f_ {3} (3), f_ {3} (2), f_ {3} (1), f_ {3} (0)}$ . Devam ediyor ve bu değerleri hesaplıyoruz.

Hesaplama ${ displaystyle f_ {3} (4), f_ {3} (3), f_ {3} (2), f_ {3} (1), f_ {3} (0)}$

${ displaystyle f_ {3} (0) = min sol {{ başla {dizi} {rr} b & { text {dönemlerde başarı olasılığı 3,4}} hline 0 ve 0.4f_ {4} (0 + 0) + 0.6f_ {4} (0-0) son {dizi}} sağ.}$

${ displaystyle f_ {3} (1) = min sol {{ başla {dizi} {rr} b & { text {dönemlerde başarı olasılığı 3,4}} hline 0 ve 0.4f_ {4} (1 + 0) + 0.6f_ {4} (1-0) 1 & 0.4f_ {4} (1 + 1) + 0.6f_ {4} (1-1) end {dizi}} sağ .}$

${ displaystyle f_ {3} (2) = min sol {{ başla {dizi} {rr} b & { text {dönemlerde başarı olasılığı 3,4}} hline 0 ve 0.4f_ {4} (2 + 0) + 0.6f_ {4} (2-0) 1 ve 0.4f_ {4} (2 + 1) + 0.6f_ {4} (2-1) 2 ve 0.4f_ {4} (2 +2) + 0.6f_ {4} (2-2) end {dizi}} sağ.}$

${ displaystyle f_ {3} (3) = min sol {{ başla {dizi} {rr} b & { text {dönemlerde başarı olasılığı 3,4}} hline 0 ve 0.4f_ {4} (3 + 0) + 0.6f_ {4} (3-0) 1 ve 0.4f_ {4} (3 + 1) + 0.6f_ {4} (3-1) 2 ve 0.4f_ {4} (3 +2) + 0.6f_ {4} (3-2) 3 & 0.4f_ {4} (3 + 3) + 0.6f_ {4} (3-3) end {dizi}} sağ.}$

${ displaystyle f_ {3} (4) = min sol {{ başla {dizi} {rr} b & { text {dönemlerde başarı olasılığı 3,4}} hline 0 ve 0.4f_ {4} (4 + 0) + 0.6f_ {4} (4-0) 1 ve 0.4f_ {4} (4 + 1) + 0.6f_ {4} (4-1) 2 ve 0.4f_ {4} (4 +2) + 0.6f_ {4} (4-2) end {dizi}} sağ.}$

${ displaystyle f_ {3} (5) = min sol {{ başla {dizi} {rr} b & { text {dönemlerde başarı olasılığı 3,4}} hline 0 ve 0.4f_ {4} (5 + 0) + 0.6f_ {4} (5-0) 1 & 0.4f_ {4} (5 + 1) + 0.6f_ {4} (5-1) end {dizi}} sağ.}$

4. aşama sistemimizdeki son aşama olduğundan, ${ displaystyle f_ {4} ( cdot)}$ temsil etmek sınır şartları bunlar aşağıdaki gibi kolayca hesaplanır.

Sınır şartları

${ displaystyle { begin {dizi} {ll} f_ {4} (0) = 0 & b_ {4} (0) = 0 f_ {4} (1) = 0 & b_ {4} (1) = {0 , 1 } f_ {4} (2) = 0 & b_ {4} (2) = {0,1,2 } f_ {4} (3) = 0.4 & b_ {4} (3) = {3 } f_ {4} (4) = 0.4 & b_ {4} (4) = {2,3,4 } f_ {4} (5) = 0.4 & b_ {4} (5 ) = {1,2,3,4,5 } f_ {4} (d) = 1 & b_ {4} (d) = {0, ldots, d-6 } { text {için }} d geq 6 end {dizi}}}$

Bu noktada, optimal politikayı ve değerini bir geri geçiş dahil olmak üzere ilk aşamada 3

Geriye doğru geçiş ${ displaystyle f_ {3} ( cdot)}$

${ displaystyle f_ {3} (0) = min sol {{ başlar {dizi} {rr} b & { text {dönemlerde başarı olasılığı 3,4}} hline 0 ve 0,4 (0) +0,6 (0) = 0 son {dizi}} sağ.}$

${ displaystyle f_ {3} (1) = min sol {{ başla {dizi} {rrr} b & { text {3,4 dönemlerinde başarı olasılığı}} ve { mbox {maks}} hline 0 & 0.4 (0) +0.6 (0) = 0 & leftarrow b_ {3} (1) = 0 1 & 0.4 (0) +0.6 (0) = 0 & leftarrow b_ {3} (1) = 1 end {dizi}} sağ.}$

${ displaystyle f_ {3} (2) = min sol {{ başla {dizi} {rrr} b & { text {3,4 dönemlerinde başarı olasılığı}} ve { mbox {maks}} hline 0 & 0.4 (0) +0.6 (0) = 0 1 & 0.4 (0.4) +0.6 (0) = 0.16 & leftarrow b_ {3} (2) = 1 2 & 0.4 (0.4) +0,6 (0) = 0,16 & leftarrow b_ {3} (2) = 2 end {dizi}} sağ.}$

${ displaystyle f_ {3} (3) = min sol {{ başla {dizi} {rrr} b & { text {3,4 dönemlerinde başarı olasılığı}} ve { mbox {maks}} hline 0 & 0.4 (0.4) +0.6 (0.4) = 0.4 & leftarrow b_ {3} (3) = 0 1 & 0.4 (0.4) +0.6 (0) = 0.16 2 & 0.4 (0.4) +0.6 (0) = 0.16 3 & 0.4 (1) +0.6 (0) = 0.4 & leftarrow b_ {3} (3) = 3 end {dizi}} sağ.}$

${ displaystyle f_ {3} (4) = min sol {{ başla {dizi} {rrr} b & { text {3,4 dönemlerinde başarı olasılığı}} ve { mbox {maks}} hline 0 & 0.4 (0.4) +0.6 (0.4) = 0.4 & leftarrow b_ {3} (4) = 0 1 & 0.4 (0.4) +0.6 (0.4) = 0.4 & leftarrow b_ {3} ( 4) = 1 2 & 0.4 (1) +0.6 (0) = 0.4 & leftarrow b_ {3} (4) = 2 end {dizi}} sağ.}$

${ displaystyle f_ {3} (5) = min sol {{ başlar {dizi} {rrr} b & { text {3,4 dönemlerinde başarı olasılığı}} ve { mbox {maks}} hline 0 & 0.4 (0.4) +0.6 (0.4) = 0.4 1 & 0.4 (1) +0.6 (0.4) = 0.64 & leftarrow b_ {3} (5) = 1 end {dizi}} sağ.}$

ve sonra 2. aşama.

Geriye doğru geçiş ${ displaystyle f_ {2} ( cdot)}$

${ displaystyle f_ {2} (0) = min left {{ begin {array} {rrr} b & { text {2,3,4 dönemlerinde başarı olasılığı}} ve { mbox {max}} hline 0 & 0.4 (0) +0.6 (0) = 0 & leftarrow b_ {2} (0) = 0 end {dizi}} sağ.}$

${ displaystyle f_ {2} (1) = min sol {{ başla {dizi} {rrr} b & { text {2,3,4 dönemlerinde başarı olasılığı}} ve { mbox {maks}} hline 0 & 0.4 (0) +0.6 (0) = 0 1 & 0.4 (0.16) +0.6 (0) = 0.064 & leftarrow b_ {2} (1) = 1 end {dizi }}sağ.}$

${ displaystyle f_ {2} (2) = min left {{ begin {array} {rrr} b & { text {2,3,4 dönemlerinde başarı olasılığı}} ve { mbox {max}} hline 0 & 0.4 (0.16) +0.6 (0.16) = 0.16 & leftarrow b_ {2} (2) = 0 1 & 0.4 (0.4) +0.6 (0) = 0.16 & leftarrow b_ {2 } (2) = 1 2 & 0.4 (0.4) +0.6 (0) = 0.16 & leftarrow b_ {2} (2) = 2 end {dizi}} sağ.}$

${ displaystyle f_ {2} (3) = min sol {{ başla {dizi} {rrr} b & { text {2,3,4 dönemlerinde başarı olasılığı}} ve { mbox {maks}} hline 0 & 0.4 (0.4) +0.6 (0.4) = 0.4 & leftarrow b_ {2} (3) = 0 1 & 0.4 (0.4) +0.6 (0.16) = 0.256 2 & 0.4 ( 0.64) +0.6 (0) = 0.256 3 & 0.4 (1) +0.6 (0) = 0.4 & leftarrow b_ {2} (3) = 3 end {dizi}} right.}$

${ displaystyle f_ {2} (4) = min left {{ begin {array} {rrr} b & { text {2,3,4 dönemlerinde başarı olasılığı}} ve { mbox {max}} hline 0 & 0.4 (0.4) +0.6 (0.4) = 0.4 1 & 0.4 (0.64) +0.6 (0.4) = 0.496 & leftarrow b_ {2} (4) = 1 2 & 0.4 ( 1) +0.6 (0.16) = 0.496 & leftarrow b_ {2} (4) = 2 end {dizi}} sağ.}$

Sonunda değeri geri kazandık ${ displaystyle f_ {1} (2)}$ optimal bir politikanın

${ displaystyle f_ {1} (2) = min left {{ begin {array} {rrr} b & { text {1,2,3,4} dönemlerinde başarı olasılığı} ve { mbox {max }} hline 0 & 0.4 (0.16) +0.6 (0.16) = 0.16 1 & 0.4 (0.4) +0.6 (0.064) = 0.1984 & leftarrow b_ {1} (2) = 1 2 & 0. 4 (0,496) +0,6 (0) = 0,1984 & leftarrow b_ {1} (2) = 2 end {dizi}} sağ.}$

Bu, daha önce gösterilen optimal politikadır. Aynı optimum değere götüren birden çok optimum politika olduğunu unutmayın ${ displaystyle f_ {1} (2) = 0,1984}$ ; örneğin, ilk oyunda 1 $ veya 2 $ bahis yapılabilir.

Python uygulaması. Takip eden tam bir Python bu örneğin uygulanması.

itibaren yazıyor ithalat Liste, Tupleithalat hatırlamak gibi memithalat functools sınıf hatırlamak:         def __içinde__(kendini, işlev):         kendini.işlev = işlev         kendini.ezberlenmiş = {}         kendini.method_cache = {}     def __telefon etmek__(kendini, *argümanlar):         dönüş kendini.cache_get(kendini.ezberlenmiş, argümanlar,             lambda: kendini.işlev(*argümanlar))     def __almak__(kendini, obj, objtype):         dönüş kendini.cache_get(kendini.method_cache, obj,             lambda: kendini.__sınıf__(functools.kısmi(kendini.işlev, obj)))     def cache_get(kendini, önbellek, anahtar, işlev):         Deneyin:             dönüş önbellek[anahtar]         dışında KeyError:             önbellek[anahtar] = işlev()             dönüş önbellek[anahtar]         def Sıfırla(kendini):        kendini.ezberlenmiş = {}         kendini.method_cache = {} sınıf Durum:    kumarbazın yıkım sorununun durumu    '''    def __içinde__(kendini, t: int, servet: yüzen):        '' 'durum kurucusu        Argümanlar:            t {int} - dönem            servet {float} - ilk servet        '''        kendini.t, kendini.servet = t, servet    def __eq__(kendini, diğer):         dönüş kendini.__dict__ == diğer.__dict__    def __str__(kendini):        dönüş str(kendini.t) + " " + str(kendini.servet)    def __hash__(kendini):        dönüş karma(str(kendini))sınıf Kumarbazlar:    def __içinde__(kendini, bahis:int, targetWealth: yüzen, pmf: Liste[Liste[Tuple[int, yüzen]]]):        kumarbazın mahvetme sorunu        Argümanlar:            betHorizon {int} - bahis ufku            targetWealth {float} - hedef servet            pmf {List [List [Tuple [int, float]]]} - olasılık kütle fonksiyonu        '''        # örnek değişkenlerini başlat        kendini.bahis, kendini.targetWealth, kendini.pmf = bahis, targetWealth, pmf        # lambdas        kendini.ag = lambda s: [ben için ben içinde Aralık(0, min(kendini.targetWealth//2, s.servet) + 1)] # eylem oluşturucu        kendini.st = lambda s, a, r: Durum(s.t + 1, s.servet - a + a*r)                       # Devlet geçişi        kendini.iv = lambda s, a, r: 1 Eğer s.servet - a + a*r >= kendini.targetWealth Başka 0      # anında değer işlevi        kendini.cache_actions = {}  Optimum durum / işlem çiftlerine sahip # önbellek    def f(kendini, servet: yüzen) -> yüzen:        s = Durum(0, servet)        dönüş kendini._f(s)    def q(kendini, t: int, servet: yüzen) -> yüzen:        s = Durum(t, servet)        dönüş kendini.cache_actions[str(s)]    @memoize    def _f(kendini, s: Durum) -> yüzen:        #Forward recursion        v = max(            [toplam([p[1]*(kendini._f(kendini.st(s, a, p[0]))                   Eğer s.t < kendini.bahis - 1 Başka kendini.iv(s, a, p[0]))   # gelecekteki değer                  için p içinde kendini.pmf[s.t]])                                     # rastgele değişken gerçekleştirme             için a içinde kendini.ag(s)])                                             # hareketler        opt_a = lambda a: toplam([p[1]*(kendini._f(kendini.st(s, a, p[0]))                                Eğer s.t < kendini.bahis - 1 Başka kendini.iv(s, a, p[0]))                                için p içinde kendini.pmf[s.t]]) == v                  q = [k için k içinde filtre(opt_a, kendini.ag(s))]                              # en iyi eylem listesini al        kendini.cache_actions[str(s)]=q[0] Eğer bool(q) Başka Yok                    # sözlüğe bir eylem kaydedin                dönüş v                                                                # geri dönüş değeriörnek = {"bahisHorizon": 4, "targetWealth": 6, "pmf": [[(0, 0.6),(2, 0.4)] için ben içinde Aralık(0,4)]}gr, initial_wealth = Kumarbazlar(**örnek), 2# f_1 (x), kumarbazın bahisin sonunda $ targetWealth elde etme olasılığıdırYazdır("f_1 ("+str(initial_wealth)+"): " + str(gr.f(initial_wealth))) # 2. periyodun başlangıcındaki ilk servet 1 dolar olduğunda 2. periyot için en uygun eylemi kurtarın.t, initial_wealth = 1, 1Yazdır("b_"+str(t+1)+"("+str(initial_wealth)+"): " + str(gr.q(t, initial_wealth)))

Java uygulaması. KumarbazlarRuin.java bağımsızdır Java 8 yukarıdaki örneğin uygulanması.

Yaklaşık dinamik programlama

Giriş yaklaşık dinamik programlama Tarafından sağlanmaktadır (Powell 2009 ).

daha fazla okuma

Bellman, R. (1957), Dinamik program, Princeton University Press, ISBN 978-0-486-42809-3. Dover ciltsiz baskısı (2003).
Ross, S. M .; Bimbaum, Z. W .; Lukacs, E. (1983), Stokastik Dinamik Programlamaya Giriş, Elsevier, ISBN 978-0-12-598420-1.
Bertsekas, D.P. (2000), Dinamik Programlama ve Optimal Kontrol (2. baskı), Athena Scientific, ISBN 978-1-886529-09-0. İki cilt halinde.
Powell, W. B. (2009), "Yaklaşık dinamik programlama hakkında bilmeniz gerekenler", Deniz Araştırma Lojistiği, 56 (1): 239–249, CiteSeerX 10.1.1.150.1854, doi:10.1002 / nav.20347

Ayrıca bakınız

Referanslar

^ Bu problem W. L. Winston, Operations Research: Applications and Algorithms (7. Baskı), Duxbury Press, 2003, böl. 19, örnek 3.

[1] Bu problem W. L. Winston, Operations Research: Applications and Algorithms (7. Baskı), Duxbury Press, 2003, böl. 19, örnek 3.

[1]