Creator |
|
Language |
|
Publisher |
|
|
Date |
|
Source Title |
|
Vol |
|
Issue |
|
First Page |
|
Last Page |
|
Publication Type |
|
Access Rights |
|
Related DOI |
|
Related DOI |
|
|
|
Related URI |
|
|
|
Related URI |
|
Related HDL |
|
Relation |
|
|
|
Abstract |
This paper studies a class of finite-stage deterministic dynamic programmings (DP's) with general state and action spaces from an algebraic viewpoint. The author has introduced inverse, reversal, comp...osition, maximum and minimum operations on a class of DP's with one-dimensional state space [5]. For general state case we can introduce the reversal and composition operations, because of an automaton-like treatment for DP. Specifying finite-stage deterministic DP in terms of set-theoretical notation (§ 2), we state three versions of Bellman's Principle of Optimality (§ 3). Our main and new result is REVERSE THEOREM in dynamic programming (§ 4): A pair of optimal reward functions and an optimal policy for a given DP is characterized by the pair of those for its reversed DP in a reverse sense. The REVERSE THEOREM has been motivated by the author's INVERSE THEOREM [2], [3], [4]. The latter is valid for one-dimensional state space. But the former for general state space. Another result is DECOMPOSITION THEOREM in dynamic programming: An $ N $-stage DP is decomposed into $ N $ one-stage DP's. This theorem is a variant of the corresponding theorems in Mitten [6] and Nemhauser [7].show more
|