確率的動的計画法

先に説明したギャンブルゲームのインスタンスを例に、前方再帰を例示します。まず、前方パスを検討します。 ${\displaystyle f_{1}(2)=\min \left\{{\begin{array}{rr}b&{\text{success probability in periods 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}}\right.}$

現時点ではまだ計算していません${\displaystyle f_{2}(4),f_{2}(3),f_{2}(2),f_{2}(1),f_{2}(0)}$計算に必要な${\displaystyle f_{1}(2)}$;これらの項目を計算します。${\displaystyle f_{2}(2+0)=f_{2}(2-0)=f_{2}(2)}$したがって、メモ化を活用することで、必要な計算を一度だけ実行できる。

計算${\displaystyle f_{2}(4),f_{2}(3),f_{2}(2),f_{2}(1),f_{2}(0)}$

${\displaystyle f_{2}(0)=\min \left\{{\begin{array}{rr}b&{\text{success probability in periods 2,3,4}}\\\hline 0&0.4f_{3}(0+0)+0.6f_{3}(0-0)\\\end{array}}\right.}$

${\displaystyle f_{2}(1)=\min \left\{{\begin{array}{rr}b&{\text{success probability in periods 2,3,4}}\\\hline 0&0.4f_{3}(1+0)+0.6f_{3}(1-0)\\1&0.4f_{3}(1+1)+0.6f_{3}(1-1)\\\end{array}}\right.}$

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

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

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

計算しました${\displaystyle f_{2}(k)}$すべての人々のために${\displaystyle k}$計算に必要な${\displaystyle f_{1}(2)}$しかし、これにより、追加の中断された再帰が発生しました。${\displaystyle f_{3}(4),f_{3}(3),f_{3}(2),f_{3}(1),f_{3}(0)}$では、これらの値を計算します。

計算${\displaystyle f_{3}(4),f_{3}(3),f_{3}(2),f_{3}(1),f_{3}(0)}$

${\displaystyle f_{3}(0)=\min \left\{{\begin{array}{rr}b&{\text{success probability in periods 3,4}}\\\hline 0&0.4f_{4}(0+0)+0.6f_{4}(0-0)\\\end{array}}\right.}$

${\displaystyle f_{3}(1)=\min \left\{{\begin{array}{rr}b&{\text{success probability in periods 3,4}}\\\hline 0&0.4f_{4}(1+0)+0.6f_{4}(1-0)\\1&0.4f_{4}(1+1)+0.6f_{4}(1-1)\\\end{array}}\right.}$

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

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

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

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

ステージ4はシステムの最終ステージなので、${\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{ for }}d\geq 6\end{array}}}$

この時点で、まずステージ3を含むバックワードパスによって、最適なポリシーとその値を復元することが可能です。

バックパスを含む${\displaystyle f_{3}(\cdot )}$

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

${\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&\leftarrow b_{3}(4)=2\\\end{array}}\right.}$

${\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段階。

バックパスを含む${\displaystyle f_{2}(\cdot )}$

${\displaystyle f_{2}(0)=\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&\leftarrow b_{2}(0)=0\\\end{array}}\right.}$

${\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&\leftarrow b_{2}(3)=3\\\end{array}}\right.}$

${\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.}$

ついに価値を取り戻しました${\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.}$

これは、既に説明した最適な方策です。なお、同じ最適値をもたらす最適な方策は複数存在することに注意してください。${\displaystyle f_{1}(2)=0.1984}$例えば、最初のゲームでは1ドルか2ドルを賭けることができます。

Pythonによる実装。以下は、この例の完全なPython実装です。

import functoolsclass memoize : def __init __ ( self , func ) : self.func = func self.memoized = { } self.method_cache = { }​​def __call __ ( self , * args ) : return self.cache_get ( self.memoized , args , lambda : self.func ( * args ) )​​​def __get __ ( self , obj , objtype ) : return self.cache_get ( self.method_cache , obj , lambda : self .__ class __ ( functools.partial ( self.func , obj ) ) , )​​​def cache_get ( self , cache , key , func ): try : return cache [ key ] except KeyError : cache [ key ] = func () return cache [ key ]def reset ( self ) : self.memoized = { } self.method_cache = { }​クラスState : """ギャンブラーの破産問題の状態"""def __init__ ( self , t : int , wealth : float ): """状態コンストラクタ引数 : t {int} -- 期間 wealth {float} -- 初期資産" "  " self.t , self.wealth = t , wealthdef __eq__ ( self , other ): return self .__ dict__ == other .__ dict__def __str __ ( self ) : return str ( self.t ) + " " + str ( self.wealth )​def __hash__ ( self ): return hash ( str ( self ))class GamblersRuin : def __init__ ( self , bettingHorizo​​n : int , targetWealth : float , pmf : list [ list [ tuple [ int , float ]]], ): """ギャンブラーの破産問題。 引数:  bettingHorizo​​n {int} -- 賭けの期間 targetWealth {float} -- 目標資産 pmf {list[list[tuple[int, float]]]} -- 確率質量関数 """# インスタンス変数を初期化しますself.bettingHorizo ​​n 、self.targetWealth 、self.pmf = ( bettingHorizo ​​n 、targetWealth 、pmf 、)#ラムダ式self.ag = lambda s : [ i for i in range ( 0 , min ( self.targetWealth // 2 , s.wealth ) + 1 ) ] #アクションジェネレーターself.st = lambda s , a , r : State ( s.t + 1 , s.wealth - a + a * r ) #状態遷移self.iv = ( lambda s , a , r : 1 if s.wealth - a + a * r > = self.targetWealth else 0 ) #即時値関数​​​​​​​​self.cache_actions = {} # 最適な状態/アクションのペアでキャッシュするdef f ( self , wealth : float ) -> float : s = State ( 0 , wealth ) return self . _f ( s )def q ( self , t : int , wealth : float ) -> float : s = State ( t , wealth ) return self . cache_actions [ str ( s )]@memoize def _f ( self , s : State ) -> float : # 前方再帰values = [ sum ([ p [ 1 ] * ( self . _f ( self . st ( s , a , p [ 0 ])) if s . t < self . bettingHorizo​​n - 1 else self . iv ( s , a , p [ 0 ])) # 値関数for p in self . pmf [ s . t ]]) # 賭けの実現値for a in self . ag ( s )] # アクション v = max ( values ) try : self.cache_actions [ str ( s )] = self.ag ( s ) [ values.index ( v ) ] # 最適なアクションを保存except ValueError : self.cache_actions [ str ( s )] = None print ( "最適なアクションの取得中にエラーが発生しました" ) return v #期待される合計コストを返すinstance = { "bettingHorizo​​n" : 4 , "targetWealth" : 6 , "pmf" : [[( 0 , 0.6 ), ( 2 , 0.4 )] for i in range ( 0 , 4 )], } gr , initial_wealth = GamblersRuin ( ** instance ), 2# f_1(x) は、賭けの終了時に $targetWealth を達成するギャンブラーの確率です。print ( "f_1(" + str ( initial_wealth ) + "): " + str ( gr . f ( initial_wealth )))# 期間 2 の開始時の初期資産が $1 の場合の期間 2 の最適行動を復元します。t 、initial_wealth = 1 、1 print ( "b_" + str ( t + 1 ) + "(" + str ( initial_wealth ) + "): " + str ( gr . q ( t 、initial_wealth )) )

Javaによる実装。GamblersRuin.javaは、上記の例をJava 8で実装したスタンドアロンのコードです。