Worst Case Design Strategies

摘要

For sequential decision processes, we consider the problem of obtaining the min-max strategy which minimizes the worst case performance. This is a game against nature, attempts to maximize it. It is apparently a folk theorem that such a min-max strategy can be obtained by means of a dynamic programming like recursion, even though we have not seen any general proof of this, applicable to stochastic systems, which does not rely on the existence of a saddle point. We prove this theorem and also examine the precise roles of the strategy sets allowed to the minimizer and the maximizer in determining the upper value of the game. Improvements in the results for the case of deterministic systems, and generalizations to continuous time systems, are indicated.