확률론적 동적 프로그래밍

원래 리차드 E에 의해 소개되었다. (Bellman 1957)의 벨만(Bellman 1957)은 확률론적 동적 프로그래밍은 불확실성 속에서 의사결정 문제를 모델링하고 해결하기 위한 기술이다.확률론적 프로그래밍과 동적 프로그래밍과 밀접한 관련이 있는 확률론적 동적 프로그래밍은 벨만 방정식의 형태로 정밀하게 검토 중인 문제를 나타낸다.그 목적은 불확실성 앞에서 어떻게 최적으로 행동할 것인가를 규정하는 정책을 계산하는 것이다.

동기부여 사례: 도박 게임

도박꾼은 2달러를 가지고 있고, 그녀는 4번의 기회 게임을 할 수 있으며, 그녀의 목표는 최소 6달러로 끝날 확률을 극대화하는 것이다.도박꾼이 게임 플레이에$$ $$[\displaystyle b}$을(를) 걸면, 0.4 확률로 게임에서 이기고, 초기 베팅을 회수하고, 자본 위치를 $$[\displaystyle b}$까지 늘리면$,$ 0.6 확률로, 그녀는 베팅 금액 $$[\displaystyle b}$를 잃는다$;$ 모든 플레이는 쌍으로 독립적이다.어떤 게임에서든 도박꾼은 그 게임을 시작할 때 그녀가 가진 돈보다 더 많은 돈을 걸지 않을 수도 있다.^[1]

확률론적 동적 프로그래밍을 사용하여 이 문제를 모델링하고 예를 들어, 도박자가 베팅 지평선이 끝날 때까지 최소 6달러의 부를 달성할 확률을 최대화하는 베팅 전략을 결정할 수 있다.

게임 횟수에 제한이 없다면 문제는 잘 알려진 세인트루이스의 변종이 된다는 점에 유의한다. 페테르부르크의 역설.

도박자가 베팅 지평선 끝까지 최소 6달러의 부를 획득할 확률을 극대화하는 최적의 베팅 전략; ${\displaystyle b_{}}$ t${\displaystyle \mathrm{}}$($${\displaystyle x}$ ) ${\displaystyle b_{t}(\$x)$는 도박자가 플레이 $$에 $ x ${\displaystyle x}$을(를) 보유할 때$$ 게임 $t{\displaystyle }$ ${\displaystystyt t}$에 대한 베팅 금액을 나타낸다$$.만약 의사 결정자가 이 정책을 따른다면, 확률 0.1984로 그녀는 적어도 6달러의 부를 얻게 될 것이다.

형식 배경

각 단계 $t{\displaystyle }$= ${\displaystyle 1}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle n}$ ${\displaystyle t=1,\ldots ,n}$이(가) 특징인$$ $n{\displaystyle }$ ${\displaystyle n}$ 단계에$$ 정의된 이산 시스템을 고려하십시오.

