DISCRETE DYNAMIC PROGRAMMING WITH RECURSIVE ADDITIVE SYSTEM
Seiichi Iwamoto · Bulletin of Mathematical Statistics · 1974
s= 1, 2, ••• , N, that is, S= {1, 2, ••• , N}, A is a set of actions labeled by the integers a= 1, 2, ••• , K, that is, A= {1, 2, ••• , , p is a transition law 14, that is, A- E = 1 , p 0 for i, j E S, k E A , J=1 r = ; i, j E S, k E A) is a set of stage-wise rewards, i3= (gFi; i, j E S, k E A) is a generalized accumulator whose value 1.3; is a discount factor depending on transition (i, k, j), and t is a translator from R1 to R1.Throughout this paper we call the dynamic programming problem with recursive additive system "recursive additive dynamic programming " or simply " recursive additive DP ".We sometimes use the convenient notations j3(i, k, j), r(i, k, j) and p(i, k, j) in stead of A, r and 14 respectively.When the system starts from initial state s1 E S at 1-st stage and the decision maker takes an action a1 E A on this state si, the system moves to next state s, E S with probability P(sl, a1, s2) at 2-nd stage and the system yields a stage-wise reward r(s" a" s2) and a discount factor P(si, a1, s2).However, at the end of 1-st stage the decision maker indeed gets the translated reward t(r(s1, a1f s2)).The system is then repeated from the new state s2 E S at 2-nd stage.If he chooses an action a2 E A on state s2, it moves to state s3 with probability p(s2, a2, s3) at 3-rd stage.Then the system also yields a stage-wise reward r(s2, a2, s3) and a discount factor 13(s2i a2, s3) at the end of 2-nd stage, and he really receives the discounted reward I3(s1, a1, s2)t(r(s2, a2, s3)) of the translated one t(r(s2, a2, s3)) multiplied by a discount factor i3(s1, a1f s2) which was swept at the end of 1-st stage.Similarly at the end of 3-rd stage he gets a reward 13(s1i a1, s2)13(s2, a2, sg)t(r(s" a3, s4)) which is discounted one of t(r(s3, a" s4)) multiplied by 13(s1i a1, s2)p(s2, a2, s3).In general when he undergoes the history (s,, a1, s2, a2, ••• , sn, an, sn.,1) of the system up to n-th stage, he comes to receive a reward )3(s1i a" s2)13(s2, a" s3) ••• 48(sn_1, an_1, sn)t(r(sn, an, sn.")) at the end of n-th stage.Furthermore, the process goes on (n±1)-st stage, (n+2)-nd stage and so on.Since we consider a sequential nonterminating decision process, the decision maker continues to take actions infinitely.Consequently if he undergoes the history h = (s1, a1, s2, a2, •••), he comes to receive the total reward V(h) = t(r(s1, a1, 52))+J3(51, a1, s2)t(r(s2, a2, s3)) +13(si, a1, s2)/3(s2, a2, s3)t(r(s3, a3, s4)) •-• H8(si, a1, 53)43(52, a2, 53) ••• i3(s" ..1, an_" sn)t(r(sn, an, sn+i))+ -. • This reward system is illustrated as follows : Discrete Dynamic Programming with Recursive Additive System51 a, aza3---