Sufficient Classes of Strategies in Discrete Dynamic Programming I: Decomposition of Randomized Strategies and Embedded Models

1. Introduction. One of the major questions that occurs in investigating problems of dynamic programming on an infinite time interval is" in which natural classes of strategies do there exist strategies that produce a pay-off uniformly close to the pure value? It is known that in the case of finite state and control sets, optimal stationary strategies exist 1] (this also follows from [2]). However, if the set of states or controls is infinite, then optimal (and even e-optimal) stationary strategies need not exist [3], [4, Chap. 6, 6, Example 2]. In the case of a countable state space X, a very general result was announced in [5, Theorem 2.1] that gives a description of such classes. Let F denote the set of all mappings F: X 2 x such that x F(x) for all x X. A nonrandomized strategy is called an F-strategy if in any current state x the control is chosen depending only on this state and the total time passed in F(x) prior to the current instant of time. Markovian and tracking [6] strategies are special cases of F-strategies. Let X* be a