• 초기 상태 $s{\displaystyle {}_{}{t}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$ $여기$서 S ${\displaystyle t_{}}$ ${\$는 단계 $t{\displaystyle }$ ${\displaystyle$ t$}$의 시작 부분에서 실현 가능한 상태의 집합이다$.$
• 결정 변수 $x{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\displaystyle {}_{}}$ X ${\displaystyle t_{}}$ ${\$ $여기$서 ${\displaystyle X_{}}$ t ${\$는 단계 $t{\displaystyle }$ ${\displaystyle t}$에서 실현 가능한 동작의 집합이다$$ –$$ ${\displaystyle X_{}}$ t ${\$$t}$는 초기 상태 t의 ${\displaystyle {함수}_{}}$일 수$$ 있다.
• ${\displaystyle s_{}}$ t ${\$이(가) 초기 상태이고 $x{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$ s_${t$$}$이(가) 선택된$$ 경우$$ 단계$$ t ${\displaystyle t}$에서 비용/비용/비용 함수를 나타내는$$즉시 $비용$/비용 함수 $p$ $(s$ $x_{t$$}).$
• 시스템을$$ 상태 ${\displaystyle t_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle t_{}{s}_{}}$ t${\displaystyle {}_{}}$ x ${\displaystyle t_{}}$)로 이끄는 상태 전환 $함수$ $g{\displaystyle {}_{}}$ $($${\displaystyle {}_{}}$t$})(s_${t},${\displaystyle {x\_}_{}}$${t$${\displaystyle {}_{}}$ {\$displaysty s_{t+1}=g_{t}(s_{t},x_{t})$.

$f{\displaystyle {}_{}{t}_{}}$ ( ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$) ${\displaystyle f_{t}(s_{t})($으)는 ${\displaystyle \mathrm{단계}}$ t${\displaystyle }$, ${\displaystyle \mathrm{t}}$+ 1${\displaystyle }$, ${\displaystyle n,}$ ${\displaystyle t,t+1,\ldots ,n}$에 걸쳐 최적의 정책을 따름으로써 얻은 최적의 비용/보상을 나타냄$$$.$ 다음에 오는 것에 있어서 일반성의 손실 없이 우리는 보상 최대화 설정을 고려할 것이다.결정론적 동적 프로그래밍에서는 보통 다음과 같은 구조를 갖는 기능 방정식을 다룬다.

${\displaystyle f_{t}(s_{t})=\max_{x_{t}\in X_{t}\{p_{t}(s_{t},x_{t})+f_{t+1}(s_{t+1})\}}$

여기서 $s{\displaystyle {}_t}$ +${\displaystyle {}_{}{1}_{}}$ = ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$( ${\displaystyle s_{}}$ ${\displaystyle {}_{}}$, ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle s_{t+1}=g_{t}(s_{t},x_{t})$이며 시스템의 경계 조건은 다음과 같다.

${\displaystyle f_{n}(s_{n})=\max_{x_{n}\in X_{n}\{p_{n}(s_{n},x_{n})\}.}$

목적은 $f{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$( $){\displaystyle f_{1}(s_{1}})}$을(를) 최대화하는 최적의 작업 집합을 결정하는 ${\displaystyle {것}_{}}$이다$.$ 현재$상태$의 t {\$displaystyle$ s_{$t}$ 및$$ ${\displaystyle {현재}_{}}$ $작업{\displaystyle {}_{}}$ x {\$displaystyle$ x_${t}}}을($를)를 고려할 때$,$ 현재 단계에서 확보된 보상을 확실히 알 수 있다.${\displaystyle {함수}_{}}$ g ${\$ $$– 시스템이 전환되는 미래 상태.

그러나 실제로 우리가 현 단계 초기의 시스템 상태와 취해진 결정을 알고 있다고 하더라도, 다음 단계 초의 시스템 상태와 현 기간 보상은 현 단계 말기에만 관측할 수 있는 임의의 변수인 경우가 많다.

확률론적 동적 프로그래밍은 현재 기간의 보상 및/또는 다음 기간 상태가 무작위인 문제, 즉 다단계 확률론적 시스템을 다룬다.의사결정자의 목표는 주어진 계획 지평선 상에 기대(할인) 보상을 최대화하는 것이다.

가장 일반적인 형태에서 확률론적 동적 프로그램은 다음과 같은 구조를 갖는 기능 방정식을 다룬다.

${\displaystyle f_{t}(s_{t})=\max _{x_{t}\in X_{t}(s_{t})}\left\{({\text{expected reward during stage }}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})\right\}}$

어디에

• ${\displaystyle f_{}}$( ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$) ${\displaystyle f_{t}(s_{t})}$은(는) 단계 $t{\displaystyle }$, ${\displaystyle \mathrm{t}}$+ 1${\displaystyle }$, ${\displaystyle n}${\$displaystyle t, t+1,\ldots ,n}$ 중에 얻을 수 있는 최대 기대 보상이며$,$ $단계{\displaystyle }$ t 단계 t의 시작 부분에$$ 지정된 $상태{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\displaystystyle$ $s_{$$t$이다.
• ${\displaystyle x_{}}$ ${\displaystyle t_{}}$ ${\$은(는) $초기{\displaystyle }$ 상태 ${\displaystyle t_{}}$ ${\$에서 설정된 X t${\displaystyle {}_{}{s}_{}}$ ${\displaystyle t_{}}$ ) $displaystyle$ $t}$에 속함$$$;$
• ${\displaystyle \alpha }$ ${\displaystyle \alpha }$이(가) 할인 요인임.
• ${\displaystyle \Pr(s_{t+1}\mid s_{t},x_{t})}$ is the conditional probability that the state at the beginning of stage ${\displaystyle t}$ is ${\displaystyle s_{t+1}}$ given current state ${\displaystyle s_{t}}$ and selected action ${\displaystyle x_{t$$}}$.

마르코프 의사결정 과정은 기초적인 확률적 과정이 마르코프 특성을 특징으로 하는 정지 과정인 특별한 종류의 확률적 동적 프로그램을 나타낸다.

확률적 다이내믹 프로그램으로서의 도박 게임

도박 게임은 다음과 같이 스토크스틱 다이내믹 프로그램으로 공식화할 수 있다: 계획적 지평선에는 $n{\displaystyle }$= ${\displaystyle 4}$ ${\displaystyle n=4}$게임$$(단계)이 있다.

• 기간 $t{\displaystyle }$ ${\displaystyle t}$의 상태 $s{\displaystyle }$ ${\displaystyle s}$은 기간 $t{\displaystyle }$ ${\displaystyle t}$의 초기 부를 나타낸다$$$.$
• 기간 $t{\displaystyle }$ ${\displaystyle t}$에서 지정된 상태 $s{\displaystyle }$ ${\displaystyle s}$은(는) 베팅 $금액{\displaystyle }$ b ${\displaystyle b$
• $상태$ $i{\displaystyle }$ ${\displaystyle$ i$}$에서${\displaystyle$ a$}$을(를) 수행할 때 $상태$i {\$displaystyle{\displaystyle }$ i}에서 $상태$ j ${\$displaystyle $j}($으)로의 전환$$ 확률 $p{\displaystyle {}_{}^{}}$ ${\displaystyle {i,}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ j}은$$ 한 $게임당$ 승리(0.4$)$ 또는 패배(0.6) 확률에서 쉽게 도출된다$$.

f ${\displaystyle t_{}}$( ${\displaystyle s}$) ${\displaystyle f_{t}(s)}}$을(를) $게임{\displaystyle }$ t$${\$displaystyle t}$의 시작$$ 부분에 $${\displaystyle }${\$displaysty s}$이(가) 있다는 점을 고려할 때, 4 게임이 끝날 때 도박꾼에게 최소 $6가 주어질 확률은$$ 되도록 한다$.$

• 상태 $s$에서 조치 $b{\displaystyle }$ ${\displaystyle b}$을(를) 취할 경우 발생하는 즉각적인 이익은 기대값 $p{\displaystyle {}_{}}$ ${\displaystyle t_{}s}$, b${\displaystyle }$)${\displaystyle }$= ${\displaystyle 0.{4f}_{}}$ t${\displaystyle {}_{}}$+ 1${\displaystyle {}_{}s}$+ ${\displaystyle b}$)${\displaystyle }$+ ${\displaystyle 0.{6f}_{}}$ t${\displaystyle {}_{}}$+ ${\displaystyle 1_{}(}$ ${\displaystyle s}$) ${\displaystyle p_{t}=0.4f_{t+$1}(s+$b)+$$0으로 주어진다.$$6f_{t+1}(s-b)}$.

$기능{\displaystyle }$ 방정식을 도출하려면 b ${\displaystyle t_{}}$${\displaystyle {}_{}}$(${\displaystyle }$${\displaystyle s}$) ${\$$displaystyle b_{t}($$s)$를 ${\displaystyle \mathrm{게임}}$${\displaystyle t_{}}$${\displaystyle }$= ${\displaystyle 4}$ ${\displaystyle f_{t$$}}$에 도달하는 베팅으로$$ 정의하십시오$.$

• < $[\$$displaystyle s<3}$인 ${\displaystyle \mathrm{경우}}$, 목표를 달성하는 것은 불가능하다. 즉, < $>$에 대해 f ${\displaystyle {4\mathrm{}}_{}}$(${\displaystyle }$s )${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle f_{4}(s)=0}$이(가) 된다
• $s{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 6}$ ${\displaystyle s$$\geq$ 6$}$의 목표가 ${\displaystyle \mathrm{달성}}$되는 경우, $즉{\displaystyle {}_{},}$ $s{\displaystyle 6}$ 6$${\$displaystyle$ $f_{4}(s)=1}$의 ${\displaystyle \mathrm{경우}}$$;$
• $만약{\displaystyle \mathrm{}}$ 3${\displaystyle s}$ s${\displaystyle 5}$ 5 $(\displaystyle$ 3$\leq$s\$leq$ 5$}$이($가$) 목표를 달성할 수 있을 만큼 도박꾼은$$ 베팅해야 한다. $즉{\displaystyle \mathrm{}}$, ${\displaystyle {3\mathrm{}}_{}}$${\displaystyle }$≤ ${\displaystyle \mathrm{s}}$ ${\displaystyle \le }$ 5 ${\displaystyle 3\leq s\leq 5$에 ${\displaystyle \mathrm{대해}}$ $f{\displaystyle {}_{}}$ $4$= $0.4}.$

For ${\displaystyle t<4}$ the functional equation is ${\displaystyle f_{t}(s)=\max _{b_{t}(s)}\{0.4f_{t+1}(s+b)+0.$$6f_{t+1}(s-b$ 여기서 $b{\displaystyle {}_{}}$ ${\displaystyle t_{}s}$ ${\displaystyle )}$ ${\displaystyle b_{t}(s)$의 ${\displaystyle \mathrm{범위}}$는 0${\displaystyle ,}$ ${\displaystyle .}$ ,${\displaystyle }$s ${\displaystyle 0,...,$ ...,$s}$이며$,$ 목적은 ${\displaystyle {f\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$( ${\displaystyle 2}$) ${\displaystystyle f_{1}(2)$를 찾는 것이다$.$

기능 방정식을 고려할 때, 아래에서 설명한 바와 같이 전방 재귀 또는 후방 재귀 알고리즘을 통해 최적의 베팅 정책을 얻을 수 있다.

솔루션 방법

확률론적 동적 프로그램은 후진 재귀 알고리즘이나 전방 재귀 알고리즘을 사용하여 최적성으로 해결할 수 있다.메모화는 일반적으로 성능을 향상시키기 위해 사용된다.그러나 결정론적 동적 프로그래밍과 마찬가지로 그것의 확률적 변형은 차원성의 저주에 시달린다.이러한 이유로 대략적인 해결방법은 일반적으로 실무적 용도에 사용된다.

후진 재귀

경계된 상태 공간이 주어진 경우, 역방향 재귀(Bertsekas 2000)는 최종 $단계{\displaystyle }$ $n${\$displaystyle$$k$}에 속하는$$ 가능한 모든 $상태{\displaystyle }$ k$${\$displaystyle$ k}에$$ $대해{\displaystyle {}_{}}$ f${\displaystyle {}_{}}$($k$ ${\displaystyle$ k$}(k)$를 표로 작성함으로써 시작된다$.$ 일단 이러한 값이 표로 작성되면 관련 최적의 상태 의존적 작업 ${\displaystyle x_{}}$ n${\displaystyle (k}$) ${\displaystyle x_{n}(k$ stage $n{\displaystyle }$- 1 ${\displaystyle n-1},$ stage ${\displaystyle \mathrm{n}}$${\displaystyle {}_{}}$-$$ {\$displaystyle f_{n-1$}($k)$로 이동할 수 있으며$$$,$ stage $n{\displaystyle }$- 1 ${\displaystystyle n-1}$에 속하는 가능한 모든 상태를 tabulate로${\displaystyle {계산}_{}}$하여 ${\displaystyle {\mathrm{프로세스}}_{}}$를 계속한다.이 표 계산 프로세스가 완료되면 $f{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$( ${\displaystyle s}$) ${\displaystyle f_{1}(s)$ - 초기 $상태{\displaystyle }$ s ${\displaystyle$ s$}$에 주어진 최적 정책의 값 - $$그리고 관련 최적 작업 $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$( s )${\displaystyle x_{1$}($s)$을 표에서 쉽게 검색할 수 있다$$.$$연산이 후진적으로 진행되기 때문에, 후진 재귀가 ${\displaystyle {f\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$( $){\displaystyle f_{1}(s)}$의 연산에 필요하지 않은 다수의 상태의 연산으로 이어질 수 있다는 것은 분명하다$.$

예: 도박 게임

이 구간은 확장이 필요하다.덧셈으로 도와줘도 된다.(2017년 1월)

전진 재귀

1주기 초에 시스템의$$ 초기 $상태{\displaystyle }$ s ${\displaystyle s}$을(를) ${\displaystyle \mathrm{감안}}$하여 기능 방정식$($전방 패스)을 점진적으로 확장하여 $f$${\displaystyle {}_{}{1\mathrm{}}_{}}$ ( s $displaystyle f_{1}(s)$을 계산한다.여기에는 주어진 $f{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ (${\displaystyle }$${\displaystyle \cdot }$ )를 계산하는 데 필요한$$ 모든 f ${\displaystyle t_{}{}_{}}$+ ${\displaystyle 1_{}}$ (${\displaystyle {}_{}}$⋅ )${\displaystyle }$, f ${\displaystyle {}_{}}$+ 2 (${\displaystyle }$⋅${\displaystyle }$)${\displaystyle }$,${\displaystyle }$… ${\displaystyle$ $f_$${t+1}(\cdot$ ),$f_$${t$$+2}(\$$cdot$$}),\$$ldots$$$}에 대한 재귀 호출이 포함된다$.$최적 정책의 값과 그 구조는 이러한 보류된 재귀 호출이 해결되는 (후진 패스)를 통해 검색된다.후진 재귀와의 주요 차이점은 $f{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$${\displaystyle \mathrm{displaystyle}}$ $f_{t}}$이(${\displaystyle {가\mathrm{}}_{}}$) f 1${\displaystyle }$($$s ){\$displaystyle f_{1}}$의 계산에 관련된 상태에만 계산된다는$$ 점이다$.$ 메모화는 이미 검토된 상태의 재조정을 피하기 위해 채택된다.

예: 도박 게임

우리는 이전에 논의된 도박 게임 사례의 맥락에서 전방 재귀에 대해 설명할 것이다.우리는 f1(2))분{시기에 b성공 확률 1,2,3,4 00.4f2(2+0)+0.6f2(2− 0)10.4f2(2+1)+0.6f2(2− 1)20.4f2(2+2)+0.6f2(2− 2){\displaystyle f_{1}(2)=\min \left\{{\begin{배열}{rr}b&amp을 고려하여,{\t은 앞 패스 시작한다.내선${기간 1,2,3,4}\\hline 0&0.4f_{2}(2+0)+0에서 확률 {message probability in 1,2,3,4}\\$$hline 0&0.4f_{2}(2+0)+0.$$6f_{2}(2-0)\\1&0.4f_{2}(2+1)+0.$$6f_{2}(2-1)\\2&0.4f_{2}(2+2)+0.$$6f_{2}(2-2)\\end{array}\오른쪽.$$}$

At this point we have not computed yet ${\displaystyle f_{2}(4),f_{2}(3),f_{2}(2),f_{2}(1),f_{2}(0)}$, which are needed to compute ${\displaystyle f_{1}(2)}$; we proceed and compute these items.$f{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$( ${\displaystyle 2}$+ ${\displaystyle 0}$)${\displaystyle }$= ${\displaystyle {f\mathrm{}}_{}}$ ${\displaystyle {}_{}}$( ${\displaystyle 2}$- 0${\displaystyle }$)${\displaystyle }$= ${\displaystyle {f\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ (${\displaystyle {}_{}}$2${\displaystyle }$) ${\displaystyle f_{2}(2+0)=f_{2}=f_{2}($2$)\}$ $그러므로$ 메모화를 활용하고 필요한 계산을 한 번만 수행할 수 있다.

$f{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$( ${\displaystyle 4}$)${\displaystyle }$, ${\displaystyle {f\mathrm{}}_{}2}$ ( 3${\displaystyle }$)${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$( ${\displaystyle 2}$)${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ( 1${\displaystyle }$)${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$( ${\displaystyle 0}$ ) , f 2 ( $0$) ${\displaystyle f_{2$}(4$), f_{2}(3),f_{2}(2),f_{2}(1),f_{2}(0)$의 연산

${\displaystyle f_{2}(0)=\min \left\{\property{array}{rrr}b&{\wr}{\line 0&0.4f_{3}(0+0)+0의 기간.6f_{3}(0-0)\\end{array}\오른쪽.}$

${\displaystyle f_{2}(1+0)=\min \left\{\loss{array}{rrr}b&{\text{data.b&{\line 0&0.4f_{3}(1+0)+0의 기간.6f_{3}(1-0)\1&0.4f_{3}(1+1)+0.6f_{3}(1-1)\\end{array}\오른쪽.}$

${\displaystyle f_{2}(2)=\min \left\{\property{array}{rrr}b&{\wr}{\line 0&0.4f_{3}(2+0)+0의 기간.6f_{3}(2-0)\1&0.4f_{3}(2+1)+0.6f_{3}(2-1)\\2&0.4f_{3}(2+2)+0.6f_{3}(2-2)\\end{array}\오른쪽.}$

${\displaystyle f_{2}(3)=\min \left\{\property{array}{rrr}b&{\wr}{\wrine 0&0.4f_{3+0)+0 기간.6f_{3}(3-0)\1&0.4f_{3}(3+1)+0.6f_{3}(3-1)\\2&0.4f_{3}(3+2)+0.6f_{3}(3-2)\3&0.4f_{3}(3+3)+0.6f_{3}(3-3)\\end{array}\오른쪽.}$

${\displaystyle f_{2}(4)=\min \left\{\property{array}{rrr}b&{\wr}{\line 0&0.4f_{3}(4+0)+0의 기간.6f_{3}(4-0)\1&0.4f_{3}(4+1)+0.6f_{3}(4-1)\\2&0.4f_{3}(4+2)+0.6f_{3}(4-2)\end{array}\오른쪽.}$

We have now computed ${\displaystyle f_{2}(k)}$ for all ${\displaystyle k}$ that are needed to compute ${\displaystyle f_{1}(2)}$. However, this has led to additional suspended recursions involving ${\displaystyle f_{3}$$(4)f_{3}(3),f_{3}(2),f_{3$}(1$),f_${3}(1),$f_{3}($0$)\}.$ 이러한 값을 계속 계산한다.

$f{\displaystyle {}_{}}$ ${\displaystyle 3{}_{}}$( 4${\displaystyle }$)${\displaystyle }$, ${\displaystyle {}_{}3}$ ( ${\displaystyle 3}$)${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}{}_{}}$( 2${\displaystyle }$)${\displaystyle }$, f ${\displaystyle {}_{}}$( ${\displaystyle 1}$)${\displaystyle }$, f ${\displaystyle {3\mathrm{}}_{}}$ ( ${\displaystyle 0}$ ) , ${\displaystyle {}_{}}$ 3 ($0$) ${\displaystyle f_{3}(4),f_{3}(3),f_{3}(2),f_{3}(1),f_{3}(0)$의 연산

${\displaystyle f_{3}(0)=\min \left\{\president{array}{rrr}b&{\wr}{\line 0&0.4f_{4}(0+0)+0의 기간.6f_{4}(0-0)\\end{array}\오른쪽.}$

${\displaystyle f_{3}(1+0)=\min \left\{\loss{array}{rrr}b&{\line 0&0.4f_{4}(1+0)+0의 기간.6f_{4}(1-0)\1&0.4f_{4}(1+1)+0.6f_{4}(1-1)\\end{array}\오른쪽.}$

${\displaystyle f_{3}(2)=\min \left\{\loss{array}{rrr}b&{\text}{hline 0&0.4f_{4}(2+0)+0의 기간.6f_{4}(2-0)\1&0.4f_{4}(2+1)+0.6f_{4}(2-1)\\2&0.4f_{4}(2+2)+0.6f_{4}(2-2)\\end{array}\오른쪽.}$

${\displaystyle f_{3}(3)=\min \left\{\loss{array}{rrr}b&{\text}{hline 0&0.4f_{4}(3+0)+0의 기간.6f_{4}(3-0)\1&0.4f_{4}(3+1)+0.6f_{4}(3-1)\\2&0.4f_{4}(3+2)+0.6f_{4}(3-2)\3&0.4f_{4}(3+3)+0.6f_{4}(3-3)\\end{array}\오른쪽.}$

${\displaystyle f_{3}(4)=\min \left\{\loss{array}{rrr}b&{\text}{hline 0&0.4f_{4}(4+0)+0의 기간.6f_{4}(4-0)\1&0.4f_{4}(4+1)+0.6f_{4}(4-1)\\2&0.4f_{4}(4+2)+0.6f_{4}(4-2)\end{array}\오른쪽.}$

${\displaystyle f_{3}(5)=\min \left\{\loss{array}{rrr}b&{\text}{hline 0&0.4f_{4}(5+0)+0의 기간.6f_{4}(5-0)\1&0.4f_{4}(5+1)+0.6f_{4}(5-1)\end{array}\오른쪽.}$

4단계는 우리 시스템의 마지막 단계인 만큼 f ${\displaystyle {4\mathrm{}}_{}}$(${\displaystyle {}_{}\cdot }$) ${\displaystyle f_{4}(\cdot$)는 다음과 같이 쉽게 계산되는 경계 조건을 나타낸다$$.

경계 조건

${\displaystyle {\begin{array}{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{{{}{}}}{}d\gets}{d\geq 6\end{array}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

이 시점에서 3단계를 포함하는 역방향 패스를 통해 최적의 정책과 그 가치를 계속 회복할 수 있다.

$f{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$ ${\displaystyle \cdot }$) ${\displaystyle f_{3}(\cdot )}$을(를) 포함하는 후진 패스

${\displaystyle f_{3}(0)=\min \left\{\put{array}{rr}b&{\\text}{hline 0&0.4(0)+0.6(0)=0\\end{array}}\right.}$

${\displaystyle f_{3}(1)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 3,4}}&{\mbox{max}}\\\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{array}}\right.}$

${\displaystyle f_{3}(2)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 3,4}}&{\mbox{max}}\\\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{array}}\right.}$

${\displaystyle f_{3}(3)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 3,4}}&{\mbox{max}}\\\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&\왼쪽 화살표 b_{3}(3)=3\\\end{array}\오른쪽.}$

${\displaystyle f_{3}(4)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 3,4}}&{\mbox{max}}\\\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&\왼쪽 화살표 b_{3}(4)=2\\\end{array}\오른쪽}$

${\displaystyle f_{3}(5)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 3,4}}&{\mbox{max}}\\\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{array}}\right.}$

그리고 2단계.

$f{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ (${\displaystyle {}_{}\cdot }$) ${\displaystyle f_{2}(\cdot )}$을(를) 포함하는 후진 패스

${\displaystyle f_{2}(0)=\min \left\{\put{array}{rrr}b&{\cHBOX{max}}\\hline 0&0.4(0)=0&\{2}(0)=0\eftarrow b_\end{array\}}}}.}$

${\displaystyle f_{2}(1)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 2,3,4}}&{\mbox{max}}\\\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{array}}\right.}$

${\displaystyle f_{2}(2)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 2,3,4}}&{\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{array}}\right.}$

${\displaystyle f_{2}(3)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 2,3,4}}&{\mbox{max}}\\\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&\좌측화살표 b_{2}(3)=3\\\end{array}}}$

${\displaystyle f_{2}(4)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 2,3,4}}&{\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{array}}\right.}$

마침내 최적의 정책의$$ 값 $f{\displaystyle {}_{}}$ ${\displaystyle 1}$(${\displaystyle {}_{}}$2$$) {\$displaystyle f_{1$}(2$)$을 복구함

${\displaystyle f_{1}(2)=\min \left\{{\begin{array}{rrr}b&{\text{success probability in periods 1,2,3,4}}&{\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{array}}\right.}$

이것은 앞서 설명한 최적의 정책이다.예를 들어, 첫 번째 게임에서 1달러 또는 ${\displaystyle \mathrm{2달러}}$ 베팅이 있을 수 있는 동일한 최적값 $f{\displaystyle {}_{}{1\mathrm{}}_{}}$=${\displaystyle 0.1984}$ $[\displaystyle f_{1}(2)=0.1984$

Python 구현.다음은 이 예제의 완전한 파이썬 구현이다.

로부터 타자 치기 수입하다 리스트, 투플레 수입하다 메모하다 로서 밈 수입하다 펑토스   계급 메모하다:           반항하다 __init___(자아의, 펑크):          자아의.펑크 = 펑크          자아의.메모한 = {}          자아의.method_properties = {}       반항하다 __call__(자아의, *아그):          돌아오다 자아의.cache_get(자아의.메모한, 아그,              람다: 자아의.펑크(*아그))       반항하다 __get___(자아의, 오비지, 오비타이프):          돌아오다 자아의.cache_get(자아의.method_properties, 오비지,              람다: 자아의.__class___(펑토스.부분적(자아의.펑크, 오비지)))       반항하다 cache_get(자아의, 캐쉬, 핵심을, 펑크):          해보다:              돌아오다 캐쉬[핵심을]          빼고는 키에러:              캐쉬[핵심을] = 펑크()              돌아오다 캐쉬[핵심을]           반항하다 리셋하다(자아의):         자아의.메모한 = {}          자아의.method_properties = {}   계급 주:     '''노름꾼의 파멸 문제의 상태 '''      반항하다 __init___(자아의, t: 인트로, 재산: 둥둥 뜨다):         ''state constructor'          인수: t {int} -- 기간 재산 {filename} -- 초기 재산 '''         자아의.t, 자아의.재산 = t, 재산      반항하다 __eq___(자아의, 타사의):          돌아오다 자아의._____ == 타사의._____      반항하다 __str___(자아의):         돌아오다 발을 동동 구르다(자아의.t) + " " + 발을 동동 구르다(자아의.재산)      반항하다 _____(자아의):         돌아오다 해시하다(발을 동동 구르다(자아의))  계급 갬블러루인:      반항하다 __init___(자아의, 베팅호라이즌:인트로, 타겟뷰티: 둥둥 뜨다, pmf: 리스트[리스트[투플레[인트로, 둥둥 뜨다]]]):         '''노름꾼의 파멸 문제          인수: 베팅Horizon {int} -- 베팅 지평선 표적으로 삼다재산 {float} - 목표 재산 pmf {list[List[Tuple[int, float]]]} -- 확률 질량 함수 '''          # 인스턴스 변수 초기화         자아의.베팅호라이즌, 자아의.타겟뷰티, 자아의.pmf = 베팅호라이즌, 타겟뷰티, pmf          # 람다스         자아의.ag = 람다 s: [i 을 위해 i 에 범위(0, 분(자아의.타겟뷰티//2, s.재산) + 1)] #조치발생기         자아의.세인트 = 람다 s, a, r: 주(s.t + 1, s.재산 - a + a*r)                       # 국가전환         자아의.iv. = 람다 s, a, r: 1 , 만약 s.재산 - a + a*r >= 자아의.타겟뷰티 다른 0      # 즉각적인 가치 함수          자아의.cache_actions = {}  최적의 상태/수행 쌍을 갖춘 # 캐시      반항하다 f(자아의, 재산: 둥둥 뜨다) -> 둥둥 뜨다:         s = 주(0, 재산)         돌아오다 자아의._f(s)      반항하다 q(자아의, t: 인트로, 재산: 둥둥 뜨다) -> 둥둥 뜨다:         s = 주(t, 재산)         돌아오다 자아의.cache_actions[발을 동동 구르다(s)]      @piecize     반항하다 _f(자아의, s: 주) -> 둥둥 뜨다:         #앞으로 재귀         v = 맥스.(             [합계를 내다([p[1]*(자아의._f(자아의.세인트(s, a, p[0]))                    , 만약 s.t < 자아의.베팅호라이즌 - 1 다른 자아의.iv.(s, a, p[0]))   # 미래가치                   을 위해 p 에 자아의.pmf[s.t]])                                     # 임의변수실현              을 위해 a 에 자아의.ag(s)])                                             # 액션          opt_a = 람다 a: 합계를 내다([p[1]*(자아의._f(자아의.세인트(s, a, p[0]))                                 , 만약 s.t < 자아의.베팅호라이즌 - 1 다른 자아의.iv.(s, a, p[0]))                                 을 위해 p 에 자아의.pmf[s.t]]) == v                   q = [k 을 위해 k 에 여과하다(opt_a, 자아의.ag(s))]                              # 베스트 액션 목록 검색         자아의.cache_actions[발을 동동 구르다(s)]=q[0] , 만약 바가지 긁다(q) 다른 없음                    # 사전에 액션을 저장한다.                  돌아오다 v                                                                # 반환값  예시 = {"bettingHorizon": 4, "타겟뷰트": 6, "pmf": [[(0, 0.6),(2, 0.4)] 을 위해 i 에 범위(0,4)]} gr, initial_beature = 갬블러루인(**예시), 2  # f_1(x)은 도박사의 달러 목표 달성 확률베팅 호라이즌의 끝자락 인쇄하다("f_1("+발을 동동 구르다(initial_beature)+"): " + 발을 동동 구르다(gr.f(initial_beature)))   #2주기 초기의 재물이 1달러일 때 2기에 대한 최적의 작용을 회복한다. t, initial_beature = 1, 1 인쇄하다("b_"+발을 동동 구르다(t+1)+"("+발을 동동 구르다(initial_beature)+"): " + 발을 동동 구르다(gr.q(t, initial_beature)))