Stochastic Dynamic Programming with Range and Ratio Criteria

摘要

In this paper we consider a finite-stage stochastic dynamic programming with range and ratio criteria. The range criterion is the maximum reward over the total stage minus minimum reward. As a ratio criterion, we take the ratio of one additive reward to the other. Our optimization problem is to minimize the expected value of the range and the ratio over a large class of policies. For each criterion of range and ratio, we use an invariant imbedding method, which introduces a family of past-value sets for reward accumulation. The imbedding expands the original state space by two dimension. First, we derive a forward recursive equation for the sequence of past-value sets. Second, we derive a backward recursive formula for sequence of optimal value functions on augmented state spaces. Finally a numerical example is illustrated for a two-state, two-action and two-stage model.